English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions

MPS-Authors
/persons/resource/persons44584

Happ,  Edda
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44705

Johannsen,  Daniel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44793

Klein,  Christian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45115

Neumann,  Frank
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Ressource
No external resources are shared
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Happ, E., Johannsen, D., Klein, C., & Neumann, F. (2008). Rigorous Analyses of Fitness-Proportional Selection for Optimizing Linear Functions. In M. Keijzer, G. Antoniol., C. B. Congdon, K. Deb, B. Doerr, N. Hansen, et al. (Eds.), Genetic and Evolutionary Computation Conference 2008 (pp. 953-960). New York, NY: ACM. doi:10.1145/1389095.1389277.


Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-1CD9-9
Abstract
Rigorous runtime analyses of evolutionary algorithms (EAs) mainly investigate algorithms that use elitist selection methods. Two algorithms commonly studied are Randomized Local Search (RLS) and the (1+1)~EA and it is well known that both optimize any linear pseudo-Boolean function on $n$ bits within an expected number of $\ensuremath{{O}}(n \log n)$ fitness evaluations. In this paper, we analyze variants of these algorithms that use fitness proportional selection. A well-known method in analyzing the local changes in the solutions of RLS is a reduction to the gambler's ruin problem. We extend this method in order to analyze the global changes imposed by the (1+1)~EA. By applying this new technique we show that with high probability using fitness proportional selection leads to an exponential optimization time for any linear pseudo-Boolean function with non-zero weights. Even worse, all solutions of the algorithms during an exponential number of fitness evaluations differ with high probability in linearly many bits from the optimal solution. Our theoretical studies are complemented by experimental investigations which confirm the asymptotic results on realistic input sizes.