TY - JOUR

T1 - An Analysis of the Fitness Landscape of Travelling Salesman Problem

AU - Tayaraninajaran, Mohammadhassan

AU - Prugel-Bennett, Adam

N1 - © 2016 Massachusetts Institute of Technology

PY - 2016/6/13

Y1 - 2016/6/13

N2 - 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.

AB - 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.

U2 - 10.1162/EVCO_a_00154

DO - 10.1162/EVCO_a_00154

M3 - Article

SN - 1063-6560

VL - 24

SP - 347

EP - 384

JO - Evolutionary Computation

JF - Evolutionary Computation

IS - 2

ER -