Abstract
Genetic programming (GP) extends traditional genetic algorithms to automatically induce computer programs. GP has been applied in a wide range of applications such as software re-engineering, electrical circuits synthesis, knowledge engineering, and data mining. One of the most important and challenging research areas in GP is the investigation of ways to successfully evolve recursive programs. A recursive program is one that calls itself either directly or indirectly through other programs. Because recursions lead to compact and general programs and provide a mechanism for reusing program code, they facilitate GP to solve larger and more complicated problems. Nevertheless, it is commonly agreed that the recursive program learning problem is very difficult for GP. In this paper, we propose techniques to tackle the difficulties in learning recursive programs. The techniques are incorporated into an adaptive Grammar Based Genetic Programming system (adaptive GBGP). A number of experiments have been performed to demonstrate that the system improves the effectiveness and efficiency in evolving recursive programs.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
H. Abramson and V. Dahl, Logic Grammars, Springer-Verlag: Berlin, 1989.
P. J. Angeline, “Two self-adaptive crossover operators for genetic programming,” in Advances in Genetic Programming 2, P. J. Angeline and K. E. Kinnear Jr. (Eds.), MIT Press: MA, 1996, pp. 89–109.
P. J. Angeline and K. E. Kinnear Jr. (Eds.), Advances in Genetic Programming 2, MIT Press: MA, 1996.
S. Brave, “Evolving recursive programs for tree search,” in Advances in Genetic Programming 2, P. J. Angeline and K. E. Kinnear Jr. (Eds.), MIT Press: MA, 1996, pp. 203–219.
A. A. Freitas, “A genetic programming framework for two data mining tasks: Classification and generalized rule induction,” in Genetic Programming 1997: Proceedings of the 2nd Annual Conference, 1997, pp. 96–101.
D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning, Addison-Wesley: Reading, MA, 1989.
J. H. Holland, Adaptation in Natural and Artificial Systems, The University of Michigan Press: Ann Arbor, 1975.
J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley: MA, 1979.
M. Keijzer and V. Babovic, “Declarative and preferential bias in GP-based scientific discovery,” Genetic Programming and Evolvable Machines vol. 3, pp. 41–79, 2002.
M. Keijzer, V. Babovic, C. Ryan, M. O'Neill, and M. Cattolico, “Adaptive logic programming,” in Proceedings of the Genetic and Evolutionary Computation Conference 2001, L. Spector, E. D. Goodman, A. Wu, W. B. Langdon, H.-M. Voigt, M. Gen, S. Sen, M. Dorigo, S. Pezeshk, M. H. Garzon, and E. Burke (Eds.), Morgan Kaufmann: CA, 2001, pp. 42–49.
K. E. Kinnear Jr. (Ed.), Advances in Genetic Programming 1, MIT Press: MA, 1994.
J. R. Koza, F. H. Bennett III, D. Andre, and M. A. Keane, Genetic Programming III: Darwinian Invention and Problem Solving, Morgan Kaufmann Publishers: San Francisco, CA, 1999.
J. R. Koza, M. A. Keane, M. J. Streeter, W. Mydlowec, J. Yu, and G. Lanza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers: Boston, MI, 2003.
J. R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press: Cambridge, MA, 1992.
J. R. Koza, Genetic Programming II: Automatic Discovery of Reusable Programs, MIT Press: Cambridge MA, 1994.
N. Lavrac and S. Dzeroski, Inductive Logic Programming: Techniques and Applications, Ellis Horword: London, 1994.
D. J. Montana, “Strongly typed genetic programming,” Evolutionary Computation vol. 3, pp. 199–230, 1995.
S. Muggletion, “Inductive logic programming,” in Inductive Logic Programming, S. Muggletion (Ed.), Academic Press: London, 1992, pp. 3–27.
M. O'Neill and C. Ryan, “Grammatical evolution,” IEEE Transactions on Evolutionary Computation vol. 5, pp. 349–58, 2001.
M. O'Neill and C. Ryan, “Grammatical evolution by grammatical evolution: The evolution of grammar and genetic code,” in Proceedings of the Seventh European Conference on Genetic Programming, 2004, pp. 138–149.
F. C. N. Pereira and S. M. Shieber, Prolog and Natural-Language Analysis, CSLI: CA, 1987.
F. C. N. Pereira and D. H. D. Warren, “Definite clause grammars for language analysis—A survey of the formalism and a comparison with augmented transition networks,” Artificial Intelligence vol. 13, pp. 231–278, 1980.
Y. Shan, R. I. McKay, R. Baxter, H. Abbass, D. Essam, and H. X. Nguyen, “Grammar model-based program evolution,” in Proceedings of the 2004 IEEE Congress on Evolutionary Computation, 2004, pp. 478–485.
L. Spector, W. B. Langdon, U. M. O'Reilly, and P. J. Angeline, (Eds.), Advances in Genetic Programming 3. MIT Press: MA, 1999.
L. R. Tang, M. E. Califf, and R. J. Mooney, “An experimental comparison of genetic programming and inductive logic programming on learning recursive list functions,” TR AI98-271, Artificial Intelligence Lab, University of Texas at Austin, 1998.
P. A. Whigham, Grammatical Bias for Evolutionary Learning, PhD Thesis. University of New South Wales, 1996.
P. A. Whigham, “Search bias, language bias, and genetic programming,” in Genetic Programming 1996: Proceedings of the First Annual Conference, J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo (Eds.), MIT Press: MA, 1996, pp. 230–237.
P. A. Whigham and R. McKay, “Genetic approaches to learning recursive relations,” Lecture Notes in Artificial Intelligence, vol. 956, pp. 17–28, 1995.
M. L. Wong, “A flexible knowledge discovery system using genetic programming and logic grammars,” Decision Support Systems vol. 31, pp. 405–428, 2001.
M. L. Wong and K. S. Leung, “Evolving recursive functions for the even-parity problem using genetic programming,” in Advances in Genetic Programming 2, P. J. Angeline and K. E. Kinnear Jr. (Eds.), MIT Press: MA, 1996, pp. 221–240.
M. L. Wong and K. S. Leung, “Learning recursive functions from noisy examples using generic genetic programming,” in Genetic Programming 1996: Proceedings of the First Annual Conference, J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo (Eds.), MIT Press: MA, 1996, pp. 238–246.
M. L. Wong and K. S. Leung, “Evolutionary program induction directed by logic grammars,” Evolutionary Computation vol. 5, pp. 143–180, 1997.
M. L. Wong and K. S. Leung, Data mining using grammar based genetic programming and the applications, Kluwer Academic Publishers: Boston, MA, 2000.
T. Yu, An Analysis of the Impact of Functional Programming Techniques on Genetic Programming, PhD Thesis. Department of Computer Science, University College London, 1999.
T. Yu, “Hierarchical processing for evolving recursive and modular programs using higher-order functions and lambda abstraction,” Genetic Programming and Evolvable Machines vol. 2, pp. 345–380, 2001.
T. Yu, “Polymorphism and genetic programming,” in Proceedings of the Fourth European Conference on Genetic Programming, 2001, pp. 416–421.
T. Yu and C. Clack, “PolyGP: A polymorphic genetic programming system in haskell,” in Genetic Programming 1998: Proceedings of the Third Annual Conference, J. R. Koza, W. Banzhaf, K. Chellapilla, K. Deb, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. Riolo (Eds.), Morgan Kaufmann: CA, 1998, pp. 416–421.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by: William B. Langdon
An erratum to this article is available at http://dx.doi.org/10.1007/s10710-006-7455-6.
Rights and permissions
About this article
Cite this article
Wong, M.L., Mun, T. Evolving Recursive Programs by Using Adaptive Grammar Based Genetic Programming. Genet Program Evolvable Mach 6, 421–455 (2005). https://doi.org/10.1007/s10710-005-4805-8
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/s10710-005-4805-8