A new crossover technique for Cartesian genetic programming

ABSTRACT

Genetic Programming was first introduced by Koza using tree representation together with a crossover technique in which random sub-branches of the parents' trees are swapped to create the offspring. Later Miller and Thomson introduced Cartesian Genetic Programming, which uses directed graphs as a representation to replace the tree structures originally introduced by Koza. Cartesian Genetic Programming has been shown to perform better than the traditional Genetic Programming; but it does not use crossover to create offspring, it is implemented using mutation only. In this paper a new crossover method in Genetic Programming is introduced. The new technique is based on an adaptation of the Cartesian Genetic Programming representation and is tested on two simple regression problems. It is shown that by implementing the new crossover technique, convergence is faster than that of using mutation only in the Cartesian Genetic Programming method.

REFERENCES

• 1: P. Angeline. Subtree crossover: Building block engine or macromutation? In Genetic Programming 1997: Proceedings of the Second Annual Conference (GP97), pages 9--17, Stanford University, USA, 13--16 July 1997. Morgan Kaufman.
• 2: J. Clegg, J. Dawson, S. Porter, and M. Barley. The use of a genetic algorithm to optimize the functional form of a multi-dimensional polynomial fit to experimental data. In 2005 IEEE Congress on Evolutionary Computation, volume 1, pages 928--934, Edinburgh, 2005.
• 3: J. Clegg, A. Marvin, J. Dawson, and S. Porter. Optimisation of stirrer designs in a reverberation chamber. In IEEE Trans. EMC, volume 47 of No. 2, pages 399--403, 2005.
• 4: L. Dawson, J. Clegg, S. Porter, J. Dawson, and M. Alexander. The use of genetic algorithms to maximise the performance of a partially lined screened room. In IEEE Trans. EMC, volume 44 of No. 1, pages 233--242, 2002.
• 5: Kenneth Alan De Jong, An analysis of the behavior of a class of genetic adaptive systems., University of Michigan, Ann Arbor, MI, 1975
• 6: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 7: John R. Koza, Genetic programming II: automatic discovery of reusable programs, MIT Press, Cambridge, MA, 1994
• 8: S. Luke and L. Spector. A comparison of crossover and mutation in genetic programming. In Genetic Programming 1997: Proceedings of the Second Annual Conference (GP97), pages 240--248, Stanford University, USA, 13--16 July 1997. Morgan Kaufman.
• 9: S. Luke and L. Spector. A revised comparison of crossover and mutation in genetic programming. In Genetic Programming 1998: Proceedings of the Third Annual Conference (GP98), pages 208--213, University of Wisconsin, Madison, WI, USA, 22--25 July 1998. Morgan Kaufman.
• 10: H. Mann and D. Whitney. On a test of whether one of 2 random variables is stochastically larger than the other. Annals of Mathematical Statistics, (18):50--60, 1947.
• 11: J. F. Miller. An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In GECCO 1999: Proceedings of the Genetic and Evolutionary Computation Conference, pages 1135--1142, Orlando, Florida, 1999. Morgan Kaufmann.
• 12: Julian F. Miller , Peter Thomson, Cartesian Genetic Programming, Proceedings of the European Conference on Genetic Programming, p.121-132, April 15-16, 2000
• 13: Riccardo Poli, Parallel distributed genetic programming, New ideas in optimization, McGraw-Hill Ltd., UK, Maidenhead, UK, 1999
• 14: J. Schaffer and L. Eshelman. On crossover as an evolutionarily viable strategy. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 61--68, La Jolla, CA, 1991. Morgan Kaufmann.
• 15: W. Spears and K. De Jong. On the virtues of uniform crossover. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 230--236, La Jolla, CA, 1991. Morgan Kaufmann.
• 16: Vesselin K. Vassilev , Julian F. Miller, The Advantages of Landscape Neutrality in Digital Circuit Evolution, Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware, p.252-263, April 17-19, 2000
• 17: M. Vose and G. Liepins. Schema disruption. In Proceedings of the Fourth International Conference on Genetic Algorithms, pages 237--242, La Jolla, CA, 1991. Morgan Kaufmann.
• 18: J. Walker and J. Miller. Automatic acquisition, evolution and re-use of modules in cartesian genetic programming. to be published in IEEE Transactions on Evolutionary Computation, 2007.
• 19: Tina Yu , Julian F. Miller, Neutrality and the Evolvability of Boolean Function Landscape, Proceedings of the 4th European Conference on Genetic Programming, p.204-217, April 18-20, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming
          Subjects: Program synthesis

General Terms:
Algorithms, Design, Performance

Keywords:
cartesian genetic programming, crossover techniques, optimisation