A Comparison of Simulated Annealing with a Simple Evolutionary Algorithm

摘要

Evolutionary algorithms belong to the class of general randomized search heuristics. Theoretical investigations often concentrate on simple instances like the well-known (1+1) EA. This EA is very similar to simulated annealing, another general randomized search heuristic. These two algorithms are systematically compared under the perspective of the expected optimization time when optimizing pseudo-boolean functions. It is investigated how well the algorithmic similarities can be exploited to transfer analytical results from one algorithm to the other. Limitations of such an approach are illustrated by the presentation of example functions where the performance of the two algorithms differs in an extreme way. Furthermore, an attempt is made to characterize classes of functions where such a transfer of results is more successful.