Multistage non homogeneous Markov chain modeling of the non homogeneous genetic algorithm and convergence results.

Genetic algorithms (GAs), in the homogeneous as well as the non homogeneous version, have been widely used to solve combinatorial global optimization problems. Despite the successes that the non homogeneous GA (NHGA) encounters in practical applications, the theoretical results which guarantee the convergence of such algorithms are cited just in a few papers. There are, at least, three different ways of modeling GA as a Markov chain in order to study its convergence. In each approach, the transition matrices depend not only on the state space of the Markov chain but also on the way the genetic operators are defined. In this article, the extension to the non homogeneous case of the crossover operator which was based on neighborhoods is proposed, convergence results are presented, and numerical simulations in order to illustrate a comparative performance of the algorithms are developed. [ABSTRACT FROM PUBLISHER]