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.
Awards
Best Paper Award
- F. Chicano, G. Ochoa, D. Whitley, R. Tinos (2018) Enhancing partition crossover with articulation points analysis. Genetic and Evolutionary Computation Conference, GECCO 2018, pp. 269–276, ACM, 2018.
- G. Ochoa, N. Veerapen, F. Daolio, M. Tomassini (2017) Understanding Phase Transitions with Local Optima Networks: Number Partitioning as a Case Study. European Conference on Evolutionary Computation in Combinatorial Optimization, EvoCOP 2017. LNCS vol. 10197, Springer pp. 233–248. DOI: 10.1007/978-3-319-55453-2_16
- G. Ochoa and N. Veerapen (2016) Deconstructing the Big Valley Search Space Hypothesis. Evolutionary Computation in Combinatorial Optimization, Proceedings of the 16th European Conference, EvoCOP 2016, Lecture Notes in Computer Science, vol. 9595, pp. 58–73. Springer International Publishing, 2016 [online][dataset][Poster]
Best Paper Nomination
- F. Chicano, D. Whitley, G. Ochoa, R. Tinos (2017) Optimizing One Million Variables NK Landscapes by Hybridizing Deterministic Recombination and Local Search. Genetic and Evolutionary Computation Conference, GECCO 2017: 753-760 . [Online]
- G. Ochoa, F. Chicano, R. Tinos and D. Whitley (2015) Tunnelling Crossover Networks. Genetic and Evolutionary Computation Conference (GECCO-2015), ACM, pp 449-456. [bib entry]
- G. Ochoa, M. Tomassini, S. Verel, C. Darabos (2008) A Study of NK Landscapes’ Basins and Local Optima Networks. Proceedings of Genetic and Evolutionary Computation Conference (GECCO-08), ACM, pp. 555-562.
Best Presentation Award
- Nadarajen Veerapen, Fabio Daolio, Gabriela Ochoa: Modelling genetic improvement landscapes with local optima networks. GECCO (Companion) 2017: 1543-1548