Conference Proceeding

The Multi-Funnel Structure of TSP Fitness Landscapes: A Visual Exploration


Ochoa G, Veerapen N, Whitley D & Burke E (2016) The Multi-Funnel Structure of TSP Fitness Landscapes: A Visual Exploration. In: Bonnevay S, Legrand P, Monmarché N, Lutton E & Schoenauer M (eds.) Artificial Evolution: 12th International Conference, Evolution Artificielle, EA 2015, Lyon, France, October 26-28, 2015. Revised Selected Papers. Lecture Notes in Computer Science, 9554. International Conference on Artificial Evolution (EA-2015), Lyon, France, 26.10.2015-28.10.2015. Cham, Switzerland: Springer, pp. 1-13.

We use the Local Optima Network model to study the structure of symmetric TSP fitness landscapes. The `big-valley' hypothesis holds that for TSP and other combinatorial problems, local optima are not randomly distributed, instead they tend to be clustered around the global optimum. However, a recent study has observed that, for solutions close in evaluation to the global optimum, this structure breaks down into multiple valleys, forming what has been called `multiple funnels'. The multiple funnel concept implies that local optima are organised into clusters, so that a particular local optimum largely belongs to a particular funnel. Our study is the first to extract and visualise local optima networks for TSP and is based on a sampling methodology relying on the Chained Lin-Kernighan algorithm. We confirm the existence of multiple funnels on two selected TSP instances, finding additional funnels in a previously studied instance. Our results suggests that transitions among funnels are possible using operators such as `double-bridge'. However, for consistently escaping sub-optimal funnels, more robust escaping mechanisms are required.

FundersEngineering and Physical Sciences Research Council
Title of seriesLecture Notes in Computer Science
Number in series9554
Publication date31/12/2016
Publication date online31/10/2015
Place of publicationCham, Switzerland
ISSN of series0302-9743
ConferenceInternational Conference on Artificial Evolution (EA-2015)
Conference locationLyon, France

Research centres/groups