Error thresholds in genetic algorithms

Citation

Ochoa G (2006) Error thresholds in genetic algorithms. Evolutionary Computation, 14 (2), pp. 157-182. https://doi.org/10.1162/evco.2006.14.2.157

Abstract
The error threshold of replication is an important notion in the quasispecies evolution model; it is a critical mutation rate (error rate) beyond which structures obtained by an evolutionary process are destroyed more frequently than selection can reproduce them. With mutation rates above this critical value, an error catastrophe occurs and the genomic information is irretrievably lost. Therefore, studying the factors that alter this magnitude has important implications in the study of evolution. Here we use a genetic algorithm, instead of the quasispecies model, as the underlying model of evolution, and explore whether the phenomenon of error thresholds is found on finite populations of bit strings evolving on complex landscapes. Our empirical results verify the occurrence of error thresholds in genetic algorithms. In this way, this notion is brought from molecular evolution to evolutionary computation. We also study the effect of modifying the most prominent evolutionary parameters on the magnitude of this critical value, and found that error thresholds depend mainly on the selection pressure and genotype length.

Keywords
genetic algorithms; error thresholds; quasispecies model; optimal mutation rates; evolutionary parameters; NK landscapes; Royal Staircase functions; multiple knapsack problems

Journal
Evolutionary Computation: Volume 14, Issue 2

People

Professor Gabriela Ochoa

Professor, Computing Science