Operator equalisation, bloat and overfitting: a study on human oral bioavailability prediction

ABSTRACT

Operator equalisation was recently proposed as a new bloat control technique for genetic programming. By controlling the distribution of program lengths inside the population, it can bias the search towards smaller or larger programs. In this paper we propose a new implementation of operator equalisation and compare it to a previous version, using a hard real-world regression problem where bloat and overfitting are major issues. The results show that both implementations of operator equalisation are completely bloat-free, producing smaller individuals than standard genetic programming, without compromising the generalization ability. We also show that the new implementation of operator equalisation is more efficient and exhibits a more predictable and reliable behavior than the previous version. We advance some arguable ideas regarding the relationship between bloat and overfitting, and support them with our results.

REFERENCES

• 1: Francesco Archetti , Stefano Lanzeni , Enza Messina , Leonardo Vanneschi, Genetic programming for computational pharmacokinetics in drug discovery and development, Genetic Programming and Evolvable Machines, v.8 n.4, p.413-432, December 2007 [doi>10.1007/s10710-007-9040-z]
• 2: Stephen Dignum , Riccardo Poli, Generalisation of the limiting distribution of program sizes in tree-based genetic programming and analysis of its effects on bloat, Proceedings of the 9th annual conference on Genetic and evolutionary computation, July 07-11, 2007, London, England [doi>10.1145/1276958.1277277]
• 3: S. Dignum and R. Poli. Crossover, sampling, bloat and the harmful effects of size limits. In M. O'Neill, et al., editors, Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, pages 158--169, Naples, 26-28 Mar. 2008. Springer.
• 4: S. Dignum and R. Poli. Operator equalisation and bloat free GP. In M. O'Neill, et al., editors, Proceedings of the 11th European Conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, pages 110--121, Naples, 26--28 Mar. 2008. Springer.
• 5: Francesco Archetti , Stefano Lanzeni , Enza Messina , Leonardo Vanneschi, Genetic programming for human oral bioavailability of drugs, Proceedings of the 8th annual conference on Genetic and evolutionary computation, July 08-12, 2006, Seattle, Washington, USA [doi>10.1145/1143997.1144042]
• 6: F. Yoshida and J. G. Topliss. QSAR model for drug human oral bioavailability. Journal of Medicinal Chemistry, 43:2575--2585, 2000.
• 7: H. Van de Waterbeemd and S. Rose. In The Practice of Medicinal Chemistry, 2nd edition. ed. Wermuth, L. G., 1367--1385,Academic Press, 2003.
• 8: I. Kola and J. Landis. Can the pharmaceutical industry reduce attrition rates? Nature Reviews Drug Discovery, 3:711--716, 2004.
• 9: C. Igel and K. Chellapilla. Investigating the influence of depth and degree of genotypic change on fitness in genetic programming. In W. Banzhaf, et al., editors, Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, pages 1061--1068, Orlando, Florida, USA, 13--17 July 1999. Morgan Kaufmann.
• 10: John R. Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992
• 11: Foundations of genetic programming, Springer-Verlag New York, Inc., New York, NY, 2002
• 12: Sean Luke, Modification point depth and genome growth in genetic programming, Evolutionary Computation, v.11 n.1, p.67-106, Spring 2003 [doi>10.1162/106365603321829014]
• 13: Sean Luke , Liviu Panait, Lexicographic Parsimony Pressure, Proceedings of the Genetic and Evolutionary Computation Conference, p.829-836, July 09-13, 2002
• 14: Pedro Domingos, The Role of Occam‘s Razor in Knowledge Discovery, Data Mining and Knowledge Discovery, v.3 n.4, p.409-425, December 1999 [doi>10.1023/A:1009868929893]
• 15: R. Poli, W. B. Langdon, and S. Dignum. On the limiting distribution of program sizes in tree-based genetic programming. In M. Ebner, et al., editors, Proceedings of the 10th European Conference on Genetic Programming, volume 4445 of Lecture Notes in Computer Science, pages 193--204, Valencia, Spain, 11-13 Apr. 2007. Springer.
• 16: Riccardo Poli , Nicholas Freitag McPhee , Leonardo Vanneschi, The impact of population size on code growth in GP: analysis and empirical validation, Proceedings of the 10th annual conference on Genetic and evolutionary computation, July 12-16, 2008, Atlanta, GA, USA [doi>10.1145/1389095.1389341]
• 17: R. Poli, W. B. Langdon, and N. F. McPhee. A field guide to genetic programming. Published via http://lulu.com and freely available at http://www.gp-field-guide.org.uk, 2008. (With contributions by J. R. Koza).
• 18: R. Todeschini and V. Consonni. Handbook of Molecular Descriptors. Wiley-VCH, Weinheim, 2000.
• 19: J. Rissanen. Modeling by shortest data description. Automatica, 14:465--471, 1978.
• 20: Justinian P. Rosca, Generality versus size in genetic programming, Proceedings of the First Annual Conference on Genetic Programming, July 28-31, 1996, Stanford, California
• 21: S. David, Wishart, C. Knox, A. C. Guo, S. Shrivastava, M. Hassanali,P. Stothard, Z. Chang and J. Woolsey. DrugBank: a comprehensive resource for in silico drug discovery and exploration. Nucleic Acids Research, 34:doi:10.1093/nar/gkj067, 2006.
• 22: S. Silva. GPLAB -- a genetic programming toolbox for MATLAB, version 3.0, 2007. http://gplab.sourceforge.net.
• 23: S. Silva and J. Almeida. Dynamic maximum tree depth. In E. Cantú-Paz, et al., editors, Genetic and Evolutionary Computation -- GECCO--2003, volume 2724 of LNCS, pages 1776---1787, Chicago, 12-16 July 2003. Springer--Verlag.
• 24: Sara Silva , Ernesto Costa, Dynamic limits for bloat control in genetic programming and a review of past and current bloat theories, Genetic Programming and Evolvable Machines, v.10 n.2, p.141-179, June 2009 [doi>10.1007/s10710-008-9075-9]
• 25: Sara Silva , Stephen Dignum, Extending Operator Equalisation: Fitness Based Self Adaptive Length Distribution for Bloat Free GP, Proceedings of the 12th European Conference on Genetic Programming, April 15-17, 2009, Tübingen, Germany [doi>10.1007/978-3-642-01181-8_14]
• 26: Simulation Plus Inc. a company that use both statistical methods and differential equations based simulations for ADME parameter estimation., 2006. See www.simulationsplus.com.
• 27: T. Kennedy. Managing the drug discovery/development interface. Drug Discovery Today, 2:436--444, 1997.
• 28: L. Vanneschi, M. Tomassini, P. Collard, and M. Clergue. Fitness distance correlation in structural mutation genetic programming. In C. Ryan, et al., editors, Genetic Programming, Proceedings of EuroGP'2003, volume 2610 of LNCS, pages 455--464, Essex, 14-16 Apr. 2003. Springer-Verlag.
• 29: W. B. Langdon and S. J. Barrett. Genetic Programming in data mining for drug discovery. in Evolutionary computing in data mining, pages 211--235, 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.2 Automatic Programming

General Terms:
Algorithms

Keywords:
bloat, genetic programming, human oral bioavailability, operator equalisation, overfitting, real-world application, regression