{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T22:21:39Z","timestamp":1787437299322,"version":"build-2736575974"},"publisher-location":"Cham","reference-count":42,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032362223","type":"print"},{"value":"9783032362230","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T00:00:00Z","timestamp":1787443200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T00:00:00Z","timestamp":1787443200000},"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":[[2027]]},"DOI":"10.1007\/978-3-032-36223-0_24","type":"book-chapter","created":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T21:44:31Z","timestamp":1787435071000},"page":"382-399","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["SPEA2$$^+$$: Improved Density Estimation in\u00a0SPEA2 with\u00a0Provable Runtime Guarantees"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6660-6625","authenticated-orcid":false,"given":"Duc-Cuong","family":"Dang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7730-7831","authenticated-orcid":false,"given":"Andre","family":"Opris","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6020-1646","authenticated-orcid":false,"given":"Dirk","family":"Sudholt","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,23]]},"reference":[{"key":"24_CR1","doi-asserted-by":"crossref","unstructured":"Alghouass, Y., Doerr, B., Krejca, M.S., Lagmah, M.: Proven approximation guarantees in multi-objective optimization: SPEA2 beats NSGA-II. In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI\u00a02025, pp. 8833\u20138841. ijcai.org (2025)","DOI":"10.24963\/ijcai.2025\/982"},{"issue":"3","key":"24_CR2","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1016\/j.ejor.2006.08.008","volume":"181","author":"N Beume","year":"2007","unstructured":"Beume, N., Naujoks, B., Emmerich, M.T.M.: SMS-EMOA: multiobjective selection based on dominated hypervolume. Eur. J. Oper. Res. 181(3), 1653\u20131669 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"24_CR3","doi-asserted-by":"crossref","unstructured":"Bian, C., Zhou, Y., Li, M., Qian, C.: Stochastic population update can provably be helpful in multi-objective evolutionary algorithms. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI\u00a02023, pp. 5513\u20135521. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/612"},{"key":"24_CR4","doi-asserted-by":"publisher","first-page":"89497","DOI":"10.1109\/ACCESS.2020.2990567","volume":"8","author":"J Blank","year":"2020","unstructured":"Blank, J., Deb, K.: Pymoo: multi-objective optimization in python. IEEE Access 8, 89497\u201389509 (2020)","journal-title":"IEEE Access"},{"key":"24_CR5","doi-asserted-by":"crossref","unstructured":"Cerf, S., Doerr, B., Hebras, B., Kahane, Y., Wietheger, S.: The first proven performance guarantees for the non-dominated sorting genetic algorithm II (NSGA-II) on a combinatorial optimization problem. In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5522\u20135530. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/613"},{"key":"24_CR6","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Salehi, B., Sudholt, D.: Analysing the robustness of NSGA-II under noise. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2023, pp. 642\u2013651. ACM Press (2023)","DOI":"10.1145\/3583131.3590421"},{"key":"24_CR7","doi-asserted-by":"publisher","first-page":"104098","DOI":"10.1016\/j.artint.2024.104098","volume":"330","author":"DC Dang","year":"2024","unstructured":"Dang, D.C., Opris, A., Sudholt, D.: Crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. Artif. Intell. 330, 104098 (2024)","journal-title":"Artif. Intell."},{"key":"24_CR8","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Sudholt, D.: Illustrating the efficiency of popular evolutionary multi-objective algorithms using runtime analysis. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2024, pp. 484\u2013492. ACM Press (2024)","DOI":"10.1145\/3638529.3654177"},{"key":"24_CR9","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Sudholt, D.: Why dominance is not enough: lessons from practical evolutionary multi-objective algorithms. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO\u00a02025, pp. 1604\u20131612. ACM Press (2025)","DOI":"10.1145\/3712256.3726414"},{"key":"24_CR10","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Sudholt, D.: Runtime analysis of functions where widely-used evolutionary multi-objective algorithms beat simple ones. ACM Trans. Evol. Learn. Optim. (2026, to appear)","DOI":"10.1145\/3732793"},{"key":"24_CR11","unstructured":"Dang, D.C., Opris, A., Sudholt, D.: SPEA2$$^+$$: improved density estimation in SPEA2 with provable runtime guarantees. CoRR abs\/2606.12382 (2026). https:\/\/arxiv.org\/abs\/2606.12382"},{"issue":"4","key":"24_CR12","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1109\/TEVC.2013.2281535","volume":"18","author":"K Deb","year":"2014","unstructured":"Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part I: solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4), 577\u2013601 (2014)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"2","key":"24_CR13","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","volume":"6","author":"K Deb","year":"2002","unstructured":"Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182\u2013197 (2002)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"24_CR14","doi-asserted-by":"crossref","unstructured":"Deng, R., Zheng, W., Doerr, B.: The first theoretical approximation guarantees for the non-dominated sorting genetic algorithm III (NSGA-III). In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI\u00a02025, pp. 8867\u20138875. ijcai.org (2025)","DOI":"10.24963\/ijcai.2025\/986"},{"key":"24_CR15","doi-asserted-by":"crossref","unstructured":"Deng, R., Zheng, W., Li, M., Liu, J., Doerr, B.: Runtime analysis for state-of-the-art multi-objective evolutionary algorithms on the subset selection problem. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN\u00a02024, pp. 264\u2013279. Springer (2024)","DOI":"10.1007\/978-3-031-70071-2_17"},{"key":"24_CR16","doi-asserted-by":"crossref","unstructured":"Doerr, B., Ivan, T., Krejca, M.S.: Speeding up the NSGA-II with a simple tie-breaking rule. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2025, pp. 26964\u201326972. AAAI Press (2025)","DOI":"10.1609\/aaai.v39i25.34902"},{"key":"24_CR17","doi-asserted-by":"crossref","unstructured":"Doerr, B., Kodric, B., Voigt, M.: Lower bounds for the runtime of a global multi-objective evolutionary algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation, CEC 2013, pp. 432\u2013439. IEEE (2013)","DOI":"10.1109\/CEC.2013.6557601"},{"key":"24_CR18","doi-asserted-by":"crossref","unstructured":"Doerr, B., Krejca, M.S., Opris, A.: Tight runtime guarantees from understanding the population dynamics of the GSEMO multi-objective evolutionary algorithm. In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI\u00a02025, pp. 8876\u20138884. ijcai.org (2025)","DOI":"10.24963\/ijcai.2025\/987"},{"key":"24_CR19","doi-asserted-by":"crossref","unstructured":"Doerr, B., Krejca, M.S., Stankovic, M.: Improved runtime guarantees for the SPEA2 multi-objective optimizer. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2026, pp. 36855\u201336863. AAAI Press (2026)","DOI":"10.1609\/aaai.v40i43.41012"},{"key":"24_CR20","doi-asserted-by":"crossref","unstructured":"Doerr, B., Qu, Z.: A first runtime analysis of the NSGA-II on a multimodal problem. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN 2022, pp. 399\u2013412. Springer (2022)","DOI":"10.1007\/978-3-031-14721-0_28"},{"key":"24_CR21","doi-asserted-by":"crossref","unstructured":"Doerr, B., Qu, Z.: From understanding the population dynamics of the NSGA-II to the first proven lower bounds. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023, pp. 12408\u201312416. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26462"},{"key":"24_CR22","doi-asserted-by":"crossref","unstructured":"Doerr, B., Qu, Z.: Runtime analysis for the NSGA-II: provable speed-ups from crossover. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2023, pp. 12399\u201312407. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26461"},{"key":"24_CR23","doi-asserted-by":"crossref","unstructured":"Doerr, B., Zheng, W.: Theoretical analyses of multi-objective evolutionary algorithms on multi-modal objectives. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2021, pp. 12293\u201312301. AAAI Press (2021)","DOI":"10.1609\/aaai.v35i14.17459"},{"key":"24_CR24","unstructured":"Eckart\u00a0Zitzler, Marco\u00a0Laumanns, L.T.: SPEA2: Improving the strength Pareto evolutionary algorithm. Technical report, ETH Zurich, Computer Engineering and Networks Laboratory (2001)"},{"key":"24_CR25","doi-asserted-by":"crossref","unstructured":"Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: Proceedings of the IEEE Congress on Evolutionary Computation (CEC 2003), pp. 1918\u20131925. IEEE Press (2003)","DOI":"10.1109\/CEC.2003.1299908"},{"key":"24_CR26","doi-asserted-by":"crossref","unstructured":"Jansen, T.: Analyzing Evolutionary Algorithms - The Computer Science Perspective. Natural Computing Series. Springer (2013)","DOI":"10.1007\/978-3-642-17339-4"},{"issue":"2","key":"24_CR27","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TEVC.2004.823470","volume":"8","author":"M Laumanns","year":"2004","unstructured":"Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions. IEEE Trans. Evol. Comput. 8(2), 170\u2013182 (2004)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"24_CR28","doi-asserted-by":"crossref","unstructured":"Laumanns, M., Thiele, L., Zitzler, E., Welzl, E., Deb, K.: Running time analysis of multi-objective evolutionary algorithms on a simple discrete optimization problem. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN 2002, pp. 44\u201353. Springer (2002)","DOI":"10.1007\/3-540-45712-7_5"},{"key":"24_CR29","doi-asserted-by":"crossref","unstructured":"Li, M., Zheng, W., Doerr, B.: Scalable speed-ups for the SMS-EMOA from a simple aging strategy. In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI\u00a02025, pp. 8885\u20138893. ijcai.org (2025)","DOI":"10.24963\/ijcai.2025\/988"},{"key":"24_CR30","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.tcs.2018.07.007","volume":"773","author":"PS Oliveto","year":"2019","unstructured":"Oliveto, P.S., Sudholt, D., Zarges, C.: On the benefits and risks of using fitness sharing for multimodal optimisation. Theoret. Comput. Sci. 773, 53\u201370 (2019)","journal-title":"Theoret. Comput. Sci."},{"key":"24_CR31","doi-asserted-by":"crossref","unstructured":"Opris, A.: A first runtime analysis of NSGA-III on a many-objective multimodal problem: Provable exponential speedup via stochastic population update. In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI\u00a02023, pp. 8903\u20138911. ijcai.org (2025)","DOI":"10.24963\/ijcai.2025\/990"},{"key":"24_CR32","doi-asserted-by":"crossref","unstructured":"Opris, A.: A first runtime analysis of the PAES-25: an enhanced variant of the Pareto archived evolution strategy. In: Proceedings of the 18th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms, FOGA\u00a02025, pp. 202\u2013213. ACM Press (2025)","DOI":"10.1145\/3729878.3746618"},{"key":"24_CR33","doi-asserted-by":"crossref","unstructured":"Opris, A.: Many-objective problems where crossover is provably essential. Artif. Intell. 350, 104453 (2026)","DOI":"10.1016\/j.artint.2025.104453"},{"key":"24_CR34","doi-asserted-by":"crossref","unstructured":"Opris, A.: Towards a rigorous understanding of the population dynamics of the NSGA-III: tight runtime bounds. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2026, pp. 37125\u201337133. AAAI Press (2026)","DOI":"10.1609\/aaai.v40i43.41042"},{"key":"24_CR35","doi-asserted-by":"crossref","unstructured":"Opris, A., Dang, D.C., Neumann, F., Sudholt, D.: Runtime analyses of NSGA-III on many-objective problems. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2024, pp. 1596\u20131604. ACM Press (2024)","DOI":"10.1145\/3638529.3654218"},{"key":"24_CR36","doi-asserted-by":"crossref","unstructured":"Ren, S., Bian, C., Li, M., Qian, C.: A first running time analysis of the strength Pareto evolutionary algorithm 2 (SPEA2). In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN 2024, pp. 295\u2013312. Springer (2024)","DOI":"10.1007\/978-3-031-70071-2_19"},{"key":"24_CR37","doi-asserted-by":"crossref","unstructured":"Thierens, D.: Convergence time analysis for the multi-objective counting ones problem. In: Evolutionary Multi-Criterion Optimization, pp. 355\u2013364. Springer (2003)","DOI":"10.1007\/3-540-36970-8_25"},{"key":"24_CR38","doi-asserted-by":"crossref","unstructured":"Wietheger, S., Doerr, B.: A mathematical runtime analysis of the non-dominated sorting genetic algorithm III (NSGA-III). In: Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI\u00a02023, pp. 5657\u20135665. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/628"},{"key":"24_CR39","doi-asserted-by":"crossref","unstructured":"Wietheger, S., Doerr, B.: Near-tight runtime guarantees for many-objective evolutionary algorithms. In: Proceedings of the International Conference on Parallel Problem Solving from Nature, PPSN 2024, pp. 153\u2013168. Springer (2024)","DOI":"10.1007\/978-3-031-70085-9_10"},{"key":"24_CR40","doi-asserted-by":"crossref","unstructured":"Zheng, W., Doerr, B.: Better approximation guarantees for the NSGA-II by using the current crowding distance. In: Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 611\u2013619. ACM Press (2022)","DOI":"10.1145\/3512290.3528847"},{"key":"24_CR41","doi-asserted-by":"crossref","unstructured":"Zheng, W., Doerr, B.: Runtime analysis of the SMS-EMOA for many-objective optimization. In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI\u00a02024, pp. 20874\u201320882. AAAI Press (2024)","DOI":"10.1609\/aaai.v38i18.30077"},{"key":"24_CR42","doi-asserted-by":"crossref","unstructured":"Zheng, W., Liu, Y., Doerr, B.: A first mathematical runtime analysis of the non-dominated sorting genetic algorithm II (NSGA-II). In: Proceedings of the AAAI Conference on Artificial Intelligence, AAAI 2022, pp. 10408\u201310416. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i9.21283"}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XIX"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-36223-0_24","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T21:44:34Z","timestamp":1787435074000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-36223-0_24"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8,23]]},"ISBN":["9783032362223","9783032362230"],"references-count":42,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-36223-0_24","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8,23]]},"assertion":[{"value":"23 August 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"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":"Trento","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Italy","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 August 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 September 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}