{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T20:45:37Z","timestamp":1760647537031},"reference-count":27,"publisher":"MIT Press","issue":"3","license":[{"start":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T00:00:00Z","timestamp":1639353600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>An optimal recombination operator for two-parent solutions provides the best solution among those that take the value for each variable from one of the parents (gene transmission property). If the solutions are bit strings, the offspring of an optimal recombination operator is optimal in the smallest hyperplane containing the two parent solutions. Exploring this hyperplane is computationally costly, in general, requiring exponential time in the worst case. However, when the variable interaction graph of the objective function is sparse, exploration can be done in polynomial time. In this article, we present a recombination operator, called Dynastic Potential Crossover (DPX), that runs in polynomial time and behaves like an optimal recombination operator for low-epistasis combinatorial problems. We compare this operator, both theoretically and experimentally, with traditional crossover operators, like uniform crossover and network crossover, and with two recently defined efficient recombination operators: partition crossover and articulation points partition crossover. The empirical comparison uses NKQ Landscapes and MAX-SAT instances. DPX outperforms the other crossover operators in terms of quality of the offspring and provides better results included in a trajectory and a population-based metaheuristic, but it requires more time and memory to compute the offspring.<\/jats:p>","DOI":"10.1162\/evco_a_00305","type":"journal-article","created":{"date-parts":[[2021,12,13]],"date-time":"2021-12-13T15:16:43Z","timestamp":1639408603000},"page":"409-446","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":7,"title":["Dynastic Potential Crossover Operator"],"prefix":"10.1162","volume":"30","author":[{"given":"Francisco","family":"Chicano","sequence":"first","affiliation":[{"name":"ITIS Software, University of Malaga, Spain chicano@lcc.uma.es"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gabriela","family":"Ochoa","sequence":"additional","affiliation":[{"name":"University of Stirling, UK gabriela.ochoa@cs.stir.ac.uk"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"L. Darrell","family":"Whitley","sequence":"additional","affiliation":[{"name":"Colorado State University, USA whitley@cs.colostate.edu"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Renato","family":"Tin\u00f3s","sequence":"additional","affiliation":[{"name":"University of Sao Paulo, Brazil rtinos@ffclrp.usp.br"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"281","published-online":{"date-parts":[[2022,9,1]]},"reference":[{"key":"2022090106561234300_B1","first-page":"1","volume-title":"Proceedings of SOFSEM","author":"Bodlaender","year":"2005"},{"key":"2022090106561234300_B2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2020.103354","article-title":"Old techniques in new ways: Clause weighting, unit propagation and hybridization for maximum satisfiability.","volume":"287","author":"Cai","year":"2020","journal-title":"Artificial Intelligence"},{"key":"2022090106561234300_B3","first-page":"75","article-title":"Decomposing SAT instances with pseudo backbones.","volume":"10197","author":"Chen","year":"2017","journal-title":"Proceedings of EvoCOP"},{"key":"2022090106561234300_B4","doi-asserted-by":"crossref","first-page":"921","DOI":"10.1145\/3205455.3205482","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Chen","year":"2018"},{"key":"2022090106561234300_B5","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1145\/3205455.3205561","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Chicano","year":"2018"},{"key":"2022090106561234300_B6","first-page":"131","article-title":"Quasi-optimal recombination operator","volume":"11452","author":"Chicano","year":"2019","journal-title":"Proceedings of EvoCOP"},{"key":"2022090106561234300_B7","doi-asserted-by":"crossref","first-page":"753","DOI":"10.1145\/3071178.3071285","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Chicano","year":"2017"},{"key":"2022090106561234300_B8","article-title":"Optimal recombination in genetic algorithms.","author":"Eremeev","year":"2013","journal-title":"CoRR"},{"key":"2022090106561234300_B9","volume-title":"Graph-theoretic concepts in computer science","author":"Galinier","year":"1995"},{"key":"2022090106561234300_B10","first-page":"359","article-title":"On the determination of the minima of pseudo-Boolean functions.","volume":"14","author":"Hammer","year":"1963","journal-title":"Studii \u015fi Cercet\u0103ri de Matematic\u0103"},{"key":"2022090106561234300_B11","first-page":"713","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Hauschild","year":"2010"},{"key":"2022090106561234300_B12","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1142\/S0219525998000041","article-title":"Amplitude spectra of fitness landscapes.","volume":"1","author":"Hordijk","year":"1998","journal-title":"Advances in Complex Systems"},{"key":"2022090106561234300_B13","doi-asserted-by":"crossref","first-page":"43","DOI":"10.1016\/j.orp.2016.09.002","article-title":"The irace package: Iterated racing for automatic algorithm configuration.","volume":"3","author":"L\u00f3pez-Ib\u00e1\u00f1ez","year":"2016","journal-title":"Operations Research Perspectives"},{"key":"2022090106561234300_B14","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1098\/rspb.1998.0438","article-title":"Effect of neutral selection on the evolution of molecular species.","volume":"265","author":"Newman","year":"1998","journal-title":"Proceedings of the Royal Society of London B"},{"key":"2022090106561234300_B15","doi-asserted-by":"crossref","first-page":"1430","DOI":"10.1145\/3319619.3326855","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO) Companion","author":"Ochoa","year":"2019"},{"key":"2022090106561234300_B16","first-page":"449","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Ochoa","year":"2015"},{"key":"2022090106561234300_B17","first-page":"555","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)","author":"Ochoa","year":"2008"},{"issue":"3","key":"2022090106561234300_B18","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s10732-017-9334-0","article-title":"Mapping the global structure of TSP fitness landscapes","volume":"24","author":"Ochoa","year":"2018","journal-title":"Journal of Heuristics"},{"issue":"4","key":"2022090106561234300_B19","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/BF01531276","article-title":"The algebra of genetic algorithms","volume":"10","author":"Radcliffe","year":"1994","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"2022090106561234300_B20","first-page":"392","volume-title":"Proceedings of AAAI","author":"Rana","year":"1998"},{"issue":"2","key":"2022090106561234300_B21","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1145\/321879.321884","article-title":"Efficiency of a good but not linear set union algorithm","volume":"22","author":"Tarjan","year":"1975","journal-title":"Journal of the ACM"},{"issue":"3","key":"2022090106561234300_B22","doi-asserted-by":"publisher","first-page":"566","DOI":"10.1137\/0213035","article-title":"Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs","volume":"13","author":"Tarjan","year":"1984","journal-title":"SIAM Journal on Computing"},{"key":"2022090106561234300_B23","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511626265","volume-title":"Fourier analysis on finite groups and applications","author":"Terras","year":"1999"},{"key":"2022090106561234300_B24","first-page":"137","volume-title":"Proceedings of Foundations of Genetic Algorithms","author":"Tin\u00f3s","year":"2015"},{"issue":"5","key":"2022090106561234300_B25","doi-asserted-by":"crossref","first-page":"748","DOI":"10.1109\/TEVC.2018.2828643","article-title":"NK hybrid genetic algorithm for clustering","volume":"22","author":"Tin\u00f3s","year":"2018","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2022090106561234300_B26","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1162\/EVCO_a_00184","article-title":"Gray box optimization for Mk landscapes (NK landscapes and MAX-kSAT).","volume":"24","author":"Whitley","year":"2016","journal-title":"Evolutionary Computation"},{"issue":"4","key":"2022090106561234300_B27","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1109\/4235.887236","article-title":"The computational complexity of NK fitness functions","volume":"4","author":"Wright","year":"2000","journal-title":"IEEE Transactions on Evolutionary Computation"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/30\/3\/409\/2040916\/evco_a_00305.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/30\/3\/409\/2040916\/evco_a_00305.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,1]],"date-time":"2022-09-01T06:56:41Z","timestamp":1662015401000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/30\/3\/409\/108663\/Dynastic-Potential-Crossover-Operator"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"references-count":27,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2022,9,1]]},"published-print":{"date-parts":[[2022,9,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00305","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2022]]},"published":{"date-parts":[[2022]]}}}