On the analysis of a dynamic evolutionary algorithm

Evolutionary algorithms are applied as problem-independent optimization algorithms. They are quite efficient in many situations. However, it is difficult to analyze even the behavior of simple variants of evolutionary algorithms like the (1+1)(1+1) EA on rather simple functions. Nevertheless, only the analysis of the expected run time and the success probability within a given number of steps can guide the choice of the free parameters of the algorithms. Here static (1+1)(1+1) EAs with a fixed mutation probability are compared with dynamic (1+1)(1+1) EAs with a simple schedule for the variation of the mutation probability. The dynamic variant is first analyzed for functions typically chosen as example-functions for evolutionary algorithms. Afterwards, it is shown that it can be essential to choose the suitable variant of the (1+1)(1+1) EA. More precisely, functions are presented where each static (1+1)(1+1) EA has exponential expected run time while the dynamic variant has polynomial expected run time. For other functions it is shown that the dynamic (1+1)(1+1) EA has exponential expected run time while a static (1+1)(1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability.