2020/06/22 by Denis Antipov, Antipov, Denis, Maxim Buzdalov +3
Computer Science · #68W50 #Advanced Multi-Objective Optimization Algorithms #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE)
paper · doi:10.48550/arxiv.2006.12161
openalex publication_date 2020/06/22 · openalex created_date 2022/07/23 · openalex updated_date 2026/07/28
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 (1+1) evolutionary algorithm and the static, self-adjusting, and heavy-tailed (1 + (λ,λ)) GA on the OneMax benchmark. We are optimistic that the question how to profit from good initial solutions is interesting beyond these first examples.