Coarse-Grained Barrier Trees of Fitness Landscapes

Citation

Herrmann S, Ochoa G & Rothlauf F (2016) Coarse-Grained Barrier Trees of Fitness Landscapes. In: Handl J, Hart E, Lewis P, LopezIbanez M, Ochoa G & Paechter B (eds.) Parallel Problem Solving from Nature – PPSN XIV. PPSN 2016. Lecture Notes in Computer Science, 9921. PPSN2016: 14th International Conference on Parallel Problem Solving from Nature, Edinburgh, 17.09.2016-21.09.2016. Cham: Springer, pp. 901-910. https://doi.org/10.1007/978-3-319-45823-6_84

Abstract
Recent literature suggests that local optima in fitness landscapes are clustered, which offers an explanation of why perturbation-based metaheuristics often fail to find the global optimum: they become trapped in a sub-optimal cluster. We introduce a method to extract and visualize the global organization of these clusters in form of a barrier tree. Barrier trees have been used to visualize the barriers between local optima basins in fitness landscapes. Our method computes a more coarsely grained tree to reveal the barriers between clusters of local optima. The core element is a new variant of the flooding algorithm, applicable to local optima networks, a compressed representation of fitness landscapes. To identify the clusters, we apply a community detection algorithm. A sample of 200 NK fitness landscapes suggests that the depth of their coarse-grained barrier tree is related to their search difficulty.

Keywords
Fitness landscape analysis; Barrier tree; Disconnectivity graph; Local optima networks; Big valley; Search difficulty; NK-landscapes

People

Professor Gabriela Ochoa

Professor, Computing Science