event
Thursday 15 Feb 2018: The Cartography of Computational Search Spaces
Dr. Gabriela Ochoa - University of Stirling
Harrison 170 14:30-15:30
This talk will present our recent findings and visual (static and animated) maps characterising combinatorial and 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.
Short Bio:
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 and serves various program committees. 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, and is a member of the executive boards of EvoStar and the ACM Special Interest Group in Evolutionary Computation (SIGEVO).
