Towards a runtime comparison of natural and artificial evolution
From MaRDI portal
Abstract: Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed a rigorous analytical theory to analyse their runtime on many illustrative problems. Here we apply this theory to a simple model of natural evolution. In the Strong Selection Weak Mutation (SSWM) evolutionary regime the time between occurrence of new mutations is much longer than the time it takes for a new beneficial mutation to take over the population. In this situation, the population only contains copies of one genotype and evolution can be modelled as a (1+1)-type process where the probability of accepting a new genotype (improvements or worsenings) depends on the change in fitness. We present an initial runtime analysis of SSWM, quantifying its performance for various parameters and investigating differences to the (1+1)EA. We show that SSWM can have a moderate advantage over the (1+1)EA at crossing fitness valleys and study an example where SSWM outperforms the (1+1)EA by taking advantage of information on the fitness gradient.
Recommendations
Cites work
- A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
- A simple ant colony optimizer for stochastic shortest path problems
- Algorithms, games, and evolution
- Analyzing evolutionary algorithms. The computer science perspective.
- Analyzing randomized search heuristics: tools from probability theory
- Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
- Black-box search by unbiased variation
- Evolutionary algorithms and matroid optimization problems
- Evolvability
- Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
- scientific article; zbMATH DE number 5686753 (Why is no real title available?)
- Introduction to evolutionary computing
- Mathematical population genetics. I: Theoretical introduction.
- On the runtime analysis of the simple genetic algorithm
- Population size versus runtime of a simple evolutionary algorithm
- Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
- Runtime analysis of a simple ant colony optimization algorithm
- Simplified drift analysis for proving lower bounds in evolutionary computation
- STACS 2005
- The analysis of evolutionary algorithms on sorting and shortest paths problems
- The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
- The fastest evolutionary trajectory
- Toward a unifying framework for evolutionary processes
- Towards a runtime comparison of natural and artificial evolution
Cited in
(18)- On the analysis of trajectory-based search algorithms: when is it beneficial to reject improvements?
- How to escape local optima in black box optimisation: when non-elitism outperforms elitism
- Does comma selection help to cope with local optima?
- When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
- Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
- Exponential upper bounds for the runtime of randomized search heuristics
- Towards a runtime comparison of natural and artificial evolution
- Comparing evolutionary algorithms to the (\(1+1\))-EA
- Population size versus runtime of a simple evolutionary algorithm
- Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial
- When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
- Do additional target points speed up evolutionary algorithms?
- scientific article; zbMATH DE number 1696516 (Why is no real title available?)
- Choosing the right algorithm with hints from complexity theory
- 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
- Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
- Comma selection outperforms plus selection on OneMax with randomly planted optima
This page was built for publication: Towards a runtime comparison of natural and artificial evolution
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2362364)
