Crossover can provably be useful in evolutionary computation

DOI10.1016/j.tcs.2010.10.035zbMath1267.68210OpenAlexW2064545488MaRDI QIDQ418021

Benjamin Doerr, Edda Happ, Christian Klein

Publication date: 14 May 2012

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

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

zbMATH Keywords

evolutionary computationcrossovermutationall-pairs shortest path (APSP) problem

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)

Related Items (18)

A rigorous runtime analysis of the \((1 + (\lambda, \lambda))\) GA on jump functions ⋮ Tight bounds on the expected runtime of a standard steady state genetic algorithm ⋮ Evolutionary algorithms and matroid optimization problems ⋮ 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 ⋮ Crossover can be constructive when computing unique input-output sequences ⋮ A generic construction for crossovers of graph-like structures and its realization in the Eclipse Modeling Framework ⋮ (1+1) genetic programming with functionally complete instruction sets can evolve Boolean conjunctions and disjunctions with arbitrarily small error ⋮ An extended jump functions benchmark for the analysis of randomized search heuristics ⋮ A simple ant colony optimizer for stochastic shortest path problems ⋮ Fixed-parameter evolutionary algorithms and the vertex cover problem ⋮ On the benefits of populations for the exploitation speed of standard steady-state genetic algorithms ⋮ Memetic algorithms outperform evolutionary algorithms in multimodal optimisation ⋮ Lower bounds on the runtime of crossover-based algorithms via decoupling and family graphs ⋮ Optimal static and self-adjusting parameter choices for the \((1+(\lambda ,\lambda ))\) genetic algorithm ⋮ Reducing the arity in unbiased black-box complexity ⋮ Global versus local search: the impact of population sizes on evolutionary algorithm performance

Uses Software

• LEDA
• Algorithm 97

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Optimization by Simulated Annealing
• Real royal road functions for constant population size
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• The analysis of evolutionary algorithms -- A proof that crossover really can help
• Real royal road functions -- where crossover provably is essential
• Efficient Algorithms for Shortest Paths in Sparse Networks
• Techniques for bounding the convergence rate of genetic algorithms
• Equation of State Calculations by Fast Computing Machines
• Automata, Languages and Programming
• A Theorem on Boolean Matrices

This page was built for publication: Crossover can provably be useful in evolutionary computation