Maximizing Drift is Not Optimal for Solving OneMax
| Autor: | Nathan Buskulic, Carola Doerr |
|---|---|
| Přispěvatelé: | Recherche Opérationnelle (RO), LIP6, Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS)-Sorbonne Université (SU)-Centre National de la Recherche Scientifique (CNRS), Sorbonne Université (SU) |
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
Mathematical optimization Unary operation Evolutionary algorithm 0102 computer and information sciences 02 engineering and technology [INFO.INFO-NE]Computer Science [cs]/Neural and Evolutionary Computing [cs.NE] 01 natural sciences Evolutionary computation Operator (computer programming) Mutation Rate Search algorithm Resampling 0202 electrical engineering electronic engineering information engineering Computer Simulation Neural and Evolutionary Computing (cs.NE) Mathematics Computer Science - Neural and Evolutionary Computing Maximization Function (mathematics) Biological Evolution Computational Mathematics 010201 computation theory & mathematics Mutation Mutation (genetic algorithm) 020201 artificial intelligence & image processing Algorithms |
| Zdroj: | Evolutionary Computation Evolutionary Computation, Massachusetts Institute of Technology Press (MIT Press), 2021, pp.1-20. ⟨10.1162/evco_a_00290⟩ Genetic and Evolutionary Computation Conference, Companion Material Genetic and Evolutionary Computation Conference, Companion Material, Jul 2019, Prague, Czech Republic. pp.425-426, ⟨10.1145/3319619.3321952⟩ GECCO (Companion) |
| ISSN: | 1063-6560 1530-9304 |
| Popis: | It may seem very intuitive that for the maximization of the OneMax problem $\OM(x):=\sum_{i=1}^n{x_i}$ the best that an elitist unary unbiased search algorithm can do is to store a best so far solution, and to modify it with the operator that yields the best possible expected progress in function value. This assumption has been implicitly used in several empirical works. In [Doerr, Doerr, Yang: Optimal parameter choices via precise black-box analysis, TCS, 2020] it was formally proven that this approach is indeed almost optimal. In this work we prove that drift maximization is not optimal. More precisely, we show that for most fitness levels between $n/2$ and $2n/3$ the optimal mutation strengths are larger than the drift-maximizing ones. This implies that the optimal RLS is more risk-affine than the variant maximizing the step-wise expected progress. We show similar results for the mutation rates of the classic (1+1) Evolutionary Algorithm (EA) and its resampling variant, the (1+1) EA$_{>0}$. As a result of independent interest we show that the optimal mutation strengths, unlike the drift-maximizing ones, can be even. To appear in Evolutionary Computation |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|