# Choosing the Right Algorithm With Hints From Complexity Theory

@article{Wang2021ChoosingTR, title={Choosing the Right Algorithm With Hints From Complexity Theory}, author={Shouda Wang and W. Zheng and Benjamin Doerr}, journal={ArXiv}, year={2021}, volume={abs/2109.06584} }

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… Expand

#### Figures from this paper

#### 3 Citations

An Extended Jump Function Benchmark for the Analysis of Randomized Search Heuristics

- Computer Science
- ArXiv
- 2021

An extended class Jumpk,δ of jump functions that contain a valley of low fitness of width δ starting at distance k from the global optimum is proposed, and it is proved that several previous results extend to this more general class. Expand

A gentle introduction to theory (for non-theoreticians)

- Computer Science
- GECCO Companion
- 2021

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial… Expand

From understanding genetic drift to a smart-restart parameter-less compact genetic algorithm

- Computer Science
- GECCO
- 2020

This work proposes a parameter-less version of the compact genetic algorithm that automatically finds a suitable population size without spending too much time in situations unfavorable due to genetic drift and proves an easy mathematical runtime guarantee for this algorithm. Expand

#### References

SHOWING 1-10 OF 132 REFERENCES

First Steps Towards a Runtime Analysis When Starting With a Good Solution

- Computer Science
- PPSN
- 2020

It is shown that different algorithms profit to a very different degree from a better initialization and that the optimal parameterization of the algorithm can depend strongly on the quality of the initial solutions, and self- adjusting and randomized heavy-tailed parameter choices can be profitable. Expand

Analyzing randomized search heuristics via stochastic domination

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2019

This work argues that stochastic domination is a notion that should be used more frequently in this area, and proves a variant of the fitness level theorem which shows that the runtime of the search heuristic is dominated by a sum of independent geometric random variables. Expand

The (1+1) Elitist Black-Box Complexity of LeadingOnes

- Computer Science, Mathematics
- GECCO
- 2016

The permutation- and bit-invariant version of LeadingOnes is regarded and it is proved that its (1+1) elitist black-box complexity is Ω(n2), a bound that is matched by (1-1)-type evolutionary algorithms. Expand

Optimal Parameter Choices via Precise Black-Box Analysis

- Mathematics, Computer Science
- GECCO
- 2016

It is proved that the unary unbiased black-box complexity of the classic OneMax function class is n ln( n) -- cn ± o(n) for a constant c between 0.2539 and 0.2665. Expand

From black-box complexity to designing new genetic algorithms

- Mathematics, Computer Science
- Theor. Comput. Sci.
- 2015

This work designs a new crossover-based genetic algorithm that uses mutation with a higher-than-usual mutation probability to increase the exploration speed and crossover with the parent to repair losses incurred by the more aggressive mutation. Expand

Black-box search by elimination of fitness functions

- Mathematics, Computer Science
- FOGA '09
- 2009

Though in its early stages, it is believed that there is utility in search methods based on ideas from the elimination of functions method, and that the viewpoint provides promise and new insight about black-box optimization. Expand

A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-boolean functions of unitation

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 2007

An approach to compare fundamental heuristics and to find out for which problems they behave in such a similar way that results on one heuristic can be transferred to the other one and to describe problems where they behave quite differently. Expand

Black-Box Search by Unbiased Variation

- Computer Science, Mathematics
- GECCO '10
- 2010

This paper introduces a more restricted black-box model for optimisation of pseudo-Boolean functions which it is claimed captures the working principles of many randomised search heuristics including simulated annealing, evolutionary algorithms, randomised local search, and others. Expand

A New Framework for the Valuation of Algorithms for Black-Box Optimization

- Mathematics, Computer Science
- FOGA
- 2002

It can be concluded that randomized search heuristics whose (worst-case) expected optimization time for some problem is close to the black-box complexity of the problem are provably efficient (in theblack-box scenario). Expand

Black-box complexities of combinatorial problems

- Computer Science
- GECCO '11
- 2011

This work reveals that the choice of how to model the optimization problem is non-trivial here and comes true where the search space does not consist of bit strings and where a reasonable definition of unbiasedness has to be agreed on. Expand