{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,30]],"date-time":"2026-06-30T01:36:55Z","timestamp":1782783415886,"version":"3.54.5"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T00:00:00Z","timestamp":1664496000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Phoenix HPC service at the University of Adelaide and by the Australian Research Council","award":["DP190103894"],"award-info":[{"award-number":["DP190103894"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Evol. Learn. Optim."],"published-print":{"date-parts":[[2022,9,30]]},"abstract":"<jats:p>Generating diverse populations of high-quality solutions has gained interest as a promising extension to the traditional optimization tasks. This work contributes to this line of research with an investigation on evolutionary diversity optimization for three of the most well-studied permutation problems: the Traveling Salesperson Problem (TSP), both symmetric and asymmetric variants, and the Quadratic Assignment Problem (QAP). It includes an analysis of the worst-case performance of a simple mutation-only evolutionary algorithm with different mutation operators, using an established diversity measure. Theoretical results show that many mutation operators for these problems guarantee convergence to maximally diverse populations of sufficiently small size within cubic to quartic expected runtime. On the other hand, the results regarding QAP suggest that strong mutations give poor worst-case performance, as mutation strength contributes exponentially to the expected runtime. Additionally, experiments are carried out on QAPLIB and synthetic instances in unconstrained and constrained settings, and reveal much more optimistic practical performances while corroborating the theoretical findings regarding mutation strength. These results should serve as a baseline for future studies.<\/jats:p>","DOI":"10.1145\/3561974","type":"journal-article","created":{"date-parts":[[2022,9,7]],"date-time":"2022-09-07T11:28:04Z","timestamp":1662550084000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":14,"title":["Analysis of Evolutionary Diversity Optimization for Permutation Problems"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3850-1671","authenticated-orcid":false,"given":"Anh","family":"Do","sequence":"first","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3478-9201","authenticated-orcid":false,"given":"Mingyu","family":"Guo","sequence":"additional","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0036-4782","authenticated-orcid":false,"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[{"name":"Optimisation and Logistics, School of Computer Science, The University of Adelaide, Adelaide, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,10,19]]},"reference":[{"key":"e_1_3_2_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/s0305-0548(99)00067-2"},{"key":"e_1_3_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3071178.3071342"},{"key":"e_1_3_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-009-0517-7_2"},{"key":"e_1_3_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/cig.2019.8848022"},{"key":"e_1_3_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/e-science.2006.261199"},{"key":"e_1_3_2_7_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2021\/2"},{"key":"e_1_3_2_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103644"},{"key":"e_1_3_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299904.3340307"},{"key":"e_1_3_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459364"},{"key":"e_1_3_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459363"},{"key":"e_1_3_2_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44808-x_3"},{"key":"e_1_3_2_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/tevc.2017.2704781"},{"key":"e_1_3_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_22"},{"key":"e_1_3_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3377930.3389844"},{"key":"e_1_3_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459313"},{"key":"e_1_3_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4"},{"key":"e_1_3_2_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02846-5_29"},{"key":"e_1_3_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ftcs.1990.89393"},{"key":"e_1_3_2_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ISAAC.2020.26"},{"key":"e_1_3_2_21_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.STACS.2021.31"},{"key":"e_1_3_2_22_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00274"},{"key":"e_1_3_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4567-5_17"},{"key":"e_1_3_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/cig.2019.8848053"},{"key":"e_1_3_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205651.3205731"},{"key":"e_1_3_2_26_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v36i4.20290"},{"key":"e_1_3_2_27_1","first-page":"3778","volume-title":"35th AAAI Conference on Artificial Intelligence (AAAI\u201921), 33rd Conference on Innovative Applications of Artificial Intelligence (IAAI\u201921), 11th Symposium on Educational Advances in Artificial Intelligence (EAAI\u201921), Virtual Event, February 2-9, 2021","author":"Hanaka Tesshu","year":"2021","unstructured":"Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, and Yota Otachi. 2021. Finding diverse trees, paths, and more. In 35th AAAI Conference on Artificial Intelligence (AAAI\u201921), 33rd Conference on Innovative Applications of Artificial Intelligence (IAAI\u201921), 11th Symposium on Educational Advances in Artificial Intelligence (EAAI\u201921), Virtual Event, February 2-9, 2021, Palo Alto, California USA. AAAI Press, 3778\u20133786."},{"key":"e_1_3_2_28_1","first-page":"1","article-title":"Derangements and applications","volume":"6","author":"Hassani Mehdi","year":"2003","unstructured":"Mehdi Hassani. 2003. Derangements and applications. Journal of Integer Sequences 6 (2003), 1\u20138.","journal-title":"Journal of Integer Sequences"},{"key":"e_1_3_2_29_1","first-page":"372","volume-title":"Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, PA","author":"Hebrard Emmanuel","year":"2005","unstructured":"Emmanuel Hebrard, Brahim Hnich, Barry O\u2019Sullivan, and Toby Walsh. 2005. Finding diverse and similar solutions in constraint programming. In Proceedings of the 20th National Conference on Artificial Intelligence and the 17th Innovative Applications of Artificial Intelligence Conference, July 9-13, 2005, Pittsburgh, PA, Manuela M. Veloso and Subbarao Kambhampati (Eds.). AAAI Press\/The MIT Press, 372\u2013377."},{"key":"e_1_3_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/tevc.2019.2936440"},{"key":"e_1_3_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/cec48606.2020.9185573"},{"key":"e_1_3_2_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ssci.2018.8628856"},{"key":"e_1_3_2_33_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5512"},{"key":"e_1_3_2_34_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.28.5.1086"},{"key":"e_1_3_2_35_1","doi-asserted-by":"publisher","DOI":"10.1162\/evco_a_00242"},{"key":"e_1_3_2_36_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0062186"},{"key":"e_1_3_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"e_1_3_2_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/tevc.2016.2638437"},{"key":"e_1_3_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/bf00253805"},{"key":"e_1_3_2_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.knosys.2004.03.001"},{"key":"e_1_3_2_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-21581-0_23"},{"key":"e_1_3_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459385"},{"key":"e_1_3_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3205455.3205532"},{"key":"e_1_3_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3321707.3321796"},{"key":"e_1_3_2_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16544-3"},{"key":"e_1_3_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/3450218.3477310"},{"key":"e_1_3_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3449639.3459384"},{"key":"e_1_3_2_48_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.16.1.150"},{"key":"e_1_3_2_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/2832249.2832285"},{"key":"e_1_3_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-07407-8"},{"key":"e_1_3_2_51_1","doi-asserted-by":"publisher","DOI":"10.3389\/frobt.2016.00040"},{"key":"e_1_3_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/icec.1995.487459"},{"key":"e_1_3_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ictai.2019.00012"},{"key":"e_1_3_2_54_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1080.0633"},{"key":"e_1_3_2_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-92910-9_32"},{"key":"e_1_3_2_56_1","doi-asserted-by":"publisher","DOI":"10.1016\/0305-0548(93)e0020-t"},{"key":"e_1_3_2_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2014.05.394"},{"key":"e_1_3_2_58_1","doi-asserted-by":"publisher","DOI":"10.1080\/0740817x.2015.1019161"},{"key":"e_1_3_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830483.1830569"},{"key":"e_1_3_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2001576.2001665"},{"key":"e_1_3_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487689"},{"key":"e_1_3_2_62_1","first-page":"1","volume-title":"Evolutionary Multimodal Optimization: A Short Survey","author":"Wong Ka-Chun","year":"2015","unstructured":"Ka-Chun Wong. 2015. Evolutionary Multimodal Optimization: A Short Survey. Nova Science Publishers, Inc., 1\u201315."},{"key":"e_1_3_2_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-015-0408-z"}],"container-title":["ACM Transactions on Evolutionary Learning and Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561974","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561974","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:07Z","timestamp":1750182547000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561974"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,9,30]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9,30]]}},"alternative-id":["10.1145\/3561974"],"URL":"https:\/\/doi.org\/10.1145\/3561974","relation":{},"ISSN":["2688-299X","2688-3007"],"issn-type":[{"value":"2688-299X","type":"print"},{"value":"2688-3007","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,9,30]]},"assertion":[{"value":"2021-10-04","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-09-02","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}