hide
Free keywords:
-
Abstract:
Successful applications of evolutionary algorithms show that certain variation
operators can lead to good solutions much faster than other ones. We examine
this behavior observed in practice from a theoretical point of view and
investigate the effect of an asymmetric mutation operator in evolutionary
algorithms with respect to the runtime behavior. Considering the Eulerian cycle
problem we present runtime bounds for evolutionary algorithms using an
asymmetric operator which are much smaller than the best upper bounds for a
more general one. In our analysis it turns out that a plateau which both
algorithms have to cope with changes its structure in a way that allows the
algorithm to obtain an improvement much faster. In addition, we present a lower
bound for the general case which shows that the asymmetric operator speeds up
computation by at least a linear factor.