Deep Genetic Programming Trees Are Robust
Article No.: 6, Pages 1 - 34
Abstract
We sample the genetic programming tree search space and show it is smooth, since many mutations on many test cases have little or no fitness impact. We generate uniformly at random high-order polynomials composed of 12,500 and 750,000 additions and multiplications and follow the impact of small changes to them. From information theory, 32 bit floating point arithmetic is dissipative, and even with 1,501 test cases, deep mutations seldom have any impact on fitness. Absolute difference between parent and child evaluation can grow as well as fall further from the code change location, but the number of disrupted fitness tests falls monotonically. In many cases, deeply nested expressions are robust to crossover syntax changes, bugs, errors, run time glitches, perturbations, and so on, because their disruption falls to zero, and so it fails to propagate beyond the program.
References
[1]
D. Andre and A. Teller. 1999. Evolving team darwin united. In Proceedings of the Robot Soccer World Cup II (RoboCup’98)(LNCS, Vol. 1604), M. Asada and H. Kitano (Eds.). Springer Verlag, 346–351.
[2]
Peter John Angeline. 1994. Genetic programming and emergent intelligence. In Advances in Genetic Programming, Kenneth E. Kinnear, Jr. (Ed.). MIT Press, Chapter 4, 75–98. Retrieved from http://cognet.mit.edu/sites/default/files/books/9780262277181/pdfs/9780262277181_chap4.pdf.
[3]
Per Bak, Chao Tang, and Kurt Wiesenfeld. 1987. Self-organized criticality: An explanation of the 1/f noise. Phys. Rev. Lett. 59 (July 1987), 381–384. Issue 4.
[4]
Ying Bi, Bing Xue, and Mengjie Zhang. 2020. Evolving deep forest with automatic feature extraction for image classification using genetic programming. In Proceedings of the 16th International Conference on Parallel Problem Solving from Nature, Part I(LNCS, Vol. 12269), Thomas Baeck, Mike Preuss, Andre Deutz, Hao Wang, Carola Doerr, Michael Emmerich, and Heike Trautmann (Eds.). Springer, 3–18.
[5]
Tobias Blickle. 1996. Theory of Evolutionary Algorithms and Application to System Synthesis. Ph.D. Dissertation. Swiss Federal Institute of Technology, Zurich, Switzerland. http://www.handshake.de/user/blickle/publications/diss.pdf.
[6]
David Clark, W. B. Langdon, and Justyna Petke. 2020. Software Robustness: A Survey, a Theory, and Some Prospects. Presented at Facebook Testing and Verification Symposium 2020. Retrieved from https://fbresearchevents.bevylabs.com/events/details/facebook-tav-symposium-division-facebook-testing-and-verification-symposium-presents-dress-rehearsal-facebook-tav-symposium-2020/.
[7]
Benjamin Danglot, Philippe Preux, Benoit Baudry, and Martin Monperrus. 2018. Correctness attraction: A study of stability of software behavior under runtime perturbation. Empir. Softw. Eng. 23, 4 (Aug. 2018), 2086–2119.
[8]
William Feller. 1957. An Introduction to Probability Theory and Its Applications (2 ed.). Vol. 1. John Wiley and Sons, New York.
[9]
Philippe Flajolet and Andrew Oldyzko. 1982. The average height of binary trees and other simple trees. J. Comput. Syst. Sci. 25, 2 (Oct. 1982), 171–213.
[10]
Edgar Galvan-Lopez, Stephen Dignum, and Riccardo Poli. 2008. The effects of constant neutrality on performance and problem hardness in GP. In Proceedings of the 11th European Conference on Genetic Programming (EuroGP’08)(Lecture Notes in Computer Science, Vol. 4971), Michael O’Neill, Leonardo Vanneschi, Steven Gustafson, Anna Isabel Esparcia Alcazar, Ivanoe De Falco, Antonio Della Cioppa, and Ernesto Tarantino (Eds.). Springer, 312–324.
[11]
Sylvain Gelly, Olivier Teytaud, Nicolas Bredeche, and Marc Schoenauer. 2005. A statistical learning theory approach of bloat. In Proceedings of the 2005 Conference on Genetic and Evolutionary Computation (GECCO’05), Hans-Georg Beyer et al. (Eds.), Vol. 2. ACM Press, 1783–1784.
[12]
Sylvain Gelly, Olivier Teytaud, Nicolas Bredeche, and Marc Schoenauer. 2006. Universal consistency and bloat in GP. Revue d’Intelligence Artificielle 20, 6 (2006), 805–827. Retrieved from http://hal.inria.fr/docs/00/11/28/40/PDF/riabloat.pdf.
[13]
Giovani Guizzo, Justyna Petke, Federica Sarro, and Mark Harman. 2021. Enhancing genetic improvement of software with regression test selection. In Proceedings of the International Conference on Software Engineering (ICSE’21), Arie van Deursen, Tao Xie, and Natalia Juristo Oscar Dieste (Eds.). IEEE, 1323–1333.
[14]
Nicolas Harrand, Simon Allier, Marcelino Rodriguez-Cancio, Martin Monperrus, and Benoit Baudry. 2019. A journey among Java neutral program variants. Genetic Programming and Evolvable Machines 20, 4 (Dec. 2019), 531–580.
[15]
Michael Hopkins, Mantas Mikaitis, Dave R. Lester, and Steve Furber. 2020. Stochastic rounding and reduced-precision fixed-point arithmetic for solving neuralordinary differential equations. Philos. Trans. A 378, 2166 (6 March 2020), 20190052.
[16]
Ting Hu, Marco Tomassini, and Wolfgang Banzhaf. 2020. A network perspective on genotype-phenotype mapping in genetic programming. Genetic Programming and Evolvable Machines 21, 3 (Sept. 2020), 375–397.
[17]
Hitoshi Iba. 1995. Random Tree Generation for Genetic Programming. Technical Report ETL-TR-95-35. ElectroTechnical Laboratory (ETL), 1-1-4 Umezono, Tsukuba-city, Ibaraki, 305, Japan. Retrieved from http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/iba_1995_rtgTR.pdf.
[18]
Hitoshi Iba. 1996. Random tree generation for genetic programming. In Parallel Problem Solving from Nature IV, Proceedings of the International Conference on Evolutionary Computation(LNCS, Vol. 1141), Hans-Michael Voigt, Werner Ebeling, Ingo Rechenberg, and Hans-Paul Schwefel (Eds.). Springer Verlag, Berlin, 144–153.
[19]
John R. Koza. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA. Retrieved from http://mitpress.mit.edu/books/genetic-programming.
[20]
W. B. Langdon. 1999. Size fair and homologous tree genetic programming crossovers. In Proceedings of the Genetic and Evolutionary Computation Conference, Wolfgang Banzhaf, Jason Daida, Agoston E. Eiben, Max H. Garzon, Vasant Honavar, Mark Jakiela, and Robert E. Smith (Eds.), Vol. 2. Morgan Kaufmann, 1092–1097. Retrieved from http://gpbib.cs.ucl.ac.uk/gecco1999/GP-405.pdf.
[21]
William B. Langdon. 2000. Size fair and homologous tree genetic programming crossovers. Genet. Program. Evolv. Mach. 1, 1/2 (Apr. 2000), 95–119.
[22]
W. B. Langdon. 2017. Long-Term Evolution of Genetic Programming Populations. Technical Report RN/17/05. University College, London, London, UK. Retrieved from http://www.cs.ucl.ac.uk/fileadmin/UCL-CS/research/Research_Notes/RN_17_05.pdf.
[23]
William B. Langdon. 2017. Long-term evolution of genetic programming populations. In Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO’17). ACM, Berlin, 235–236.
[24]
William B. Langdon. 2020. Fast Generation of Big Random Binary Trees. Technical Report RN/20/01. Computer Science, University College, London, Gower Street, London, UK. Retrieved from https://arxiv.org/abs/2001.04505.
[25]
William B. Langdon. 2021. Incremental Evaluation in Genetic Programming. In Proceedings of the 24th European Conference on Genetic Programming (EuroGP’21)(LNCS, Vol. 12691), Ting Hu, Nuno Lourenco, and Eric Medvet (Eds.). Springer Verlag, 229–246.
[26]
William B. Langdon, Afnan Al-Subaihin, and David Clark. 2022. Measuring failed disruption propagation in genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’22), Alma Rahat et al. (Eds.). ACM.
[27]
W. B. Langdon and W. Banzhaf. 2008. Repeated patterns in genetic programming. Natur. Comput. 7, 4 (Dec. 2008), 589–613.
[28]
William B. Langdon and Wolfgang Banzhaf. 2022. Long-term evolution experiment with genetic programming. Artific. Life 28, 2 (2022).
[29]
William B. Langdon and Justyna Petke. 2015. Software is not fragile. In Proceedings of the Complex Systems Digital Campus E-Conference (CS-DC’15) (Proceedings in Complexity), Pierre Parrend, Paul Bourgine, and Pierre Collet (Eds.). Springer, 203–211. Invited talk.
[30]
William B. Langdon, Justyna Petke, and David Clark. 2021. Dissipative polynomials. In Proceedings of the 5th Workshop on Landscape-Aware Heuristic Search (GECCO’21), Nadarajen Veerapen, Katherine Malan, Arnaud Liefooghe, Sebastien Verel, and Gabriela Ochoa (Eds.). ACM, 1683–1691.
[31]
William B. Langdon, Justyna Petke, and David Clark. 2021. Information Loss Leads to Robustness. IEEE Software Blog. Retrieved from http://blog.ieeesoftware.org/2021/09/information-loss-leads-to-robustness-w.html.
[32]
W. B. Langdon and R. Poli. 1997. Fitness causes bloat. In Soft Computing in Engineering Design and Manufacturing, P. K. Chawdhry, R. Roy, and R. K. Pant (Eds.). Springer-Verlag London, 13–22.
[33]
W. B. Langdon and R. Poli. 1998. Why ants are hard. In Proceedings of the 3rd Annual Conference on Genetic Programming, John R. Koza, Wolfgang Banzhaf, Kumar Chellapilla, Kalyanmoy Deb, Marco Dorigo, David B. Fogel, Max H. Garzon, David E. Goldberg, Hitoshi Iba, and Rick Riolo (Eds.). Morgan Kaufmann, 193–201. Retrieved from http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/papers/WBL.antspace_gp98.pdf.
[34]
W. B. Langdon and Riccardo Poli. 2002. Foundations of Genetic Programming. Springer-Verlag.
[35]
Mingyi Lim, Giovani Guizzo, and Justyna Petke. 2020. Impact of test suite coverage on overfitting in genetic improvement of software. In Proceedings of the 12th International Symposium on Search Based Software Engineering (SSBSE’20)(LNCS, Vol. 12420), Juan Pablo Galeotti and Bonita Sharif (Eds.). Springer, 188–203.
[36]
Sean Luke. 2009. Essentials of Metaheuristics (1st ed.). lulu.com. Retrieved from http://cs.gmu.edu/sean/book/metaheuristics/ Available at http://cs.gmu.edu/sean/books/metaheuristics/.
[37]
Ibrahim Mesecan, Daniel Blackwell, David Clark, Myra B. Cohen, and Justyna Petke. 2021. HyperGI: Automated detection and repair of information flow leakage. In Proceedings of the 36th IEEE/ACM International Conference on Automated Software Engineering, New Ideas and Emerging Results Track (ASE NIER’21), Hourieh Khalajzadeh and Jean-Guy Schneider (Eds.). Retrieved from https://arxiv.org/abs/2108.12075.
[38]
Martin Monperrus. 2017. Principles of antifragile software. In Proceedings of the 1st International Conference on the Art, Science and Engineering of Programming (Programming’17). ACM, New York, NY, Article 32, 4 pages.
[39]
Alberto Moraglio. 2007. Towards a Geometric Unification of Evolutionary Algorithms. Ph.D. Dissertation. Department of Computer Science, University of Essex, UK. Retrieved from http://eden.dei.uc.pt/moraglio/Thesis_final.pdf.
[40]
Justyna Petke. 2015. Constraints: The future of combinatorial interaction testing. In Proceedings of the IEEE/ACM 8th International Workshop on Search-Based Software Testing. 17–18.
[41]
Justyna Petke, Brad Alexander, Earl T. Barr, Alexander E. I. Brownlee, Markus Wagner, and David R. White. 2019. A survey of genetic improvement search spaces. In Proceedings of the 7th edition of GI @ GECCO 2019, Brad Alexander, Saemundur O. Haraldsson, Markus Wagner, and John R. Woodward (Eds.). ACM, 1715–1721.
[42]
Justyna Petke, David Clark, and William B. Langdon. 2021. Software robustness: A survey, a theory, and some prospects. In ESEC/FSE 2021, Ideas, Visions and Reflections, Paris Avgeriou and Dongmei Zhang (Eds.). ACM, 1475–1478.
[43]
Justyna Petke, Mark Harman, William B. Langdon, and Westley Weimer. 2018. Specialising software for different downstream applications using genetic improvement and code transplantation. IEEE Trans. Softw. Eng. 44, 6 (June 2018), 574–594.
[44]
Justyna Petke, Claire Le Goues, Stephanie Forrest, and William B. Langdon. 2018. Genetic improvement of software: Report from dagstuhl seminar 18052. Dagstuhl Rep. 8, 1 (23 July 2018), 158–182.
[45]
Justyna Petke, Shin Yoo, Myra B. Cohen, and Mark Harman. 2013. Efficiency and early fault detection with lower and higher strength combinatorial interaction testing. In Proceedings of the ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE’13), Bertrand Meyer, Luciano Baresi, and Mira Mezini (Eds.). ACM, 26–36.
[46]
Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee. 2008. A Field Guide to Genetic Programming. Retrieved from http://www.gp-field-guide.org.uk.
[47]
Nicholas J. Radcliff. 1993. Genetic set recombination. In Foundations of Genetic Algorithms 2, L. Darrell Whitley (Ed.). Morgan Kaufmann, 203–219.
[48]
Joseph Renzullo, Westley Weimer, Melanie Moses, and Stephanie Forrest. 2018. Neutrality and epistasis in program space. In Proceedings of the International Conference on Software Engineering Workshops (ICSE’18), Justyna Petke, Kathryn Stolee, William B. Langdon, and Westley Weimer (Eds.). ACM, 1–8.
[49]
Craig W. Reynolds. 1994. Evolution of corridor following behavior in a noisy world. In Simulation of Adaptive Behaviour (SAB-94), David Cliff, Phil Husbands, Jean-Arcady Meyer, and Stewart W. Wilson (Eds.). MIT Press, 402–410. Retrieved from http://www.red3d.com/cwr/papers/1994/sab94.pdf.
[50]
Robert Sedgewick and Philippe Flajolet. 1996. An Introduction to the Analysis of Algorithms. Addison-Wesley.
[51]
David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, Yutian Chen, Timothy P. Lillicrap, Fan Hui, Laurent Sifre, George van den Driessche, Thore Graepel, and Demis Hassabis. 2017. Mastering the game of Go without human knowledge. Nature 550, 7676 (2017), 354–359.
[52]
Andy Singleton. 1994. Genetic programming with C++. BYTE (Feb. 1994), 171–176. Retrieved from http://www.assembla.com/wiki/show/andysgp/GPQuick_Article.
[53]
Robert J. Smith and Malcolm I. Heywood. 2017. Coevolving deep hierarchies of programs to solve complex tasks. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’17). ACM, 1009–1016.
[54]
Eduardo D. Sontag. 1998. VC dimension of neural networks. In Neural Networks and Machine Learning. Springer, 69–95. Retrieved from http://www.sontaglab.org/FTPDIR/vc-expo.pdf.
[55]
Walter Alden Tackett. 1994. Recombination, Selection, and the Genetic Construction of Computer Programs. Ph.D. Dissertation. University of Southern California, Department of Electrical Engineering Systems. Retrieved from http://www.cs.ucl.ac.uk/staff/W.Langdon/ftp/ftp.io.com/papers/WAT_PHD_DissFull_USC94_Recombination_etc_Genetic_Construction_of_Computer_Programs.pdf.
[56]
W. A. van Aardt, A. S. Bosman, and K. M. Malan. 2017. Characterising neutrality in neural network error landscapes. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC’17), Jose A. Lozano (Ed.). IEEE, 1374–1381. DOI:
[57]
Leonardo Vanneschi, Yuri Pirola, and Philippe Collard. 2006. A quantitative study of neutrality in GP boolean landscapes. In Proceedings of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO’06), Maarten Keijzer et al. (Eds.), Vol. 1. ACM Press, Seattle, WA, 895–902.
[58]
Nadarajen Veerapen and Gabriela Ochoa. 2018. Visualising the global structure of search landscapes: Genetic improvement as a case study. Genetic Program. Evolv. Mach. 19, 3 (Sept. 2018), 317–349.
[59]
Jeffrey M. Voas. 1992. PIE: A dynamic failure-based technique. IEEE Trans. Softw. Eng. 18, 8 (Aug. 1992), 717–727.
[60]
Ladislaus von Bortkiewicz. 1898. Das Gesetz der Kleinen Zahlen. B.G. Teubner, Leipzig. Retrieved from https://archive.org/download/dasgesetzderklei00bortrich/dasgesetzderklei00bortrich.pdf. The Law of Small Numbers.
[61]
Michael D. Vose and Alden H. Wright. 1998. The simple genetic algorithm and the Walsh transform: Part I, theory. Evolution. Comput. 6, 3 (1998), 253–273.
[62]
Thomas Weise. 2008. Global Optimization Algorithms—Theory Application (2nd ed.). Retrieved from http://www.it-weise.de/projects/book.pdf.
[63]
Alden H. Wright and Cheyenne L. Laue. 2021. Evolvability and complexity properties of the digital circuit genotype-phenotype map. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO’21), Francisco Chicano et al. (Eds.). ACM, 840–848.
[64]
Sewall Wright. 1932. The roles of mutation, inbreeding, crossbreeding and selection in evolution. In Proceedings of the 6th Annual Congress of Genetics. 356–366. Retrieved from http://www.blackwellpublishing.com/ridley/classictexts/wright.pdf.
[65]
George Kingsley Zipf. 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley Press, Cambridge, MA.
Index Terms
- Deep Genetic Programming Trees Are Robust
Index terms have been assigned to the content through auto-classification.
Recommendations
Failed disruption propagation in integer genetic programming
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference CompanionWe inject a random value into the evaluation of highly evolved deep integer GP trees 9 743 720 times and find 99.7% of test outputs are unchanged. Suggesting crossover and mutation's impact are dissipated and seldom propagate outside the program. Indeed ...
Dissipative polynomials
GECCO '21: Proceedings of the Genetic and Evolutionary Computation Conference CompanionLimited precision floating point computer implementations of large polynomial arithmetic expressions are nonlinear and dissipative. They are not reversible (irreversible, lack conservation), lose information, and so are robust to perturbations (anti-...
Genetic programming convergence
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference CompanionWe study both genotypic and phenotypic convergence in GP floating point continuous domain symbolic regression over thousands of generations. Subtree fitness variation across the population is measured and shown in many cases to fall. In an expanding ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2022
125 pages
EISSN:2688-3007
DOI:10.1145/3544008
- Editors:
- Juergen Branke,
- Manuel López-Ibáñez
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 August 2022
Online AM: 01 June 2022
Accepted: 01 May 2022
Revised: 01 May 2022
Received: 01 September 2021
Published in TELO Volume 2, Issue 2
Check for updates
Author Tags
- Heritability
- information theory
- information funnels
- sandpile 1/f powerlaw
- self-organised criticality
- SOC
- self-similar fractal
- GP fitness landscape
- evolvability
- mutational robustness
- neutral networks
- SBSE
- software robustness
- correctness attraction
- diversity
- software testing
- theory of bloat
- introns
- error hiding
- invisible faults
- failed disruption propagation
- FDP
- FEP
Qualifiers
- Research-article
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 360Total Downloads
- Downloads (Last 12 months)57
- Downloads (Last 6 weeks)8
Reflects downloads up to 25 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in