On the Analysis of a Simple Evolutionary Algorithm With Dynamic Parameter Control

Evolutionary algorithms usually are controlled by various parameters and it is well known that an appropriate choice of these control parameters is crucial for the efficiency of the algorithms. In many cases it seems to be favorable not to use a static set of parameter settings for a problem but let the sizes of the parameters vary during an optimization. Even for the most simple type of nonstatic parameter settings, dynamic parameter control, no formal general proof is known that varying the parameter settings is advantageous. Here, a very simple evolutionary algorithm is analyzed, and an exponential improvement against even the optimal static parameter setting is proved. This result is closely related to the open question whether simulated annealing with a natural cooling schedule can provably outperform the Metropolis algorithm on a natural problem