Multiplicative drift analysis
From MaRDI portal
Publication:1945169
DOI10.1007/s00453-012-9622-xzbMath1264.68220arXiv1101.0776MaRDI 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
68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
68W20: Randomized algorithms
Related Items
Variable solution structure can be helpful in evolutionary optimization, Global Linear Convergence of Evolution Strategies on More than Smooth Strongly Convex Functions, Unnamed Item, Tail bounds on hitting times of randomized search heuristics using variable drift analysis, 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, 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, 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, Simulated annealing is a polynomial-time approximation scheme for the minimum spanning tree problem, 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, Optimizing linear functions with the \((1 + \lambda)\) evolutionary algorithm -- different asymptotic runtimes for different instances, Linear multi-objective 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, 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, Adaptive drift analysis, Multiplicative drift analysis, 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, On some variants of the merging variables based \((1+1)\)-evolutionary algorithm with application to MaxSAT problem, Fixed-target runtime analysis, Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints, 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, The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm, Reducing the arity in unbiased black-box complexity, First-hitting times under drift, 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, On the benefits and risks of using fitness sharing for multimodal optimisation, Analyzing randomized search heuristics via stochastic domination, 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, Focused jump-and-repair constraint handling for fixed-parameter tractable graph problems closed under induced subgraphs, Concentrated Hitting Times of Randomized Search Heuristics with Variable Drift, Drift Analysis and Evolutionary Algorithms Revisited
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
