Choosing the Right Algorithm With Hints From Complexity Theory (Hot-off-the-Press Track at GECCO 2022)
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 .
|EI Accession Number|
Computational complexity ; Genetic algorithms ; Heuristic algorithms
|ESI Classification Code|
Machine Tools, General:603.1 ; Computer Theory, Includes Formal Logic, Automata Theory, Switching Theory, Programming Theory:721.1 ; Computer Programming:723.1
Cited Times [WOS]:0
|Document Type||Conference paper|
|Department||Department of Computer Science and Engineering|
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.
|Files in This Item:||There are no files associated with this item.|
|Recommend this item|
|Export to Endnote|
|Export to Excel|
|Export to Csv|
|Similar articles in Google Scholar|
|Similar articles in Baidu Scholar|
|Similar articles in Bing Scholar|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.