Towards a runtime comparison of natural and artificial evolution

DOI10.1007/S00453-016-0212-1zbMATH Open1366.68270arXiv1504.06260OpenAlexW2521372821WikidataQ59607240 ScholiaQ59607240MaRDI QIDQ2362364FDOQ2362364

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)

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.

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

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

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)

Cites Work

• Mathematical population genetics. I: Theoretical introduction.
• Black-box search by unbiased variation
• Title not available (Why is that?)
• STACS 2005
• Analyzing randomized search heuristics: tools from probability theory
• Algorithms, games, and evolution
• A simple ant colony optimizer for stochastic shortest path problems
• On the runtime analysis of the simple genetic algorithm
• The choice of the offspring population size in the \((1,\lambda)\) evolutionary algorithm
• Bioinspired computation in combinatorial optimization. Algorithms and their computational complexity
• Analyzing evolutionary algorithms. The computer science perspective.
• Simplified drift analysis for proving lower bounds in evolutionary computation
• The analysis of evolutionary algorithms on sorting and shortest paths problems
• Expected runtimes of evolutionary algorithms for the Eulerian cycle problem
• Runtime analysis of a simple ant colony optimization algorithm
• Randomized local search, evolutionary algorithms, and the minimum spanning tree problem
• Evolvability
• Population size versus runtime of a simple evolutionary algorithm
• Evolutionary algorithms and matroid optimization problems
• A comparison of simulated annealing with a simple evolutionary algorithm on pseudo-Boolean functions of unitation
• Toward a unifying framework for evolutionary processes
• Introduction to evolutionary computing
• The fastest evolutionary trajectory
• Towards a runtime comparison of natural and artificial evolution

Cited In (17)

• 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
• 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
• Title not available (Why is that?)
• When move acceptance selection hyper-heuristics outperform metropolis and elitist evolutionary algorithms and when not
• Self-adjusting offspring population sizes outperform fixed parameters on the Cliff function
• When hypermutations and ageing enable artificial immune systems to outperform evolutionary algorithms
• Do additional target points speed up evolutionary algorithms?
• Comparing evolutionary algorithms to the (\(1+1\))-EA
• Analysing the robustness of evolutionary algorithms to noise: refined runtime bounds and an example where noise is beneficial

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)