Understanding randomised search heuristics lessons from the evolution of theory: A case study

Recently the perspective of fixed budget computations has been added as a novel branch to the theory of evolutionary algorithms and other randomised search heuristics. It has been found that fixed budget results can provide a more detailed and fairer assessment of the performance of heuristic optimisation methods. Here, the focus is on well known simple heuristics where an understanding of their strengths and weaknesses has been developed in previous publications. It is shown that even on a relatively simple and well-understood example function the heuristics exhibit surprisingly complex and unexpected behaviour. In particular, a search heuristic which is known to be bad at hill-climbing in general is shown to be a very efficient hill-climber for a specific example problem.