The cartography of computational search spaces

Abstract

This talk will present our recent findings and visual (static and animated) maps characterising combinatorial and computer program search spaces. We seek to lay the foundations for a new perspective to understand problem structure and improve heuristic search algorithms: search space cartography.

Heuristic methods 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 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.

Most fitness landscapes analysis techniques study the local structure of search spaces. Our recently proposed model, Local Optima Networks, helps to study instead their global structure. This graph-based model provides fundamental new insight into the structural organisation and the connectivity pattern of a search space with given move operators. Most importantly, it allows us to visualise realistic search spaces in ways not previously possible and brings a whole new set of network metrics for characterising them.