Using context-aware crossover to improve the performance of GP

ABSTRACT

This paper describes the use of a recently introduced crossover operator for GP, context-aware crossover. Given a randomly selected subtree from one parent, context-aware crossover will always find the best location to place the subtree in the other parent.We examine the performance of GP when context-aware crossover is used as an extra crossover operator, and show that standard crossover is far more destructive, and that performance is better when only context-aware crossover is used.There is still a place for standard crossover, however, and results suggest that using standard crossover in the initial part of the run and then switching to context-aware crossover yields the best performance.We show that, across a range of standard GP benchmark problems, context-aware crossover produces a higher best fitness as well as a higher mean fitness, and even manages to solve the 11-bit multiplexer problem without ADFs. Furthermore, the individuals produced this way are much smaller than standard GP, and far fewer individual evaluations are required, so GP achieves a higher fitness by evaluating fewer and smaller individuals.

REFERENCES

• 1: Lee Altenberg, The evolution of evolvability in genetic programming, Advances in genetic programming, MIT Press, Cambridge, MA, 1994
• 2: 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
• 3: Patrik D'haeseleer. Context preserving crossover in genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, volume 1, pages 256--261, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.
• 4: S. Hengproprohm and P. Chongstitvatana. Selective crossover in genetic programming. In ISCIT International Symposium on Communications and Information Technologies, ChiangMai Orchid, ChiangMai Thailand, 14-16 November 2001.
• 5: Takuya Ito , Hitoshi Iba , Satoshi Sato, Non-destructive Depth-Dependent Crossover for Genetic Programming, Proceedings of the First European Workshop on Genetic Programming, p.71-82, April 14-15, 1998
• 6: Hammad Majeed, A new approach to evaluate GP schema in context, Proceedings of the 2005 workshops on Genetic and evolutionary computation, June 25-26, 2005, Washington, D.C. [doi>10.1145/1102256.1102341]
• 7: Hammad Majeed and Conor Ryan. A less destructive, context-aware crossover operator for GP. In Proceedings of the 9th European Conference on Genetic Programming, volume 3905 of Lecture Notes in Computer Science, pages 36--48, Budapest, Hungary, 10-12 April 2006. Springer.
• 8: Riccardo Poli and William B. Langdon. On the search properties of different crossover operators in genetic programming. In Genetic Programming 1998: Proceedings of the Third Annual Conference, pages 293--301, University of Wisconsin, Madison, Wisconsin, USA, 22-25 July 1998. Morgan Kaufmann.
• 9: Walter Alden Tackett. Recombination, Selection, and the Genetic Construction of Computer Programs. PhD thesis, University of Southern California, Department of Electrical Engineering Systems, USA, 1994.
• 10: Chi Chung Yuen. Selective crossover using gene dominance as an adaptive strategy for genetic programming. Msc intelligent systems, University College, London, UK, September 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search

General Terms:
Performance

Keywords:
context, context aware crossover, destructive effects, one point crossover, performance, standard crossover, tree context