Multiplicative drift analysis
From MaRDI portal
Publication:1945169
DOI10.1007/s00453-012-9622-xzbMath1264.68220arXiv1101.0776OpenAlexW3122779104MaRDI QIDQ1945169
Benjamin Doerr, Daniel Johannsen, Carola Winzen
Publication date: 3 April 2013
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.0776
Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)
Related Items (60)
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 ⋮ Variable solution structure can be helpful in evolutionary optimization ⋮ Runtime analysis of non-elitist populations: from classical optimisation to partial information ⋮ Robustness of populations in stochastic environments ⋮ Concentration of first hitting times under additive drift ⋮ 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 ⋮ Fixed-target runtime analysis ⋮ Linear multi-objective drift analysis ⋮ Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions ⋮ Runtime performances of randomized search heuristics for the dynamic weighted vertex cover problem ⋮ Analysis of noisy evolutionary optimization when sampling fails ⋮ 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 ⋮ On the benefits and risks of using fitness sharing for multimodal optimisation ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions ⋮ Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations ⋮ First Steps Towards a Runtime Analysis of Neuroevolution ⋮ Adaptive drift analysis ⋮ OneMax is not the easiest function for fitness improvements ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ Unnamed Item ⋮ Two-dimensional drift analysis: optimizing two functions simultaneously can be hard ⋮ Lower bounds from fitness levels made easy ⋮ More precise runtime analyses of non-elitist evolutionary algorithms in uncertain environments ⋮ Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution ⋮ Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs ⋮ Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem ⋮ Multiplicative drift analysis ⋮ The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate ⋮ Solving problems with unknown solution length at almost no extra cost ⋮ Running time analysis of the \((1+1)\)-EA for OneMax and LeadingOnes under bit-wise noise ⋮ 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 ⋮ Runtime analysis of the \((\mu + 1)\)-EA on the dynamic BinVal function ⋮ Time complexity analysis of evolutionary algorithms for 2-hop \((1,2)\)-minimum spanning tree problem ⋮ Multiplicative up-drift ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ Self-adjusting mutation rates with provably optimal success rules ⋮ Time complexity analysis of randomized search heuristics for the dynamic graph coloring problem ⋮ 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 ⋮ Static and self-adjusting mutation strengths for multi-valued decision variables ⋮ The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm ⋮ Reducing the arity in unbiased black-box complexity ⋮ 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 ⋮ First-hitting times under drift ⋮ On some variants of the merging variables based \((1+1)\)-evolutionary algorithm with application to MaxSAT problem
Cites Work
- Unnamed Item
- Unnamed Item
- Simplified drift analysis for proving lower bounds in evolutionary computation
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
- Maximum of k-th maximal spanning trees of a weighted graph
- On the analysis of the \((1+1)\) evolutionary algorithm
- 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
This page was built for publication: Multiplicative drift analysis
