Please use this identifier to cite or link to this item:
|Scopus||Web of Science®||Altmetric|
|Title:||Optimal fixed and adaptive mutation rates for the leadingones problem|
|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|
|Series/Report no.:||Lecture Notes in Computer Science ; 6238|
|Conference Name:||International Conference on Parallel Problem Solving from Nature (11th : 2010 : Krakow, Poland)|
|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|
|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.