Choosing the right algorithm with hints from complexity theory

DOI10.1016/J.IC.2023.105125MaRDI QIDQ6178456zbMATH OpenOpenAlexFDO

Authors Weijie Zheng, Benjamin Doerr

Publication date 18 January 2024

Published in Information and Computation (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://arxiv.org/abs/2109.06584

zbMATH Keywords

black-box optimizationcomplexity theoryestimation-of-distribution algorithmMetropolis algorithmruntime analysis

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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(n^3)$ runtimes for several classic evolutionary algorithms and an $O(n^{2}logn)$ runtime for an estimation-of-distribution algorithm. Our finding that the unary unbiased black-box complexity is only $O(n^2)$ 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(nlogn)$ runtime leads to the result that the significance-based compact genetic algorithm (sig-cGA) can solve the DLB problem also in time $O(nlogn)$. Our experiments show a remarkably good performance of the Metropolis algorithm, clearly the best of all algorithms regarded for reasonable problem sizes.

Cites work

• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• A study of drift analysis for estimating computation time of evolutionary algorithms
• A tight runtime analysis for the (1+(,)) GA on LeadingOnes
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• Analyzing evolutionary algorithms. The computer science perspective.
• Automata, Languages and Programming
• Automatic adaptation of hypermutation rates for multimodal optimisation
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Black-box complexities of combinatorial problems
• Black-box search by elimination of fitness functions
• Black-box search by unbiased variation
• Does comma selection help to cope with local optima?
• Drift analysis and evolutionary algorithms revisited
• Equation of state calculations by fast computing machines
• Evolutionary learning: advances in theories and algorithms
• Fast mutation in crossover-based algorithms
• Faster black-box algorithms through higher arity operators
• From black-box complexity to designing new genetic algorithms
• How to escape local optima in black box optimisation: when non-elitism outperforms elitism
• scientific article; zbMATH DE number 6019551 (Why is no real title available?)
• scientific article; zbMATH DE number 1962832 (Why is no real title available?)
• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• scientific article; zbMATH DE number 3194843 (Why is no real title available?)
• Improved time complexity analysis of the simple genetic algorithm
• Level-based analysis of the univariate marginal distribution algorithm
• Metaheuristics -- the metaphor exposed
• Multiplicative up-drift
• On the analysis of the \((1+1)\) evolutionary algorithm
• On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization
• On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help
• Optimal parameter choices via precise black-box analysis
• Optimal static and self-adjusting parameter choices for the (1+( , )) genetic algorithm
• Probability Inequalities for Sums of Bounded Random Variables
• Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes
• Runtime analysis for self-adaptive mutation rates
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• Runtime analysis of the 1-ANT ant colony optimizer
• Self-adjusting evolutionary algorithms for multimodal optimization
• Simulated annealing versus Metropolis for a TSP instance
• Stagnation detection meets fast mutation
• The (1+1) elitist black-box complexity of LeadingOnes
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• The benefits and limitations of voting mechanisms in evolutionary optimisation
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• The Metropolis algorithm for graph bisection
• The query complexity of a permutation-based variant of mastermind
• The runtime of the compact genetic algorithm on jump functions
• The time complexity of maximum matching by simulated annealing
• Time complexity analysis of evolutionary algorithms on random satisfiable k-CNF formulas
• Towards a runtime comparison of natural and artificial evolution
• Upper and lower bounds for randomized search heuristics in black-box optimization
• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not

This page was built for publication: Choosing the right algorithm with hints from complexity theory

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6178456)