Extrema Graphs: Fitness Landscape Analysis to the Extreme!

Authors. Sophie Sadler, Alma Rahat, David J. Walker, Daniel Archambault

Venue. GECCO (2023)

Materials. DOI ACM PDF

Abstract. Fitness landscape analysis often relies on visual tools to provide insight to a search space, allowing for reasoning before optimisation. Currently, the dominant approach for visualisation is the local optima network, where the local structure around a potential global optimum is visualised using a network with the nodes as local minima and the edges as transitions between those minima through an optimiser. In this paper, we present an approach based on extrema graphs, originally used for isosurface extraction in volume visualisation, where transitions are captured between both maxima and minima embedded in two dimensions through dimensionality reduction techniques (multidimensional scaling in our prototype). These diagrams enable evolutionary computation practitioners to understand the entire search space by incorporating global information describing the spatial relationships between extrema. We demonstrate the approach on a number of continuous benchmark problems from the literature and highlight that the resulting visualisations enable the observation of known problem features, leading to the conclusion that extrema graphs are a suitable tool for extracting global information about problem landscapes.

@inproceedings{10.1145/3583133.3596343,
    title        = {Extrema Graphs: Fitness Landscape Analysis to the Extreme!},
    author       = {Sadler, Sophie and Rahat, Alma and Walker, David and Archambault, Daniel},
    year         = {2023},
    booktitle    = {Proceedings of the Companion Conference on Genetic and Evolutionary Computation},
    publisher    = {Association for Computing Machinery},
    series       = {GECCO '23 Companion},
    pages        = {2081–2089},
    doi          = {10.1145/3583133.3596343},
    url          = {https://doi.org/10.1145/3583133.3596343},
    abstract     = {Fitness landscape analysis often relies on visual tools to provide insight to a search space, allowing for reasoning before optimisation. Currently, the dominant approach for visualisation is the local optima network, where the local structure around a potential global optimum is visualised using a network with the nodes as local minima and the edges as transitions between those minima through an optimiser. In this paper, we present an approach based on extrema graphs, originally used for isosurface extraction in volume visualisation, where transitions are captured between both maxima and minima embedded in two dimensions through dimensionality reduction techniques (multidimensional scaling in our prototype). These diagrams enable evolutionary computation practitioners to understand the entire search space by incorporating global information describing the spatial relationships between extrema. We demonstrate the approach on a number of continuous benchmark problems from the literature and highlight that the resulting visualisations enable the observation of known problem features, leading to the conclusion that extrema graphs are a suitable tool for extracting global information about problem landscapes.},
    numpages     = {9}
}