From black-box complexity to designing new genetic algorithms
From MaRDI portal
Publication:487994
DOI10.1016/j.tcs.2014.11.028zbMath1314.68290OpenAlexW1971237725MaRDI QIDQ487994
Franziska Ebel, Benjamin Doerr, Carola 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
genetic algorithmsheuristic searchruntime analysistheory of randomized search heuristicsblack-box complexity
Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
\textsc{OneMax} in black-box models with several restrictions ⋮ On easiest functions for mutation operators in bio-inspired optimisation ⋮ A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions ⋮ Fast mutation in crossover-based algorithms ⋮ Fixed-target runtime analysis ⋮ The “One-fifth Rule” with Rollbacks for Self-Adjustment of the Population Size in the (1 + (λ,λ)) Genetic Algorithm ⋮ A tight runtime analysis for the \((\mu + \lambda)\) EA ⋮ Fixed-parameter tractability of crossover: steady-state GAs on the closest string problem ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Self-adjusting population sizes for the (1,\( \lambda )\)-EA on monotone functions ⋮ OneMax is not the easiest function for fitness improvements ⋮ The cost of randomness in evolutionary algorithms: crossover can save random bits ⋮ Choosing the right algorithm with hints from complexity theory ⋮ 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 ⋮ Using Automated Algorithm Configuration for Parameter Control ⋮ Memetic algorithms outperform evolutionary algorithms in multimodal optimisation ⋮ Exponential upper bounds for the runtime of randomized search heuristics ⋮ The \((1+\lambda)\) evolutionary algorithm with self-adjusting mutation rate ⋮ Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints ⋮ The runtime of the compact genetic algorithm on jump 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 ⋮ Correction to: ``Reoptimization time analysis of evolutionary algorithms on linear functions under dynamic uniform constraints ⋮ Optimal parameter choices via precise black-box analysis ⋮ Working principles of binary differential evolution ⋮ An Experimental Study of Operator Choices in the $$(1+(\lambda ,\lambda ))$$ Genetic Algorithm ⋮ Artificial immune systems can find arbitrarily good approximations for the NP-hard number partitioning problem
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ranking-based black-box complexity
- On the analysis of the \((1+1)\) evolutionary algorithm
- Black-box complexities of combinatorial problems
- Black-box search by unbiased variation
- Reducing the arity in unbiased black-box complexity
- Playing mastermind with constant-size memory
- Upper and lower bounds for randomized search heuristics in black-box optimization
- The Query Complexity of Finding a Hidden Permutation
- Linear Convergence of Comparison-based Step-size Adaptive Randomized Search via Stability of Markov Chains
- 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
- Black-box search by elimination of fitness functions
- Faster black-box algorithms through higher arity operators
- Adaptive population models for offspring populations and parallel evolutionary algorithms
- Foundations of Genetic Algorithms
- Introduction to evolutionary computing
