Analyzing randomized search heuristics via stochastic domination

DOI10.1016/j.tcs.2018.09.024zbMath1451.68363arXiv1801.04487OpenAlexW2783263582WikidataQ129020376 ScholiaQ129020376MaRDI QIDQ2415323

Benjamin Doerr

Publication date: 21 May 2019

Published in: Theoretical Computer Science, Evolutionary Computation in Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.04487

zbMATH Keywords

evolutionary algorithmsruntime analysis

Mathematics Subject Classification ID

Inequalities; stochastic orderings (60E15) Analysis of algorithms (68W40) Evolutionary algorithms, genetic algorithms (computational aspects) (68W50) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Randomized algorithms (68W20)

Related Items (21)

Does comma selection help to cope with local optima? ⋮ Fixed-target runtime analysis ⋮ Runtime analysis for self-adaptive mutation rates ⋮ A tight runtime analysis for the \((\mu + \lambda)\) EA ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II) ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ Choosing the right algorithm with hints from complexity theory ⋮ Lower bounds from fitness levels made easy ⋮ An extended jump functions benchmark for the analysis of randomized search heuristics ⋮ Using Automated Algorithm Configuration for Parameter Control ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ Solving problems with unknown solution length at almost no extra cost ⋮ Multiplicative up-drift ⋮ The runtime of the compact genetic algorithm on jump functions ⋮ Self-adjusting mutation rates with provably optimal success rules ⋮ Optimal parameter choices via precise black-box analysis ⋮ Working principles of binary differential evolution ⋮ Merging Variables: One Technique of Search in Pseudo-Boolean Optimization ⋮ The univariate marginal distribution algorithm copes well with deception and epistasis ⋮ On some variants of the merging variables based \((1+1)\)-evolutionary algorithm with application to MaxSAT problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Runtime analysis of non-elitist populations: from classical optimisation to partial information
• The impact of random initialization on the runtime of randomized search heuristics
• Approximation quality of the hypervolume indicator
• Crossover can provably be useful in evolutionary computation
• The use of tail inequalities on the probable computational time of randomized search heuristics
• 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 benefits and drawbacks of aging strategies for randomized search heuristics
• Evolutionary algorithms and dynamic programming
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Improved time complexity analysis of the simple genetic algorithm
• The impact of parametrization in memetic evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• Island models meet rumor spreading
• The \((1+1)\) elitist black-box complexity of LeadingOnes
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Black-box complexities of combinatorial problems
• Adaptive drift analysis
• A simple ant colony optimizer for stochastic shortest path problems
• Multiplicative drift analysis
• Black-box search by unbiased variation
• Optimal parameter choices via precise black-box analysis
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Fitness levels with tail bounds for the analysis of randomized search heuristics
• Analyzing randomized search heuristics via stochastic domination
• On the analysis of a dynamic evolutionary algorithm
• Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
• Comparing evolutionary algorithms to the (\(1+1\))-EA
• Population size versus runtime of a simple evolutionary algorithm
• Black-box Complexity of Parallel Search with Distributed Populations
• Fixed Budget Performance of the (1+1) EA on Linear Functions
• Probabilistic Analysis of Online Bin Coloring Algorithms Via Stochastic Comparison
• A limiting distribution for quicksort
• On the Optimization of Monotone Polynomials by Simple Randomized Search Heuristics
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• Tight Analysis of Randomized Rumor Spreading in Complete Graphs
• On the impact of the mutation-selection balance on the runtime of evolutionary algorithms
• Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding
• The Existence of Probability Measures with Given Marginals
• Lower Bounds on the Run Time of the Univariate Marginal Distribution Algorithm on OneMax
• Drift analysis and average time complexity of evolutionary algorithms

This page was built for publication: Analyzing randomized search heuristics via stochastic domination