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

Citation

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. https://doi.org/10.1007/978-3-319-31471-6_1

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

People

Professor Gabriela Ochoa

Professor, Computing Science