Research output

Conference Paper (in Formal Publication) ()

Comparing Communities of Optima with Funnels in Combinatorial Fitness Landscapes

Citation
Thomson S, Daolio F & Ochoa G (2017) Comparing Communities of Optima with Funnels in Combinatorial Fitness Landscapes In: Proceedings of the Genetic and Evolutionary Computation Conference 2017, Berlin, Germany, July 15–19, 2017 (GECCO ’17), New York: ACM. GECCO ’17: The Genetic and Evolutionary Computation Conference, 15.7.2017 - 19.7.2017, Berlin, Germany, pp. 377-384.

Notes
Authors listed as ECOM Track

Abstract
The existence of sub-optimal funnels in combinatorial fitness landscapes has been linked to search difficulty. The exact nature of these structures — and how commonly they appear — is not yet fully understood. Improving our understanding of funnels could help with designing effective diversification mechanisms for a ‘smoothing’ effect, making optimisation easier. We model fitness landscapes as local optima networks. The relationship between communities of local optima found by network clustering algorithms and funnels is explored. Funnels are identified using the notion of monotonic sequences from the study of energy landscapes in theoretical chemistry. NK Landscapes and the Quadratic Assignment Problem are used as case studies. Our results show that communities are linked to funnels. The analysis exhibits relationships between these landscape structures and the performance of trajectory-based metaheuristics such as Simulated Annealing (SA) and Iterated Local Search (ILS). In particular, ILS gets trapped in funnels, and modular communities of optima slow it down. The funnels contribute to lower success for SA. We show that increasing the strength of ILS perturbation helps to ‘smooth’ the funnels and improves performance in multi-funnel landscapes.

Keywords
Fitness Landscapes; NK Landscapes; Quadratic Assignment Problem; Local Optima Networks; Funnel Landscapes; Combinatorial Optimisation

StatusPublished
AuthorsThomson Sarah, Daolio Fabio, Ochoa Gabriela
Publication date2017
Date of public distribution07/2017
Date accepted by journal20/03/2017
URLhttp://dx.doi.org/10.1145/3071178.3071211
PublisherACM
Place of publicationNew York
ISBN 978-1-4503-4920-8
LanguageEnglish
© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
My Portal