An Analysis of the Fitness Landscape of Travelling Salesman Problem

Mohammadhassan Tayaraninajaran, Adam Prugel-Bennett

Research output: Contribution to journalArticlepeer-review

12 Citations (Scopus)


The fitness landscape of the travelling salesman problem is investigated for 11 different types of the problem. The types differ in how the distances between cities are generated. Many different properties of the landscape are studied. The properties chosen are all potentially relevant to choosing an appropriate search algorithm. The analysis includes a scaling study of the time to reach a local optimum, the number of local optima, the expected probability of reaching a local optimum as a function of its fitness, the expected fitness found by local search and the best fitness, the probability of reaching a global optimum, the distance between the local optima and the global optimum, the expected fitness as a function of the distance from an optimum, their basins of attraction and a principal component analysis of the local optima. The principal component analysis shows the correlation of the local optima in the component space. We show how the properties of the principal components of the local optima change from one problem type to another.
Original languageEnglish
Pages (from-to)347-384
JournalEvolutionary Computation
Issue number2
Publication statusE-pub ahead of print - 13 Jun 2016


Dive into the research topics of 'An Analysis of the Fitness Landscape of Travelling Salesman Problem'. Together they form a unique fingerprint.

Cite this