University of Hertfordshire

By the same authors

An Analysis of the Fitness Landscape of Travelling Salesman Problem

Research output: Contribution to journalArticle

View graph of relations
Original languageEnglish
Pages (from-to)347-384
JournalEvolutionary Computation
Journal publication date13 Jun 2016
Volume24
Issue2
DOIs
Publication statusE-pub ahead of print - 13 Jun 2016

Abstract

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.

Notes

© 2016 Massachusetts Institute of Technology

ID: 16383960