The cartography of computational search spaces

by Gabriela Ochoa (University of Stirling)

16:00 (60 min) in USB 2.022

This talk will present our recent findings and visual (static and animated) maps characterising computational search spaces from several domains. 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. Local Optima Networks help 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. 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.