Anzeige
Erschienen in:
2008 | OriginalPaper | Buchkapitel
Markov Chain Analysis of Genetic Algorithms Applied to Fitness Functions Perturbed by Multiple Sources of Additive Noise
verfasst von : Takéhiko Nakama
Erschienen in: Software Engineering, Artificial Intelligence, Networking and Parallel/Distributed Computing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We investigate the convergence properties of genetic algorithms (GAs) applied to fitness functions perturbed by multiple sources of additive noise that each take on finitely many values. Our analysis of GAs in noisy environments employs a novel approach; we explicitly construct a Markov chain that models such GAs and analyze it to uncover the convergence properties of the algorithms. We show that the chain has only one positive recurrent communication class. This immediately implies that the GAs eventually (i.e., as the number of iterations goes to infinity) find at least one globally optimal solution with probability 1. Furthermore, our analysis shows that the chain has a stationary distribution that is also its steady-state distribution. Using 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.