{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:59:28Z","timestamp":1783749568815,"version":"3.55.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,6,28]],"date-time":"2023-06-28T00:00:00Z","timestamp":1687910400000},"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":[[2023,6,30]]},"abstract":"<jats:p>\n            To understand better how and why crossover can benefit constrained optimization, we consider pseudo-Boolean functions with an upper bound\n            <jats:italic>B<\/jats:italic>\n            on the number of 1-bits allowed in the length-\n            <jats:italic>n<\/jats:italic>\n            bit string (i.e., a cardinality constraint). We investigate the natural translation of the OneMax test function to this setting, a linear function where\n            <jats:italic>B<\/jats:italic>\n            bits have a weight of 1+ 1\/\n            <jats:italic>n<\/jats:italic>\n            and the remaining bits have a weight of 1. Friedrich\u00a0et\u00a0al.\u00a0[TCS 2020] gave a bound of \u0398 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) for the expected running time of the (1+1)\u00a0EA on this function.\n          <\/jats:p>\n          <jats:p>\n            Part of the difficulty when optimizing this problem lies in having to improve individuals meeting the cardinality constraint by flipping a 1 and a 0 simultaneously. The experimental literature proposes balanced operators, preserving the number of 1-bits, as a remedy. We show that a balanced mutation operator optimizes the problem in\n            <jats:italic>O(n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) if\n            <jats:italic>n-B<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (1). However, if\n            <jats:italic>n-B<\/jats:italic>\n            = \u0398 (\n            <jats:italic>n<\/jats:italic>\n            ), we show a bound of \u03a9 (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ), just as for classic bit mutation. Crossover together with a simple island model gives running times of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            \/ log\n            <jats:italic>n<\/jats:italic>\n            ) (uniform crossover) and\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(O(n\\sqrt {n})\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (3-ary majority vote crossover). For balanced uniform crossover with Hamming-distance maximization for diversity, we show a bound of\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>\n          <jats:p>As an additional contribution, we present an extensive analysis of different balanced crossover operators from the literature.<\/jats:p>","DOI":"10.1145\/3603629","type":"journal-article","created":{"date-parts":[[2023,6,9]],"date-time":"2023-06-09T12:29:33Z","timestamp":1686313773000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Crossover for Cardinality Constrained Optimization"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0076-6308","authenticated-orcid":false,"given":"Tobias","family":"Friedrich","sequence":"first","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1028-5228","authenticated-orcid":false,"given":"Timo","family":"K\u00f6tzing","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5667-8780","authenticated-orcid":false,"given":"Aishwarya","family":"Radhakrishnan","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7315-237X","authenticated-orcid":false,"given":"Leon","family":"Schiller","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7086-5577","authenticated-orcid":false,"given":"Martin","family":"Schirneck","sequence":"additional","affiliation":[{"name":"Faculty of Computer Science, University of Vienna, Austria"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0734-0684","authenticated-orcid":false,"given":"Georg","family":"Tennigkeit","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0734-0708","authenticated-orcid":false,"given":"Simon","family":"Wietheger","sequence":"additional","affiliation":[{"name":"Hasso Plattner Institute, University of Potsdam, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,28]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"crossref","first-page":"1268","DOI":"10.1145\/3377930.3390172","volume-title":"Proceedings of the 2020 Genetic and Evolutionary Computation Conference","author":"Antipov Denis","year":"2020","unstructured":"Denis Antipov, Maxim Buzdalov, and Benjamin Doerr. 2020. Fast mutation in crossover-based algorithms. In Proceedings of the 2020 Genetic and Evolutionary Computation Conference. 1268\u20131276. DOI:10.1145\/3377930.3390172"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/11779568_23"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2745715"},{"key":"e_1_3_2_5_1","doi-asserted-by":"crossref","first-page":"645","DOI":"10.1145\/2908812.2908956","volume-title":"Proceedings of the 2016 Genetic and Evolutionary Computation Conference","author":"Dang Duc-Cuong","year":"2016","unstructured":"Duc-Cuong Dang, Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, Per Kristian Lehre, Pietro S. Oliveto, Dirk Sudholt, and Andrew M. Sutton. 2016. Escaping local optima with diversity mechanisms and crossover. In Proceedings of the 2016 Genetic and Evolutionary Computation Conference. 645\u2013652. DOI:10.1145\/2908812.2908956"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2017.2724201"},{"key":"e_1_3_2_7_1","doi-asserted-by":"crossref","first-page":"1423","DOI":"10.1145\/2739480.2754683","volume-title":"Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation","author":"Doerr Benjamin","year":"2015","unstructured":"Benjamin Doerr and Carola Doerr. 2015. A tight runtime analysis of the \\((1+ (\\lambda , \\lambda))\\) genetic algorithm on OneMax. In Proceedings of the 2015 Annual Conference on Genetic and Evolutionary Computation. ACM, New York, NY, 1423\u20131430. DOI:10.1145\/2739480.2754683"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-018-0445-2"},{"key":"e_1_3_2_9_1","doi-asserted-by":"crossref","first-page":"1142","DOI":"10.1145\/3449639.3459352","volume-title":"Proceedings of the 2021 Genetic and Evolutionary Computation Conference","author":"Doerr Benjamin","year":"2021","unstructured":"Benjamin Doerr and Timo K\u00f6tzing. 2021. Lower bounds from fitness levels made easy. In Proceedings of the 2021 Genetic and Evolutionary Computation Conference. ACM, 1142\u20131150. DOI:10.1145\/3449639.3459352"},{"key":"e_1_3_2_10_1","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/2908812.2908884","volume-title":"Proceedings of the 2016 Genetic and Evolutionary Computation Conference","author":"Friedrich Tobias","year":"2016","unstructured":"Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, Samadhi Nallaperuma, Frank Neumann, and Martin Schirneck. 2016. Fast building block assembly by majority vote crossover. In Proceedings of the 2016 Genetic and Evolutionary Computation Conference. 661\u2013668. DOI:10.1145\/2908812.2908884"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.04.051"},{"key":"e_1_3_2_12_1","doi-asserted-by":"crossref","first-page":"1399","DOI":"10.1145\/3512290.3528713","volume-title":"Proceedings of the 2022 Genetic and Evolutionary Computation Conference","author":"Friedrich Tobias","year":"2022","unstructured":"Tobias Friedrich, Timo K\u00f6tzing, Aishwarya Radhakrishnan, Leon Schiller, Martin Schirneck, Georg Tennigkeit, and Simon Wietheger. 2022. Crossover for cardinality constrained optimization. In Proceedings of the 2022 Genetic and Evolutionary Computation Conference. 1399\u20131407. DOI:10.1145\/3512290.3528713"},{"key":"e_1_3_2_13_1","first-page":"16","volume-title":"Proceedings of the 13th Conference on Foundations of Genetic Algorithms","author":"Jansen Thomas","year":"2015","unstructured":"Thomas Jansen. 2015. On the black-box complexity of example functions: The real jump function. In Proceedings of the 13th Conference on Foundations of Genetic Algorithms. 16\u201324. DOI:10.1145\/2725494.2725507"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco.2010.18.1.18101"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-002-0940-2"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.spl.2017.11.017"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11042-020-10139-6"},{"key":"e_1_3_2_18_1","first-page":"989","volume-title":"Proceedings of the 2011 Genetic and Evolutionary Computation Conference","author":"K\u00f6tzing Timo","year":"2011","unstructured":"Timo K\u00f6tzing, Dirk Sudholt, and Madeleine Theile. 2011. How crossover helps in pseudo-boolean optimization. In Proceedings of the 2011 Genetic and Evolutionary Computation Conference. 989\u2013996. DOI:10.1145\/2001576.2001711"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9616-8"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.swevo.2020.100646"},{"key":"e_1_3_2_21_1","first-page":"1809","volume-title":"Proceedings of the 2009 Genetic and Evolutionary Computation Conference","author":"Meinl Thorsten","year":"2009","unstructured":"Thorsten Meinl and Michael R. Berthold. 2009. Crossover operators for multiobjective k-subset selection. In Proceedings of the 2009 Genetic and Evolutionary Computation Conference. 1809\u20131810. DOI:10.1145\/1569901.1570173"},{"key":"e_1_3_2_22_1","doi-asserted-by":"crossref","first-page":"1377","DOI":"10.1007\/978-3-540-24854-5_131","volume-title":"Proceedings of the 2004 Genetic and Evolutionary Computation Conference","author":"Moraglio Alberto","year":"2004","unstructured":"Alberto Moraglio and Riccardo Poli. 2004. Topological interpretation of crossover. In Proceedings of the 2004 Genetic and Evolutionary Computation Conference. Kalyanmoy Deb (Ed.), Springer, 1377\u20131388. DOI:10.1007\/978-3-540-24854-5_131"},{"key":"e_1_3_2_23_1","doi-asserted-by":"crossref","first-page":"1587","DOI":"10.1145\/2001576.2001790","volume-title":"Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation","author":"Neumann Frank","year":"2011","unstructured":"Frank Neumann, Pietro Simone Oliveto, G\u00fcnter Rudolph, and Dirk Sudholt. 2011. On the effectiveness of crossover for migration in parallel evolutionary algorithms. In Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation. ACM, 1587\u20131594. DOI:10.1145\/2001576.2001790"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.11.002"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01531276"},{"key":"e_1_3_2_26_1","first-page":"2035","volume-title":"Proceedings of the 2011 Genetic and Evolutionary Computation Conference","author":"Rowe Jonathan E.","year":"2011","unstructured":"Jonathan E. Rowe and Michael D. Vose. 2011. Unbiased black box search algorithms. In Proceedings of the 2011 Genetic and Evolutionary Computation Conference. 2035\u20132042. DOI:10.1145\/2001576.2001850"},{"key":"e_1_3_2_27_1","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00171"},{"key":"e_1_3_2_28_1","doi-asserted-by":"crossref","first-page":"1452","DOI":"10.1145\/1276958.1277224","volume-title":"Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation","author":"Watson Richard A.","year":"2007","unstructured":"Richard A. Watson and Thomas Jansen. 2007. A building-block royal road where crossover is provably essential. In Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation. ACM, 1452\u20131459. DOI:10.1145\/1276958.1277224"},{"key":"e_1_3_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-306-48041-7_14"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1162\/EVCO_a_00184"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.09.013"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603629","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3603629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:21Z","timestamp":1750178241000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3603629"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,28]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1145\/3603629"],"URL":"https:\/\/doi.org\/10.1145\/3603629","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,28]]},"assertion":[{"value":"2022-10-07","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-21","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-06-28","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}