Adaptive drift analysis
From MaRDI portal
Publication:1939672
DOI10.1007/s00453-011-9585-3zbMath1277.68289arXiv1108.0295OpenAlexW3100597221MaRDI QIDQ1939672
Benjamin Doerr, Leslie Ann Goldberg
Publication date: 5 March 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.0295
Analysis of algorithms (68W40) Nonnumerical algorithms (68W05) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ The interplay of population size and mutation probability in the \((1+\lambda )\) EA on OneMax ⋮ A runtime analysis of parallel evolutionary algorithms in dynamic optimization ⋮ Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ Concentration of first hitting times under additive drift ⋮ Drift Analysis and Evolutionary Algorithms Revisited ⋮ Does comma selection help to cope with local optima? ⋮ Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions ⋮ 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 ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ Unnamed Item ⋮ Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise ⋮ 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 ⋮ Runtime analysis of the \((\mu + 1)\)-EA on the dynamic BinVal function ⋮ Multiplicative up-drift ⋮ Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs ⋮ 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 ⋮ Working principles of binary differential evolution ⋮ Destructiveness of lexicographic parsimony pressure and alleviation by a concatenation crossover in genetic programming ⋮ The impact of lexicographic parsimony pressure for ORDER/MAJORITY on the run time ⋮ First-hitting times under drift
Cites Work
- Non-existence of linear universal drift functions
- Simplified drift analysis for proving lower bounds in evolutionary computation
- Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
- On the analysis of the \((1+1)\) evolutionary algorithm
- Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms
- A study of drift analysis for estimating computation time of evolutionary algorithms
- Multiplicative drift analysis
- Hitting-time and occupation-time bounds implied by drift analysis with applications
- Computing single source shortest paths using single-objective fitness
- Drift analysis and average time complexity of evolutionary algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Adaptive drift analysis
