The Cartography of Computational Search Spaces - School of Computing Seminar Series

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.

Gabriela Ochoa is a Senior Lecturer in Computing Science at the University of Stirling, Scotland. She holds a PhD from the University of Sussex, UK, and has held academic positions at the University of Nottingham, UK and the University Simon Bolivar, Venezuela. Her research interests lie in the foundations and application of evolutionary algorithms and heuristic search methods, with emphasis on autonomous search, hyper-heuristics, fitness landscape analysis and visualisation; and applications to combinatorial optimisation, healthcare, and software engineering. She has published over 100 scholarly papers, has served on various program committees and organising committees of evolutionary and bio-inspired computation conferences such as GECCO, PPSN, EvoStar, FOGA and CEC. She is associate editor of the IEEE Transactions on Evolutionary Computation and the Evolutionary Computation Journal (MIT Press), served as the Editor-in-Chief for the 2017 edition of the Genetic and Evolutionary computation conference (GECCO), and is a member of the executive boards of EvoStar and the ACM Special Interest Group in Evolutionary Computation (SIGEVO).