Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Currently most of the analysis about the running mechanism of GA focuses on the convergence problem while few focus on population characteristics after the single generation descendiblity. This paper presents the concept of evolution ability of population and discusses the ability of finding the optimal solution for the population after one-generation selection, crossover and mutation. Based on the analysis of effect of crossover on evolution ability of population, this paper presents some important conclusions. The important method to improve evolution ability of population is to include larger crossover optimal solution area in a smaller crossover family area. If the crossover optimal solution area isn't included in any crossover family area of population, the population either converges to the optimal solution, or evolution will be trapped in the premature of convergence. These conclusions above do not only help improve the GA, but also provide the basis for later research work.

REFERENCES

• 1: John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992
• 2: Li M Q, Kou J S, Lin D. Genetic algorithm theory and applications. Beijing: Science Press, 2002
• 3: Zhang W X, Liang Y. Mathematical foundation of genetic algorithms. Xi'an: Xi'an Jiaotong University Press, 2006
• 4: David E. Goldberg , Philip Segrest, Finite Markov chain analysis of genetic algorithms, Proceedings of the Second International Conference on Genetic Algorithms on Genetic algorithms and their application, p.1-8, October 1987, Cambridge, Massachusetts, United States
• 5: Rudolph G. Convergence properties of canonical genetic algorithms. IEEE Trans on Neural Networks, 1994, 5(1): 96 101
• 6: Cerf R. Asymptotic convergence of genetic algorithms. Adv Appl Prob, 1998, 30:521--550
• 7: Fogel D. B. Asymptotic convergence properties of genetic algorithms and evolutionary programming. Analysis and experiments, Cybernetics and Systems, 1994, 25(2): 389--407
• 8: Suzuki J. A Markov chain analysis on simple genetic algorithms. IEEE Transactions on Systems, Man, and Cybernetics, 1995, 25(4):650--659
• 9: Suzuki J. A further result on the Markov chain model of genetic algorithms and its application to simulated annealing-like-strategy. IEEE Trans Sys, Man, and Cybernetics, 1998, 28(1)
• 10: Xu Z.B., Chen Z.P. Theoretical development on genetic algorithms: a review. Advances in Mathematics, 2000, 29(2):97--114
• 11: Xu Z B, Nie Z K, Zhang W X. Almost sure convergence of genetic algorithms: A martingale approach. Chinese Journal of Computers, 2002,25(8): 785--793
• 12: XU Zong ben, NIE Zan kan, ZHANG Wei xiu. Further Results on Convergence Analysis of Genetic Algorithms Based on axiomatation Model. Chinese Journal of Engineering Mathematics, 2001, 18(1): 1--11

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Unconstrained optimization

General Terms:
Algorithms, Performance, Reliability, Theory, Verification

Keywords:
crossover operators, evolution ability of population, genetic algorithm