Groupe d’études et de recherche en analyse des décisions


Bounds for Probability of Success of Classical Genetic Algorithm based on Hamming Distance


Genetic algorithm has proven itself to be a fairly good optimization algorithm. Despite its many successful applications, there is a lack of theoretical understanding of why it works. In this paper, Vose-Liepins' so called "infinite population model" is used to derive a lower and upper bound for the probability of success of the genetic algorithm in finding the global optimal solution within a prescribed number of generations. The approach is to aggregate the Markov chain into subsets of decreasing Hamming distances. Our bounds take into account some general fitness function landscapes. The model is then extended to Nix-Vose's fully realistic "finite population model". Finally, a lower and upper bound expression is reported based on the first passage theory of the Markov chain for the probability of success of the model.

, 26 pages

Ce cahier a été révisé en janvier 2004