Towards a runtime comparison of natural and artificial evolution

DOI10.1007/S00453-016-0212-1MaRDI QIDQ2362364zbMATH OpenOpenAlexWikidataFDO

Authors Tiago Paixão, Jorge Pérez Heredia, Dirk Sudholt, Barbora Trubenová

Publication date 7 July 2017

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1504.06260

zbMATH Keywords

population geneticsevolutionary algorithmstheoryruntime analysisstrong selection weak mutation regimenatural evolution

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Problems related to evolution (92D15) Analysis of algorithms (68W40)

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

• On the analysis of a dynamic evolutionary algorithm
• Comparing evolutionary algorithms to the (\(1+1\))-EA
• On the analysis of the \((1+1)\) evolutionary algorithm
• Runtime analysis for self-adaptive mutation rates
• On the Brittleness of Evolutionary Algorithms

Cites work

• scientific article; zbMATH DE number 5686753 (Why is no real title available?)
• 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
• 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
• STACS 2005
• Simplified drift analysis for proving lower bounds in evolutionary computation
• 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

(17)

• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial
• 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
• Population size versus runtime of a simple evolutionary algorithm
• Memetic algorithms outperform evolutionary algorithms in multimodal optimisation
• Towards a runtime comparison of natural and artificial evolution
• Exponential upper bounds for the runtime of randomized search heuristics
• Does comma selection help to cope with local optima?
• Choosing the right algorithm with hints from complexity theory
• scientific article; zbMATH DE number 1696516 (Why is no real title available?)
• 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
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
• Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
• Do additional target points speed up evolutionary algorithms?
• Comparing evolutionary algorithms to the (\(1+1\))-EA

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)