Skip to main content

Characterising optimisation problems using information theory

Primary supervisor

Aldeida Aleti

The suitability of a search method for solving an optimisation problem instance depends on the structure of the fitness landscape of that instance. A fitness landscape in the context of combinatorial optimisation problems refers to the search space of possible solutions, the fitness function, and the neighbourhood operator.

Aim/outline

In this project, we will use information theory to develop suitable metrics to characterise the fitness landscape of optimisation problems. The metrics will then be used to classify optimisation problems as hard or easy for particular search methods.

Required knowledge

Local search, optimisation, mathematics, statistics, probability, information theory.