Barrier-based models of hard problems and crossover

Model problems are useful in the study of combinatorial optimisation algorithms as they allow results to be calculated that are difficult or impossible with real problems. However, these ´toy´ problems are often contrived to show a particular feature, and it is difficult to know how they compare to real problems. We present a framework for creating models of hard optimisation problems that captures large landscape features such as local optima and their basins. The framework aggregates configurations by partitioning the search space based on the structure of basins and barriers in the landscape. This results in a model problem with a massively reduced number of states. For the model problem it is readily feasible to study simple optimisation algorithms using a Markov chain analysis. Genetic algorithms are one type of problem that is hard to model in this framework. We demonstrate the difficulty in modelling just one aspect of these algorithms, crossover, by trying a simple technique to model it.