{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,5]],"date-time":"2025-08-05T13:04:07Z","timestamp":1754399047949,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"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_13","type":"book-chapter","created":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T23:02:54Z","timestamp":1725663774000},"page":"197-212","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Proven Runtime Guarantees for\u00a0How the MOEA\/D: Computes the\u00a0Pareto Front from the\u00a0Subproblem Solutions"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9786-220X","authenticated-orcid":false,"given":"Benjamin","family":"Doerr","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1765-1219","authenticated-orcid":false,"given":"Martin S.","family":"Krejca","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-3008-1372","authenticated-orcid":false,"given":"No\u00e9","family":"Weeks","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,9,7]]},"reference":[{"key":"13_CR1","doi-asserted-by":"publisher","unstructured":"Bian, C., Qian, C.: Better running time of the non-dominated sorting genetic algorithm\u00a0II (NSGA-II) by using stochastic tournament selection. In: Rudolph, G., Kononova, A.V., Aguirre, H., Kerschke, P., Ochoa, G., Tu\u0161ar, T. (eds.) Parallel Problem Solving From Nature, PPSN 2022, pp. 428\u2013441. Springer, Cham (2022). https:\/\/doi.org\/10.1007\/978-3-031-14721-0_30","DOI":"10.1007\/978-3-031-14721-0_30"},{"key":"13_CR2","doi-asserted-by":"crossref","unstructured":"Cerf, S., Doerr, B., Hebras, B., Kahane, J., Wietheger, S.: The first proven performance guarantees for the Non-Dominated Sorting Genetic Algorithm II (NSGA-II) on a combinatorial optimization problem. In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5522\u20135530. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/613"},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Salehi, B., Sudholt, D.: Analysing the robustness of NSGA-II under noise. In: Genetic and Evolutionary Computation Conference, GECCO 2023, pp. 642\u2013651. ACM (2023)","DOI":"10.1145\/3583131.3590421"},{"key":"13_CR4","doi-asserted-by":"crossref","unstructured":"Dang, D.C., Opris, A., Salehi, B., Sudholt, D.: A proof that using crossover can guarantee exponential speed-ups in evolutionary multi-objective optimisation. In: Conference on Artificial Intelligence, AAAI 2023, pp. 12390\u201312398. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26460"},{"key":"13_CR5","unstructured":"Do, A.V., Neumann, A., Neumann, F., Sutton, A.M.: Rigorous runtime analysis of MOEA\/D for solving multi-objective minimum weight base problems. In: Advances in Neural Information Processing Systems, pp. 36434\u201336448. Curran Associates (2023)"},{"key":"13_CR6","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/s00453-011-9585-3","volume":"65","author":"B Doerr","year":"2013","unstructured":"Doerr, B., Goldberg, L.A.: Adaptive drift analysis. Algorithmica 65, 224\u2013250 (2013)","journal-title":"Algorithmica"},{"key":"13_CR7","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, 673\u2013697 (2012)","journal-title":"Algorithmica"},{"key":"13_CR8","doi-asserted-by":"crossref","unstructured":"Doerr, B., Krejca, M.S., Weeks, N.: Proven runtime guarantees for how the MOEA\/D computes the pareto front from the subproblem solutions. CoRR abs\/2405.01014 (2024)","DOI":"10.1007\/978-3-031-70071-2_13"},{"key":"13_CR9","doi-asserted-by":"crossref","unstructured":"Doerr, B., Le, H.P., Makhmara, R., Nguyen, T.D.: Fast genetic algorithms. In: Genetic and Evolutionary Computation Conference, GECCO 2017, pp. 777\u2013784. ACM (2017)","DOI":"10.1145\/3071178.3071301"},{"key":"13_CR10","doi-asserted-by":"publisher","first-page":"1288","DOI":"10.1109\/TEVC.2023.3250552","volume":"27","author":"B Doerr","year":"2023","unstructured":"Doerr, B., Qu, Z.: A first runtime analysis of the NSGA-II on a multimodal problem. IEEE Trans. Evol. Comput. 27, 1288\u20131297 (2023)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"13_CR11","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: Conference on Artificial Intelligence, AAAI 2023, pp. 12408\u201312416. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26462"},{"key":"13_CR12","doi-asserted-by":"crossref","unstructured":"Doerr, B., Qu, Z.: Runtime analysis for the NSGA-II: provable speed-ups from crossover. In: Conference on Artificial Intelligence, AAAI 2023, pp. 12399\u201312407. AAAI Press (2023)","DOI":"10.1609\/aaai.v37i10.26461"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: Congress on Evolutionary Computation, CEC 2003, pp. 1918\u20131925. IEEE (2003)","DOI":"10.1109\/CEC.2003.1299908"},{"key":"13_CR14","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1162\/EVCO_a_00013","volume":"18","author":"O Giel","year":"2010","unstructured":"Giel, O., Lehre, P.K.: On the effect of populations in evolutionary multi-objective optimisation. Evol. Comput. 18, 335\u2013356 (2010)","journal-title":"Evol. Comput."},{"key":"13_CR15","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhou, Y.: Runtime analysis of somatic contiguous hypermutation operators in MOEA\/D framework. In: Conference on Artificial Intelligence, AAAI 2020, pp. 2359\u20132366. AAAI Press (2020)","DOI":"10.1609\/aaai.v34i03.5615"},{"key":"13_CR16","doi-asserted-by":"publisher","first-page":"5130","DOI":"10.1109\/TCYB.2019.2930979","volume":"51","author":"Z Huang","year":"2021","unstructured":"Huang, Z., Zhou, Y., Chen, Z., He, X., Lai, X., Xia, X.: Running time analysis of MOEA\/D on pseudo-Boolean functions. IEEE Trans. Cybern. 51, 5130\u20135141 (2021)","journal-title":"IEEE Trans. Cybern."},{"key":"13_CR17","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, 170\u2013182 (2004)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"13_CR18","doi-asserted-by":"publisher","unstructured":"Lengler, J.: Drift analysis. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, pp. 89\u2013131. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4_2, also available at https:\/\/arxiv.org\/abs\/1712.00964","DOI":"10.1007\/978-3-030-29414-4_2"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/TEVC.2015.2501315","volume":"20","author":"YL Li","year":"2016","unstructured":"Li, Y.L., Zhou, Y.R., Zhan, Z.H., Zhang, J.: A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 20, 563\u2013576 (2016)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Opris, A., Dang, D.C., Neumann, F., Sudholt, D.: Runtime analyses of NSGA-III on many-objective problems. In: Genetic and Evolutionary Computation Conference, GECCO 2024. ACM (2024, to appear)","DOI":"10.1145\/3638529.3654218"},{"key":"13_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1007\/BFb0040787","volume-title":"Evolutionary Programming VII","author":"G Rudolph","year":"1998","unstructured":"Rudolph, G.: Evolutionary search for minimal elements in partially ordered finite sets. In: Porto, V.W., Saravanan, N., Waagen, D., Eiben, A.E. (eds.) EP 1998. LNCS, vol. 1447, pp. 345\u2013353. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0040787"},{"key":"13_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/3-540-36970-8_25","volume-title":"Evolutionary Multi-Criterion Optimization","author":"D Thierens","year":"2003","unstructured":"Thierens, D.: Convergence time analysis for the multi-objective counting ones problem. In: Fonseca, C.M., Fleming, P.J., Zitzler, E., Thiele, L., Deb, K. (eds.) EMO 2003. LNCS, vol. 2632, pp. 355\u2013364. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-36970-8_25"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Wietheger, S., Doerr, B.: A mathematical runtime analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III). In: International Joint Conference on Artificial Intelligence, IJCAI 2023, pp. 5657\u20135665. ijcai.org (2023)","DOI":"10.24963\/ijcai.2023\/628"},{"key":"13_CR24","doi-asserted-by":"crossref","unstructured":"Zhang, J., Xing, L.: A survey of multiobjective evolutionary algorithms. In: International Conference on Computational Science and Engineering (CSE), pp. 93\u2013100. IEEE (2017)","DOI":"10.1109\/CSE-EUC.2017.27"},{"key":"13_CR25","doi-asserted-by":"publisher","first-page":"712","DOI":"10.1109\/TEVC.2007.892759","volume":"11","author":"Q Zhang","year":"2007","unstructured":"Zhang, Q., Li, H.: MOEA\/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11, 712\u2013731 (2007)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"13_CR26","doi-asserted-by":"crossref","unstructured":"Zheng, W., Doerr, B.: Better approximation guarantees for the NSGA-II by using the current crowding distance. In: Genetic and Evolutionary Computation Conference, GECCO 2022, pp. 611\u2013619. ACM (2022)","DOI":"10.1145\/3512290.3528847"},{"key":"13_CR27","doi-asserted-by":"publisher","first-page":"104016","DOI":"10.1016\/j.artint.2023.104016","volume":"325","author":"W Zheng","year":"2023","unstructured":"Zheng, W., Doerr, B.: Mathematical runtime analysis for the non-dominated sorting genetic algorithm II (NSGA-II). Artif. Intell. 325, 104016 (2023)","journal-title":"Artif. Intell."},{"key":"13_CR28","doi-asserted-by":"publisher","unstructured":"Zheng, W., Doerr, B.: Runtime analysis for the NSGA-II: proving, quantifying, and explaining the inefficiency for many objectives. IEEE Trans. Evol. Comput. (2023, in press). https:\/\/doi.org\/10.1109\/TEVC.2023.3320278","DOI":"10.1109\/TEVC.2023.3320278"},{"key":"13_CR29","doi-asserted-by":"crossref","unstructured":"Zheng, W., Doerr, B.: Runtime analysis of the SMS-EMOA for many-objective optimization. In: Conference on Artificial Intelligence, AAAI 2024. AAAI Press (2024)","DOI":"10.1145\/3638530.3664064"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Zheng, W., Li, M., Deng, R., Doerr, B.: How to use the metropolis algorithm for multi-objective optimization? In: Conference on Artificial Intelligence, AAAI 2024. AAAI Press (2024)","DOI":"10.1145\/3638530.3664078"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Zheng, W., Liu, Y., Doerr, B.: A first mathematical runtime analysis of the Non-Dominated Sorting Genetic Algorithm\u00a0II (NSGA-II). In: Conference on Artificial Intelligence, AAAI 2022, pp. 10408\u201310416. AAAI Press (2022)","DOI":"10.1609\/aaai.v36i9.21283"},{"key":"13_CR32","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.swevo.2011.03.001","volume":"1","author":"A Zhou","year":"2011","unstructured":"Zhou, A., Qu, B.Y., Li, H., Zhao, S.Z., Suganthan, P.N., Zhang, Q.: Multiobjective evolutionary algorithms: a survey of the state of the art. Swarm Evol. Comput. 1, 32\u201349 (2011)","journal-title":"Swarm Evol. Comput."}],"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_13","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,27]],"date-time":"2024-11-27T21:39:37Z","timestamp":1732743577000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-70071-2_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031700705","9783031700712"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-70071-2_13","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 declare no competing interests.","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"}}]}}