Comparing Evolutionary Algorithms to the (1+1)-EA

(1+1)-EA compares favorably to other evolutionary algorithms (EAs) in
terms of fitness function distribution at a given iteration and with
respect to the average optimization time. Our approach is applicable
when the reproduction operator of an evolutionary algorithm is dominated
by the mutation operator of the (1+1)-EA. In this case one can extend
the lower bounds obtained for the expected optimization time of the
(1+1)-EA to other EAs based on the dominated reproduction operator. This method is exampled on the sorting problem with HAM landscape and the exchange mutation operator. We consider several simple examples where the (1+1)-EA is the best possible search strategy in the class of the EAs.

The talk covers our joint work with Pavel Borisovsky

P. A. Borisovsky and A. V. Eremeev. Comparing Evolutionary Algorithms to the (1+1)-EA. Theoretical Computer Science. 403 (1), 2008, pp. 33-41.