Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
From MaRDI portal
Publication:4911174
DOI10.1017/S0963548312000600zbMath1258.68183DBLPjournals/cpc/Witt13arXiv1108.4386OpenAlexW2102044362WikidataQ57200604 ScholiaQ57200604MaRDI QIDQ4911174
Publication date: 14 March 2013
Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.4386
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items (43)
The interplay of population size and mutation probability in the \((1+\lambda )\) EA on OneMax ⋮ On easiest functions for mutation operators in bio-inspired optimisation ⋮ Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems ⋮ The impact of random initialization on the runtime of randomized search heuristics ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions ⋮ Tight bounds on the expected runtime of a standard steady state genetic algorithm ⋮ Does comma selection help to cope with local optima? ⋮ Self-adjusting evolutionary algorithms for multimodal optimization ⋮ Fast mutation in crossover-based algorithms ⋮ Fixed-target runtime analysis ⋮ Runtime analysis for self-adaptive mutation rates ⋮ A tight runtime analysis for the \((\mu + \lambda)\) EA ⋮ Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ Lower bounds on the run time of the univariate marginal distribution algorithm on OneMax ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ OneMax is not the easiest function for fitness improvements ⋮ Two-dimensional drift analysis: optimizing two functions simultaneously can be hard ⋮ Lower bounds from fitness levels made easy ⋮ Self-adjusting population sizes for non-elitist evolutionary algorithms: why success rates matter ⋮ An extended jump functions benchmark for the analysis of randomized search heuristics ⋮ On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Upper bounds on the running time of the univariate marginal distribution algorithm on OneMax ⋮ Solving problems with unknown solution length at almost no extra cost ⋮ Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints ⋮ Island models meet rumor spreading ⋮ Drift analysis of ant colony optimization of stochastic linear pseudo-Boolean functions ⋮ Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances ⋮ From black-box complexity to designing new genetic algorithms ⋮ On the choice of the update strength in estimation-of-distribution algorithms and ant colony optimization ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ Improved runtime results for simple randomised search heuristics on linear functions with a uniform constraint ⋮ Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm ⋮ Optimal mutation rates for the \((1+\lambda)\) EA on OneMax through asymptotically tight drift analysis ⋮ Static and self-adjusting mutation strengths for multi-valued decision variables ⋮ The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm ⋮ Running time analysis of the (1+1)-EA for robust linear optimization ⋮ Optimal parameter choices via precise black-box analysis ⋮ Working principles of binary differential evolution ⋮ The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time ⋮ The linear hidden subset problem for the \((1 + 1)\) EA with scheduled and adaptive mutation rates
Cites Work
- Unnamed Item
- Unnamed Item
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
- On the analysis of the \((1+1)\) evolutionary algorithm
- A study of drift analysis for estimating computation time of evolutionary algorithms
- On the analysis of a simple evolutionary algorithm on quadratic pseudo-Boolean functions
- Black-box search by unbiased variation
- Algorithmic analysis of a basic evolutionary algorithm for continuous optimization
- On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
- Inequalities: theory of majorization and its applications
- Drift analysis and average time complexity of evolutionary algorithms
This page was built for publication: Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
