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

Citation

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. https://doi.org/10.1007/s10710-018-9328-1

Abstract
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.

Keywords
fitness landscape; genetic improvement; local optima network; visualisation

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

People

Professor Gabriela Ochoa

Professor, Computing Science