Fitness Landscapes and Local Optima Networks

Heuristic methods such as evolutionary algorithms and metaheuristics operate by searching a large space of candidate solutions. The search space can be regarded as a spatial structure where each point (candidate solution) has a height (objective or fitness value) forming a fitness landscape surface. The performance of heuristic search algorithms crucially depends on the fitness landscape structure, and the study of landscapes offers an alternative to problem understanding where realistic formulations and algorithms can be analysed.

LON with basin transition edges.
Local optima network with basin-transition edges for an NK-landscape instance with N = 18, K = 2. The size of the nodes is proportional to the basin sizes. The nodes’ color represents the fitness values: the darker the color, the highest the fitness value. The edges’ width scales with the transition probability (weight) between local optima.
LON with escape edges (D = 2).
Local optima network with escape edges (with D = 2 ) for an NK-landscape instance with N = 18, K = 2. The nodes’ color represents the fitness values: the darker the color, the highest the fitness value. The edges’ width scales with the transition probability (weight) between local optima.
LON with escape edges (D = 1).
Local optima network with escape edges (with D = 2) for an NK-landscape instance with N = 18, K = 2. The nodes’ color represents the fitness values: the darker the color, the highest the fitness value. The edges’ width scales with the transition probability (weight) between local optima.

 

Local Optima Networks (LONs) are a graph-based model of fitness landscapes we developed in 2008 (Ochoa et al, 2008, Tomassini et al, 2008, Verel et al, 2011). The inspiration behind this model comes from the study of energy landscapes in theoretical chemistry (Doye, 2002). LONs compress a search space into a network where nodes are local optima and edges are possible search transitions among these optima.

LON for TSP Instance gr66.
Ochoa, Gabriela; Veerapen, Nadarajen.
Deconstructing the Big Valley Search Space Hypothesis
Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
Ochoa, Gabriela; Veerapen, Nadarajen.
Deconstructing the Big Valley Search Space Hypothesis
Evolutionary Computation in Combinatorial Optimization - EvoCOP 2016, pp. 58–73, Springer, 2016.
3D LON for a Number Partitioning Problem Instance .
Ochoa G, Veerapen N, Daolio F & Tomassini M.
Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study
Evolutionary Computation in Combinatorial Optimization. EvoCOP 2017.

 

Most fitness landscapes analysis techniques study the local structure of search spaces. Local Optima Networks help to study instead their global structure. They provide fundamental new insight into the structural organisation and the connectivity pattern of a search space with given move operators. Most importantly, LONs allow us to visualise realistic search spaces in ways not previously possible; and bring a whole new set of complex network tools and metrics for analysing and characterising computational search.

 

Goal

Our goal is to develop and establish a set of methodologies, visualisation techniques and metrics to thoroughly characterise and exploit the structure of computational search spaces. This site intends to be a unified resource space offering a new perspective to understand problem structure and improve heuristic search algorithms.

Currently, the site mainly covers research on Local Optima Networks and Gray-box optimisation. However, we seek to incorporate additional methodologies for data visualisation and dimensionality reduction; as well as novel approaches for understanding and exploiting problem structure.

This effort emerged after the completion in 2018 of a research project entitled “The Cartography of Computational Search Spaces” funded by the Leverhulme Trust.

 

Acknowledgements

Work conducted at the University of Stirling has been supported by the Leverhulme Trust [award number RPG-2015-395] and by the UK’s Engineering and Physical Sciences Research Council – EPSRC [grant number EP/J017515/1]. Many of our results were obtained using the EPSRC-funded ARCHIE-WeSt High Performance Computer, EPSRC grant EP/K000586/1.

 

trophy_icon Awards

Best Paper Award

 

Best Paper Nomination

 

Best Presentation Award