Error thresholds in genetic algorithms



Ochoa G (2006) Error thresholds in genetic algorithms. Evolutionary Computation, 14 (2), pp. 157-182.

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.

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

Evolutionary Computation: Volume 14, Issue 2

Publication date01/06/2006
PublisherMIT Press

People (1)


Professor Gabriela Ochoa

Professor Gabriela Ochoa

Professor, Computing Science