{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,7]],"date-time":"2026-07-07T15:43:15Z","timestamp":1783438995983,"version":"3.54.6"},"publisher-location":"California","reference-count":0,"publisher":"International Joint Conferences on Artificial Intelligence Organization","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,9]]},"abstract":"<jats:p>Together with the NSGA-II and SMS-EMOA, the strength Pareto evolutionary algorithm 2 (SPEA2) is one of the most prominent dominance-based multi-objective evolutionary algorithms (MOEAs). Different from the NSGA-II, it does not employ the crowding distance (essentially the distance to neighboring solutions) to compare pairwise non-dominating solutions but a complex system of \u03c3-distances that builds on the distances to all other solutions. In this work, we give a first mathematical proof showing that this more complex system of distances can be superior. More specifically, we prove that a simple steady-state SPEA2 can compute optimal approximations of the Pareto front of the OneMinMax benchmark in polynomial time. The best proven guarantee for a comparable variant of the NSGA-II only assures approximation ratios of roughly a factor of two, and both mathematical analyses and experiments indicate that optimal approximations are not found efficiently.<\/jats:p>","DOI":"10.24963\/ijcai.2025\/982","type":"proceedings-article","created":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T08:10:40Z","timestamp":1758269440000},"page":"8833-8841","source":"Crossref","is-referenced-by-count":8,"title":["Proven Approximation Guarantees in Multi-Objective Optimization: SPEA2 Beats NSGA-II"],"prefix":"10.24963","author":[{"given":"Yasser","family":"Alghouass","sequence":"first","affiliation":[{"name":"\u00c9cole Polytechnique, Institut Polytechnique de Paris"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benjamin","family":"Doerr","sequence":"additional","affiliation":[{"name":"Laboratoire d'Informatique (LIX), CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin S.","family":"Krejca","sequence":"additional","affiliation":[{"name":"Laboratoire d'Informatique (LIX), CNRS, \u00c9cole Polytechnique, Institut Polytechnique de Paris"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Mohammed","family":"Lagmah","sequence":"additional","affiliation":[{"name":"\u00c9cole Polytechnique, Institut Polytechnique de Paris"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"10584","event":{"name":"Thirty-Fourth International Joint Conference on Artificial Intelligence {IJCAI-25}","theme":"Artificial Intelligence","location":"Montreal, Canada","acronym":"IJCAI-2025","number":"34","sponsor":["International Joint Conferences on Artificial Intelligence Organization (IJCAI)"],"start":{"date-parts":[[2025,8,16]]},"end":{"date-parts":[[2025,8,22]]}},"container-title":["Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence"],"original-title":[],"deposited":{"date-parts":[[2025,9,23]],"date-time":"2025-09-23T11:35:43Z","timestamp":1758627343000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ijcai.org\/proceedings\/2025\/982"}},"subtitle":[],"proceedings-subject":"Artificial Intelligence Research Articles","short-title":[],"issued":{"date-parts":[[2025,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.24963\/ijcai.2025\/982","relation":{},"subject":[],"published":{"date-parts":[[2025,9]]}}}