{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,26]],"date-time":"2025-09-26T13:18:58Z","timestamp":1758892738103,"version":"3.37.3"},"reference-count":46,"publisher":"MIT Press","issue":"4","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,12,2]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>Genetic variation operators in grammar-guided genetic programming are fundamental to guide the evolutionary process in search and optimization problems. However, they show some limitations, mainly derived from an unbalanced exploration and local-search trade-off. This paper presents an estimation of distribution algorithm for grammar-guided genetic programming to overcome this difficulty and thus increase the performance of the evolutionary algorithm. Our proposal employs an extended dynamic stochastic context-free grammar to encode and calculate the estimation of the distribution of the search space from some promising individuals in the population. Unlike traditional estimation of distribution algorithms, the proposed approach improves exploratory behavior by smoothing the estimated distribution model. Therefore, this algorithm is referred to as SEDA, smoothed estimation of distribution algorithm. Experiments have been conducted to compare overall performance using a typical genetic programming crossover operator, an incremental estimation of distribution algorithm, and the proposed approach after tuning their hyperparameters. These experiments involve challenging problems to test the local search and exploration features of the three evolutionary systems. The results show that grammar-guided genetic programming with SEDA achieves the most accurate solutions with an intermediate convergence speed.<\/jats:p>","DOI":"10.1162\/evco_a_00345","type":"journal-article","created":{"date-parts":[[2024,1,25]],"date-time":"2024-01-25T20:24:51Z","timestamp":1706214291000},"page":"339-370","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":4,"title":["Estimation of Distribution Algorithm for Grammar-Guided Genetic Programming"],"prefix":"10.1162","volume":"32","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4765-1105","authenticated-orcid":true,"given":"Pablo Ramos","family":"Criado","sequence":"first","affiliation":[{"name":"Aturing Research, Salamanca, Spain pablo.ramos@aturing.com"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4060-965X","authenticated-orcid":true,"given":"D. Barrios","family":"Rolan\u00eda","sequence":"additional","affiliation":[{"name":"Depto. Matem\u00e1tica Aplicada a la Ingenier\u00eda Industrial, ETSI Industriales, Universidad Polit\u00e9cnica de Madrid, Spain dolores.barrios.rolania@upm.es"}]},{"given":"David","family":"de la Hoz","sequence":"additional","affiliation":[{"name":"Depto. Inteligencia Artificial, ETSI Inform\u00e1ticos, Universidad Polit\u00e9cnica de Madrid, Spain david.delahoz.galiana@alumnos.upm.es"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0792-4156","authenticated-orcid":true,"given":"Daniel","family":"Manrique","sequence":"additional","affiliation":[{"name":"Depto. Inteligencia Artificial, ETSI Inform\u00e1ticos, Universidad Polit\u00e9cnica de Madrid, Spain daniel.manrique@upm.es"}]}],"member":"281","published-online":{"date-parts":[[2024,12,2]]},"reference":[{"key":"2024120202545137900_B1","doi-asserted-by":"crossref","DOI":"10.1887\/0750308958","volume-title":"Handbook of evolutionary computation","author":"B\u00e4ck","year":"1997"},{"issue":"3\u20134","key":"2024120202545137900_B2","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1007\/s10472-018-9601-2","article-title":"Multilayered neural architectures evolution for computing sequences of orthogonal polynomials","volume":"84","author":"Barrios Rolan\u00eda","year":"2018","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"issue":"10","key":"2024120202545137900_B3","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1007\/s00500-006-0144-9","article-title":"Crossover and mutation operators for grammar-guided genetic programming","volume":"11","author":"Couchet","year":"2007","journal-title":"Soft Computing"},{"volume-title":"On the origin of the species by means of natural selection, or the preservation of favoured races in the struggle for life","year":"1959","author":"Darwin","key":"2024120202545137900_B4"},{"issue":"4","key":"2024120202545137900_B5","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/MCI.2006.329691","article-title":"Ant colony optimization","volume":"1","author":"Dorigo","year":"2006","journal-title":"IEEE Computational Intelligence Magazine"},{"key":"2024120202545137900_B6","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1007\/978-3-642-21344-1_7","article-title":"Grammar-guided evolutionary construction of Bayesian networks","volume-title":"Foundations on natural and artificial computation","author":"Font","year":"2011"},{"issue":"12","key":"2024120202545137900_B7","doi-asserted-by":"publisher","first-page":"7711","DOI":"10.1016\/j.eswa.2010.04.070","article-title":"Evolutionary construction and adaptation of intelligent systems","volume":"37","author":"Font","year":"2010","journal-title":"Expert Systems with Applications"},{"key":"2024120202545137900_B8","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-31519-0_3","article-title":"Locality in continuous fitness-valued cases and genetic programming difficulty","author":"Galv\u00e1n","year":"2013","journal-title":"EVOLVE\u2014A bridge between probability, set oriented numerics, and evolutionary computation II. Advances in Intelligent Systems and Computing, Vol. 175"},{"issue":"4","key":"2024120202545137900_B9","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10710-011-9136-3","article-title":"Defining locality as a problem difficulty measure in genetic programming","volume":"12","author":"Galv\u00e1n-L\u00f3pez","year":"2011","journal-title":"Genetic Programming and Evolvable Machines"},{"key":"2024120202545137900_B10","doi-asserted-by":"publisher","DOI":"10.1109\/MICAI.2009.17","article-title":"Towards understanding the effects of locality in GP","author":"Galv\u00e1n-L\u00f3pez","year":"2009","journal-title":"Eighth Mexican International Conference on Artificial Intelligence"},{"issue":"2","key":"2024120202545137900_B11","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/j.knosys.2006.11.006","article-title":"Initialization method for grammar-guided genetic programming","volume":"20","author":"Garc\u00eda-Arnau","year":"2007","journal-title":"Knowledge-Based Systems"},{"issue":"6","key":"2024120202545137900_B12","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1109\/TEVC.2008.915999","article-title":"A Bayesian network approach to program generation","volume":"12","author":"Hasegawa","year":"2008","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"3","key":"2024120202545137900_B13","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/j.swevo.2011.08.003","article-title":"An introduction and survey of estimation of distribution algorithms","volume":"1","author":"Hauschild","year":"2011","journal-title":"Swarm Evolutionary Computation"},{"key":"2024120202545137900_B14","first-page":"167","volume-title":"Genr8: Architects' experience with an emergent design tool","author":"Hemberg","year":"2008"},{"key":"2024120202545137900_B15","volume-title":"Introduction to automata theory, languages and computation","author":"Hopcroft","year":"2006","edition":"3rd"},{"volume-title":"Handbook of formal languages 3: Beyond words","year":"1997","author":"Joshi","key":"2024120202545137900_B16"},{"issue":"10","key":"2024120202545137900_B17","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1145\/1400181.1400200","article-title":"The many facets of natural computing","volume":"51","author":"Kari","year":"2008","journal-title":"Communications of the ACM"},{"issue":"3","key":"2024120202545137900_B18","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1109\/TEVC.2012.2196521","article-title":"Stochastic diversity loss and scalability in estimation of distribution genetic programming","volume":"17","author":"Kim","year":"2013","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"2","key":"2024120202545137900_B19","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/s10710-013-9205-x","article-title":"Probabilistic model building in genetic programming: A critical review","volume":"15","author":"Kim","year":"2014","journal-title":"Genetic Programming and Evolvable Machines"},{"volume-title":"Genetic programming: On the programming of computers by means of natural selection","year":"1992","author":"Koza","key":"2024120202545137900_B20"},{"volume-title":"Genetic programming IV: Routine human-competitive machine intelligence","year":"2006","author":"Koza","key":"2024120202545137900_B21"},{"volume-title":"Introduction to formal languages, automata theory and computation","year":"2009","author":"Krithivasan","key":"2024120202545137900_B22"},{"key":"2024120202545137900_B23","doi-asserted-by":"crossref","first-page":"747","DOI":"10.1145\/1068009.1068134","article-title":"Learning computer programs with the Bayesian optimization algorithm","author":"Looks","year":"2005","journal-title":"Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO)"},{"issue":"3","key":"2024120202545137900_B24","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.ecoinf.2006.02.005","article-title":"Model-building with interpolated temporal data","volume":"1","author":"McKay","year":"2006","journal-title":"Ecological Informatics"},{"issue":"3\u20134","key":"2024120202545137900_B25","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/s10710-010-9109-y","article-title":"Grammar-based genetic programming: A survey","volume":"11","author":"McKay","year":"2010","journal-title":"Genetic Programming and Evolvable Machines"},{"volume-title":"An introduction to formal language theory","year":"2012","author":"Moll","key":"2024120202545137900_B26"},{"issue":"4","key":"2024120202545137900_B27","doi-asserted-by":"publisher","first-page":"443","DOI":"10.1007\/s11047-006-9007-7","article-title":"Grammatical swarm: The generation of programs by social programming","volume":"5","author":"O'Neill","year":"2006","journal-title":"Natural Computing"},{"key":"2024120202545137900_B28","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4615-0447-4","volume-title":"Grammatical evolution: Evolutionary automatic programming in an arbitrary language","author":"O'Neill","year":"2003"},{"issue":"3","key":"2024120202545137900_B29","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1007\/s10710-010-9113-2","article-title":"Open issues in genetic programming","volume":"11","author":"O'Neill","year":"2010","journal-title":"Genetic Programming and Evolvable Machines"},{"volume-title":"A field guide to genetic programming","year":"2008","author":"Poli","key":"2024120202545137900_B30"},{"year":"2017","author":"Ramos Criado","article-title":"New techinques for Grammar Guided Genetic Programming: Dealing with large derivation trees and high cardinality terminal symbol sets","key":"2024120202545137900_B31"},{"key":"2024120202545137900_B32","doi-asserted-by":"publisher","first-page":"11265","DOI":"10.1007\/s00500-020-05061-w","article-title":"Grammatically uniform population initialization for grammar-guided genetic programming","volume":"24","author":"Ramos Criado","year":"2020","journal-title":"Soft Computing"},{"key":"2024120202545137900_B33","first-page":"255","article-title":"Avoiding the bloat with stochastic grammar-based genetic programming","volume-title":"International Conference on Artificial Evolution","author":"Ratle","year":"2001"},{"key":"2024120202545137900_B34","first-page":"207","article-title":"A novel approach to machine discovery: Genetic programming and stochastic grammars","volume-title":"International Conference on Inductive Logic Programming","author":"Ratle","year":"2002"},{"key":"2024120202545137900_B35","doi-asserted-by":"crossref","DOI":"10.1007\/BFb0055930","article-title":"Grammatical evolution: Evolving programs for an arbitrary language","author":"Ryan","year":"1998","journal-title":"European Conference on Genetic Programming"},{"issue":"2","key":"2024120202545137900_B36","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1162\/evco.1997.5.2.123","article-title":"Probabilistic incremental program evolution","volume":"5","author":"Salustowicz","year":"1997","journal-title":"Evolutionary Computation"},{"key":"2024120202545137900_B37","first-page":"205","volume-title":"Probabilistic model building and competent genetic programming","author":"Sastry","year":"2006"},{"key":"2024120202545137900_B38","first-page":"121","volume-title":"A survey of probabilistic model building genetic programming","author":"Shan","year":"2003"},{"key":"2024120202545137900_B39","volume-title":"Introduction to the theory of computation","author":"Sipser","year":"2013","edition":"3rd"},{"key":"2024120202545137900_B40","first-page":"155","article-title":"Implications of incorporating learning probabilistic context-sensitive grammar in genetic programming on evolvability of adaptive locomotion gaits of snakebot","author":"Tanev","year":"2004","journal-title":"Proceedings of the Conference on Genetic and Evolutionary Computation (GECCO)"},{"issue":"188","key":"2024120202545137900_B41","doi-asserted-by":"publisher","DOI":"10.1007\/s42979-022-01045-9","article-title":"Grammatical evolution of complex digital circuits in SystemVerilog","volume":"3","author":"Tetteh","year":"2022","journal-title":"SN Computer Science"},{"key":"2024120202545137900_B42","article-title":"The role of syntactic and semantic locality of crossover in genetic programming","author":"Uy","year":"2010","journal-title":"11th International Conference on Parallel Problem Solving from Nature, Part II"},{"key":"2024120202545137900_B43","article-title":"Avoiding syntactically incorrect individuals via parameterized operators applied on derivation trees","volume":"4","author":"Vanyi","year":"2003","journal-title":"Congress on Evolutionary Computation"},{"key":"2024120202545137900_B44","article-title":"Grammatically-based genetic programming","author":"Whigham","year":"1995","journal-title":"Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications"},{"issue":"1","key":"2024120202545137900_B45","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s10710-012-9177-2","article-title":"Better GP benchmarks: Community survey results and proposals","volume":"14","author":"White","year":"2013","journal-title":"Genetic Programming and Evolvable Machines"},{"volume-title":"Data mining using grammar based genetic programming and applications","year":"2000","author":"Wong","key":"2024120202545137900_B46"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/32\/4\/339\/2477792\/evco_a_00345.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/32\/4\/339\/2477792\/evco_a_00345.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,12,2]],"date-time":"2024-12-02T02:55:10Z","timestamp":1733108110000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/32\/4\/339\/119215\/Estimation-of-Distribution-Algorithm-for-Grammar"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"references-count":46,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2024,12,2]]},"published-print":{"date-parts":[[2024,12,2]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00345","relation":{},"ISSN":["1530-9304"],"issn-type":[{"type":"electronic","value":"1530-9304"}],"subject":[],"published-other":{"date-parts":[[2024]]},"published":{"date-parts":[[2024]]}}}