Please use this identifier to cite or link to this item:
Scopus Web of Science® Altmetric
Type: Conference paper
Title: Optimal fixed and adaptive mutation rates for the leadingones problem
Author: Bottcher, S.
Doerr, B.
Neumann, F.
Citation: Parallel Problem Solving from Nature – PPSN XI: 11th International Conference, Kraków, Poland, September 11-15, 2010, Proceedings, Part I / Robert Schaefer, Carlos Cotta, Joanna Kołodziej and Günter Rudolph (eds.): pp.1-10
Publisher: Springer-Verlag
Publisher Place: Berlin
Issue Date: 2010
Series/Report no.: Lecture Notes in Computer Science ; 6238
ISBN: 3642158439
ISSN: 0302-9743
Conference Name: International Conference on Parallel Problem Solving from Nature (11th : 2010 : Krakow, Poland)
Statement of
Süntje Böttcher, Benjamin Doerr and Frank Neumann
Abstract: We reconsider a classical problem, namely how the (1+1) evolutionary algorithm optimizes the LEADINGONES function. We prove that if a mutation probability of p is used and the problem size is n, then the optimization time is1/2p2 ((1 - p)-n+1 - (1 - p)). For the standard value of p ≅ 1/n, this is approximately 0.86n2. As our bound shows, this mutation probability is not optimal: For p ≅ 1.59/n, the optimization time drops by more than 16% to approximately 0.77n2. Our method also allows to analyze mutation probabilities depending on the current fitness (as used in artificial immune systems). Again, we derive an exact expression. Analysing it, we find a fitness dependent mutation probability that yields an expected optimization time of approximately 0.68n2, another 12% improvement over the optimal mutation rate. In particular, this is the first example where an adaptive mutation rate provably speeds up the computation time. In a general context, these results suggest that the final word on mutation probabilities in evolutionary computation is not yet spoken.
Rights: Springer-Verlag Berlin, Heidelberg ©2010
RMID: 0020110552
DOI: 10.1007/978-3-642-15844-5_1
Published version:
Appears in Collections:Computer Science publications

Files in This Item:
There are no files associated with this item.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.