Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR06-083 | 16th May 2006 00:00

Speeding up Evolutionary Algorithms by Restricted Mutation Operators

RSS-Feed




TR06-083
Authors: Nils Hebbinghaus, Benjamin Doerr, Frank Neumann
Publication: 16th July 2006 12:00
Downloads: 2946
Keywords: 


Abstract:

We investigate the effect of restricting the mutation operator in
evolutionary algorithms with respect to the runtime behavior.
Considering the Eulerian cycle problem we present runtime bounds on
evolutionary algorithms with a restricted operator that are much
smaller than the best upper bounds for the general case. In our
analysis it turns out that a plateau which has to be coped with for
both algorithms changes its structure in a way that allows the
algorithms to obtain an improvement much faster. In addition, we
present a lower bound for the general case which shows that the
restricted operator speeds up computation by at least a linear
factor.



ISSN 1433-8092 | Imprint