Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T00:52:36.779Z Has data issue: false hasContentIssue false

A Markov Chain Analysis of Genetic Algorithms: Large Deviation Principle Approach

Published online by Cambridge University Press:  14 July 2016

Joe Suzuki*
Affiliation:
Osaka University
*
∗ Postal address: Department of Mathematics, Osaka University, Toyonaka, Osaka 560-0043, Japan. Email address: suzuki@math.sci.osaka-u.ac.jp
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In this paper we prove that the stationary distribution of populations in genetic algorithms focuses on the uniform population with the highest fitness value as the selective pressure goes to ∞ and the mutation probability goes to 0. The obtained sufficient condition is based on the work of Albuquerque and Mazza (2000), who, following Cerf (1998), applied the large deviation principle approach (Freidlin-Wentzell theory) to the Markov chain of genetic algorithms. The sufficient condition is more general than that of Albuquerque and Mazza, and covers a set of parameters which were not found by Cerf.

Information

Type
Research Article
Copyright
Copyright © Applied Probability Trust 2010