Convergence Properties of Genetic Algorithms in a Wide Variety of Noisy Environments

摘要

Random noise perturbs objective functions in practical optimization problems, and genetic algorithms (GAs) have been proposed as an effective optimization tool for dealing with noisy objective functions. In this paper, we investigate GAs in a variety of noisy environments where fitness perturbation can occur in any form-for example, fitness evaluations can be concurrently disturbed by additive and multiplicative noise. We reveal the convergence properties of GAs by constructing and analyzing a Markov chain that explicitly models the evolution of the algorithms in noisy environments. We compute the one-step transition probabilities of the Markov chain and show that the chain has only one positive recurrent communication class, which is also aperiodic. Based on this property, we establish a condition that is both necessary and sufficient for GAs to eventually (i.e., as the number of iterations goes to infinity) find a globally optimal solution with probability 1. We also identify a condition that is both necessary and sufficient for GAs to eventually with probability 1 fail to find any globally optimal solution. Furthermore, in all the noisy environments, our analysis shows that the chain has a stationary distribution that is also its steady-state distribution. Based on this property and the transition probabilities of the chain, we examine the number of iterations sufficient to ensure with at least a specified probability that GAs select a globally optimal solution upon termination.