From black-box complexity to designing new genetic algorithms

DOI10.1016/J.TCS.2014.11.028zbMATH Open1314.68290OpenAlexW1971237725MaRDI QIDQ487994FDOQ487994

Carola Doerr, Franziska Ebel, Benjamin Doerr

Publication date: 23 January 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.11.028

Recommendations

• Faster black-box algorithms through higher arity operators
• Optimal parameter choices via precise black-box analysis
• Black-box search by unbiased variation
• Black-box complexity: advantages of memory usage
• On the black-box complexity of example functions: the real jump function

zbMATH Keywords

genetic algorithmsheuristic searchruntime analysistheory of randomized search heuristicsblack-box complexity

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Analysis of algorithms and problem complexity (68Q25)

Cites Work

• Introduction to evolutionary computing
• Black-box search by unbiased variation
• Playing mastermind with constant-size memory
• Upper and lower bounds for randomized search heuristics in black-box optimization
• Ranking-based black-box complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions
• On the utility of the population size for inversely fitness proportional mutation rates
• Adaptive population models for offspring populations and parallel evolutionary algorithms
• On the analysis of the \((1+1)\) evolutionary algorithm
• Black-box complexities of combinatorial problems
• Reducing the arity in unbiased black-box complexity
• The Query Complexity of Finding a Hidden Permutation
• Faster black-box algorithms through higher arity operators
• Title not available (Why is that?)
• Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
• Black-box search by elimination of fitness functions
• Foundations of Genetic Algorithms

Cited In (33)

• An Experimental Study of Operator Choices in the $$(1+(\lambda ,\lambda ))$$ Genetic Algorithm
• A tight runtime analysis for the \((\mu + \lambda)\) EA
• The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate
• Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm
• Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation
• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• Optimal parameter choices via precise black-box analysis
• OneMax is not the easiest function for fitness improvements
• The cost of randomness in evolutionary algorithms: crossover can save random bits
• Working principles of binary differential evolution
• Static and self-adjusting mutation strengths for multi-valued decision variables
• \textsc{OneMax} in black-box models with several restrictions
• Exponential upper bounds for the runtime of randomized search heuristics
• A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions
• Fast mutation in crossover-based algorithms
• Fixed-target runtime analysis
• Choosing the right algorithm with hints from complexity theory
• Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions
• The runtime of the compact genetic algorithm on jump functions
• Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
• On easiest functions for mutation operators in bio-inspired optimisation
• Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution
• 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
• Stagnation detection in highly multimodal fitness landscapes
• Tight runtime bounds for static unary unbiased evolutionary algorithms on linear functions
• Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem
• Using Automated Algorithm Configuration for Parameter Control
• Correction to: ``Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints
• Analyzing randomized search heuristics via stochastic domination
• Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
• The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm
• Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints

This page was built for publication: From black-box complexity to designing new genetic algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q487994)