Algebraic simplification of GP programs during evolution

ABSTRACT

Program bloat is a fundamental problem in the field of Genetic Programming (GP). Exponential growth of redundant and functionally useless sections of programs can quickly overcome a GP system, exhausting system resources and causing premature termination of the system before an acceptable solution can be found. Simplification is an attempt to remove such redundancies from programs. This paper looks at the effects of applying an algebraic simplification algorithm to programs during the GP evolution. The GP system with the simplification is examined and compared to a standard GP system on four regression and classification problems of varying difficulty. The results suggest that the GP system employing a simplification component can achieve superior efficiency and effectiveness to the standard system on these problems.

REFERENCES

• 1: Wolfgang Banzhaf , Frank D. Francone , Robert E. Keller , Peter Nordin, Genetic programming: an introduction: on the automatic evolution of computer programs and its applications, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 2: T. Blickle and L. Thiele. Genetic programming and redundancy. In J. Hopf, editor, Genetic Algorithms within the Framework of Evolutionary Computation, pages 33--38, Germany, 1994.
• 3: Jens Busch , Jens Ziegler , Christian Aue , Andree Ross , Daniel Sawitzki , Wolfgang Banzhaf, Automatic Generation of Control Programs for Walking Robots Using Genetic Programming, Proceedings of the 5th European Conference on Genetic Programming, p.258-267, April 03-05, 2002
• 4: B. Cherowitzo, 2006. Lecture Notes. http://www-math.cudenver.edu/wcherowi/courses/m5410/exeucalg.html. Visited on 7 January 2006.
• 5: Athinodoros S. Georghiades , Peter N. Belhumeur , David J. Kriegman, From Few to Many: Illumination Cone Models for Face Recognition under Variable Lighting and Pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.6, p.643-660, June 2001 [doi>10.1109/34.927464]
• 6: Athinodoros S. Georghiades , Peter N. Belhumeur , David J. Kriegman, From Few to Many: Illumination Cone Models for Face Recognition under Variable Lighting and Pose, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.6, p.643-660, June 2001 [doi>10.1109/34.927464]
• 7: Gaston H. Gonnet, Determining equivalence of expressions in random polynomial time, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.334-341, December 1984 [doi>10.1145/800057.808698]
• 8: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 9: John R. Koza, Genetic Programming IV: Routine Human-Competitive Machine Intelligence, Kluwer Academic Publishers, Norwell, MA, 2003
• 10: Rudolf Lidl , Harald Niederreiter, Introduction to finite fields and their applications, Cambridge University Press, New York, NY, 1986
• 11: T. Loveard and V. Ciesielski. Representing classification problems in genetic programming. In Proceedings of the Congress on Evolutionary Computation, volume 2, pages 1070--1077, Seoul, Korea, 2001. IEEE Press.
• 12: William A. Martin, Determining the Equivalence of Algebraic Expressions by Hash Coding, Journal of the ACM (JACM), v.18 n.4, p.549-558, Oct. 1971 [doi>10.1145/321662.321668]
• 13: R. Poli. Genetic programming for image analysis. In Proceedings of the First Annual Conference, pages 363--368, Stanford University, CA, USA, 28-31 July 1996. MIT Press.
• 14: T. Soule, J. A. Foster, and J. Dickinson. Code growth in genetic programming. In Proceedings of the First Annual Conference, pages 215--223, Stanford University, CA, USA, 28-31 1996. MIT Press.
• 15: Lawrence C. Washington , Wade Trappe, Introduction to Cryptography: With Coding Theory, Prentice Hall PTR, Upper Saddle River, NJ, 2002
• 16: Mengjie Zhang , Victor Ciesielski, Genetic Programming for Multiple Class Object Detection, Proceedings of the 12th Australian Joint Conference on Artificial Intelligence: Advanced Topics in Artificial Intelligence, p.180-192, December 06-10, 1999
• 17: M. Zhang and W. Smart. Multiclass object classification using genetic programming. In Applications of Evolutionary Computing, EvoWorkshops2004, volume 3005 of LNCS, pages 369--378, Portugal. 2004. Springer Verlag.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.m Miscellaneous

General Terms:
Algorithms, Performance

Keywords:
algebraic simplification, code bloating, genetic programming, online simplification, program simplification