No Access

EVOLVING MORE REPRESENTATIVE PROGRAMS WITH GENETIC PROGRAMMING

DANIEL MCGAUGHRAN

School of Engineering and Computing Sciences, Victoria University of Wellington, P.O. Box 600, Wellington, New Zealand

Search for more papers by this author

and

MENGJIE ZHANG

School of Engineering and Computing Sciences, Victoria University of Wellington, P.O. Box 600, Wellington, New Zealand

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S021819400900409XCited by:3 (Source: Crossref)

Abstract

This paper describes a new representation of tree-based genetic programs in Genetic Programming, an approach of artificial intelligence and knowledge engineering, in order to adopt a form more conducive to imperative functions as developed by human programmers. This representation incorporates the Abstract Syntax Tree form into a larger tree structure based on a Control Flow Graph, thereby causing statements to be chained together sequentially and allowing genetic programs to be output as (non-object-oriented) C++ code fragments. Maintaining or improving the evolutionary performance has been a key priority in this development. These prompt additional genetic operators to be defined to better preserve chains of statements than the traditional Mutation and Crossover operators, thereby encouraging a more efficient evolution of genetic programs. Experimental results suggest that adopting a chained approach can make a significant improvement in evolutionary performance over using ProgN functions that evaluate their children sequentially. The introduction of additional operators can improve the evolutionary performance even further.

This approach can automatically generate computer programs for a particular problem using artificial intelligence and knowledge engineering approaches. In particular, the newly developed operators in the chained approach have great potential for generating human competitive programs in commonly used imperative programming languages such as C++.

Keywords:

References

John R. Koza, Encyclopaedia of Computer Science and Technology 39 (1998) pp. 29–43. Google Scholar
William B. Langdon and Riccardo Poli , Foundations of Genetic Programming ( Springer-Verlag , 2002 ) . Crossref, Google Scholar
John R. Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( MIT Press , 1992 ) . Google Scholar
Vic Ciesielski and Xiang Li , Experiments with explicit for-loops in genetic programming , 2004 Congress on Evolutionary Computation ( 2004 ) . Google Scholar
Vic Ciesielski and Xiang Li , Using loops in genetic programming for a two-class binary image classification problem , 17th Australian Joint Conference on Artificial Intelligence ( 2004 ) . Google Scholar
Seven differences between genetic programming and other approaches to machine learning and artificial intelligence. Available from http://www.genetic-programming.com/sevendiffs.html (Accessed March 2005) . Google Scholar
William B. Langdon , Genetic Programming and Data Structures ( Kluwer Academic Publishers , 1998 ) . Crossref, Google Scholar
David J. Montana, Strongly typed genetic programming, BBN Technical Report (7866), March 1994 . Google Scholar
John R. Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( MIT Press , Cambridge, MA , 1992 ) . Google Scholar
Wolfgang Banzhaf et al. , Genetic Programming: An Introduction on the Automatic Evolution of Computer Programs and Its Applications ( Morgan Kaufmann Publishers , 1998 ) . Crossref, Google Scholar
John R. Koza , Genetic Programming II: Automatic Discovery of Reusable Programs ( MIT Press , Cambridge, MA , 1994 ) . Google Scholar
Andy Song, Vic Ciesielski and Hugh Williams, Proceedings of the 2002 Congress on Evolutionary Computation, eds. David B. Fogelet al. (IEEE Press, 2002) pp. 243–248. Google Scholar
Walter Alden Tackett, Genetic programming for feature discovery and image discrimination, Proceedings of the 5th International Conference on Genetic Algorithms, ed. Stephanie Forrest pp. 303–309. Google Scholar
Mengjie Zhang, Peter Andreae and Mark Pritchard, Applications of Evolutionary Computing, LNCS 2611, ed. Stefano Cagnoni (Springer-Verlag, 2003) pp. 455–466. Crossref, Google Scholar
Mengjie Zhang, Victor Ciesielski and Peter Andreae, EURASIP Journal on Signal Processing, Special Issue on Genetic and Evolutionary Computation for Signal Processing and Image Analysis 8, 841 (2003). Google Scholar
Daniel Howard, Simon C. Roberts and Richard Brankin, Advances in Engineering Software 30, 303 (1999), DOI: 10.1016/S0965-9978(98)00093-3. Crossref, Web of Science, Google Scholar
Daniel Howard, Simon C. Roberts and Conor Ryan, The boru data crawler for object detection tasks in machine vision, Applications of Evolutionary Computing, Proceedings of EvoWorkshops2002: EvoCOP, EvoIASP, EvoSTim2279, eds. Stefano Cagnoniet al. (Springer-Verlag, 2002) pp. 220–230. Google Scholar
Astro Teller and Manuela Veloso, A controlled experiment: Evolution for learning difficult image classification, Proceedings of the 7th Portuguese Conference on Artificial Intelligence990, LNAI, eds. Carlos Pinto-Ferreira and Nuno J. Mamede pp. 165–176. Google Scholar
Jay F. Winkeler and B. S. Manjunath, Genetic programming for object detection, Genetic Programming 1997: Proceedings of the Second Annual Conference, eds. John R. Kozaet al. (1997) pp. 330–335. Google Scholar
R. Friedberg, IBM Journal of Research and Development 2, 2 (1958). Crossref, Web of Science, Google Scholar
R. Friedberg, B. Dunham and J. North, IBM Journal of Research and Development 3, 282 (1959). Crossref, Web of Science, Google Scholar
Steven S. Muchnick , Advanced Compiler Design and Implementation ( Morgan Kaufmann Publishers , 1997 ) . Google Scholar
Cezary Z. Janikow, A methodology for processing problem constraints in genetic programming, University of Missouri, 1996 . Google Scholar
Cezary Z. Janikow, Adapting representation in genetic programming, Proceedings of the Genetic and Evolutionary Computation Conference (2004) pp. 507–518. Google Scholar
P. A. Whigham, Grammatically-based genetic programming, University of New South Wales, 1995 . Google Scholar
Nguyen Xuan Hoai, Softening the structural difficulty in genetic programming with tag-based representation and insertion/deletion operators, Proceedings of the Genetic and Evolutionary Computation Conference (2004) pp. 605–616. Google Scholar
Frances E. Allen, Control flow analysis, Proceedings of a Symposium on Compiler Optimization (1970) pp. 1–19. Google Scholar
Bruce A. Cota, Douglas G. Fritz and Robert G. Sargent, Control flow graphs as a representation language, Proceedings of the 26th Conference on Winter Simulation (1994) pp. 555–559. Google Scholar
D. J. McGaughran, Genetic programming: Evolving simulated human-generated programs with loops and control structures, BSc (Honours) Research Project, Victoria University of Wellington, 2005 . Google Scholar