{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,29]],"date-time":"2025-09-29T20:37:44Z","timestamp":1759178264891,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,6,8]],"date-time":"2024-06-08T00:00:00Z","timestamp":1717804800000},"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":[[2024,6,30]]},"abstract":"<jats:p>\n            Many optimization problems tackled by evolutionary algorithms are not only computationally expensive but also complicated, with one or more sources of noise. One technique to deal with high computational overhead is parallelization. However, though the existing literature gives good insight about the expected behavior of parallelized evolutionary algorithms, we still lack an understanding of their performance in the presence of noise. This article considers how parallelization might be leveraged together with multi-parent crossover in order to handle noisy problems. We present a rigorous running time analysis of an island model with weakly connected topology tasked with hill climbing in the presence of general additive noise (i.e., noisy\n            <jats:sc>OneMax<\/jats:sc>\n            ). Our proofs yield insights into the relationship between the noise intensity and number of required parents. We translate this into positive and negative results for two kinds of multi-parent crossover operators. We then empirically analyze and extend this framework to investigate the tradeoffs between noise impact, optimization time, and limits of computation power to deal with noise.\n          <\/jats:p>","DOI":"10.1145\/3630638","type":"journal-article","created":{"date-parts":[[2023,11,9]],"date-time":"2023-11-09T11:39:01Z","timestamp":1699529941000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["The Influence of Noise on Multi-parent Crossover for an Island Model Genetic Algorithm"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1749-437X","authenticated-orcid":false,"given":"Brahim","family":"Aboutaib","sequence":"first","affiliation":[{"name":"Univ. du Littoral C\u00f4te d\u2019Opale, Calais, France, and Mohammed V University in Rabat, Rabat, Morocco"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1295-6715","authenticated-orcid":false,"given":"Andrew M.","family":"Sutton","sequence":"additional","affiliation":[{"name":"University of Minnesota Duluth, Duluth, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,8]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"crossref","first-page":"666","DOI":"10.1145\/3512290.3528854","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference","author":"Aboutaib Brahim","year":"2022","unstructured":"Brahim Aboutaib and Andrew M. Sutton. 2022. The influence of noise on multi-parent crossover for an island model GA. In Proceedings of the Genetic and Evolutionary Computation Conference. 666\u2013674."},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2019.11.037"},{"key":"e_1_3_2_4_1","first-page":"892","volume-title":"Proceedings of the 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (Lecture Notes in Computer Science)","volume":"8672","author":"Badkobeh Golnaz","year":"2014","unstructured":"Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt. 2014. Unbiased black-box complexity of parallel search. In Proceedings of the 13th International Conference on Parallel Problem Solving from Nature (PPSN XIII) (Lecture Notes in Computer Science), Thomas Bartz-Beielstein, J\u00fcrgen Branke, Bogdan Filipic, and Jim Smith (Eds.), Vol. 8672. Springer, 892\u2013901. DOI:10.1007\/978-3-319-10762-2_88"},{"key":"e_1_3_2_5_1","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2725494.2725504","volume-title":"Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII","author":"Badkobeh Golnaz","year":"2015","unstructured":"Golnaz Badkobeh, Per Kristian Lehre, and Dirk Sudholt. 2015. Black-box complexity of parallel search with distributed populations. In Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII, Jun He, Thomas Jansen, Gabriela Ochoa, and Christine Zarges (Eds.). ACM, 3\u201315. DOI:10.1145\/2725494.2725504"},{"key":"e_1_3_2_6_1","first-page":"114","volume-title":"Proceedings of the 6th International Conference on Genetic Algorithms","author":"Belding Theodore C.","year":"1995","unstructured":"Theodore C. Belding. 1995. The distributed genetic algorithm revisited. In Proceedings of the 6th International Conference on Genetic Algorithms, Larry Eshelman (Ed.). Morgan Kaufmann, 114\u2013121. arxiv:adap-org\/adap-org\/9504007https:\/\/arxiv.org\/abs\/adap-org\/9504007"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCOMM.2011.072011.100049"},{"issue":"1","key":"e_1_3_2_8_1","first-page":"263","article-title":"On bounds for the normal integral","volume":"42","author":"Chu John T.","year":"1955","unstructured":"John T. Chu. 1955. On bounds for the normal integral. Biometrika 42, 1\/2 (1955), 263\u2013265. http:\/\/www.jstor.org\/stable\/2333443","journal-title":"Biometrika"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"issue":"3","key":"e_1_3_2_10_1","doi-asserted-by":"crossref","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","article-title":"Runtime analysis of non-elitist populations: From classical optimisation to partial information","volume":"75","author":"Dang Duc-Cuong","year":"2016","unstructured":"Duc-Cuong Dang and Per Kristian Lehre. 2016. Runtime analysis of non-elitist populations: From classical optimisation to partial information. Algorithmica 75, 3 (2016), 428\u2013461.","journal-title":"Algorithmica"},{"issue":"2","key":"e_1_3_2_11_1","doi-asserted-by":"crossref","first-page":"886","DOI":"10.1007\/s00453-018-0445-2","article-title":"Island models meet rumor spreading","volume":"81","author":"Doerr Benjamin","year":"2019","unstructured":"Benjamin Doerr, Philipp Fischbeck, Clemens Frahnow, Tobias Friedrich, Timo K\u00f6tzing, and Martin Schirneck. 2019. Island models meet rumor spreading. Algorithmica 81, 2 (2019), 886\u2013915.","journal-title":"Algorithmica"},{"key":"e_1_3_2_12_1","first-page":"1088","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201904), Part I (Lecture Notes in Computer Science)","volume":"3102","author":"Droste Stefan","year":"2004","unstructured":"Stefan Droste. 2004. Analysis of the (1+1) EA for a noisy OneMax. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201904), Part I (Lecture Notes in Computer Science), Kalyanmoy Deb, Riccardo Poli, Wolfgang Banzhaf, Hans-Georg Beyer, Edmund K. Burke, Paul J. Darwen, Dipankar Dasgupta, Dario Floreano, James A. Foster, Mark Harman, Owen Holland, Pier Luca Lanzi, Lee Spector, Andrea Tettamanzi, Dirk Thierens, and Andrew M. Tyrrell (Eds.), Vol. 3102. Springer, 1088\u20131099. DOI:10.1007\/978-3-540-24854-5_107"},{"key":"e_1_3_2_13_1","first-page":"78","volume-title":"Proceedings of the 3rd Conference on Parallel Problem Solving from Nature -(PPSN III), International Conference on Evolutionary Computation (Lecture Notes in Computer Science)","volume":"866","author":"Eiben A. E.","year":"1994","unstructured":"A. E. Eiben, Paul-Erik Rau\u00e9, and Zs\u00f3fia Ruttkay. 1994. Genetic algorithms with multi-parent recombination. In Proceedings of the 3rd Conference on Parallel Problem Solving from Nature -(PPSN III), International Conference on Evolutionary Computation (Lecture Notes in Computer Science), Yuval Davidor, Hans-Paul Schwefel, and Reinhard M\u00e4nner (Eds.), Vol. 866. Springer, 78\u201387. DOI:10.1007\/3-540-58484-6_252"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/CEC.2011.5949731"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00113893"},{"key":"e_1_3_2_16_1","first-page":"129","volume-title":"Proceedings of the 15th International Conference on Parallel Problem Solving from Nature (PPSN XV), Part II (Lecture Notes in Computer Science)","volume":"11102","author":"Frahnow Clemens","year":"2018","unstructured":"Clemens Frahnow and Timo K\u00f6tzing. 2018. Ring migration topology helps bypassing local optima. In Proceedings of the 15th International Conference on Parallel Problem Solving from Nature (PPSN XV), Part II (Lecture Notes in Computer Science), Anne Auger, Carlos M. Fonseca, Nuno Louren\u00e7o, Penousal Machado, Lu\u00eds Paquete, and L. Darrell Whitley (Eds.), Vol. 11102. Springer, 129\u2013140. DOI:10.1007\/978-3-319-99259-4_11"},{"key":"e_1_3_2_17_1","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/2908812.2908884","volume-title":"Proceedings of the 2016 on 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. 2016a. Fast building block assembly by majority vote crossover. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Tobias Friedrich, Frank Neumann, and Andrew M. Sutton (Eds.). ACM, 661\u2013668. DOI:10.1145\/2908812.2908884"},{"key":"e_1_3_2_18_1","doi-asserted-by":"crossref","first-page":"661","DOI":"10.1145\/2908812.2908884","volume-title":"Proceedings of the 2016 on 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. 2016b. Fast building block assembly by majority vote crossover. In Proceedings of the 2016 on Genetic and Evolutionary Computation Conference, Tobias Friedrich, Frank Neumann, and Andrew M. Sutton (Eds.). ACM, 661\u2013668. DOI:10.1145\/2908812.2908884"},{"key":"e_1_3_2_19_1","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-662-48971-0_13","volume-title":"International Symposium on Algorithms and Computation","author":"Friedrich Tobias","year":"2015","unstructured":"Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, and Andrew M. Sutton. 2015. The benefit of recombination in noisy evolutionary search. In International Symposium on Algorithms and Computation. Springer, 140\u2013150."},{"key":"e_1_3_2_20_1","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1145\/3040718.3040723","volume-title":"Proceedings of the 14th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA\u201917)","author":"Friedrich Tobias","year":"2017","unstructured":"Tobias Friedrich, Timo K\u00f6tzing, Francesco Quinzan, and Andrew M. Sutton. 2017a. Resampling vs recombination: A statistical run time estimation. In Proceedings of the 14th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA\u201917), Christian Igel, Dirk Sudholt, and Carsten Witt (Eds.). ACM, 25\u201335. DOI:10.1145\/3040718.3040723"},{"issue":"3","key":"e_1_3_2_21_1","first-page":"477","article-title":"The compact genetic algorithm is efficient under extreme gaussian noise","volume":"21","author":"Friedrich Tobias","year":"2017","unstructured":"Tobias Friedrich, Timo K\u00f6tzing, Martin S. Krejca, and Andrew M. Sutton. 2017b. The compact genetic algorithm is efficient under extreme gaussian noise. IEEE Transactions on Evolutionary Computation 21, 3 (2017), 477\u2013490.","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"3","key":"e_1_3_2_22_1","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/s00453-015-0072-0","article-title":"Robustness of populations in stochastic environments","volume":"75","author":"Gie\u00dfen Christian","year":"2016","unstructured":"Christian Gie\u00dfen and Timo K\u00f6tzing. 2016. Robustness of populations in stochastic environments. Algorithmica 75, 3 (2016), 462\u2013489.","journal-title":"Algorithmica"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3400031"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/4235.797971"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2005.846356"},{"key":"e_1_3_2_26_1","doi-asserted-by":"crossref","first-page":"490","DOI":"10.1007\/s00453-015-0048-0","article-title":"Concentration of first hitting times under additive drift","volume":"75","author":"K\u00f6tzing Timo","year":"2016","unstructured":"Timo K\u00f6tzing. 2016. Concentration of first hitting times under additive drift. Algorithmica 75 (2016), 490\u2013506.","journal-title":"Algorithmica"},{"key":"e_1_3_2_27_1","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1016\/j.tcs.2019.08.021","article-title":"First-hitting times under drift","volume":"796","author":"K\u00f6tzing Timo","year":"2019","unstructured":"Timo K\u00f6tzing and Martin S. Krejca. 2019. First-hitting times under drift. Theoretical Computer Science 796 (2019), 51\u201369.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00500-013-0991-0"},{"issue":"3","key":"e_1_3_2_29_1","doi-asserted-by":"crossref","first-page":"405","DOI":"10.1162\/EVCO_a_00114","article-title":"General upper bounds on the runtime of parallel evolutionary algorithms","volume":"22","author":"L\u00e4ssig J\u00f6rg","year":"2014","unstructured":"J\u00f6rg L\u00e4ssig and Dirk Sudholt. 2014. General upper bounds on the runtime of parallel evolutionary algorithms. Evolutionary Computation 22, 3 (2014), 405\u2013437.","journal-title":"Evolutionary Computation"},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TEVC.2019.2954234"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.camwa.2012.04.015"},{"issue":"2","key":"e_1_3_2_32_1","doi-asserted-by":"crossref","first-page":"641","DOI":"10.1007\/s00453-016-0262-4","article-title":"A runtime analysis of parallel evolutionary algorithms in dynamic optimization","volume":"78","author":"Lissovoi Andrei","year":"2017","unstructured":"Andrei Lissovoi and Carsten Witt. 2017. A runtime analysis of parallel evolutionary algorithms in dynamic optimization. Algorithmica 78, 2 (2017), 641\u2013659.","journal-title":"Algorithmica"},{"issue":"4","key":"e_1_3_2_33_1","doi-asserted-by":"crossref","first-page":"559","DOI":"10.1162\/EVCO_a_00153","article-title":"Design and analysis of schemes for adapting migration intervals in parallel evolutionary algorithms","volume":"23","author":"Mambrini Andrea","year":"2015","unstructured":"Andrea Mambrini and Dirk Sudholt. 2015. Design and analysis of schemes for adapting migration intervals in parallel evolutionary algorithms. Evolutionary Computation 23, 4 (2015), 559\u2013582.","journal-title":"Evolutionary Computation"},{"key":"e_1_3_2_34_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511814075","volume-title":"Randomized Algorithms","author":"Motwani Rajeev","year":"1995","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press."},{"key":"e_1_3_2_35_1","doi-asserted-by":"crossref","first-page":"1587","DOI":"10.1145\/2001576.2001790","volume-title":"Proceedings of the 13th Annual Genetic and Evolutionary Computation Conference (GECCO\u201911)","author":"Neumann Frank","year":"2011","unstructured":"Frank Neumann, Pietro S. 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 Genetic and Evolutionary Computation Conference (GECCO\u201911), Natalio Krasnogor and Pier Luca Lanzi (Eds.). ACM, 1587\u20131594. DOI:10.1145\/2001576.2001790"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-52915-4"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00201"},{"key":"e_1_3_2_38_1","volume-title":"R: A Language and Environment for Statistical Computing","author":"Team R Core","year":"2023","unstructured":"R Core Team. 2023. R: A Language and Environment for Statistical Computing. R Foundation for Statistical Computing, Vienna, Austria. https:\/\/www.R-project.org\/"},{"key":"e_1_3_2_39_1","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/3299904.3340305","volume-title":"Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA\u201919)","author":"Rowe Jonathan E.","year":"2019","unstructured":"Jonathan E. Rowe and Aishwaryaprajna. 2019. The benefits and limitations of voting mechanisms in evolutionary optimisation. In Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms (FOGA\u201919). 34\u201342. DOI:10.1145\/3299904.3340305"},{"key":"e_1_3_2_40_1","series-title":"Research","first-page":"5827","volume-title":"Proceedings of the 36th International Conference on Machine Learning","volume":"97","author":"Simsekli Umut","year":"2019","unstructured":"Umut Simsekli, Levent Sagun, and Mert Gurbuzbalaban. 2019. A tail-index analysis of stochastic gradient noise in deep neural networks. In Proceedings of the 36th International Conference on Machine LearningResearch, Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.), Vol. 97. PMLR, 5827\u20135837. https:\/\/proceedings.mlr.press\/v97\/simsekli19a.html"},{"key":"e_1_3_2_41_1","first-page":"1452","volume-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO\u201907)","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 Genetic and Evolutionary Computation Conference (GECCO\u201907), Hod Lipson (Ed.). ACM, 1452\u20131459. DOI:10.1145\/1276958.1277224"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/0-306-48041-7_14"},{"key":"e_1_3_2_43_1","first-page":"33","article-title":"The island model genetic algorithm: On separability, population size and convergence","volume":"7","author":"Whitley Darrell","year":"1998","unstructured":"Darrell Whitley, Soraya Rana, and Robert B. Heckendorn. 1998. The island model genetic algorithm: On separability, population size and convergence. Journal of Computing and Information Technology 7 (1998), 33\u201347.","journal-title":"Journal of Computing and Information Technology"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3630638","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3630638","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:32Z","timestamp":1750178192000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3630638"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,8]]},"references-count":42,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,6,30]]}},"alternative-id":["10.1145\/3630638"],"URL":"https:\/\/doi.org\/10.1145\/3630638","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"type":"print","value":"2688-299X"},{"type":"electronic","value":"2688-3007"}],"subject":[],"published":{"date-parts":[[2024,6,8]]},"assertion":[{"value":"2022-12-12","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-09-30","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}