Approximating geometric crossover in semantic space

ABSTRACT

We propose a crossover operator that works with genetic programming trees and is approximately geometric crossover in the semantic space. By defining semantic as program's evaluation profile with respect to a set of fitness cases and constraining to a specific class of metric-based fitness functions, we cause the fitness landscape in the semantic space to have perfect fitness-distance correlation. The proposed approximately geometric semantic crossover exploits this property of the semantic fitness landscape by an appropriate sampling. We demonstrate also how the proposed method may be conveniently combined with hill climbing. We discuss the properties of the methods, and describe an extensive computational experiment concerning logical function synthesis and symbolic regression.

REFERENCES

• 1: L. Altenberg. Emergent phenomena in genetic programming. In A. V. Sebald and L. J. Fogel, editors, Evolutionary Programming -- Proceedings of the Third Annual Conference, pages 233--241, San Diego, CA, USA, 24-26 Feb. 1994. World Scientific Publishing.
• 2: L. Beadle and C. Johnson. Semantically driven crossover in genetic programming. In J. Wang, editor, Proceedings of the IEEE World Congress on Computational Intelligence, pages 111--116, Hong Kong, 1-6 June 2008. IEEE Computational Intelligence Society, IEEE Press.
• 3: Benjamin Doerr , Edda Happ , Christian Klein, Crossover can provably be useful in evolutionary computation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389202]
• 4: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 5: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 6: S. Luke. ECJ evolutionary computation system, 2002. (http://cs.gmu.edu/ eclab/projects/ecj/).
• 7: N. F. McPhee, B. Ohs, and T. Hutchison. Semantic building blocks in genetic programming. In M. O'Neill, L. Vanneschi, S. Gustafson, A. I. E. Alcázar, I. D. Falco, A. D. Cioppa, and E. Tarantino, editors, Genetic Programming, volume 4971 of LNCS, pages 134--145. Springer, 2008.
• 8: Peter Merz, A Comparison Of Memetic Recombination Operators For The Traveling Salesman Problem, Proceedings of the Genetic and Evolutionary Computation Conference, p.472-479, July 09-13, 2002
• 9: A. Moraglio and R. Poli. Topological interpretation of crossover. In K. Deb, R. Poli, W. Banzhaf, H.-G. Beyer, E. Burke, P. Darwen, D. Dasgupta, D. Floreano, J. Foster, M. Harman, O. Holland, P. L. Lanzi, L. Spector, A. Tettamanzi, D. Thierens, and A. Tyrrell, editors, Genetic and Evolutionary Computation -- GECCO-2004, Part I, volume 3102 of Lecture Notes in Computer Science, pages 1377--1388, Seattle, WA, USA, 26-30 June 2004. Springer-Verlag.
• 10: A. Moraglio and R. Poli. Geometric landscape of homologous crossover for syntactic trees. In Proceedings of the 2005 IEEE Congress on Evolutionary Computation (CEC-2005), volume 1, pages 427--434, Edinburgh, 2-4 Sept. 2005. IEEE.
• 11: Riccardo Poli , Jonathan Page, Solving High-Order Boolean Parity Problems with Smooth Uniform Crossover, Sub-Machine Code GP and Demes, Genetic Programming and Evolvable Machines, v.1 n.1-2, p.37-56, April 2000 [doi>10.1023/A:1010068314282]
• 12: F. Rothlauf. On the locality of representations. Technical report, University of Mannheim, Department of Information Systems 1, 2003.
• 13: F. Rothlauf and M. Oetzel. On the locality of grammatical evolution. Working Paper 11/2005, Department of Business Administration and Information Systems, University of Mannheim, D-68131 Mannheim, Germany, Dec. 2005.
• 14: W. A. Tackett and A. Carmi. The unique implications of brood selection for genetic programming. In Proceedings of the 1994 IEEE World Congress on Computational Intelligence, Orlando, Florida, USA, 27-29 June 1994. IEEE Press.
• 15: L. Vanneschi and M. Tomassini. Pros and cons of fitness distance correlation in genetic programming. In A. M. Barry, editor, GECCO 2003: Proceedings of the Bird of a Feather Workshops, Genetic and Evolutionary Computation Conference, pages 284--287, Chigaco, 11 July 2003. AAAI.
• 16: Huayang Xie , Mengjie Zhang , Peter Andreae, An analysis of constructive crossover and selection pressure in genetic programming, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277297]
• 17: M. Yangiya. Efficient genetic programming based on binary decision diagrams. In 1995 IEEE Conference on Evolutionary Computation, volume 1, pages 234--239, Perth, Australia, 29 Nov. - 1 Dec. 1995. IEEE Press.

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
fitness-distance correlation, genetic programming, geometric crossover, global convexity, program semantics