Visualising the Global Structure of Search Landscapes: Genetic Improvement as a Case Study


Veerapen N & Ochoa G (2018) Visualising the Global Structure of Search Landscapes: Genetic Improvement as a Case Study. Genetic Programming and Evolvable Machines, 19 (3, Special Issue: SI), pp. 317-349.

The search landscape is a common metaphor to describe the structure of computational search spaces. Different landscape metrics can be computed and used to predict search difficulty. Yet, the metaphor falls short in visualisation terms because it is hard to represent complex landscapes, both in terms of size and dimensionality. This paper combines Local Optima Networks, as a compact representation of the global structure of a search space, and dimensionality reduction, using the t-Distributed Stochastic Neighbour Embedding (t-SNE) algorithm, in order to both bring the metaphor to life and convey new insight into the search process. As a case study, two benchmark programs, under a Genetic Improvement bug-fixing scenario, are analysed and visualised using the proposed method. Local Optima Networks for both iterated local search and a hybrid genetic algorithm, across different neighbourhoods, are compared, highlighting the differences in how the landscape is explored.

fitness landscape; genetic improvement; local optima network; visualisation

Genetic Programming and Evolvable Machines: Volume 19, Issue 3, Special Issue: SI

FundersThe Leverhulme Trust and Engineering and Physical Sciences Research Council
Publication date30/09/2018
Publication date online06/08/2018
Date accepted by journal11/07/2018
Related URLs

Research centres/groups