When the Plus Strategy Outperforms the Comma Strategyand When Not

摘要

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}ⁿ 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.