EVOLVING MORE REPRESENTATIVE PROGRAMS WITH GENETIC PROGRAMMING
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++.
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 , 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. Fogel (IEEE Press, 2002) pp. 243–248. Google ScholarWalter 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- Applications of Evolutionary Computing,
LNCS 2611, ed.Stefano Cagnoni (Springer-Verlag, 2003) pp. 455–466. Crossref, Google Scholar , - EURASIP Journal on Signal Processing, Special Issue on Genetic and Evolutionary Computation for Signal Processing and Image Analysis 8, 841 (2003). Google Scholar
- 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 Cagnoni (Springer-Verlag, 2002) pp. 220–230. Google ScholarAstro 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 ScholarJay F. Winkeler and B. S. Manjunath , Genetic programming for object detection, Genetic Programming 1997: Proceedings of the Second Annual Conference, eds.John R. Koza (1997) pp. 330–335. Google Scholar- IBM Journal of Research and Development 2, 2 (1958). Crossref, Web of Science, Google Scholar
- 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 ScholarFrances E. Allen , Control flow analysis, Proceedings of a Symposium on Compiler Optimization (1970) pp. 1–19. Google ScholarBruce 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
Remember to check out the Most Cited Articles! |
---|
Check out our titles in C++ Programming! |