Conference Proceeding

Coarse-Grained Barrier Trees of Fitness Landscapes


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.

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.

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

FundersThe Leverhulme Trust
Title of seriesLecture Notes in Computer Science
Number in series9921
Publication date31/12/2016
Publication date online31/08/2016
Place of publicationCham
ISSN of series0302-9743
Conference PPSN2016: 14th International Conference on Parallel Problem Solving from Nature
Conference locationEdinburgh

Research centres/groups