{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,11]],"date-time":"2026-07-11T05:55:19Z","timestamp":1783749319860,"version":"3.55.0"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783031147203","type":"print"},{"value":"9783031147210","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2022]]},"DOI":"10.1007\/978-3-031-14721-0_30","type":"book-chapter","created":{"date-parts":[[2022,8,15]],"date-time":"2022-08-15T00:02:52Z","timestamp":1660521772000},"page":"428-441","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Better Running Time of\u00a0the\u00a0Non-dominated Sorting Genetic Algorithm II (NSGA-II) by\u00a0Using Stochastic Tournament Selection"],"prefix":"10.1007","author":[{"given":"Chao","family":"Bian","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chao","family":"Qian","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,15]]},"reference":[{"key":"30_CR1","doi-asserted-by":"publisher","DOI":"10.1142\/7438","volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments","author":"A Auger","year":"2011","unstructured":"Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments. World Scientific, Singapore (2011)"},{"key":"30_CR2","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780195099713.001.0001","volume-title":"Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms","author":"T B\u00e4ck","year":"1996","unstructured":"B\u00e4ck, T.: Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms. Oxford University Press, Oxford (1996)"},{"key":"30_CR3","doi-asserted-by":"crossref","unstructured":"Bian, C., Qian, C., Tang, K.: A general approach to running time analysis of multi-objective evolutionary algorithms. In: Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI 2018), Stockholm, Sweden, pp. 1405\u20131411 (2018)","DOI":"10.24963\/ijcai.2018\/195"},{"key":"30_CR4","doi-asserted-by":"publisher","DOI":"10.1142\/5712","volume-title":"Applications of Multi-Objective Evolutionary Algorithms","author":"CA Coello Coello","year":"2004","unstructured":"Coello Coello, C.A., Lamont, G.B.: Applications of Multi-Objective Evolutionary Algorithms. World Scientific, Singapore (2004)"},{"key":"30_CR5","doi-asserted-by":"crossref","unstructured":"Coello Coello, C.A., Sierra, M.R.: A general approach to running time analysis of multi-objective evolutionary algorithms. In: Proceedings of the Mexican International Conference on Artificial Intelligence (MICAI 2004), Mexico City, Mexico, pp. 688\u2013697 (2004)","DOI":"10.1007\/978-3-540-24694-7_71"},{"key":"30_CR6","doi-asserted-by":"publisher","first-page":"123","DOI":"10.1016\/j.tcs.2018.06.009","volume":"832","author":"E Covantes Osuna","year":"2020","unstructured":"Covantes Osuna, E., Gao, W., Neumann, F., Sudholt, D.: Design and analysis of diversity-based parent selection schemes for speeding up evolutionary multi-objective optimisation. Theoret. Comput. Sci. 832, 123\u2013142 (2020)","journal-title":"Theoret. Comput. Sci."},{"key":"30_CR7","doi-asserted-by":"publisher","unstructured":"Deb, K.: Multi-objective optimisation using evolutionary algorithms: an introduction. In: Multi-objective Evolutionary Optimisation for Product Design and Manufacturing, pp. 3\u201334. Springer, London (2011). https:\/\/doi.org\/10.1007\/978-0-85729-652-8_1","DOI":"10.1007\/978-0-85729-652-8_1"},{"issue":"2","key":"30_CR8","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":"30_CR9","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 2013 IEEE Congress on Evolutionary Computation (CEC 2013), Cancun, Mexico, pp. 432\u2013439 (2013)","DOI":"10.1109\/CEC.2013.6557601"},{"key":"30_CR10","doi-asserted-by":"publisher","unstructured":"Doerr, B., Neumann, F. (eds.): Theory of Evolutionary Computation: Recent Developments in Discrete Optimization, Natural Computing Series, Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-29414-4","DOI":"10.1007\/978-3-030-29414-4"},{"key":"30_CR11","doi-asserted-by":"publisher","unstructured":"E. Eiben, A., E. Smith, J.: Introduction to Evolutionary Computing. Springer-Verlag, Berlin (2015). https:\/\/doi.org\/10.1007\/978-3-662-05094-1","DOI":"10.1007\/978-3-662-05094-1"},{"issue":"4","key":"30_CR12","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","volume":"18","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., He, J., Hebbinghaus, N., Neumann, F., Witt, C.: Approximating covering problems by randomized search heuristics using multi-objective models. Evol. Comput. 18(4), 617\u2013633 (2010)","journal-title":"Evol. Comput."},{"issue":"6","key":"30_CR13","doi-asserted-by":"publisher","first-page":"854","DOI":"10.1016\/j.tcs.2009.06.020","volume":"411","author":"T Friedrich","year":"2010","unstructured":"Friedrich, T., Hebbinghaus, N., Neumann, F.: Plateaus can be harder in multi-objective optimization. Theoret. Comput. Sci. 411(6), 854\u2013864 (2010)","journal-title":"Theoret. Comput. Sci."},{"issue":"17","key":"30_CR14","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. Theoret. Comput. Sci. 412(17), 1546\u20131556 (2011)","journal-title":"Theoret. Comput. Sci."},{"issue":"4","key":"30_CR15","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1162\/EVCO_a_00159","volume":"23","author":"T Friedrich","year":"2015","unstructured":"Friedrich, T., Neumann, F.: Maximizing submodular functions under matroid constraints by evolutionary algorithms. Evol. Comput. 23(4), 543\u2013558 (2015)","journal-title":"Evol. Comput."},{"key":"30_CR16","doi-asserted-by":"crossref","unstructured":"Giel, O.: Expected runtimes of a simple multi-objective evolutionary algorithm. In: Proceedings of the 2003 IEEE Congress on Evolutionary Computation (CEC 2003), Canberra, Australia, pp. 1918\u20131925 (2003)","DOI":"10.1109\/CEC.2003.1299908"},{"issue":"3","key":"30_CR17","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(3), 335\u2013356 (2010)","journal-title":"Evol. Comput."},{"key":"30_CR18","doi-asserted-by":"crossref","unstructured":"Horoba, C.: Analysis of a simple evolutionary algorithm for the multiobjective shortest path problem. In: Proceedings of the 10th International Workshop on Foundations of Genetic Algorithms (FOGA 2009), Orlando, FL, pp. 113\u2013120 (2009)","DOI":"10.1145\/1527125.1527140"},{"key":"30_CR19","doi-asserted-by":"crossref","unstructured":"Huang, Z., Zhou, Y., Luo, C., Lin, Q.: A runtime analysis of typical decomposition approaches in MOEA\/D framework for many-objective optimization problems. In: Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021), Virtual, pp. 1682\u20131688 (2021)","DOI":"10.24963\/ijcai.2021\/232"},{"key":"30_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1023\/B:NACO.0000023415.22052.55","volume":"3","author":"M Laumanns","year":"2004","unstructured":"Laumanns, M., Thiele, L., Zitzler, E.: Running time analysis of evolutionary algorithms on a simplified multiobjective knapsack problem. Nat. Comput. 3, 37\u201351 (2004)","journal-title":"Nat. Comput."},{"issue":"2","key":"30_CR21","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":"30_CR22","doi-asserted-by":"crossref","unstructured":"Li, M., Yao, X.: Quality evaluation of solution sets in multiobjective optimisation: a survey. ACM Comput. Surv. 52(2), 26:1\u201338 (2020)","DOI":"10.1145\/3300148"},{"issue":"4","key":"30_CR23","doi-asserted-by":"publisher","first-page":"563","DOI":"10.1109\/TEVC.2015.2501315","volume":"20","author":"Y Li","year":"2016","unstructured":"Li, Y., Zhou, Y., Zhan, Z., Zhang, J.: A primary theoretical study on decomposition-based multiobjective evolutionary algorithms. IEEE Trans. Evol. Comput. 20(4), 563\u2013576 (2016)","journal-title":"IEEE Trans. Evol. Comput."},{"issue":"3","key":"30_CR24","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.ejor.2006.08.005","volume":"181","author":"F Neumann","year":"2007","unstructured":"Neumann, F.: Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem. Eur. J. Oper. Res. 181(3), 1620\u20131629 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"30_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1007\/s00453-009-9370-8","volume":"59","author":"F Neumann","year":"2011","unstructured":"Neumann, F., Reichel, J., Skutella, M.: Computing minimum cuts by randomized search heuristics. Algorithmica 59, 323\u2013342 (2011)","journal-title":"Algorithmica"},{"key":"30_CR26","doi-asserted-by":"crossref","unstructured":"Neumann, F., Theile, M.: How crossover speeds up evolutionary algorithms for the multi-criteria all-pairs-shortest-path problem. In: Proceedings of the 11th International Conference on Parallel Problem Solving from Nature (PPSN 2010), Krakow, Poland, pp. 667\u2013676 (2010)","DOI":"10.1007\/978-3-642-15844-5_67"},{"key":"30_CR27","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s11047-006-9004-x","volume":"5","author":"F Neumann","year":"2006","unstructured":"Neumann, F., Wegener, I.: Minimum spanning trees made easier via multi-objective optimization. Nat. Comput. 5, 305\u2013319 (2006)","journal-title":"Nat. Comput."},{"key":"30_CR28","doi-asserted-by":"publisher","unstructured":"Neumann, F., Witt, C.: Bioinspired Computation in Combinatorial Optimization: Algorithms and Their Computational Complexity. Springer-Verlag, Berlin (2010). https:\/\/doi.org\/10.1007\/978-3-642-16544-3","DOI":"10.1007\/978-3-642-16544-3"},{"key":"30_CR29","doi-asserted-by":"crossref","unstructured":"Qian, C., Tang, K., Zhou, Z.H.: Selection hyper-heuristics can provably be helpful in evolutionary multi-objective optimization. In: Proceedings of the 14th International Conference on Parallel Problem Solving from Nature (PPSN 2016), Edinburgh, Scotland, pp. 835\u2013846 (2016)","DOI":"10.1007\/978-3-319-45823-6_78"},{"key":"30_CR30","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.artint.2013.09.002","volume":"204","author":"C Qian","year":"2013","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: An analysis on recombination in multi-objective evolutionary optimization. Artif. Intell. 204, 99\u2013119 (2013)","journal-title":"Artif. Intell."},{"key":"30_CR31","unstructured":"Qian, C., Yu, Y., Zhou, Z.H.: On constrained Boolean Parto optimization. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015), Buenos Aires, Argentina, pp. 389\u2013395 (2015)"},{"issue":"6","key":"30_CR32","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(6), 712\u2013731 (2007)","journal-title":"IEEE Trans. Evol. Comput."},{"key":"30_CR33","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 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Virtual (to appear 2022)","DOI":"10.1145\/3520304.3534070"},{"key":"30_CR34","doi-asserted-by":"publisher","unstructured":"Zhou, Z.H., Yu, Y., Qian, C.: Evolutionary Learning: Advances in Theories and Algorithms. Springer, Singapore (2019). https:\/\/doi.org\/10.1007\/978-981-13-5956-9","DOI":"10.1007\/978-981-13-5956-9"},{"issue":"2","key":"30_CR35","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1162\/106365600568202","volume":"8","author":"E Zitzler","year":"2000","unstructured":"Zitzler, E., Deb, K., Thiele, L.: Comparison of multiobjective evolutionary algorithms: empirical results. Evol. Comput. 8(2), 173\u2013195 (2000)","journal-title":"Evol. Comput."}],"container-title":["Lecture Notes in Computer Science","Parallel Problem Solving from Nature \u2013 PPSN XVII"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-14721-0_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T18:24:43Z","timestamp":1727807083000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-14721-0_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031147203","9783031147210"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-14721-0_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"15 August 2022","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":"Dortmund","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"10 September 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 September 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"ppsn2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/ppsn2022.cs.tu-dortmund.de\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"185","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"85","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"46% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.75","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3.11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"No","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}