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.


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.


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