Bloat is an excess of code growth without a corresponding improvement in fitness. This is a serious problem in Genetic Programming, often leading to the stagnation of the evolutionary process. Here we provide an extensive review of all the past and current theories regarding why bloat occurs. After more than 15 years of intense research, recent work is shedding new light on what may be the real reasons for the bloat phenomenon. We then introduce Dynamic Limits, our new approach to bloat control. It implements a dynamic limit that can be raised or lowered, depending on the best solution found so far, and can be applied either to the depth or size of the programs being evolved. Four problems were used as a benchmark to study the efficiency of Dynamic Limits. The quality of the results is highly dependent on the type of limit used: depth or size. The depth variants performed very well across the set of problems studied, achieving similar fitness to the baseline technique while using significantly smaller trees. Unlike many other methods available so far, Dynamic Limits does not require specific genetic operators, modifications in fitness evaluation or different selection schemes, nor does it add any parameters to the search process. Furthermore, its implementation is simple and its efficiency does not rely on the usage of a static upper limit. The results are discussed in the context of the newest bloat theory.
Genetic Programming and Evolvable Machines, Vol. 10, #2, pp. 141-179, June 2009
Cited by
Year 2012 : 7 citations
McDermott J, White DR, Luke S, Manzoni L, Castelli M, Vanneschi L, Jaskowski W, Krawiec K, Harper R, De Jong K, O'Reilly U-M (2012). Genetic Programming Needs Better Benchmarks. In Proc of Genetic and Evolutionary Computation Conference (GECCO 2012), 791-798.
Castelli M (2012). Measures and methods for robust genetic programming. PhD Thesis. University of Milano-Bicocca, Italy.
Darabos C, Giacobini M, Hu T, Moore, JH (2012). Lévy-Flight Genetic Programming: Towards a New Mutation Paradigm. European Conference on Evolutionary Computation, Machine Learning and Data Mining in Computational Biology (EvoBIO), 38-49.
Dabhi VK, Chaudhary S (2012). A Survey on Techniques of Improving Generalization Ability of Genetic Programming Solutions. arXiv preprint arXiv:1211.1119.
Trujillo L, Martinez Y, Galvan-Lopez E, Legrand P (2012). A comparison of predictive measures of problem difficulty for classification with Genetic Programming. Proceedings of ERA-2012.
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.
Trujillo L, Legrand P, Olague G, Lévy-Véhele J (2012). Evolving estimators of the pointwise Hölder exponent with Genetic Programming. Information Sciences 209: 61–79.
Year 2011 : 12 citations
Fraser G, Arcuri A (2011). Evolutionary Generation of Whole Test Suites. In 11th International Conference on Quality Software (QSIC 2011), 31–40.
Fraser G, Arcuri A (2011). It is not the length that matters, it is how you control it. In 2011 IEEE Fourth International Conference on Software Testing, Verification and Validation (ICST 2011), 150–159.
Gardner M-A, Gagné C, Parizeau M (2011). Bloat control in genetic programming with a histogram-based accept-reject method. In Proc 13th Genetic and Evolutionary Computation Conference, 187–188.
Helmuth T, Spector L, Martin B (2011). Size-based tournaments for node selection. In Proc 13th Genetic and Evolutionary Computation Conference, 799–802.
Kronberger G, Fink S, Kommenda M, Affenzeller M (2011). Macro-economic Time Series Modeling and Interaction Networks. In Proc EvoApplications 2011, 101-110.
Miller JF (2011). Cartesian Genetic Programming. Natural Computing Series. Springer.
Poli R, Salvaris M, Cinel Caterina (2011). Evolution of an Effective Brain-Computer Interface Mouse via Genetic Programming with Adaptive Tarpeian Bloat Control. In Genetic Programming Theory and Practice IX, 77–95.
Stokic I (2011). Primjena Genetskog Programiranja u Strojnom Ucenju. DIPLOMSKI RAD br. 213. Sveuciliste u Zagrebu, Fakultet Elektrotehnike I Racunarstva, Zagreb, Croatia.
Trujillo L (2011). Genetic programming with one-point crossover and subtree mutation for effective problem solving and bloat control. Soft Computing - A Fusion of Foundations, Methodologies and Applications 15(8): 1551–1567.
Trujillo L, Martinez Y, Melin P (2011). Estimating Classifier Performance with Genetic Programming. In Proc European Conference on Genetic Programming (EuroGP 2011), 274-285.
Trujillo L, Martinez Y, Galvan-Lopez E, Legrand P (2011). Predicting problem difficulty for genetic programming applied to data classification. In Proc Genetic and Evolutionary Computation Conference (GECCO 2011), 1355–1362.
Vanneschi L, Mussi L, Cagnoni S (2011). Hot topics in Evolutionary Computation. Intelligenza Artificiale 5(1): 5–17.
Year 2010 : 1 citations
HAJIRA JABEEN, ABDUL RAUF BAIG (2010). Review of Classification Using Genetic Programming. Hajira Jabeen et al. (eds). International Journal of Engineering Science and Technology, Vol.2 (2), 2010, pp. 94-103, 2010.
Year 2009 : 1 citations
Kinzett D, Johnston M, Zhang M. How Online Simplification Affects Building Blocks in Genetic Programming.
In Proc Genetic and Evolutionary Computation Conference (GECCO 2009), 979"986.
