The Convergence Mechanism and Strategies for Non-Elitist Genetic Programming

Abstract:

Genetic programming is an evolutionary algorithm that proposed to solve the automatic computer program design problem by J.R.Koza in the 1990s. It has good universality and intelligence, and has been widely applied in the field of computer engineering. But genetic programming is essentially a stochastic optimization algorithm, lack theoretic basis on the convergence of algorithm, which limit the scope of its application in some extent. The convergence mechanism of non-elitist genetic programming was studied in this paper. A recursive estimation of the probability of population contains satisfactory solution with the evolution algebra was established by the analysis of operators characteristic parameters, then a sufficient condition of population converge in probability was derived from this estimation, and thereby some operational convergence strategies for many common evolution modes were provided.

• Periodical: Applied Mechanics and Materials (Volumes 347-350)
• Pages: 3850-3860
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.347-350.3850
• Online since: August 2013
• Authors: He Ni, Fan Ming Zeng, Bo Yu, Feng Rui Sun
• Keywords: Algorithmic Pause Time, Convergence Mechanism, Convergence Strategy, Non-Elitist Genetic Programming

References

[1] J.R. Koza. Genetic Programming: On the Programming of Computers by Means of Natural Selection [M]. Cambridge, MA: MIT press, (1994).

[2] J.R. Koza. Genetic Programming Ⅱ: Automatic Discovery of Reusable Programs [M]. Cambridge, MA: MIT press, (1992).

[3] J.R. Koza, M.A. Keane, M.J. Streeter, et al. Genetic programming Ⅳ: Routine human-Competitive machine intelligence [M]. Nerwell, MA: Kluwer academic publishers, (2003).

[4] H. Mohammad. Analysis on the evolution of the discourse on computer software and programming languages in the light of literary genres and power-knowledge [J]. Computers in Human Behavior, 2010, 26(3): 464-473.

DOI: 10.1016/j.chb.2009.12.005

[5] J.R. Koza. Automatic creation of human-competitive programs and controllers by means of genetic programming [J]. Genetic Programming and Evolvable Machines, 2000, 1(2): 121-164.

DOI: 10.1007/s10710-010-9112-3

[6] D. Lin, M.Q. Li, J.S. Kou. A theorem on the Convergence of genetic programming [J]. Journal of Xiamen University (Natural Science), 2000, 39(1): 125-127.

[7] Thomas Back. Handbook of evolutionary computation [M]. Oxford University Press, (1997).

[8] J. Qin, L.S. Kang, T.P. Chen. The convergence analysis and algorithm improvement of computation algorithm [J]. Computer Engineering and Application, 2003(19): 91-93.

[9] M. Vose, A.H. Wright. Simple genetic algorithms with linear fitness [J]. Evolutionary Computation, 1995, 2(4): 347-368.

DOI: 10.1162/evco.1994.2.4.347

[10] A.H. Wright, M. Vose. Finiteness of the fixed point for Simple genetic algorithms [J]. Evolutionary Computation, 1996, 3(3): 299-309.

DOI: 10.1162/evco.1995.3.3.299

[11] G. Rudolph. Convergence analysis of canonical genetic algorithm [J]. IEEE Tran Neural Network, 1994, 5(1): 96-101.

[12] R. Cerf. Asymptotic convergence of genetic algorithms [J]. Advance in applied probability, 1998, 30(2): 521-550.

DOI: 10.1239/aap/1035228082

[13] J. Qin, L.S. Kang. A convergence analysis framework for multi-objective optimization evolutionary algorithm [J]. Computer Application Reasearch, 2005(2): 68-70.

[14] J. Suzuki. A further result on the markov chain model of genetic algorithms and its application to a simulated annealing-like strategy [J]. IEEE Tran on systems, Man and Cybernetics-part B: Cybernetics, 1998(1): 95-102.

DOI: 10.1109/3477.658583

[15] A. Trouve. The evolutionary computation and simulated annealing [J], SIAM journal on control and optimization, 1997(34): 966-986.

[16] Q.H. Duan. The convergence theory and strategies for evolutionary algorithm [Ph. D]. Xi'an: Xi'an Jiaotong University, (2002).

[17] J.S. Zhang, Z.B. Xu, Y. Liang. The whole annealing genetic algorithm and its convergence necessaryand sufficient condition [J]. Science in China (Series E), 1997, 27(2): 154-164.

[18] W.X. Zhang, Z.B. Xu, Z.K. Nie, et al. Probability convergence theorems of genetic algorithms [J]. Journal of Engineering Mathematics, 2001, 18(4): 1-11.

[19] X.M. Dai, R. Sun, R.M. Zou, et al. Global convergence analysis of non-crossover genetic algorithm and its application to optimization [J]. Journal of systems engineering and electronics, 2002, 13(2): 84-91.

[20] J. Jana, R. Zbynek. Influence of multiple crossover and mutation to the convergence of genetic optimization (Article number 4630326) [C]. Proceedings on the 17th international conference on microwaves, radar and wireless communications (MIKON 2008), Wroclaw, Poland, May 19-May 21, 2008: 419-423.