Communities of Local Optima as Funnels in Fitness Landscapes

Citation

Herrmann S, Ochoa G & Rothlauf F (2016) Communities of Local Optima as Funnels in Fitness Landscapes. In: Friedrich T (ed.) Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Denver, CO, USA, July 20 - 24, 2016. GECCO 16: Genetic and Evolutionary Computation Conference 2016, Denver, CO, USA, 20.07.2016-24.07.2016. New York: ACM, pp. 325-331. https://doi.org/10.1145/2908812.2908818

Abstract
We conduct an analysis of local optima networks extracted from fitness landscapes of the Kauffman NK model under iterated local search. Applying the Markov Cluster Algorithm for community detection to the local optima networks, we find that the landscapes consist of multiple clusters. This result complements recent findings in the literature that landscapes often decompose into multiple funnels, which increases their difficulty for iterated local search. Our results suggest that the number of clusters as well as the size of the cluster in which the global optimum is located are correlated to the search difficulty of landscapes. We conclude that clusters found by community detection in local optima networks offer a new way to characterize the multi-funnel structure of fitness landscapes.

People

Professor Gabriela Ochoa

Professor, Computing Science