Thursday 17 Nov 2016: The Fitness Landscape of Combinatorial Optimisation Problems
Adam Prugel-Bennett - University of Southampton
Harrison 170 14:30-15:30
Combinatorial optimisation problems are an important set of problems with many practical applications. Many heuristic search algorithms have been designed to solve these. However, do we have any right to believe that these search strategy should work? In this talk we describe our attempt to study the landscapes of a number of classical optimisation problems. In particularly, we study instances of MAXSAT, Graph-colouring, TSP and Quadratic Assignment Problem. Despite their many differences we show that there is a lot of commonality in the large-scale structure of these problems. This provides some optimism that common research heuristics are likely to be effective on a large number of problems that we are likely to face.