Abstract
We propose and analyze a self-adaptive version of the (1,) evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time (number of fitness evaluations) of O(n /log + n log n). This time is asymptotically smaller than the optimization time of the classic (1,) EA and (1 +) EA for all static mutation rates and best possible among all -parallel mutation-based unbiased black-box algorithms. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr et al. (GECCO 2017) can be replaced by our simple endogenous scheme. Moreover, the paper contributes new tools for the analysis of the two-dimensional drift processes arising in self-adaptive EAs, including bounds on occupation probabilities in processes with non-constant drift.
Original language | English |
---|---|
Title of host publication | 2018 Proceedings of the Genetic and Evolutionary Computation Conference |
Publisher | Association for Computing Machinery |
Publication date | 2018 |
Pages | 1475-1482 |
ISBN (Print) | 978-1-4503-5618-3 |
DOIs | |
Publication status | Published - 2018 |
Event | 2018 Genetic and Evolutionary Computation Conference - Kyoto Terrsa, Kyoto, Japan Duration: 15 Jul 2018 → 19 Jul 2018 |
Conference
Conference | 2018 Genetic and Evolutionary Computation Conference |
---|---|
Location | Kyoto Terrsa |
Country/Territory | Japan |
City | Kyoto |
Period | 15/07/2018 → 19/07/2018 |
Keywords
- Self-adaptive evolutionary algorithms
- Theory
- Run-time analysis