Transition and convergence properties of genetic algorithms applied to fitness functions perturbed concurrently by additive and multiplicative noise
Takéhiko Nakama · 2009
We investigate the properties of genetic algorithms (GAs) applied to fitness functions perturbed concurrently by additive noise and multiplicative noise that each take on finitely many values. First we explicitly construct a Markov chain that models GAs in this noisy environment. By analyzing this chain, we establish a condition that is both necessary and sufficient for GAs to eventually find a globally optimal solution with probability 1. Furthermore, we identify a condition that is both necessary and sufficient for GAs to eventually with probability 1 fail to find any globally optimal solution. Interestingly, both of these conditions are completely determined by the fitness function and multiplicative noise, and they are unaffected by the additive noise. Our analysis also shows that the chain converges to stationarity. Based on this property and the transition probabilities of the chain, we derive an upper bound for the number of iterations sufficient to ensure with certain probability that a GA selects a globally optimal solution upon termination.