{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,17]],"date-time":"2026-08-17T15:45:43Z","timestamp":1786981543292,"version":"build-2736575974"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,29]],"date-time":"2019-10-29T00:00:00Z","timestamp":1572307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["1789003"],"award-info":[{"award-number":["1789003"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Nat Comput"],"published-print":{"date-parts":[[2021,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We introduce the concept of Semantic Neutral Drift (SND) for genetic programming (GP), where we exploit equivalence laws to design semantics preserving mutations guaranteed to preserve individuals\u2019 fitness scores. A number of digital circuit benchmark problems have been implemented with rule-based graph programs and empirically evaluated, demonstrating quantitative improvements in evolutionary performance. Analysis reveals that the benefits of the designed SND reside in more complex processes than simple growth of individuals, and that there are circumstances where it is beneficial to choose otherwise detrimental parameters for a GP system if that facilitates the inclusion of SND.<\/jats:p>","DOI":"10.1007\/s11047-019-09772-4","type":"journal-article","created":{"date-parts":[[2019,10,30]],"date-time":"2019-10-30T18:20:09Z","timestamp":1572459609000},"page":"127-143","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Evolving graphs with semantic neutral drift"],"prefix":"10.1007","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5036-3358","authenticated-orcid":false,"given":"Timothy","family":"Atkinson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1148-822X","authenticated-orcid":false,"given":"Detlef","family":"Plump","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3146-5401","authenticated-orcid":false,"given":"Susan","family":"Stepney","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,10,29]]},"reference":[{"key":"9772_CR1","doi-asserted-by":"publisher","unstructured":"Atkinson T, Plump D, Stepney S (2018a) Evolving graphs by graph programming. In: Proceedings of 21st European conference on genetic programming (EuroGP 2018), LNCS, vol. 10781. Springer, pp 35\u201351. https:\/\/doi.org\/10.1007\/978-3-319-77553-1_3","DOI":"10.1007\/978-3-319-77553-1_3"},{"key":"9772_CR2","doi-asserted-by":"publisher","unstructured":"Atkinson T, Plump D, Stepney S (2018b) Probabilistic graph programs for randomised and evolutionary algorithms. In: Proceedings of 10th international conference on graph transformation, LNCS, vol. 10887. Springer, pp 63\u201378. https:\/\/doi.org\/10.1007\/978-3-319-92991-0_5","DOI":"10.1007\/978-3-319-92991-0_5"},{"key":"9772_CR3","doi-asserted-by":"publisher","unstructured":"Banzhaf W (1994) Genotype\u2013phenotype-mapping and neutral variation\u2014a case study in genetic programming. In: Proceedings of 3rd international conference on parallel problem solving from nature, LNCS, vol. 866. Springer, pp 322\u2013332. https:\/\/doi.org\/10.1007\/3-540-58484-6_276","DOI":"10.1007\/3-540-58484-6_276"},{"key":"9772_CR4","unstructured":"Barnett L (1998) Ruggedness and neutrality; the NKp family of fitness landscapes. In: Proceedings of 6th international conference on artificial life. MIT Press, pp 18\u201327. http:\/\/dl.acm.org\/citation.cfm?id=286139.286143"},{"key":"9772_CR5","first-page":"445","volume":"2","author":"DM Chickering","year":"2002","unstructured":"Chickering DM (2002) Learning equivalence classes of Bayesian-network structures. J Mach Learn Res 2:445\u2013498","journal-title":"J Mach Learn Res"},{"issue":"4","key":"9772_CR6","doi-asserted-by":"publisher","first-page":"043016","DOI":"10.1088\/1367-2630\/13\/4\/043016","volume":"13","author":"B Coecke","year":"2011","unstructured":"Coecke B, Duncan R (2011) Interacting quantum observables: categorical algebra and diagrammatics. New J Phys 13(4):043016. https:\/\/doi.org\/10.1088\/1367-2630\/13\/4\/043016","journal-title":"New J Phys"},{"issue":"2","key":"9772_CR7","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/s10710-006-9001-y","volume":"7","author":"M Collins","year":"2006","unstructured":"Collins M (2006) Finding needles in haystacks is harder with neutrality. Genet Program Evolvable Mach 7(2):131\u2013144. https:\/\/doi.org\/10.1007\/s10710-006-9001-y","journal-title":"Genet Program Evolvable Mach"},{"key":"9772_CR8","doi-asserted-by":"publisher","unstructured":"Downing RM (2005) Evolving binary decision diagrams using implicit neutrality. In: Proceedings of 2005 IEEE congress on evolutionary computation, vol.\u00a03. IEEE, pp 2107\u20132113. https:\/\/doi.org\/10.1109\/CEC.2005.1554955","DOI":"10.1109\/CEC.2005.1554955"},{"key":"9772_CR9","doi-asserted-by":"publisher","unstructured":"Downing RM (2006) Neutrality and gradualism: encouraging exploration and exploitation simultaneously with binary decision diagrams. In: Proceedings of 2006 IEEE congress on evolutionary computation. IEEE, pp 615\u2013622. https:\/\/doi.org\/10.1109\/CEC.2006.1688367","DOI":"10.1109\/CEC.2006.1688367"},{"issue":"3","key":"9772_CR10","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1007\/s12530-011-9030-5","volume":"2","author":"E Galv\u00e1n-L\u00f3pez","year":"2011","unstructured":"Galv\u00e1n-L\u00f3pez E, Poli R, Kattan A, O\u2019Neill M, Brabazon A (2011) Neutrality in evolutionary algorithms: What do we know? Evol Syst 2(3):145\u2013163. https:\/\/doi.org\/10.1007\/s12530-011-9030-5","journal-title":"Evol Syst"},{"key":"9772_CR11","doi-asserted-by":"publisher","unstructured":"Habel A, Kreowski HJ, Plump D (1988) Jungle evaluation. In: Recent trends in data type specification (WADT\u201987), selected papers, LNCS, vol. 332. Springer, pp 92\u2013112. https:\/\/doi.org\/10.1007\/3-540-50325-0_5","DOI":"10.1007\/3-540-50325-0_5"},{"issue":"2","key":"9772_CR12","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1111\/j.1558-5646.2007.00308.x","volume":"62","author":"MW Hahn","year":"2007","unstructured":"Hahn MW (2007) Toward a selection theory of molecular evolution. Evolution 62(2):255\u2013265. https:\/\/doi.org\/10.1111\/j.1558-5646.2007.00308.x","journal-title":"Evolution"},{"key":"9772_CR13","doi-asserted-by":"publisher","unstructured":"Harvey I, Thompson A (1997) Through the labyrinth evolution finds a way: a silicon ridge. In: Proceedings of 1st international conference on evolvable systems, LNCS, vol. 1259. Springer, pp 406\u2013422. https:\/\/doi.org\/10.1007\/3-540-63173-9_62","DOI":"10.1007\/3-540-63173-9_62"},{"key":"9772_CR14","doi-asserted-by":"publisher","unstructured":"Hu T, Banzhaf W (2009) Neutrality and variability: two sides of evolvability in linear genetic programming. In: Proceedings of the 11th annual conference on genetic and evolutionary computation, GECCO \u201909. ACM, pp 963\u2013970. https:\/\/doi.org\/10.1145\/1569901.1570033","DOI":"10.1145\/1569901.1570033"},{"key":"9772_CR15","doi-asserted-by":"publisher","unstructured":"Hu T, Banzhaf W (2018) Neutrality, robustness, and evolvability in genetic programming. Springer, pp 101\u2013117. https:\/\/doi.org\/10.1007\/978-3-319-97088-2_7","DOI":"10.1007\/978-3-319-97088-2_7"},{"key":"9772_CR16","doi-asserted-by":"crossref","unstructured":"Husa J, Kalkreuth R (2018) A comparative study on crossover in Cartesian genetic programming. In: Proceedings of European conference on genetic programming, EuroGP 2018, LNCS, vol. 10781. Springer, pp 203\u2013219","DOI":"10.1007\/978-3-319-77553-1_13"},{"key":"9772_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511623486","volume-title":"The neutral theory of molecular evolution","author":"M Kimura","year":"1983","unstructured":"Kimura M (1983) The neutral theory of molecular evolution. Cambridge University Press, Cambridge"},{"key":"9772_CR18","volume-title":"Genetic programming: on the programming of computers by means of natural selection","author":"JR Koza","year":"1992","unstructured":"Koza JR (1992) Genetic programming: on the programming of computers by means of natural selection. MIT Press, Cambridge"},{"key":"9772_CR19","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.ins.2012.12.051","volume":"233","author":"P Larra\u00f1aga","year":"2013","unstructured":"Larra\u00f1aga P, Karshenas H, Bielza C, Santana R (2013) A review on evolutionary algorithms in Bayesian network learning and inference tasks. Inf Sci 233:109\u2013125. https:\/\/doi.org\/10.1016\/j.ins.2012.12.051","journal-title":"Inf Sci"},{"key":"9772_CR20","doi-asserted-by":"publisher","unstructured":"L\u00f3pez EG, Rodr\u00edguez-V\u00e1zquez K (2007) Multiple interactive outputs in a single tree: an empirical investigation. In: Proceedings of 10th European conference on genetic programming (EuroGP 2007), LNCS, vol. 4445. Springer, pp 341\u2013350. https:\/\/doi.org\/10.1007\/978-3-540-71605-1_32","DOI":"10.1007\/978-3-540-71605-1_32"},{"issue":"1","key":"9772_CR21","doi-asserted-by":"publisher","first-page":"50","DOI":"10.1214\/aoms\/1177730491","volume":"18","author":"HB Mann","year":"1947","unstructured":"Mann HB, Whitney DR (1947) On a test of whether one of two random variables is stochastically larger than the other. Ann Math Stat 18(1):50\u201360","journal-title":"Ann Math Stat"},{"key":"9772_CR22","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17310-3","volume-title":"Cartesian genetic programming","year":"2011","unstructured":"Miller JF (ed) (2011) Cartesian genetic programming. Springer, Berlin. https:\/\/doi.org\/10.1007\/978-3-642-17310-3"},{"issue":"2","key":"9772_CR23","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1109\/TEVC.2006.871253","volume":"10","author":"JF Miller","year":"2006","unstructured":"Miller JF, Smith SL (2006) Redundancy and computational efficiency in cartesian genetic programming. IEEE Trans Evol Comput 10(2):167\u2013174. https:\/\/doi.org\/10.1109\/TEVC.2006.871253","journal-title":"IEEE Trans Evol Comput"},{"key":"9772_CR24","doi-asserted-by":"publisher","unstructured":"Miller JF, Thomson P (2000) Cartesian genetic programming. In: Proceedings of 3rd European conference on genetic programming (EuroGP 2000), LNCS, vol. 1802. Springer, pp 121\u2013132. https:\/\/doi.org\/10.1007\/978-3-540-46239-2_9","DOI":"10.1007\/978-3-540-46239-2_9"},{"key":"9772_CR25","doi-asserted-by":"publisher","unstructured":"Moraglio A, Krawiec K, Johnson CG (2012) Geometric semantic genetic programming. In: Parallel problem solving from nature\u2014PPSN XII, LNCS, vol. 7491. Springer, pp 21\u201331. https:\/\/doi.org\/10.1007\/978-3-642-32937-1_3","DOI":"10.1007\/978-3-642-32937-1_3"},{"key":"9772_CR26","doi-asserted-by":"publisher","unstructured":"Nguyen QU, Nguyen XH, O\u2019Neill M (2009) Semantic aware crossover for genetic programming: the case for real-valued function regression. In: Proceedings of European conference on genetic programming, EuroGP 2009, LNCS, vol. 5481. Springer, pp 292\u2013302. https:\/\/doi.org\/10.1007\/978-3-642-01181-8_25","DOI":"10.1007\/978-3-642-01181-8_25"},{"key":"9772_CR27","doi-asserted-by":"crossref","unstructured":"Pham TA, Nguyen QU, Nguyen XH, O\u2019Neill M (2013) Examining the diversity property of semantic similarity based crossover. In: Proceedings of European conference on genetic programming, EuroGP 2013, LNCS, vol. 7831. Springer, pp 265\u2013276","DOI":"10.1007\/978-3-642-37207-0_23"},{"key":"9772_CR28","doi-asserted-by":"publisher","unstructured":"Plump D (2012) The design of GP\u00a02. In: Proceedings of workshop on reduction strategies in rewriting and programming (WRS 2011), EPTCS, vol.\u00a082, pp 1\u201316. https:\/\/doi.org\/10.4204\/EPTCS.82.1","DOI":"10.4204\/EPTCS.82.1"},{"key":"9772_CR29","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.jlamp.2016.12.001","volume":"88","author":"D Plump","year":"2017","unstructured":"Plump D (2017) From imperative to rule-based graph programs. J Log Algebraic Methods Program 88:154\u2013173. https:\/\/doi.org\/10.1016\/j.jlamp.2016.12.001","journal-title":"J Log Algebraic Methods Program"},{"key":"9772_CR30","unstructured":"Poli R (1997) Evolution of graph-like programs with parallel distributed genetic programming. In: Proceedings of international conference on genetic algorithms. Morgan Kaufmann, pp 346\u2013353"},{"key":"9772_CR31","unstructured":"Poli R (1999) Parallel distributed genetic programming. In: New ideas in optimization. McGraw-Hill, pp 346\u2013353"},{"issue":"1","key":"9772_CR32","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/s10710-014-9233-1","volume":"16","author":"AJ Turner","year":"2015","unstructured":"Turner AJ, Miller JF (2015a) Introducing a cross platform open source cartesian genetic programming library. Genet Program Evolvable Mach 16(1):83\u201391. https:\/\/doi.org\/10.1007\/s10710-014-9233-1","journal-title":"Genet Program Evolvable Mach"},{"issue":"4","key":"9772_CR33","doi-asserted-by":"publisher","first-page":"531","DOI":"10.1007\/s10710-015-9244-6","volume":"16","author":"AJ Turner","year":"2015","unstructured":"Turner AJ, Miller JF (2015b) Neutral genetic drift: an investigation using cartesian genetic programming. Genet Program Evolvable Mach 16(4):531\u2013558. https:\/\/doi.org\/10.1007\/s10710-015-9244-6","journal-title":"Genet Program Evolvable Mach"},{"key":"9772_CR34","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.tcs.2011.03.011","volume":"425","author":"L Vanneschi","year":"2012","unstructured":"Vanneschi L, Pirola Y, Mauri G, Tomassini M, Collard P, Verel S (2012) A study of the neutrality of Boolean function landscapes in genetic programming. Theor Comput Sci 425:34\u201357. https:\/\/doi.org\/10.1016\/j.tcs.2011.03.011","journal-title":"Theor Comput Sci"},{"issue":"2","key":"9772_CR35","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10710-013-9210-0","volume":"15","author":"L Vanneschi","year":"2014","unstructured":"Vanneschi L, Castelli M, Silva S (2014) A survey of semantic methods in genetic programming. Genet Program Evolvable Mach 15(2):195\u2013214. https:\/\/doi.org\/10.1007\/s10710-013-9210-0","journal-title":"Genet Program Evolvable Mach"},{"issue":"2","key":"9772_CR36","first-page":"101","volume":"25","author":"A Vargha","year":"2000","unstructured":"Vargha A, Delaney HD (2000) A critique and improvement of the CL common language effect size statistics of McGraw and Wong. J Educ Behav Stat 25(2):101\u2013132","journal-title":"J Educ Behav Stat"},{"key":"9772_CR37","doi-asserted-by":"publisher","unstructured":"Vassilev VK, Miller JF (2000) The advantages of landscape neutrality in digital circuit evolution. In: Proceedings of 3rd international conference on evolvable systems, LNCS, vol. 1801. Springer, pp 252\u2013263. https:\/\/doi.org\/10.1007\/3-540-46406-9_25","DOI":"10.1007\/3-540-46406-9_25"},{"issue":"4","key":"9772_CR38","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1109\/TEVC.2007.903549","volume":"12","author":"JA Walker","year":"2008","unstructured":"Walker JA, Miller JF (2008) The automatic acquisition, evolution and reuse of modules in cartesian genetic programming. IEEE Trans Evol Comput 12(4):397\u2013417. https:\/\/doi.org\/10.1109\/TEVC.2007.903549","journal-title":"IEEE Trans Evol Comput"},{"key":"9772_CR39","doi-asserted-by":"publisher","unstructured":"Yu T, Miller J (2002) Finding needles in haystacks is not hard with neutrality. In: Proceedings of 5th European conference on genetic programming, LNCS, vol. 2278. Springer, pp 13\u201325. https:\/\/doi.org\/10.1007\/3-540-45984-7_2","DOI":"10.1007\/3-540-45984-7_2"},{"issue":"6","key":"9772_CR40","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1016\/S0169-5347(03)00033-8","volume":"18","author":"J Zhang","year":"2003","unstructured":"Zhang J (2003) Evolution by gene duplication: an update. Trends Ecol Evolut 18(6):292\u2013298. https:\/\/doi.org\/10.1016\/S0169-5347(03)00033-8","journal-title":"Trends Ecol Evolut"}],"container-title":["Natural Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-019-09772-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s11047-019-09772-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s11047-019-09772-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,4]],"date-time":"2021-03-04T16:06:56Z","timestamp":1614874016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s11047-019-09772-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,29]]},"references-count":40,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,3]]}},"alternative-id":["9772"],"URL":"https:\/\/doi.org\/10.1007\/s11047-019-09772-4","relation":{},"ISSN":["1567-7818","1572-9796"],"issn-type":[{"value":"1567-7818","type":"print"},{"value":"1572-9796","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,29]]},"assertion":[{"value":"29 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}