CISUC - Dynamic Maximum Tree Depth - A Simple Technique for Avoiding Bloat in Tree-Based GP
CISUC

Dynamic Maximum Tree Depth - A Simple Technique for Avoiding Bloat in Tree-Based GP

Authors

Abstract

We present a technique, designated as dynamic maximum tree depth, for avoiding excessive growth of tree-based GP individuals during the evolutionary process. This technique introduces a dynamic tree depth limit, very similar to the Koza-style strict limit except in two aspects: it is initially set with a low value; it is increased when needed to accomodate an individual that is deeper than the limit but is better than any other individual found during the run. The results show that the dynamic maximum tree depth technique efficiently avoids the growth of trees beyond the necessary size to solve the problem, maintaining the ability to find individuals with good fitness values. When compared to lexicographic parsimony pressure, dynamic maximum tree depth proves to be significantly superior. When both techniques are coupled, the results are even better.

Keywords

genetic programming, bloat, code growth, introns, tree depth

Subject

Genetic Programming

Conference

Genetic and Evolutionary Computation Conference (GECCO-2003), July 2003

PDF File


Cited by

Year 2013 : 1 citations

 Havlicek V, Hanel M, Maca P, Kuraz M, Pech P (2013). Incorporating basic hydrological concepts into genetic programming for rainfall-runoff forecasting. Computing. DOI 10.1007/s00607-013-0298-0

Year 2012 : 2 citations

 Allaeys F (2012). Ontwikkeling van evolutionaire compacte robotsturingen en hun morfologie. MSc Thesis. University of Ghent, Belgium.

 Ragalo AW (2012). A building block conservation and extension mechanism for improved performance in Polynomial Symbolic Regression tree-based Genetic Programming. Fourth World Congress on Nature and Biologically Inspired Computing (NaBIC), 123-129.

Year 2011 : 1 citations

 Ni J, Drieberg RH, Rockett PI (2011). The Use of an Analytic Quotient Operator in Genetic Programming. IEEE Transactions on Evolutionary Computation, to appear.

Year 2010 : 4 citations

 Badran K, Rockett PI (2010). The influence of mutation on population dynamics in multiobjective genetic programming. Genetic Programming and Evolvable Machines 11(1): 5-33.

 Trujillo L, Legrand P, Lévy-Véhel J (2010). The estimation of holderian regularity using genetic programming. GECCO-2010, pp. 861-868, ACM 2010.

 Beikia M, Basharib A, Majdia A (2010). Genetic programming approach for estimating the deformation modulus of rock mass using sensitivity analysis by neural network. International Journal of Rock Mechanics and Mining Sciences, 47(7): 1091--1103.

 Whigham PA, Dick G (2010). Implicitly Controlling Bloat in Genetic Programming. IEEE Transactions on Evolutionary Computation, 14(2): 173--190.

Year 2009 : 9 citations

 Amil NM, Bredeche N, Gagné C, Gelly S, Schoenauer M, Teytaud O (2009). A Statistical Learning Perspective of Genetic Programming. In Proc 12th European Conference on Genetic Programming (EuroGP) at EvoStar 2009, 327"338.

 Liu K-H, Xu C-G (2009). A genetic programming-based approach to the classification of multiclass microarray datasets. Bioinformatics 2009 25(3):331"337.

 Kouchakpour P, Zaknich A, Braunl T (2009). A survey and taxonomy of performance improvement of canonical genetic programming. Knowledge and Information Systems 21(1): 1-39.

 Kumar R, Bal BK, Rockett PI (2009). Multiobjective Genetic Programming Approach to Evolving Heuristics for the Bounded Diameter Minimum Spanning Tree Problem. In Proc Genetic and Evolutionary Computation Conference (GECCO 2009), 309"316.

 Soleimani-B H, Lucas C (2009). Input Variable Generation for Long Term Prediction of EEG Signal Using Genetic Programming. Proceedings of the Seventh International Conference on Computer Science and Information Technologies (CSIT 2009), 239-242.

 Xu C-G, Liu K-H, Huang D-S (2009). The analysis of microarray datasets using a genetic programming. Proceedings of the 6th Annual IEEE conference on Computational Intelligence in Bioinformatics and Computational Biology, 176-181.

 Zhang L, Nandi AK (2009). Diversity-preserving non-destructive operators in genetic programming and their application to breast cancer diagnosis. Transactions of the Institute of Measurement and Control 31(6): 533-550.

 White DR (2009). Genetic programming for low-resource systems. PhD Thesis, University of York, UK.

 Beadle LCJ (2009). Semantic and structural analysis of genetic programming. PhD Thesis, University of Kent, UK.

Year 2008 : 6 citations

 Poli R, Langdon WB, McPhee NF (2008). A Field Guide to Genetic Programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk (With contributions by J.R. Koza).

 William E, Northern J (2008). Genetic Programming Lab (GPLab) Tool Set Version 3.0. In Proc 2008 IEEE Region 5 Conference, 1"6.

 Luerssen MH, Powers DMW (2008). Evolving encapsulated programs as shared grammars. Genetic Programming and Evolvable Machines, 9(3): 203"228.

 Poli R, McPhee NF, Vanneschi L (2008). The impact of population size on code growth in GP: analysis and empirical validation. In Proc Genetic and Evolutionary Computation Conference (GECCO 2008), 1275"1282.

 Kouchakpour P (2008). Population Variation in Canonical Tree-based Genetic Programming. PhD Thesis, School of Electrical, Electronic and Computer Engineering, University of Western Australia. Nedlands, Perth, Western Australia.

 Xu C-G, Liu K-H (2008). A GP Based Approach to the Classification of Multiclass Microarray Datasets. In Advanced Intelligent Computing Theories and Applications. With Aspects of Artificial Intelligence, 340-346.

