Abstract
Standard GP crossover is widely accepted as being a largely destructive operator, creating many poor offspring in the search for better ones. One of the major reasons for its destructiveness is its disrespect for the context of swapped subtrees in their respective parent trees when creating offspring. At times, this hampers GP’s performance considerably, and results in populations with low average fitness values.
Many attempts have been made to make it a more constructive crossover, mostly by preserving the context of the selected subtree in the offspring. Although successful at preserving context, none of these methods provide the opportunity to discover new and better contexts for exchanged subtrees.
We introduce a context-aware crossover operator which operates by identifying all possible contexts for a subtree, and evaluating each of them. The context that produces the highest fitness is used to create a child which is then passed into the next generation.
We have tested its performance on many benchmark problems. It has shown better results than the standard GP crossover operator, using either the same number or fewer individual evaluations. Furthermore, the average fitness of populations using this scheme improves considerably, and programs produced in this way are much smaller than those produced using standard crossover.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Banzhaf, W., Nordin, P., Keller, R.E., Francone, F.D.: Genetic Programming – An Introduction. In: On the Automatic Evolution of Computer Programs and its Applications, dpunkt.verlag, Morgan Kaufmann, San Francisco (1998)
D’haeseleer, P.: Context preserving crossover in genetic programming. In: Proceedings of the 1994 IEEE World Congress on Computational Intelligence, Orlando, Florida, USA, 27-29 June 1994, vol. 1, pp. 256–261. IEEE Press, Los Alamitos (1994)
Hengproprohm, S., Chongstitvatana, P.: Selective crossover in genetic programming. In: ISCIT International Symposium on Communications and Information Technologies, ChiangMai Orchid, ChiangMai Thailand, 14-16 November (2001)
Ito, T., Iba, H., Sato, S.: Non-destructive depth-dependent crossover for genetic programming. In: Banzhaf, W., Poli, R., Schoenauer, M., Fogarty, T.C. (eds.) EuroGP 1998. LNCS, vol. 1391, pp. 71–82. Springer, Heidelberg (1998)
Koza, J.R.: Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge (1994)
Majeed, H.: A new approach to evaluate GP schema in context. In: Rothlauf, F., Blowers, M., Branke, J., Cagnoni, S., Garibay, I.I., Garibay, O., Grahl, J., Hornby, G., de Jong, E.D., Kovacs, T., Kumar, S., Lima, C.F., Llorá, X., Lobo, F., Merkle, L.D., Miller, J., Moore, J.H., O’Neill, M., Pelikan, M., Riopka, T.P., Ritchie, M.D., Sastry, K., Smith, S.L., Stringer, H., Takadama, K., Toussaint, M., Upton, S.C., Wright, A.H. (eds.) Genetic and Evolutionary Computation Conference (GECCO2005) workshop program, Washington, D.C., USA, June 25-29, 2005, pp. 378–381. ACM Press, New York (2005)
Montana, D.J.: Strongly typed genetic programming. BBN Technical Report #7866, Bolt Beranek and Newman, Inc., 10 Moulton Street, Cambridge, MA 02138, USA, May 7, (1993)
Poli, R., Langdon, W.B.: On the search properties of different crossover operators in genetic programming. In: Koza, J.R., Banzhaf, W., Chellapilla, K., Deb, K., Dorigo, M., Fogel, D.B., Garzon, M.H., Goldberg, D.E., Iba, H., Riolo, R. (eds.) Proceedings of the Third Annual Conference on Genetic Programming 1998, University of Wisconsin, Madison, Wisconsin, USA, July 22-25, 1998, pp. 293–301. Morgan Kaufmann, San Francisco (1998)
Tackett, W.A.: Recombination, Selection, and the Genetic Construction of Computer Programs. PhD thesis, University of Southern California, Department of Electrical Engineering Systems, USA (1994)
Vekaria, K.P.: Selective Crossover as an Adaptive Strategy for Genetic Algorithms. PhD thesis, University of London, Department of Selective Recombination (Dominance Crossover) Computer Science, University College London, UK (1999)
Yuen, C.C.: Selective crossover using gene dominance as an adaptive strategy for genetic programming. Msc intelligent systems, University College, London, UK (September 2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Majeed, H., Ryan, C. (2006). A Less Destructive, Context-Aware Crossover Operator for GP. In: Collet, P., Tomassini, M., Ebner, M., Gustafson, S., Ekárt, A. (eds) Genetic Programming. EuroGP 2006. Lecture Notes in Computer Science, vol 3905. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11729976_4
Download citation
DOI: https://doi.org/10.1007/11729976_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-33143-8
Online ISBN: 978-3-540-33144-5
eBook Packages: Computer ScienceComputer Science (R0)