{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:14:54Z","timestamp":1750220094527,"version":"3.41.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2022,6,30]],"date-time":"2022-06-30T00:00:00Z","timestamp":1656547200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>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\u00a0bit 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.<\/jats:p>","DOI":"10.1145\/3539738","type":"journal-article","created":{"date-parts":[[2022,6,1]],"date-time":"2022-06-01T11:17:18Z","timestamp":1654082238000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Deep Genetic Programming Trees Are Robust"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6388-4160","authenticated-orcid":false,"given":"William B.","family":"Langdon","sequence":"first","affiliation":[{"name":"Department of Computer Science, University College London, London, UK"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,8,16]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-48422-1_28"},{"key":"e_1_3_3_3_2","first-page":"75","volume-title":"Advances in Genetic Programming","author":"Angeline Peter John","year":"1994","unstructured":"Peter John Angeline. 1994. Genetic programming and emergent intelligence. In Advances in Genetic Programming, Kenneth E. Kinnear, Jr. (Ed.). MIT Press, Chapter 4, 75\u201398. Retrieved from http:\/\/cognet.mit.edu\/sites\/default\/files\/books\/9780262277181\/pdfs\/9780262277181_chap4.pdf."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.59.381"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-58112-1_1"},{"key":"e_1_3_3_6_2","volume-title":"Theory of Evolutionary Algorithms and Application to System Synthesis","author":"Blickle Tobias","year":"1996","unstructured":"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."},{"key":"e_1_3_3_7_2","article-title":"Software Robustness: A Survey, a Theory, and Some Prospects","author":"Clark David","year":"2020","unstructured":"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\/.","journal-title":"Presented at Facebook Testing and Verification Symposium 2020"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10664-017-9571-8"},{"key":"e_1_3_3_9_2","volume-title":"An Introduction to Probability Theory and Its Applications (2 ed.)","author":"Feller William","year":"1957","unstructured":"William Feller. 1957. An Introduction to Probability Theory and Its Applications (2 ed.). Vol. 1. John Wiley and Sons, New York."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90004-6"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-78671-9_27"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/1068009.1068309"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.3166\/ria.20.805-827"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICSE43902.2021.00120"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10710-019-09355-3"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsta.2019.0052"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10710-020-09379-0"},{"key":"e_1_3_3_18_2","volume-title":"Random Tree Generation for Genetic Programming","author":"Iba Hitoshi","year":"1995","unstructured":"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."},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61723-X_978"},{"key":"e_1_3_3_20_2","volume-title":"Genetic Programming: On the Programming of Computers by Means of Natural Selection","author":"Koza John R.","year":"1992","unstructured":"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."},{"key":"e_1_3_3_21_2","first-page":"1092","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","volume":"2","author":"Langdon W. B.","year":"1999","unstructured":"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\u20131097. Retrieved from http:\/\/gpbib.cs.ucl.ac.uk\/gecco1999\/GP-405.pdf."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1010024515191"},{"key":"e_1_3_3_23_2","volume-title":"Long-Term Evolution of Genetic Programming Populations","author":"Langdon W. B.","year":"2017","unstructured":"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."},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3067695.3075965"},{"key":"e_1_3_3_25_2","volume-title":"Fast Generation of Big Random Binary Trees","author":"Langdon William B.","year":"2020","unstructured":"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."},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-72812-0_15"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/3512290.3528738"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11047-007-9038-8"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1162\/artl_a_00360"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-45901-1_24"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3449726.3463147"},{"key":"e_1_3_3_32_2","article-title":"Information Loss Leads to Robustness","author":"Langdon William B.","year":"2021","unstructured":"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.","journal-title":"IEEE Software Blog"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4471-0427-8_2"},{"key":"e_1_3_3_34_2","first-page":"193","volume-title":"Proceedings of the 3rd Annual Conference on Genetic Programming","author":"Langdon W. B.","year":"1998","unstructured":"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\u2013201. Retrieved from http:\/\/www.cs.ucl.ac.uk\/staff\/W.Langdon\/ftp\/papers\/WBL.antspace_gp98.pdf."},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-04726-2"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59762-7_14"},{"key":"e_1_3_3_37_2","volume-title":"Essentials of Metaheuristics (1st ed.)","author":"Luke Sean","year":"2009","unstructured":"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\/."},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the 36th IEEE\/ACM International Conference on Automated Software Engineering, New Ideas and Emerging Results Track (ASE NIER\u201921)","author":"Mesecan Ibrahim","year":"2021","unstructured":"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\u201921), Hourieh Khalajzadeh and Jean-Guy Schneider (Eds.). Retrieved from https:\/\/arxiv.org\/abs\/2108.12075."},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3079368.3079412"},{"key":"e_1_3_3_40_2","volume-title":"Towards a Geometric Unification of Evolutionary Algorithms","author":"Moraglio Alberto","year":"2007","unstructured":"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."},{"key":"e_1_3_3_41_2","doi-asserted-by":"publisher","DOI":"10.1109\/SBST.2015.11"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3319619.3326870"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1145\/3468264.3473133"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSE.2017.2702606"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.4230\/DagRep.8.1.158"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2491411.2491436"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.5555\/1796422"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-08-094832-4.50019-2"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3194810.3194812"},{"key":"e_1_3_3_50_2","first-page":"402","volume-title":"Simulation of Adaptive Behaviour (SAB-94)","author":"Reynolds Craig W.","year":"1994","unstructured":"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\u2013410. Retrieved from http:\/\/www.red3d.com\/cwr\/papers\/1994\/sab94.pdf."},{"key":"e_1_3_3_51_2","doi-asserted-by":"publisher","DOI":"10.5555\/227351"},{"key":"e_1_3_3_52_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature24270"},{"key":"e_1_3_3_53_2","first-page":"171","article-title":"Genetic programming with C++","author":"Singleton Andy","year":"1994","unstructured":"Andy Singleton. 1994. Genetic programming with C++. BYTE (Feb. 1994), 171\u2013176. Retrieved from http:\/\/www.assembla.com\/wiki\/show\/andysgp\/GPQuick_Article.","journal-title":"BYTE"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3071178.3071316"},{"key":"e_1_3_3_55_2","first-page":"69","volume-title":"Neural Networks and Machine Learning","author":"Sontag Eduardo D.","year":"1998","unstructured":"Eduardo D. Sontag. 1998. VC dimension of neural networks. In Neural Networks and Machine Learning. Springer, 69\u201395. Retrieved from http:\/\/www.sontaglab.org\/FTPDIR\/vc-expo.pdf."},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.5555\/222025"},{"key":"e_1_3_3_57_2","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2017.7969464"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.1145\/1143997.1144152"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10710-018-9328-1"},{"key":"e_1_3_3_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.153381"},{"key":"e_1_3_3_61_2","volume-title":"Das Gesetz der Kleinen Zahlen","author":"Bortkiewicz Ladislaus von","year":"1898","unstructured":"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."},{"key":"e_1_3_3_62_2","doi-asserted-by":"publisher","DOI":"10.1162\/evco.1998.6.3.253"},{"key":"e_1_3_3_63_2","volume-title":"Global Optimization Algorithms\u2014Theory Application (2nd ed.)","author":"Weise Thomas","year":"2008","unstructured":"Thomas Weise. 2008. Global Optimization Algorithms\u2014Theory Application (2nd ed.). Retrieved from http:\/\/www.it-weise.de\/projects\/book.pdf."},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459393"},{"key":"e_1_3_3_65_2","first-page":"356","volume-title":"Proceedings of the 6th Annual Congress of Genetics","author":"Wright Sewall","year":"1932","unstructured":"Sewall Wright. 1932. The roles of mutation, inbreeding, crossbreeding and selection in evolution. In Proceedings of the 6th Annual Congress of Genetics. 356\u2013366. Retrieved from http:\/\/www.blackwellpublishing.com\/ridley\/classictexts\/wright.pdf."},{"key":"e_1_3_3_66_2","volume-title":"Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology","author":"Zipf George Kingsley","year":"1949","unstructured":"George Kingsley Zipf. 1949. Human Behavior and the Principle of Least Effort: An Introduction to Human Ecology. Addison-Wesley Press, Cambridge, MA."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3539738","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3539738","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:02Z","timestamp":1750183802000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3539738"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,30]]},"references-count":65,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3539738"],"URL":"https:\/\/doi.org\/10.1145\/3539738","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"type":"print","value":"2688-299X"},{"type":"electronic","value":"2688-3007"}],"subject":[],"published":{"date-parts":[[2022,6,30]]},"assertion":[{"value":"2021-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}