First Steps Towards a Runtime Analysis When Starting With a Good Solution
arXiv:2006.12161 · doi:10.1145/3675783
Abstract
The mathematical runtime analysis of evolutionary algorithms traditionally regards the time an algorithm needs to find a solution of a certain quality when initialized with a random population. In practical applications it may be possible to guess solutions that are better than random ones. We start a mathematical runtime analysis for such situations. We observe that different algorithms profit to a very different degree from a better initialization. We also show that the optimal parameterization of the algorithm can depend strongly on the quality of the initial solutions. To overcome this difficulty, self-adjusting and randomized heavy-tailed parameter choices can be profitable. Finally, we observe a larger gap between the performance of the best evolutionary algorithm we found and the corresponding black-box complexity. This could suggest that evolutionary algorithms better exploiting good initial solutions are still to be found. These first findings stem from analyzing the performance of the evolutionary algorithm and the static, self-adjusting, and heavy-tailed GA on the OneMax benchmark. We are optimistic that the question how to profit from good initial solutions is interesting beyond these first examples.
arXiv commentThe extended version of the PPSN 2020 conference paper
References in corpus (10)
- Multiplicative Drift Analysis
- Probabilistic Tools for the Analysis of Randomized Optimization Heuristics
- Adaptive Drift Analysis
- Runtime Analysis of the Genetic Algorithm on Random Satisfiable 3-CNF Formulas
- Analysis of Evolutionary Algorithms in Dynamic and Stochastic Environments
- A Rigorous Runtime Analysis of the GA on Jump Functions
- Fast Re-Optimization via Structural Diversity
- Fast Mutation in Crossover-based Algorithms
- Fixed-Target Runtime Analysis
- Lazy Parameter Tuning and Control: Choosing All Parameters Randomly From a Power-Law Distribution