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.
Paru en mars 2003 , 26 pages
Ce cahier a été révisé en janvier 2004