Additional Dimensions to the Study of Funnels in Combinatorial Landscapes

Citation

Ochoa G & Veerapen N (2016) Additional Dimensions to the Study of Funnels in Combinatorial Landscapes. In: GECCO '16 Proceedings of the 2016 Genetic and Evolutionary Computation Conference 2016. The 2016 Genetic and Evolutionary Computation Conference (GECCO 2016), Denver, Colorado, USA, 20.07.2016-24.07.2016. New York, NY, USA: ACM, pp. 373-380. http://dl.acm.org/citation.cfm?id=2908820&CFID=827599008&CFTOKEN=74602334; https://doi.org/10.1145/2908812.2908820

Abstract
The global structure of travelling salesman's fitness landscapes has recently revealed the presence of multiple `funnels'. This implies that local optima are organised into several clusters, so that a particular local optimum largely belongs to a particular funnel. Such a global structure can increase search difficulty, especially, when the global optimum is located in a deep, narrow funnel. Our study brings more precision (and dimensions) to the notion of funnels with a data-driven approach using Local Optima Networks and the Chained Lin-Kernighan heuristic. We start by exploring the funnel 'floors', characterising them using the notion of communities from complex networks. We then analyse the more complex funnel 'basins'. Since their depth is relevant to search, we visualise them in 3D. Our study, across a set of TSP instances, reveals a multi-funnel structure in most of them. However, the specific topology varies across instances and relates to search difficulty. Finally, including a stronger perturbation into Chained Lin-Kernighan proved to smooth the funnel structure, reducing the number of funnels and enlarging the valley leading to global optima.

Keywords
Local Optima Networks; Travelling Salesman Problem; Hill Climbing; Local Search; Fitness Landscapes

People

Professor Gabriela Ochoa

Professor, Computing Science