When the Plus Strategy Outperforms the Comma Strategyand When Not
- 1 April 2007
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 25-32
Abstract
Occasionally there have been long debates on whether to use elitist selection or not. In the present paper the simple (1, lambda) EA and {1 + lambda) EA operating on {0, l}n are compared by means of a rigorous runtime analysis. It turns out that only values for lambda that are logarithmic in n are interesting. An illustrative function is presented for which newly developed proof methods show that the (1, lambda) EA - where lambda is logarithmic in n - outperforms the (1 + lambda) EA for any lambda. For smaller offspring populations the (1, lambda) EA is inefficient on every function with a unique optimum, whereas for larger lambda the two randomized search heuristics behave almost equivalently.Keywords
This publication has 8 references indexed in Scilit:
- Runtime Analysis of the (μ + 1) EA on Simple Pseudo-Boolean FunctionsEvolutionary Computation, 2006
- How Comma Selection Helps with the Escape from Local Optima2006
- On the Choice of the Offspring Population Size in Evolutionary AlgorithmsEvolutionary Computation, 2005
- On the Choice of the Population Size2004
- On the analysis of the (1+1) evolutionary algorithmTheoretical Computer Science, 2002
- Drift analysis and average time complexity of evolutionary algorithmsArtificial Intelligence, 2001
- Rigorous Hitting Times for Binary MutationsEvolutionary Computation, 1999
- Randomized Algorithms1995