A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation

The development in the area of randomized search heuristics has shown the importance of a rigorous theoretical analysis of the performance of these heuristics. Unfortunately, the analysis of the expected optimization time of a specific algorithm has in general no implications on the behaviour of other algorithms — even if they differ only in some aspects. Indeed, small differences may imply large differences in the optimization time. Hence, it is an important issue to compare fundamental heuristics and to find out for which problems they behave in such a similar way that results on one heuristic can be transferred to the other one and to describe problems where they behave quite differently.Such an approach is performed here to the simple and well-known (1+1) EA, which is based on elitist selection and a global search operator, and simulated annealing, which is based on nonelitist selection and a local search operator.