On the analysis of the \((1+1)\) evolutionary algorithm
From MaRDI portal
Publication:1605304
DOI10.1016/S0304-3975(01)00182-7zbMath1002.68037MaRDI QIDQ1605304
Stefan Droste, Thomas Jansen, Ingo Wegener
Publication date: 15 July 2002
Published in: Theoretical Computer Science (Search for Journal in Brave)
Searching and sorting (68P10) Nonnumerical algorithms (68W05) Learning and adaptive systems in artificial intelligence (68T05)
Related Items (only showing first 100 items - show all)
Tail bounds on hitting times of randomized search heuristics using variable drift analysis ⋮ Variable solution structure can be helpful in evolutionary optimization ⋮ On the analysis of the (1+1) evolutionary algorithm for the maximum leaf spanning tree problem ⋮ Black-Box Complexity for Bounding the Performance of Randomized Search Heuristics ⋮ Transition functions for evolutionary algorithms on continuous state-space ⋮ Asymptotic Hitting Time for a Simple Evolutionary Model of Protein Folding ⋮ On black-box optimization in divide-and-conquer SAT solving ⋮ Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial ⋮ 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 ⋮ On the impact of the performance metric on efficient algorithm configuration ⋮ When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not ⋮ Evolutionary algorithms and submodular functions: benefits of heavy-tailed mutations ⋮ First Steps Towards a Runtime Analysis of Neuroevolution ⋮ Self-adaptation Can Improve the Noise-tolerance of Evolutionary Algorithms ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ Exact Markov chain-based runtime analysis of a discrete particle swarm optimization algorithm on sorting and OneMax ⋮ Choosing the right algorithm with hints from complexity theory ⋮ Lower bounds from fitness levels made easy ⋮ Lazy parameter tuning and control: choosing all parameters randomly from a power-law distribution ⋮ An extended jump functions benchmark for the analysis of randomized search heuristics ⋮ Runtime analysis for permutation-based evolutionary algorithms ⋮ Do additional target points speed up evolutionary algorithms? ⋮ How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys ⋮ A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation ⋮ Optimal parameters for search using a barrier tree Markov model ⋮ Finding large cliques in sparse semi-random graphs by simple randomized search heuristics ⋮ On the analysis of a dynamic evolutionary algorithm ⋮ Tight Bounds on the Optimization Time of a Randomized Search Heuristic on Linear Functions ⋮ First steps to the runtime complexity analysis of ant colony optimization ⋮ Expected runtimes of evolutionary algorithms for the Eulerian cycle problem ⋮ Evolutionary algorithms for continuous-space optimisation ⋮ Analysis of a multiobjective evolutionary algorithm on the 0-1 knapsack problem ⋮ How the (1+1) ES using isotropic mutations minimizes positive definite quadratic forms ⋮ Recent advances in evolutionary computation ⋮ Estimation-of-distribution algorithms for multi-valued decision variables ⋮ Fourier analysis meets runtime analysis: precise runtimes on plateaus ⋮ Stagnation detection in highly multimodal fitness landscapes ⋮ Population size versus runtime of a simple evolutionary algorithm ⋮ Runtime analysis of quality diversity algorithms ⋮ Stagnation detection meets fast mutation ⋮ Using Merging Variables-Based Local Search to Solve Special Variants of MaxSAT Problem ⋮ Merging Variables: One Technique of Search in Pseudo-Boolean Optimization ⋮ Stagnation detection meets fast mutation ⋮ On the Evolution of Monotone Conjunctions: Drilling for Best Approximations ⋮ Theoretical Analysis of Local Search in Software Testing ⋮ Estimation of distribution algorithms on non-separable problems ⋮ An efficient, adaptive parameter variation scheme for metaheuristics based on the epsilon-constraint method ⋮ The one-dimensional Ising model: mutation versus recombination ⋮ Erratum to: ``Drift analysis and average time complexity of evolutionary algorithms ⋮ Time complexity analysis of evolutionary algorithms on random satisfiable \(k\)-CNF formulas ⋮ Populations can be essential in tracking dynamic optima ⋮ On easiest functions for mutation operators in bio-inspired optimisation ⋮ A comparative performance analysis of evolutionary algorithms on \(k\)-median and facility location problems ⋮ A comparative runtime analysis of heuristic algorithms for satisfiability problems ⋮ Algorithmic analysis of a basic evolutionary algorithm for continuous optimization ⋮ A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions ⋮ Does comma selection help to cope with local optima? ⋮ Self-adjusting evolutionary algorithms for multimodal optimization ⋮ Plateaus can be harder in multi-objective optimization ⋮ Choosing selection pressure for wide-gap problems ⋮ Evolutionary algorithms and matroid optimization problems ⋮ Linear multi-objective drift analysis ⋮ The effect of multiple optima on the simple GA run-time complexity ⋮ A new approach to estimating the expected first hitting time of evolutionary algorithms ⋮ A rigorous analysis of the compact genetic algorithm for linear functions ⋮ Minimum spanning trees made easier via multi-objective optimization ⋮ Novelty-driven binary particle swarm optimisation for truss optimisation problems ⋮ Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem ⋮ Randomized local search, evolutionary algorithms, and the minimum spanning tree problem ⋮ Stochastic runtime analysis of a cross-entropy algorithm for traveling salesman problems ⋮ The analysis of expected fitness and success ratio of two heuristic optimizations on two bimodal MaxSat problems ⋮ Analysis of the \((1 + 1)\) EA on subclasses of linear functions under uniform and linear constraints ⋮ When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms ⋮ Analyzing randomized search heuristics via stochastic domination ⋮ Analysis of runtime of optimization algorithms for noisy functions over discrete codomains ⋮ Design and analysis of migration in parallel evolutionary algorithms ⋮ Practical performance models of algorithms in evolutionary program induction and other domains ⋮ Adaptive drift analysis ⋮ Crossover can be constructive when computing unique input-output sequences ⋮ Analyzing different variants of immune inspired somatic contiguous hypermutations ⋮ On benefits and drawbacks of aging strategies for randomized search heuristics ⋮ Analysis of an iterated local search algorithm for vertex cover in sparse random graphs ⋮ Runtime analysis of the \((1+1)\) EA on computing unique input output sequences ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Multiplicative drift analysis ⋮ Black-box search by unbiased variation ⋮ A large population size can be unhelpful in evolutionary algorithms ⋮ Non-existence of linear universal drift functions ⋮ The use of tail inequalities on the probable computational time of randomized search heuristics ⋮ Illustration of fairness in evolutionary multi-objective optimization ⋮ Free lunches on the discrete Lipschitz class ⋮ Runtime analysis of the 1-ANT ant colony optimizer ⋮ Computing minimum cuts by randomized search heuristics ⋮ Hybridizing evolutionary algorithms with variable-depth search to overcome local optima ⋮ Combining Markov-chain analysis and drift analysis. The \((1+1)\) evolutionary algorithm on linear functions reloaded ⋮ Convergence of multi-objective evolutionary algorithms to a uniformly distributed representation of the Pareto front ⋮ Evolutionary algorithms for quantum computers ⋮ Exponential upper bounds for the runtime of randomized search heuristics
Cites Work
This page was built for publication: On the analysis of the \((1+1)\) evolutionary algorithm
