A Study on Performance of the (1+1)-Evolutionary Algorithm.
Pavel Borisovsky, Anton V. Eremeev · 2002
The first contribution of this paper is a theoretical comparison of the (1+1)- EA evolutionary algorithm to other evolutionary algorithms in the case of so-called monotone reproduction operator, which indicates that the (1+1)- EA is an optimal search technique in this setting. After that we study the expected optimization time for the (1+1)-EA and show two set covering problem families where it is superior to certain general-purpose exact algorithms. Finally some pessimistic estimates of mutation operators in terms of upper bounds on evolvability are suggested for the NP-hard optimization problems.