Top

Soft Computing

Published in:

01-09-2011 | Original Paper

Depth-control strategies for crossover in tree-based genetic programming

Authors: Huayang Xie, Mengjie Zhang

Published in: Soft Computing | Issue 9/2011

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The standard subtree crossover operator in the tree-based genetic programming (GP) has been considered as problematic. In order to improve the standard subtree crossover, controlling depth of crossover points becomes a research topic. However, the existence of many different and inconsistent crossover depth-control schemes and the possibility of many other depth-control schemes make the identification of good depth-control schemes a challenging problem. This paper aims to investigate general heuristics for making good depth-control schemes for crossover in tree-based GP. It analyses the patterns of depth of crossover points in good predecessor programs of five GP systems that use the standard subtree crossover and four approximations of the optimal crossover operator on three problems in different domains. The analysis results show that an effective depth-control scheme is problem-dependent and evolutionary stage-dependent, and that good crossover events have a strong preference for roots and (less strongly) bottoms of parent program trees. The results also show that some ranges of depths between the roots and the bottoms are also preferred, suggesting that unequal-depth-selection-probability strategies are better than equal-depth-selection-probability strategies.

previous article Fuzzy region assignment for visual tracking

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Trees with the minimal number of nodes for their depths.

Bottom nodes of a program tree are likely leaf nodes but leaf nodes may appear at any depth of a program tree.

This translates the numeric outputs of a GP classifier into class labels based on the sign of the numeric values.

Discussions of a large size limit will be covered in Sect. 5.

Angeline PJ (1996) An investigation into the sensitivity of genetic programming to the frequency of leaf selection during subtree crossover. In: Koza JR, Goldberg DE, Fogel DB, Riolo RL (eds) Genetic programming 1996: proceedings of the first annual conference, Stanford University, CA, USA. MIT Press, Cambridge, pp 21–29

Angeline PJ (1996) Two self-adaptive crossover operators for genetic programming. In: Angeline PJ, Kinnear KE Jr (eds) Advances in genetic programming 2, chap 5. MIT Press, Cambridge, pp 89–110

Banzhaf W, Nordin P, Keller R, Francone FD (1998) Genetic programming—an introduction: on the automatic evolution of computer programs and its applications. Morgan Kaufmann, San FranciscoMATH

Birge L, Rozenholc Y (2006) How many bins should be put in a regular histogram. Eur Ser Appl Ind Math Probab Stat 10:24–45MathSciNetMATH

Couchet J, Manrique D, Rios J, Rodriguez-Paton A (2007) Crossover and mutation operators for grammar-guided genetic programming. Soft Comput Fusion Found Methodol Appl 11(10):943–955

Crawford-Marks R, Spector L (2002) Size control via size fair genetic operators in the PushGP genetic programming system. In: Proceedings of the genetic and evolutionary computation conference, pp 733–739

da Silva SGO (2008) Controlling bloat: individual and population based approaches in genetic programming. PhD thesis, University of Coimbra

D’haeseleer P (1994) Context preserving crossover in genetic programming. In: Proceedings of the 1994 IEEE world congress on computational intelligence, vol 1, Orlando, Florida, USA. IEEE Press, USA, pp 256–261

Espejo PG, Ventura S, Herrera F (2010) A survey on the application of genetic programming to classification. IEEE Trans Syst Man Cybern Part C 40(2):121–144CrossRef

Fernandez F, Tomassini M, Vanneschi L (2003) An empirical study of multipopulation genetic programming. Genet Program Evol Mach 4(1):21–51MATHCrossRef

Frank A, Asuncion A (2010) UCI machine learning repository. University of California, Irvine, School of Information and Computer Sciences. http://archive.ics.uci.edu/ml

Gathercole C, Ross P (1994) Dynamic training subset selection for supervised learning in genetic programming. In: In Davidor Y, Schwefel H-P, Manner R (eds) Parallel problem solving from nature III. Springer, Berlin, pp 312–321

Gruau F (1996) On using syntactic constraints with genetic programming. Adv Genet Program 2:377–394

