6533b861fe1ef96bd12c5003
RESEARCH PRODUCT
Coarse-Grained Barrier Trees of Fitness Landscapes
Franz RothlaufSebastian HerrmannGabriela Ochoasubject
Local optima networksTheoretical computer scienceFitness landscapeComputer scienceSearch difficulty0102 computer and information sciences02 engineering and technology01 natural sciencesLocal optimum0202 electrical engineering electronic engineering information engineeringCluster (physics)Disconnectivity graphRepresentation (mathematics)MetaheuristicNK-landscapesFlooding algorithmbusiness.industryFitness landscape analysisBig valleyLocal optima networksTree (data structure)010201 computation theory & mathematicsBarrier tree020201 artificial intelligence & image processingArtificial intelligencebusinessdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-01-01 |