Bounds for probability of success of classical genetic algorithm based on hamming distance

• Published in: IEEE transactions on evolutionary computation 2006-02, Vol.10 (1), p.1-18
• Main Authors: Shiu Yin Yuen, Cheung, B.K.S.
• Format: Article
• Language: English
• Subjects: Agglomeration; Aggregates; Aggregation; Algorithm design and analysis; Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Computation; Computer science; control theory; systems; Convergence; convergence rate; evolutionary algorithms (EAs); Evolutionary computation; Exact sciences and technology; first passage probability; first passage time; Genetic algorithms; genetic algorithms (GAs); Genetic mutations; Hamming distance; Markov chain (MC); Mathematical analysis; Mathematical models; Numerical simulation; perfect lumping; probability of success; Proving; Studies; Theoretical computing; Upper bound; Upper bounds
• ISSN: 1089-778X; 1941-0026
• DOI: 10.1109/TEVC.2005.851401

Genetic algorithms have proven to be reasonably good optimization algorithms. Despite many successful applications, there is a lack of theoretical insight into why they work so well. In this paper, Vose-Liepins' so called "infinite population model" is used to derive a lower and upper bound for the expected probability of the global optimal solution under proportional selection and uniform crossover. Elitist selection is not assumed. The approach is to aggregate the Markov chain (MC) into subsets of decreasing Hamming distances. The aggregation is based on a proof of equally likelihood in probability of elements in these subsets. The aggregation model is then extended to Nix-Vose's fully realistic "finite population model." This leads to a lower and upper bound expression based on the first passage theory of the MC for the probability of success of the algorithm. The proof of equally likelihood is extended correspondingly to permutations of populations. Numerical simulations reveal that the bounds are useful for small perturbations of the fitness function for all problem sizes in the infinite population model. Due to the computational burden, however, the aggregated finite population model is still restricted to relatively small problem sizes. Finally, an approximate aggregated finite population model that does not require computation of the full mixing matrix is found to give excellent performance.