Gustafson SM (2004) An analysis of diversity in genetic programming. PhD thesis, University of Nottingham

Harries K, Smith P (1997) Exploring alternative operators and search strategies in genetic programming. In: Proceedings of the second annual conference on genetic programming, Stanford University, CA, USA. Morgan Kaufmann, Menlo Park, pp 147–155

Haynes TD, Schoenefeld DA, Wainwright RL (1996) Type inheritance in strongly typed genetic programming. Adv Genet Program 2:359–376

Hengproprohm S, Chongstitvatana P (2001) Selective crossover in genetic programming. In: ISCIT international symposium on communications and information technologies, ChiangMai Orchid, ChiangMai Thailand, 14–16 November 2001

Howard D, Roberts SC, Brankin R (1999) Target detection in SAR imagery by genetic programming. Adv Eng Softw 30:303–311CrossRef

Iba H, de Garis H (1996) Extending genetic programming with recombinative guidance. In: Angeline PJ, Kinnear KE Jr (eds) Advances in genetic programming 2, chap 4. MIT Press, Cambridge, pp 69–88

Ito T, Iba H, Sato S (1998) Depth-dependent crossover for genetic programming. In: Proceedings of the 1998 IEEE world congress on computational intelligence, Anchorage, Alaska, USA, 5–9 May 1998. IEEE Press, USA, pp 775–780

Ito T, Iba H, Sato S (1998) Non-destructive depth-dependent crossover for genetic programming. In: Banzhaf W, Poli R, Schoenauer M, Fogarty TC (eds) Proceedings of the first European workshop on genetic programming. LNCS, vol 1391, Paris, 14–15 April 1998. Springer, Berlin, pp 71–82

Ito T, Iba H, Sato S (1999) A self-tuning mechanism for depth-dependent crossover. In: Spector L, Langdon WB, O’Reilly U-M, Angeline PJ (eds) Advances in genetic programming 3, chap 16. MIT Press, Cambridge, pp 377–399

Kim M, Becker YL, Fei P, O’Reilly U-M (2009) Constrained genetic programming to minimize overfitting in stock selection. In: Genetic programming theory and practice VI, chap 12. Springer, Berlin, pp 179–194

Koza JR (1992) Genetic programming—on the programming of computers by means of natural selection. MIT Press, CambridgeMATH

Lang KJ (1995) Hill climbing beats genetic search on a boolean circuit synthesis of Koza’s. In: Proceedings of the twelfth international conference on machine learning, Tahoe City, California, USA, July 1995. Morgan Kaufmann, Menlo Park

Langdon WB (1999) Size fair and homologous tree genetic programming crossovers. In: Proceedings of the genetic and evolutionary computation conference, vol 2, pp 1092–1097

Langdon WB (2000) Size fair and homologous tree crossovers for tree genetic programming. Genet Program Evol Mach 1:95–119MATHCrossRef

Langdon WB, Poli R (2002) Foundations of genetic programming. Springer, BerlinMATH

Loveard T, Ciesielski V (2001) Representing classification problems in genetic programming. In: Proceedings of the congress on evolutionary computation, vol 2. IEEE Press, USA, pp 1070–1077

Majeed H, Ryan C (2006) A less destructive, context-aware crossover operator for GP. In: Proceedings of EuroGP 2006. LNCS, vol 3905. Springer, Berlin, pp 36–48

Manrique D, Marquez F, Rios J, Rodriguez-Paton A (2005) Grammar based crossover operator in genetic programming. In: Proceedings of the 1st international work-conference on the interplay between natural and artificial computation, part II, pp 252–261

O’Reilly U-M, Oppacher F (1994) Program search with a hierarchical variable length representation: genetic programming, simulated annealing and hill climbing. Lect Notes Comput Sci 866:397–406

Poli R, Langdon WB (1998) On the search properties of different crossover operators in genetic programming. In: Genetic programming 1998: proceedings of the third annual conference, pp 293–301

