2007 · 100 citations · 6 references
ComputingComputer ScienceMathematicsAlgorithmsEvolutionary TheoryOptimizationComputational ComplexityEvolutionary ComputationEvolutionary OptimizationGenetic AlgorithmsMetaheuristic OptimizationPopulation-based SearchEvolutionary SearchGenetic Algorithms For SearchHeuristicsPopulation-based OptimizationRuntime AnalysisSearch HeuristicsSelection
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} <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sup> 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.
6
Drift analysis and average time complexity of evolutionary algorithms
Jun He, Xin Yao · Artificial Intelligence · 2001 · 469 citations
Rigorous Hitting Times for Binary Mutations
Josselin Garnier, Leila Kallel, Marc Schoenauer · Evolutionary Computation · 1999 · 169 citations · Full text