Name
Abstract | ||
|---|---|---|
We propose and analyze a self-adaptive version of the (1,lambda) evolutionary algorithm in which the current mutation rate is encoded within 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 lambda/log lambda+n log n) when lambda is at least C ln n for some constant C > 0. For all values of lambda >= Cl n n , this performance is asymptotically best possible among all lambda-parallel mutation-based unbiased black-box algorithms. Our result rigorously proves for the first time that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. In particular, it gives asymptotically the same performance as the relatively complicated self-adjusting scheme for the mutation rate proposed by Doerr, Giessen, Witt, and Yang (Algorithmica 2019). On the technical side, the paper contributes new tools for the analysis of two-dimensional drift processes arising in the analysis of dynamic parameter choices in EAs, including bounds on occupation probabilities in processes with non-constant drift. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.1007/s00453-020-00726-2 | ALGORITHMICA |
Keywords | DocType | Volume |
Evolutionary algorithms, Self-adaptive, Runtime analysis | Journal | 83 |
Issue | ISSN | Citations |
4 | 0178-4617 | 1 |
PageRank | References | Authors |
0.35 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Benjamin Doerr | 1 | 1504 | 127.25 |
| Carsten Witt | 2 | 987 | 59.83 |
| Jing Yang | 3 | 45 | 2.32 |