Rosca JP, Ballard DH (1995) Causality in genetic programming. In: Proceedings of the sixth international conference on genetic algorithms. Morgan Kaufmann, Menlo Park, pp 256–263

Sherrah JR, Bogner RE, Bouzerdoum A (1997) The evolutionary pre-processor: automatic feature extraction for supervised classification using genetic programming. In: Proceedings of 2nd international conference on genetic programming, pp 304–312

Smart W, Zhang M (2004) Probability based genetic programming for multiclass object classification. In: Proceedings of the 8th Pacific Rim international conference on artificial intelligence, pp 251–261

Song A, Ciesielski V, Williams H (2002) Texture classifiers generated by genetic programming. In: Proceedings of the congress on evolutionary computation. IEEE Press, USA, pp 243–248

Soule T, Foster JA (1997) Code size and depth flows in genetic programming. In: Koza JR, Deb K, Dorigo M, Fogel DB, Garzon M, Iba H, Riolo RL (eds) Genetic programming 1997: proceedings of the second annual conference, Stanford University, CA, USA. Morgan Kaufmann, Menlo Park, pp 313–320

Tackett WA (1993) Genetic programming for feature discovery and image discrimination. In: Proceedings of 5th international conference on genetic algorithms, pp 303–309

Tackett WA (1994) Recombination, selection, and the genetic construction of computer programs. PhD thesis, University of Southern California, Los Angeles, CA, USA

Teller A, Veloso M (1995) A controlled experiment: evolution for learning difficult image classification. In: Proceedings of 7th Portuguese conference on artificial intelligence, pp 165–176

Winkeler JF, Manjunath BS (1997) Genetic programming for object detection. In: Proceedings of 2nd international conference on genetic programming, pp 330–335

Xie H, Zhang M (2009) An analysis and evaluation of the saving capability and feasibility of backward-chaining evolutionary algorithms. In: The fourth Australian conference on artificial life. LNAI, vol 5865. Springer, Berlin, pp 63–72

Xie H, Zhang M, Andreae P (2006) A study of good predecessor programs for reducing fitness evaluation cost in genetic programming. In: Proceedings of the 2006 IEEE congress on evolutionary computation. IEEE Press, USA, pp 9211–9218

Xie H, Zhang M, Andreae P (2007) An analysis of constructive crossover and selection pressure in genetic programming. In: Proceedings of genetic and evolutionary computation conference, pp 1739–1746

Xie H, Zhang M, Andreae P, Johnston M (2008) Is the not-sampled issue in tournament selection critical? In: Proceedings of IEEE congress on evolutionary computation. IEEE Press, USA, pp 3711–3718

Yuen CC (2004) Selective crossover using gene dominance as an adaptive strategy for genetic programming. MSc Intelligent Systems, University College, London, UK

Zhang M, Ciesielski V, Andreae P (2003) A domain independent window-approach to multiclass object detection using genetic programming. EURASIP J Appl Signal Process 2003(8):841–859MATHCrossRef

Zhang M, Gao X, Lou W (2007) A new crossover operator in genetic programming for object classification. IEEE Trans Syst Man Cybern Part B 37(5):1332–1343CrossRef

Zhang M, Smart W (2004) Multiclass object classification using genetic programming. In: Applications of evolutionary computing, EvoWorkshops2004. LNCS, vol 3005. Springer, Berlin, pp 369–378

Title: Depth-control strategies for crossover in tree-based genetic programming
Authors: Huayang Xie
Mengjie Zhang
Publication date: 01-09-2011
Publisher: Springer-Verlag
Published in: Soft Computing / Issue 9/2011
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-011-0700-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 9/2011

Dynamic combinatorial optimisation problems: an analysis of the subset sum problem

Weighted local sharing and local clearing for multimodal optimisation

Improving the performance and scalability of Differential Evolution on problems exhibiting parameter interactions

Crossover can be constructive when computing unique input–output sequences

Fuzzy region assignment for visual tracking

Guest Editorial: special issue on evolutionary optimisation and learning

Premium Partner