Choosing the right algorithm with hints from complexity theory
From MaRDI portal
Publication:6178456
DOI10.1016/j.ic.2023.105125arXiv2109.06584OpenAlexW4286977063MaRDI QIDQ6178456
Weijie Zheng, Unnamed Author, Benjamin Doerr
Publication date: 18 January 2024
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2109.06584
Metropolis algorithmcomplexity theoryruntime analysisblack-box optimizationestimation-of-distribution algorithm
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Runtime analysis of non-elitist populations: from classical optimisation to partial information
- From black-box complexity to designing new genetic algorithms
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Analyzing evolutionary algorithms. The computer science perspective.
- Runtime analysis of the 1-ANT ant colony optimizer
- Improved time complexity analysis of the simple genetic algorithm
- The Metropolis algorithm for graph bisection
- On the analysis of the \((1+1)\) evolutionary algorithm
- The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
- Level-based analysis of the univariate marginal distribution algorithm
- On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization
- The query complexity of a permutation-based variant of mastermind
- The \((1+1)\) elitist black-box complexity of LeadingOnes
- How to escape local optima in black box optimisation: when non-elitism outperforms elitism
- Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
- A study of drift analysis for estimating computation time of evolutionary algorithms
- Black-box complexities of combinatorial problems
- Black-box search by unbiased variation
- Optimal parameter choices via precise black-box analysis
- A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
- Does comma selection help to cope with local optima?
- Self-adjusting evolutionary algorithms for multimodal optimization
- Fast mutation in crossover-based algorithms
- When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
- Multiplicative up-drift
- The runtime of the compact genetic algorithm on jump functions
- Runtime analyses of the population-based univariate estimation of distribution algorithms on LeadingOnes
- The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
- Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas
- Towards a runtime comparison of natural and artificial evolution
- Simulated annealing versus Metropolis for a TSP instance
- Analyzing randomized search heuristics via stochastic domination
- Upper and lower bounds for randomized search heuristics in black-box optimization
- A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
- Runtime analysis for self-adaptive mutation rates
- A tight runtime analysis for the \((\mu + \lambda)\) EA
- When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
- Drift Analysis and Evolutionary Algorithms Revisited
- The time complexity of maximum matching by simulated annealing
- Automatic adaptation of hypermutation rates for multimodal optimisation
- The benefits and limitations of voting mechanisms in evolutionary optimisation
- On the limitations of the univariate marginal distribution algorithm to deception and where bivariate EDAs might help
- A tight runtime analysis for the (1 + (λ, λ)) GA on leadingones
- Equation of State Calculations by Fast Computing Machines
- Evolutionary Learning: Advances in Theories and Algorithms
- Metaheuristics—the metaphor exposed
- Black-box search by elimination of fitness functions
- Faster black-box algorithms through higher arity operators
- Probability Inequalities for Sums of Bounded Random Variables
- Automata, Languages and Programming
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
- Stagnation detection meets fast mutation
