Almost sure convergence of genetic algorithms: A martingale approach

The most convergence analysis on genetic algorithms (GAs) is conducted currently in the sense of probabilistic convergence and based on ergodicity analysis on the GA Markovian chain. Such analysis can not infer in general that the GA would be convergent to a global optimum in a finite number of evolution steps, and it validates normally only for the GAs with the elitist record strategy. In the paper, a martingale analysis approach is proposed to study the almost sure convergence of GAs. It is shown that without using the elitist record strategy, a large class of GAs, including the elitist selection GAs, the global annealing GAs, the canonical GAs with time-varying power gauge transformation, can guaranteedly converge to a global optimum in a finite number of steps, provided the involved crossover rate {P_C(t)} and mutation rate {P_M(t)} satisfy certain delay conditions. The obtained results underlies application of the GAs, and the suggested martingale analysis approach provides a new methodology for convergence analysis of genetic algorithms.