Understanding Problem Difficulty in Heuristic Search

The goal of this project is to better understand what makes a combinatorial optimisation problem easy or difficult for a given (meta-)heuristic search algorithm. This is achieved using landscape analysis and by evolving problem instances. The problems considered include traditional combinatorial problems, such as the Traveling Salesman Problem, as well as problems occurring in Software Engineering, such as Mutation Testing or Combinatorial Interaction Testing.

We analyse a search space by sampling points across the space induced by some problem instance and some heuristic search algorithm in order to produce a representation of the fitness landscape the search process has to travel through. In particular, we use Local Optima Networks to model the search space as a graph having local optima as vertices, and transitions among them according to a given search operator as edges. These networks are then analysed, by measuring specific characteristics and through visualisations, in order to better understand the challenges faced by the solving method and to propose improvements.

This ARCHIE-WeSt project is carried out in the context of two projects at the University of Stirling: the ‘Dynamic Adaptive Automated Software Engineering’ (DAASE, grant number EP/J017515/1, Co-I Dr Gabriela Ochoa) project funded by the EPSRC and ‘The Cartography of Computational Search Spaces’ (award number RPG-2015-395, PI Dr Gabriela Ochoa) funded by the Leverhulme Trust.

For more information about the project contact Prof Gabriela Ochoa (gabriela.ochoa@cs.stir.ac.uk), Professor in Computing Science at the University of Stirling.

For a list of the research areas in which ARCHIE-WeSt users are active please click here.