Towards a Runtime Comparison of Natural and Artificial Evolution

摘要: Evolutionary algorithms (EAs) form a popular optimisation paradigm inspired by natural evolution. In recent years the field of evolutionary computation has developed rigorous analytical theory to analyse runtimes EAs on many illustrative problems. Here we apply this simple model Strong Selection Weak Mutation (SSWM) regime time between occurrences new mutations is much longer than it takes for mutated genotype take over population. situation, population only contains copies one and evolution can be modelled as stochastic process evolving means mutation selection resident genotype. The probability accepting then depends change in fitness. We study process, SSWM, from an algorithmic perspective, quantifying its expected various parameters investigating differences similar algorithm, well-known (1+1) EA. show that SSWM have moderate advantage EA at crossing fitness valleys example where outperforms taking information gradient.