The density of states - a measure of the difficulty of optimisation problems
Abstract
We introduce a classifying measure of fitness landscapes - the density of states - for continuous and discrete problems, especially optimisation of sequences and graphs. By means of the Boltzmann strategy we obtain a simple algorithm to calculate the density of states for a given problem. Knowing the density of states we are able to approximate the optimal fitness value of the problem which makes it feasible to assess the effectivity of practical optimisations.
