{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:35:40Z","timestamp":1742913340910,"version":"3.40.3"},"publisher-location":"Cham","reference-count":34,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783031700705"},{"type":"electronic","value":"9783031700712"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024]]},"DOI":"10.1007\/978-3-031-70071-2_10","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774000},"page":"149-165","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Analysis of\u00a0Evolutionary Diversity Optimisation for\u00a0the\u00a0Maximum Matching Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0869-0865","authenticated-orcid":false,"given":"Jonathan","family":"Gadea Harder","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0036-4782","authenticated-orcid":false,"given":"Aneta","family":"Neumann","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":false,"given":"Frank","family":"Neumann","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"doi-asserted-by":"publisher","unstructured":"Alvarez, A., Dahlskog, S., Font, J.M., Togelius, J.: Empowering quality diversity in dungeon design with interactive constrained map-elites. In: IEEE Conference on Games, CoG 2019, pp.\u00a01\u20138. IEEE (2019). https:\/\/doi.org\/10.1109\/CIG.2019.8848022","key":"10_CR1","DOI":"10.1109\/CIG.2019.8848022"},{"doi-asserted-by":"publisher","unstructured":"Bossek, J., Neumann, A., Neumann, F.: Breeding diverse packings for the knapsack problem by means of diversity-tailored evolutionary algorithms. In: Chicano, F., Krawiec, K. (eds.) GECCO 2021: Genetic and Evolutionary Computation Conference, Lille, France, 10\u201314 July 2021, pp. 556\u2013564. ACM (2021). https:\/\/doi.org\/10.1145\/3449639.3459364","key":"10_CR2","DOI":"10.1145\/3449639.3459364"},{"doi-asserted-by":"publisher","unstructured":"Bossek, J., Neumann, F.: Evolutionary diversity optimization and the minimum spanning tree problem. In: Chicano, F., Krawiec, K. (eds.) GECCO 2021: Genetic and Evolutionary Computation Conference, Lille, France, 10\u201314 July 2021, pp. 198\u2013206. ACM (2021). https:\/\/doi.org\/10.1145\/3449639.3459363","key":"10_CR3","DOI":"10.1145\/3449639.3459363"},{"issue":"2","key":"10_CR4","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1109\/TEVC.2020.3036578","volume":"25","author":"DM Bossens","year":"2021","unstructured":"Bossens, D.M., Tarapore, D.: QED: using quality-environment-diversity to evolve resilient robot swarms. IEEE Trans. Evol. Comput. 25(2), 346\u2013357 (2021). https:\/\/doi.org\/10.1109\/TEVC.2020.3036578","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"2","key":"10_CR5","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1109\/TEVC.2017.2704781","volume":"22","author":"A Cully","year":"2018","unstructured":"Cully, A., Demiris, Y.: Quality and diversity optimization: a unifying modular framework. IEEE Trans. Evol. Comput. 22(2), 245\u2013259 (2018). https:\/\/doi.org\/10.1109\/TEVC.2017.2704781","journal-title":"IEEE Trans. Evol. Comput."},{"doi-asserted-by":"publisher","unstructured":"Do, A.V., Bossek, J., Neumann, A., Neumann, F.: Evolving diverse sets of tours for the travelling salesperson problem. In: Coello, C.A.C. (ed.) GECCO 2020: Genetic and Evolutionary Computation Conference, Canc\u00fan Mexico, 8\u201312 July 2020, pp. 681\u2013689. ACM (2020). https:\/\/doi.org\/10.1145\/3377930.3389844","key":"10_CR6","DOI":"10.1145\/3377930.3389844"},{"doi-asserted-by":"publisher","unstructured":"Do, A.V., Guo, M., Neumann, A., Neumann, F.: Analysis of evolutionary diversity optimization for permutation problems. ACM Trans. Evol. Learn. Optim. 2(3), 11:1\u201311:27 (2022). https:\/\/doi.org\/10.1145\/3561974","key":"10_CR7","DOI":"10.1145\/3561974"},{"doi-asserted-by":"publisher","unstructured":"Do, A.V., Guo, M., Neumann, A., Neumann, F.: Diverse approximations for monotone submodular maximization problems with a matroid constraint. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5558\u20135566. ijcai.org (2023). https:\/\/doi.org\/10.24963\/IJCAI.2023\/617","key":"10_CR8","DOI":"10.24963\/IJCAI.2023\/617"},{"issue":"4","key":"10_CR9","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/S00453-012-9622-X","volume":"64","author":"B Doerr","year":"2012","unstructured":"Doerr, B., Johannsen, D., Winzen, C.: Multiplicative drift analysis. Algorithmica 64(4), 673\u2013697 (2012). https:\/\/doi.org\/10.1007\/S00453-012-9622-X","journal-title":"Algorithmica"},{"issue":"17","key":"10_CR10","doi-asserted-by":"publisher","first-page":"1546","DOI":"10.1016\/J.TCS.2010.09.023","volume":"412","author":"T Friedrich","year":"2011","unstructured":"Friedrich, T., Horoba, C., Neumann, F.: Illustration of fairness in evolutionary multi-objective optimization. Theor. Comput. Sci. 412(17), 1546\u20131556 (2011). https:\/\/doi.org\/10.1016\/J.TCS.2010.09.023","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"10_CR11","doi-asserted-by":"publisher","first-page":"455","DOI":"10.1162\/EVCO.2009.17.4.17401","volume":"17","author":"T Friedrich","year":"2009","unstructured":"Friedrich, T., Oliveto, P.S., Sudholt, D., Witt, C.: Analysis of diversity-preserving mechanisms for global exploration. Evol. Comput. 17(4), 455\u2013476 (2009). https:\/\/doi.org\/10.1162\/EVCO.2009.17.4.17401","journal-title":"Evol. Comput."},{"issue":"1","key":"10_CR12","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1162\/evco_a_00274","volume":"29","author":"W Gao","year":"2021","unstructured":"Gao, W., Nallaperuma, S., Neumann, F.: Feature-based diversity optimization for problem instance classification. Evol. Comput. 29(1), 107\u2013128 (2021). https:\/\/doi.org\/10.1162\/evco_a_00274","journal-title":"Evol. Comput."},{"doi-asserted-by":"publisher","unstructured":"Gao, W., Pourhassan, M., Neumann, F.: Runtime analysis of evolutionary diversity optimization and the vertex cover problem. In: Silva, S., Esparcia-Alc\u00e1zar, A.I. (eds.) Genetic and Evolutionary Computation Conference, GECCO 2015, Companion Material Proceedings, pp. 1395\u20131396. ACM (2015). https:\/\/doi.org\/10.1145\/2739482.2764668","key":"10_CR13","DOI":"10.1145\/2739482.2764668"},{"doi-asserted-by":"crossref","unstructured":"Gounder, S., Neumann, F., Neumann, A.: Evolutionary diversity optimisation for sparse directed communication networks. In: Genetic and Evolutionary Computation Conference, GECCO 2024. ACM (2024, to appear)","key":"10_CR14","DOI":"10.1145\/3638529.3654184"},{"doi-asserted-by":"publisher","unstructured":"Gravina, D., Khalifa, A., Liapis, A., Togelius, J., Yannakakis, G.N.: Procedural content generation through quality diversity. In: IEEE Conference on Games, CoG 2019, London, United Kingdom, 20\u201323 August 2019, pp.\u00a01\u20138. IEEE (2019). https:\/\/doi.org\/10.1109\/CIG.2019.8848053","key":"10_CR15","DOI":"10.1109\/CIG.2019.8848053"},{"unstructured":"Harder, J.G., Neumann, A., Neumann, F.: Analysis of evolutionary diversity optimisation for the maximum matching problem (2024). https:\/\/arxiv.org\/abs\/2404.11784","key":"10_CR16"},{"issue":"1","key":"10_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1023\/B:NACO.0000023417.31393.C7","volume":"3","author":"J He","year":"2004","unstructured":"He, J., Yao, X.: A study of drift analysis for estimating computation time of evolutionary algorithms. Nat. Comput. 3(1), 21\u201335 (2004). https:\/\/doi.org\/10.1023\/B:NACO.0000023417.31393.C7","journal-title":"Nat. Comput."},{"doi-asserted-by":"publisher","unstructured":"Hopcroft, J.E., Karp, R.M.: An N5\/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). https:\/\/doi.org\/10.1137\/0202019","key":"10_CR18","DOI":"10.1137\/0202019"},{"unstructured":"Mouret, J.B., Clune, J.: Illuminating search spaces by mapping elites. arXiv preprint arXiv:1504.04909 (2015)","key":"10_CR19"},{"doi-asserted-by":"publisher","unstructured":"Neumann, A., Antipov, D., Neumann, F.: Coevolutionary pareto diversity optimization. In: GECCO 2022: Genetic and Evolutionary Computation Conference, pp. 832\u2013839. ACM (2022). https:\/\/doi.org\/10.1145\/3512290.3528755","key":"10_CR20","DOI":"10.1145\/3512290.3528755"},{"doi-asserted-by":"publisher","unstructured":"Neumann, A., Bossek, J., Neumann, F.: Diversifying greedy sampling and evolutionary diversity optimisation for constrained monotone submodular functions. In: GECCO 2021: Genetic and Evolutionary Computation Conference, pp. 261\u2013269. ACM (2021). https:\/\/doi.org\/10.1145\/3449639.3459385","key":"10_CR21","DOI":"10.1145\/3449639.3459385"},{"doi-asserted-by":"publisher","unstructured":"Neumann, A., Gao, W., Doerr, C., Neumann, F., Wagner, M.: Discrepancy-based evolutionary diversity optimization. In: Proceedings of the Genetic and Evolutionary Computation Conference, pp. 991\u2013998. ACM (2018). https:\/\/doi.org\/10.1145\/3205455.3205532","key":"10_CR22","DOI":"10.1145\/3205455.3205532"},{"doi-asserted-by":"publisher","unstructured":"Neumann, A., Gao, W., Wagner, M., Neumann, F.: Evolutionary diversity optimization using multi-objective indicators. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2019, pp. 837\u2013845. ACM (2019). https:\/\/doi.org\/10.1145\/3321707.3321796","key":"10_CR23","DOI":"10.1145\/3321707.3321796"},{"doi-asserted-by":"publisher","unstructured":"Neumann, A., et al.: Diversity optimization for the detection and concealment of spatially defined communication networks. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2023, pp. 1436\u20131444. ACM (2023). https:\/\/doi.org\/10.1145\/3583131.3590405","key":"10_CR24","DOI":"10.1145\/3583131.3590405"},{"doi-asserted-by":"publisher","unstructured":"Neumann, F., Witt, C.: Bioinspired computation in combinatorial optimization: algorithms and their computational complexity. In: Blum, C., Alba, E. (eds.) Genetic and Evolutionary Computation Conference, GECCO 2013, pp. 567\u2013590. ACM (2013). https:\/\/doi.org\/10.1145\/2464576.2466738","key":"10_CR25","DOI":"10.1145\/2464576.2466738"},{"doi-asserted-by":"publisher","unstructured":"Nikfarjam, A., Bossek, J., Neumann, A., Neumann, F.: Computing diverse sets of high quality TSP tours by eax-based evolutionary diversity optimisation. In: FOGA 2021: Foundations of Genetic Algorithms XVI, pp. 9:1\u20139:11. ACM (2021). https:\/\/doi.org\/10.1145\/3450218.3477310","key":"10_CR26","DOI":"10.1145\/3450218.3477310"},{"doi-asserted-by":"publisher","unstructured":"Nikfarjam, A., Bossek, J., Neumann, A., Neumann, F.: Entropy-based evolutionary diversity optimisation for the traveling salesperson problem. In: GECCO 2021: Genetic and Evolutionary Computation Conference, pp. 600\u2013608. ACM (2021). https:\/\/doi.org\/10.1145\/3449639.3459384","key":"10_CR27","DOI":"10.1145\/3449639.3459384"},{"doi-asserted-by":"publisher","unstructured":"Nikfarjam, A., Neumann, A., Neumann, F.: Evolutionary diversity optimisation for the traveling thief problem. In: GECCO 2022: Genetic and Evolutionary Computation Conference, pp. 749\u2013756. ACM (2022). https:\/\/doi.org\/10.1145\/3512290.3528862","key":"10_CR28","DOI":"10.1145\/3512290.3528862"},{"doi-asserted-by":"publisher","unstructured":"Nikfarjam, A., Neumann, A., Neumann, F.: On the use of quality diversity algorithms for the traveling thief problem. In: GECCO 2022: Genetic and Evolutionary Computation Conference, pp. 260\u2013268. ACM (2022). https:\/\/doi.org\/10.1145\/3512290.3528752","key":"10_CR29","DOI":"10.1145\/3512290.3528752"},{"key":"10_CR30","doi-asserted-by":"publisher","first-page":"40","DOI":"10.3389\/FROBT.2016.00040","volume":"3","author":"JK Pugh","year":"2016","unstructured":"Pugh, J.K., Soros, L.B., Stanley, K.O.: Quality diversity: a new frontier for evolutionary computation. Front. Robot. AI 3, 40 (2016). https:\/\/doi.org\/10.3389\/FROBT.2016.00040","journal-title":"Front. Robot. AI"},{"key":"10_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"707","DOI":"10.1007\/978-3-642-15844-5_71","volume-title":"Parallel Problem Solving from Nature, PPSN XI","author":"T Ulrich","year":"2010","unstructured":"Ulrich, T., Bader, J., Thiele, L.: Defining and optimizing indicator-based diversity measures in multiobjective search. In: Schaefer, R., Cotta, C., Ko\u0142odziej, J., Rudolph, G. (eds.) PPSN 2010. LNCS, vol. 6238, pp. 707\u2013717. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-15844-5_71"},{"doi-asserted-by":"publisher","unstructured":"Ulrich, T., Thiele, L.: Maximizing population diversity in single-objective optimization. In: Krasnogor, N., Lanzi, P.L. (eds.) 13th Annual Genetic and Evolutionary Computation Conference, GECCO 2011, Proceedings, Dublin, Ireland, 12\u201316 July 2011, pp. 641\u2013648. ACM (2011). https:\/\/doi.org\/10.1145\/2001576.2001665","key":"10_CR32","DOI":"10.1145\/2001576.2001665"},{"issue":"4","key":"10_CR33","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1109\/TEVC.2017.2735550","volume":"22","author":"V Vassiliades","year":"2017","unstructured":"Vassiliades, V., Chatzilygeroudis, K., Mouret, J.B.: Using centroidal voronoi tessellations to scale up the multidimensional archive of phenotypic elites algorithm. IEEE Trans. Evol. Comput. 22(4), 623\u2013630 (2017)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"4","key":"10_CR34","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1109\/MCI.2023.3304085","volume":"18","author":"H Zhang","year":"2023","unstructured":"Zhang, H., Chen, Q., Xue, B., Banzhaf, W., Zhang, M.: Map-elites for genetic programming-based ensemble learning: an interactive approach [AI-explained]. IEEE Comput. Intell. Mag. 18(4), 62\u201363 (2023). https:\/\/doi.org\/10.1109\/MCI.2023.3304085","journal-title":"IEEE Comput. Intell. Mag."}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVIII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-70071-2_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:10:45Z","timestamp":1725664245000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70071-2_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700705","9783031700712"],"references-count":34,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70071-2_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"7 September 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"PPSN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Parallel Problem Solving from Nature","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Hagenberg","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Austria","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 September 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2024.fh-ooe.at\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}