Year 2007 : 7 citations

 Zhang L, Nandi AK (2007). Neutral offspring controlling operators in genetic programming. Pattern Recognition, 40(10): 2696"2705.

 Khan A, Mirza AM (2007). Genetic perceptual shaping: Utilizing cover image and conceivable attack information during watermark embedding. Information Fusion 8(4): 354"365.

 Couchet J, Manrique D, Rios J, Rodriguez-Paton A (2007). Crossover and mutation operators for grammar-guided genetic programming. Soft Computing 11(10): 943"955.

 Brazdilova SL (2007). Towards reliable autofocusing in automated microscopy. In Proc Fourth International Conference on Informatics in Control, Automation and Robotics, Intelligent Control Systems and Optimization (ICINCO 2007), 440"447.

 Chaudhry A, Khan A, Ali A, Mirza AM (2007). A hybrid image restoration approach: Using fuzzy punctual kriging and genetic programming. International Journal of Imaging Systems and Technology 17(4): 224"231.

 Teytaud O (2007). Slightly Beyond Turing's Computability for Studying Genetic Programming. In Proc Fifth International Conference on Machines, Computations, and Universality, 279"290.

 Day P, Nandi AK (2007). Robust Text-Independent Speaker Verification Using Genetic Programming. IEEE Transactions on Audio, Speech, and Language Processing 15(1): 285"295.

Year 2006 : 11 citations

 Sylvain Gelly, Olivier Teytaud, Nicolas Bredeche and Schoenauer M (2006). Universal Consistency and Bloat in GP. Revue d"Intelligence Artificielle 20(6): 805"827.

 Gagne C, Schoenauer M, Parizeau M, Tomassini M (2006). Genetic Programming, Validation Sets, and Parsimony Pressure. In Proc 9th European Conference on Genetic Programming (EuroGP 2006), 109"120.

 Teytaud O (2006). Why Simulation-Based Approachs with Combined Fitness are a Good Approach for Mining Spaces of Turing-equivalent functions. In Proc 2006 IEEE Congress on Evolutionary Computation (CEC 2006), 283"290.

 Khan A, Mirza AM, Majid A (2006). Intelligent perceptual shaping of a digital watermark: Exploiting Characteristics of human visual system. International Journal of Knowledge-Based and Intelligent Engineering Systems 10(3): 213"223.

 Khan A (2006). A novel approach to decoding: Exploiting anticipated attack information using genetic programming. International Journal of Knowledge-Based and Intelligent Engineering Systems 10(5): 337"346.

 Costa EO (2006). Proposta de um Algoritmo de Programação Genética Baseado em Estratégias Evolucionárias. MSc Thesis, Universidade Federal do Paraná, Curitiba, Brasil.

 Luke S, Panait L (2006). A Comparison of Bloat Control Methods for Genetic Programming. Evolutionary Computation 14(3): 309"344.

 Crane EF, McPhee NF (2006). The Effects of Size and Depth Limits on Tree Based Genetic Programming. In Genetic Programming Theory and Practice III, 223"240.

 Shuhua Z, Qian G, Jianguo S (2006). Genetic Programming Approach for Predicting Surface Subsidence Induced by Mining. Journal of China University of Geosciences 17(4): 361"366.

 Brazdilova SL (2006). Autofocusing in Automated Microscopy. RNDr Thesis, Masaryk University, Faculty of Informatics, Czech Republic.

 Zhang Y, Chen H (2006). Improved Approach of Genetic Programming and Applications for Data Mining. In Proc Second International Conference on Natural Computation, 816"819.

Year 2005 : 7 citations

 Daida JM (2005). Towards Identifying Populations that Increase the Likelihood of Sucess in Genetic Programming. In Proc Genetic and Evolutionary Computation Conference (GECCO 2005), 1627"1634.

 Gelly S, Teytaud O, Bredeche N, Schoenauer M (2005). A statistical learning theory approach of bloat. In Proc Genetic and Evolutionary Computation Conference (GECCO 2005), 1783"1784.

 Luerssen MH (2005). Graph Grammar Encoding and Evolution of Automata Networks. In Proc 28th Australasian Computer Science Conference (ACSC 2005), 229"238.

 Teytaud O, Gelly S, Bredeche N, Schoenauer M (2005). Apprentissage statistique et programmation génétique: la croissance du code est-elle inévitable? Conférence d'Apprentissage (CAP 2005), 163"178.

 Washbrook B, Li J (2005). The Application of Evolutionary Computation to the Analysis of the Profiles of Elliptical Galaxies: A Maximum Likelihood Approach. In Proc 2005 IEEE Congress on Evolutionary Computation (CEC 2005), 2607"2612.

 Manrique D, Marquez F, RiosJ, Rodriguez-Paton A (2005). Grammar Based Crossover Operator in Genetic Programming. In Proc First International Work-Conference on the Interplay Between Natural and Artificial Computation (IWINAC 2005), 252"261.

 Jakobovic D (2005). Rasporedivanje Zasnovano na Prilagodljivim Pravilima (Monitor-based multithreaded embedded systems). PhD Thesis, Faculty of Electrical Engineering and Computing, University of Zagreb, Croatia.

Year 2004 : 3 citations

 Panait L, Luke S (2004). Alternative Bloat Control Methods. In Proc Genetic and Evolutionary Computation Conference (GECCO 2004), 630"641.

 McPhee NF, Jarvis A, Crane EF. On the Strength of Size Limits in Linear Genetic Programming. In Proc Genetic and Evolutionary Computation Conference (GECCO 2004), 593"604.

 Barlow GJ (2004). Design of Autonomous Navigation Controllers for Unmanned Aerial Vehicles Using Multi-objective Genetic Programming. MSc Thesis, North Carolina State University.