Choosing the Right Algorithm With Hints From Complexity Theory (Hot-off-the-Press Track at GECCO 2022)

Wang，Shouda1; Zheng，Weijie2; Doerr，Benjamin1

10.1145/3520304.3534069

2022-07-09

GECCO 2022 Companion - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

45-46

Choosing a suitable algorithm from the myriads of different search heuristics is difficult when faced with a novel optimization problem. In this work, we argue that the purely academic question of what could be the best possible algorithm in a certain broad class of black-box optimizers can give fruitful indications in which direction to search for good established optimization heuristics. We demonstrate this approach on the recently proposed DLB benchmark, for which the only known results are O(n3) runtimes for several classic evolutionary algorithms and an O(n2 log n) runtime for an estimation-of-distribution algorithm. Our finding that the unary unbiased black-box complexity is only O(n2) suggests the Metropolis algorithm as an interesting candidate and we prove that it solves the DLB problem in quadratic time. Since we also prove that better runtimes cannot be obtained in the class of unary unbiased algorithms, we shift our attention to algorithms that use the information of more parents to generate new solutions. An artificial algorithm of this type having an O(n log n) runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem also in time O(n log n). This paper for the Hot-of-the-Press track at GECCO 2022 summarizes the work Shouda Wang, Weijie Zheng, Benjamin Doerr: Choosing the Right Algorithm With Hints From Complexity Theory. IJCAI 2021: 1697 - 1703 [11].

complexity theory metropolis algorithm runtime analysis

Others

English

EI

20223312576717

Computational complexity ; Genetic algorithms ; Heuristic algorithms

Machine Tools, General:603.1 ; Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Computer Programming:723.1

2-s2.0-85136327052

Scopus

1.Laboratoire d'Informatique (LIX),Cnrs,École Polytechnique,Institute Polytechnique de Paris,Palaiseau,France
2.Department of Computer Science and Engineering,Southern University of Science and Technology,Shenzhen,China

Wang，Shouda,Zheng，Weijie,Doerr，Benjamin. Choosing the Right Algorithm With Hints From Complexity Theory (Hot-off-the-Press Track at GECCO 2022)[C],2022:45-46.