On the analysis of a dynamic evolutionary algorithm |
| |
Authors: | Thomas Jansen Ingo Wegener |
| |
Affiliation: | FB Informatik, LS 2, Univ. Dortmund, 44221 Dortmund, Germany |
| |
Abstract: | 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) 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) EAs with a fixed mutation probability are compared with dynamic (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) EA. More precisely, functions are presented where each static (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) EA has exponential expected run time while a static (1+1) EA with a good choice of the mutation probability has polynomial run time with overwhelming probability. |
| |
Keywords: | Evolutionary algorithms Run time analysis Mutation probability Time-dependent parameter setting |
本文献已被 ScienceDirect 等数据库收录! |
|