{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T16:43:24Z","timestamp":1769100204151,"version":"3.49.0"},"reference-count":40,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T00:00:00Z","timestamp":1732665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Sponsor Engineering and Physical Sciences Research Council","award":["#EP\/M004252\/1"],"award-info":[{"award-number":["#EP\/M004252\/1"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2024,12,31]]},"abstract":"<jats:p>In this article, we present the first rigorous theoretical analysis of the generalisation performance of a Geometric Semantic Genetic Programming (GSGP) system. More specifically, we consider a hill-climber using the GSGP Fixed Block Mutation (FBM) operator for the domain of Boolean functions. We prove that the algorithm cannot evolve Boolean conjunctions of arbitrary size that are correct on unseen inputs chosen uniformly at random from the complete truth table i.e., it generalises poorly. Two algorithms based on the Varying Block Mutation (VBM) operator are proposed and analysed to address the issue. We rigorously prove that under the uniform distribution the first one can efficiently evolve any Boolean function of constant size with respect to the number of available variables, while the second one can efficiently evolve general conjunctions or disjunctions of any size without requiring prior knowledge of the target function class. An experimental analysis confirms the theoretical insights for realistic problem sizes and indicates the superiority of the proposed operators also for small parity functions not explicitly covered by the theory.<\/jats:p>","DOI":"10.1145\/3677124","type":"journal-article","created":{"date-parts":[[2024,7,16]],"date-time":"2024-07-16T10:11:06Z","timestamp":1721124666000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["On the Generalisation Performance of Geometric Semantic Genetic Programming for Boolean Functions: Learning Block Mutations"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4151-2734","authenticated-orcid":false,"given":"Dogan","family":"Corus","sequence":"first","affiliation":[{"name":"Kadir Has University, Istanbul, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8164-6767","authenticated-orcid":false,"given":"Pietro S.","family":"Oliveto","sequence":"additional","affiliation":[{"name":"Southern University of Science and Technology, Shenzhen, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,11,27]]},"reference":[{"issue":"3","key":"e_1_3_2_2_1","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/s10710-009-9082-5","article-title":"Semantic analysis of program initialisation in genetic programming","volume":"10","author":"Beadle Lawrence","year":"2009","unstructured":"Lawrence Beadle and Colin G. Johnson. 2009. Semantic analysis of program initialisation in genetic programming. Genetic Programming and Evolvable Machines 10, 3 (2009), 307\u2013337.","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"e_1_3_2_3_1","volume-title":"Linear Genetic Programming","author":"Brameier Markus F.","year":"2007","unstructured":"Markus F. Brameier and Wolfgang Banzhaf. 2007. Linear Genetic Programming. Springer, Boston, MA."},{"key":"e_1_3_2_4_1","doi-asserted-by":"crossref","first-page":"334","DOI":"10.1007\/978-3-642-37192-9_34","volume-title":"Proceedings of Applications of Evolutionary Computation - 16th European Conference (EvoApplications \u201913)","author":"Castelli Mauro","year":"2013","unstructured":"Mauro Castelli, Sara Silva, Leonardo Vanneschi, Ana Cabral, Maria J. P. de Vasconcelos, Lu\u00eds Catarino, and Jo\u00e3o Manuel de Brito Carreiras. 2013a. Land cover\/land use multiclass classification using GP with geometric semantic operators. In Proceedings of Applications of Evolutionary Computation - 16th European Conference (EvoApplications \u201913). Springer, Berlin, 334\u2013343."},{"key":"e_1_3_2_5_1","first-page":"17","article-title":"Prediction of high performance concrete strength using Genetic Programming with geometric semantic genetic operators","volume":"40","author":"Castelli Mauro","year":"2013","unstructured":"Mauro Castelli, Leonardo Vanneschi, and Sara Silva. 2013b. Prediction of high performance concrete strength using Genetic Programming with geometric semantic genetic operators. Expert Systems with Applications 40, 17 (2013), 6856\u20136862.","journal-title":"Expert Systems with Applications"},{"key":"e_1_3_2_6_1","volume-title":"On the Origin of Species by Means of Natural Selection","author":"Darwin Charles","year":"1859","unstructured":"Charles Darwin. 1859. On the Origin of Species by Means of Natural Selection. Murray, London."},{"key":"e_1_3_2_7_1","first-page":"174","volume-title":"Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN \u201910), Part I","author":"Doerr Benjamin","year":"2010","unstructured":"Benjamin Doerr and Leslie Ann Goldberg. 2010. Drift analysis with tail bounds. In Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN \u201910), Part I. Springer, Berlin, 174\u2013183."},{"key":"e_1_3_2_8_1","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201919)","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr, Andrei Lissovoi, and Pietro Simone Oliveto. 2019. Evolving Boolean functions with conjunctions and disjunctions via genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201919). ACM, New York, NY, 1003\u20131011."},{"key":"e_1_3_2_9_1","first-page":"253","volume-title":"Proceedings of the 24th Annual Conference on Learning Theory (COLT \u201911)","author":"Feldman Vitaly","year":"2011","unstructured":"Vitaly Feldman. 2011. Distribution-independent evolvability of linear threshold functions. In Proceedings of the 24th Annual Conference on Learning Theory (COLT \u201911). PMLR, 253\u2013272."},{"key":"e_1_3_2_10_1","first-page":"41","volume-title":"Proceedings of Genetic Programming - 18th European Conference (EuroGP \u201915)","author":"Gon\u00e7alves Ivo","year":"2015","unstructured":"Ivo Gon\u00e7alves, Sara Silva, and Carlos M. Fonseca. 2015. On the generalization ability of geometric semantic genetic programming. In Proceedings of Genetic Programming - 18th European Conference (EuroGP \u201915). Springer International Publishing, Cham, 41\u201352."},{"key":"e_1_3_2_11_1","first-page":"1","volume-title":"Theory and Principled Methods for the Design of Metaheuristics","author":"Igel Christian","year":"2014","unstructured":"Christian Igel. 2014. No free lunch theorems: Limitations and perspectives of metaheuristics. In Theory and Principled Methods for the Design of Metaheuristics. Jossi Borenstein and Alberto Moraglio (Eds.), Springer, 1\u201323."},{"key":"e_1_3_2_12_1","first-page":"98","volume-title":"Proceedings of Genetic Programming - 13th European Conference (EuroGP \u201910)","author":"Jackson David","year":"2010","unstructured":"David Jackson. 2010. Phenotypic diversity in initial genetic programming populations. In Proceedings of Genetic Programming - 13th European Conference (EuroGP \u201910). Springer, Berlin, 98\u2013109."},{"key":"e_1_3_2_13_1","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."},{"key":"e_1_3_2_14_1","first-page":"3","article-title":"Human-competitive results produced by genetic programming","volume":"11","author":"Koza John R.","year":"2010","unstructured":"John R. Koza. 2010. Human-competitive results produced by genetic programming. Genetic Programming and Evolvable Machines 11, 3\u20134 (2010), 251\u2013284.","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"e_1_3_2_15_1","first-page":"987","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201909)","author":"Krawiec Krzysztof","year":"2009","unstructured":"Krzysztof Krawiec and Pawel Lichocki. 2009. Approximating geometric crossover in semantic space. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201909). ACM, New York, NY, 987\u2013994."},{"key":"e_1_3_2_16_1","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-030-29414-4_2","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"Lengler Johannes","year":"2020","unstructured":"Johannes Lengler. 2020. Drift analysis. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Benjamin Doerr and Frank Neumann (Eds.), Springer International Publishing, Cham, 89\u2013132."},{"key":"e_1_3_2_17_1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1080\/09528139008953717","article-title":"Representational issues in genetic optimization","volume":"2","author":"Liepins G. E.","year":"1990","unstructured":"G. E. Liepins and M. D. Vose. 1990. Representational issues in genetic optimization. Journal of Experimental and Theoretical Artificial Intelligence 2 (1990), 101\u2013115.","journal-title":"Journal of Experimental and Theoretical Artificial Intelligence"},{"key":"e_1_3_2_18_1","first-page":"1363","volume-title":"Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI \u201918)","author":"Lissovoi Andrei","year":"2018","unstructured":"Andrei Lissovoi and Pietro S. Oliveto. 2018. On the time and space complexity of genetic programming for evolving Boolean conjunctions. In Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI \u201918). AAAI Press, California, 1363\u20131370."},{"key":"e_1_3_2_19_1","doi-asserted-by":"crossref","first-page":"655","DOI":"10.1613\/jair.1.11821","article-title":"On the time and space complexity of genetic programming for evolving Boolean conjunctions","volume":"66","author":"Lissovoi Andrei","year":"2019","unstructured":"Andrei Lissovoi and Pietro S. Oliveto. 2019. On the time and space complexity of genetic programming for evolving Boolean conjunctions. Journal of Artificial Intelligence Research 66 (2019), 655\u2013689.","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_3_2_20_1","doi-asserted-by":"crossref","first-page":"475","DOI":"10.1007\/978-3-030-29414-4_11","volume-title":"Theory of Evolutionary Computation: Recent Developments in Discrete Optimization","author":"Lissovoi Andrei","year":"2020","unstructured":"Andrei Lissovoi and Pietro S. Oliveto. 2020. Computational complexity analysis of genetic programming. In Theory of Evolutionary Computation: Recent Developments in Discrete Optimization. Benjamin Doerr and Frank Neumann (Eds.), Springer International Publishing, Cham, 475\u2013518."},{"key":"e_1_3_2_21_1","first-page":"143","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201914)","author":"Mambrini Andrea","year":"2014","unstructured":"Andrea Mambrini and Luca Manzoni. 2014. A comparison between geometric semantic GP and Cartesian GP for Boolean functions learning. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201914). ACM, New York, NY, 143\u2013144."},{"key":"e_1_3_2_22_1","first-page":"416","volume-title":"Proceedings of the Congress on Evolutionary Computation (CEC \u201913)","author":"Mambrini Andrea","year":"2013","unstructured":"Andrea Mambrini, Luca Manzoni, and Alberto Moraglio. 2013. Theory-laden design of mutation-based Geometric Semantic Genetic Programming for learning classification trees. In Proceedings of the Congress on Evolutionary Computation (CEC \u201913). IEEE, 416\u2013423."},{"key":"e_1_3_2_23_1","first-page":"99","volume-title":"Proceedings of Genetic Programming - 19th European Conference (EuroGP \u201916)","author":"Mambrini Andrea","year":"2016","unstructured":"Andrea Mambrini and Pietro S. Oliveto. 2016. On the analysis of simple genetic programming for evolving Boolean functions. In Proceedings of Genetic Programming - 19th European Conference (EuroGP \u201916). Springer, Cham, 99\u2013114."},{"key":"e_1_3_2_24_1","doi-asserted-by":"crossref","first-page":"845","DOI":"10.1007\/978-3-662-43505-2_43","volume-title":"Springer Handbook of Computational Intelligence","author":"McDermott James","year":"2015","unstructured":"James McDermott and Una-May O\u2019Reilly. 2015. Genetic programming. In Springer Handbook of Computational Intelligence. Janusz Kacprzyk and Witold Pedrycz (Eds.), Springer, Berlin, 845\u2013869."},{"key":"e_1_3_2_25_1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17310-3","volume-title":"Cartesian Genetic Programming","author":"Miller Julian F.","year":"2011","unstructured":"Julian F. Miller (Ed.). 2011. Cartesian Genetic Programming. Springer, Berlin."},{"key":"e_1_3_2_26_1","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1007\/978-3-642-32937-1_3","volume-title":"Proceedings of the 12th International Conference on Parallel Problem Solving from Nature (PPSN \u201912)","author":"Moraglio Alberto","year":"2012","unstructured":"Alberto Moraglio, Krzysztof Krawiec, and Colin G. Johnson. 2012. Geometric semantic genetic programming. In Proceedings of the 12th International Conference on Parallel Problem Solving from Nature (PPSN \u201912). Springer, Berlin, 21\u201331."},{"key":"e_1_3_2_27_1","first-page":"989","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201913)","author":"Moraglio Alberto","year":"2013","unstructured":"Alberto Moraglio and Andrea Mambrini. 2013. Runtime analysis of mutation-based geometric semantic genetic programming for basis functions regression. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201913). ACM, New York, NY, 989\u2013996."},{"key":"e_1_3_2_28_1","first-page":"119","volume-title":"Proceedings of the 12th International Workshop on Foundations of Genetic Algorithms (FOGA \u201913)","author":"Moraglio Alberto","year":"2013","unstructured":"Alberto Moraglio, Andrea Mambrini, and Luca Manzoni. 2013. Runtime analysis of mutation-based geometric semantic genetic programming on Boolean functions. In Proceedings of the 12th International Workshop on Foundations of Genetic Algorithms (FOGA \u201913). ACM, New York, NY, 119\u2013132."},{"key":"e_1_3_2_29_1","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1007\/978-3-319-78717-6_7","volume-title":"Handbook of Grammatical Evolution","author":"Moraglio Alberto","year":"2018","unstructured":"Alberto Moraglio, James McDermott, and Michael O\u2019Neill. 2018. Geometric semantic grammatical evolution. In Handbook of Grammatical Evolution. Conor Ryan, Michael O\u2019Neill, and J. J. Collins (Eds.), Springer International Publishing, Cham, 163\u2013188."},{"key":"e_1_3_2_30_1","doi-asserted-by":"crossref","first-page":"1183","DOI":"10.1145\/3205455.3205539","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201918)","author":"Orzechowski Patryk","year":"2018","unstructured":"Patryk Orzechowski, William La Cava, and Jason H. Moore. 2018. Where are we now?: A large benchmark study of recent symbolic regression methods. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO \u201918). ACM, New York, NY, 1183\u20131190."},{"issue":"2","key":"e_1_3_2_31_1","first-page":"1","article-title":"Competent geometric semantic genetic programming for symbolic regression and Boolean function synthesis","volume":"26","author":"Pawlak Tomasz P.","year":"2017","unstructured":"Tomasz P. Pawlak and Krzysztof Krawiec. 2017. Competent geometric semantic genetic programming for symbolic regression and Boolean function synthesis. Evolutionary Computation 26, 2 (2017), 1\u201336.","journal-title":"Evolutionary Computation"},{"key":"e_1_3_2_32_1","volume-title":"A Field Guide to Genetic Programming","author":"Poli Riccardo","year":"2008","unstructured":"Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee. 2008. A Field Guide to Genetic Programming. Lulu Press, Raleigh, NC."},{"key":"e_1_3_2_33_1","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/978-3-642-37192-9_41","volume-title":"Proceedings of Applications of Evolutionary Computation - 16th European Conference (EvoApplications \u201913)","author":"Silva Sara","year":"2013","unstructured":"Sara Silva, Vijay Ingalalli, Susana Vinga, Jo\u00e3o M. de Brito Carreiras, Joana B. Melo, Mauro Castelli, Leonardo Vanneschi, Ivo Gon\u00e7alves, and Jos\u00e9 Caldas. 2013. Prediction of forest aboveground biomass: An exercise on avoiding overfitting. In Proceedings of Applications of Evolutionary Computation - 16th European Conference (EvoApplications \u201913). Springer, Berlin, 407\u2013417."},{"issue":"1","key":"e_1_3_2_34_1","doi-asserted-by":"crossref","first-page":"7","DOI":"10.1023\/A:1014538503543","article-title":"Genetic programming and autoconstructive evolution with the push programming language","volume":"3","author":"Spector Lee","year":"2002","unstructured":"Lee Spector and Alan J. Robinson. 2002. Genetic programming and autoconstructive evolution with the push programming language. Genetic Programming and Evolvable Machines 3, 1 (2002), 7\u201340.","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"e_1_3_2_35_1","first-page":"465","volume-title":"Proceedings of Parallel Problem Solving from Nature \u2013 PPSN XIII","author":"Thorhauer Ann","year":"2014","unstructured":"Ann Thorhauer and Franz Rothlauf. 2014. On the locality of standard search operators in grammatical evolution. In Proceedings of Parallel Problem Solving from Nature \u2013 PPSN XIII. Springer, Berlin, 465\u2013475."},{"issue":"2","key":"e_1_3_2_36_1","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s10710-010-9121-2","article-title":"Semantically-based crossover in genetic programming: Application to real-valued symbolic regression","volume":"12","author":"Uy Nguyen Q.","year":"2011","unstructured":"Nguyen Q. Uy, Nguyen X. Hoai, Michael O\u2019Neill, Robert I. McKay, and Edgar G. L\u00f3pez. 2011. Semantically-based crossover in genetic programming: Application to real-valued symbolic regression. Genetic Programming and Evolvable Machines 12, 2 (2011), 91\u2013119.","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"e_1_3_2_37_1","volume-title":"Probably Approximately Correct: Nature\u2019s Algorithms for Learning and Prospering in a Complex World","author":"Valiant Leslie","year":"2013","unstructured":"Leslie Valiant. 2013. Probably Approximately Correct: Nature\u2019s Algorithms for Learning and Prospering in a Complex World. Basic Books, New York, NY."},{"issue":"1","key":"e_1_3_2_38_1","first-page":"3:1","article-title":"Evolvability","volume":"56","author":"Valiant Leslie G.","year":"2009","unstructured":"Leslie G. Valiant. 2009. Evolvability. Journal of the ACM 56, 1 (2009), 3:1\u20133:21.","journal-title":"Journal of the ACM"},{"key":"e_1_3_2_39_1","first-page":"205","volume-title":"Proceedings of Genetic Programming - 16th European Conference (EuroGP \u201913)","author":"Vanneschi Leonardo","year":"2013","unstructured":"Leonardo Vanneschi, Mauro Castelli, Luca Manzoni, and Sara Silva. 2013a. A new implementation of geometric semantic GP and its application to problems in pharmacokinetics. In Proceedings of Genetic Programming - 16th European Conference (EuroGP \u201913). Springer, Berlin, 205\u2013216."},{"issue":"2","key":"e_1_3_2_40_1","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s10710-013-9210-0","article-title":"A survey of semantic methods in genetic programming","volume":"15","author":"Vanneschi Leonardo","year":"2014","unstructured":"Leonardo Vanneschi, Mauro Castelli, and Sara Silva. 2014. A survey of semantic methods in genetic programming. Genetic Programming and Evolvable Machines 15, 2 (2014), 195\u2013214.","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"e_1_3_2_41_1","first-page":"191","volume-title":"Proceedings of Genetic Programming Theory and Practice XI (GPTP \u201913)","author":"Vanneschi Leonardo","year":"2013","unstructured":"Leonardo Vanneschi, Sara Silva, Mauro Castelli, and Luca Manzoni. 2013b. Geometric semantic genetic programming for real life applications. In Proceedings of Genetic Programming Theory and Practice XI (GPTP \u201913). Springer, New York, NY, 191\u2013209."}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677124","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677124","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:06:17Z","timestamp":1750291577000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677124"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,11,27]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12,31]]}},"alternative-id":["10.1145\/3677124"],"URL":"https:\/\/doi.org\/10.1145\/3677124","relation":{},"ISSN":["2688-3007"],"issn-type":[{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,11,27]]},"assertion":[{"value":"2023-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}