{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,3]],"date-time":"2025-06-03T04:03:38Z","timestamp":1748923418486,"version":"3.41.0"},"reference-count":33,"publisher":"MIT Press","issue":"2","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,2]]},"abstract":"<jats:p>Chance-constrained optimization problems allow us to model problems where constraints involving stochastic components should be violated only with a small probability. Evolutionary algorithms have been applied to this scenario and shown to achieve high-quality results. With this paper, we contribute to the theoretical understanding of evolutionary algorithms for chance-constrained optimization. We study the scenario of stochastic components that are independent and normally distributed. Considering the simple single-objective (1+1) EA, we show that imposing an additional uniform constraint already leads to local optima for very restricted scenarios and an exponential optimization time. We therefore introduce a multiobjective formulation of the problem which trades off the expected cost and its variance. We show that multiobjective evolutionary algorithms are highly effective when using this formulation and obtain a set of solutions that contains an optimal solution for any possible confidence level imposed on the constraint. Furthermore, we prove that this approach can also be used to compute a set of optimal solutions for the chance-constrained minimum spanning tree problem. In order to deal with potentially exponentially many trade-offs in the multiobjective formulation, we propose and analyze improved convex multiobjective approaches. Experimental investigations on instances of the NP-hard stochastic minimum weight dominating set problem confirm the benefit of the multiobjective and the improved convex multiobjective approach in practice.<\/jats:p>","DOI":"10.1162\/evco_a_00355","type":"journal-article","created":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T14:36:02Z","timestamp":1722868562000},"page":"191-214","update-policy":"https:\/\/doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":1,"title":["Runtime Analysis of Single- and Multiobjective Evolutionary Algorithms for Chance-Constrained Optimization Problems with Normally Distributed Random Variables*"],"prefix":"10.1162","volume":"33","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2721-3618","authenticated-orcid":true,"given":"Frank","family":"Neumann","sequence":"first","affiliation":[{"name":"Optimisation and Logistics, The University of Adelaide, Adelaide, Australia frank.neumann@adelaide.edu.au"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6105-7700","authenticated-orcid":true,"given":"Carsten","family":"Witt","sequence":"additional","affiliation":[{"name":"DTU Compute, Technical University of Denmark, Kgs. Lyngby, Denmark cawi@dtu.dk"}]}],"member":"281","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"key":"2025060207554737100_B1","first-page":"307","article-title":"Evolutionary bi-objective optimization for the dynamic chance-constrained knapsack problem based on tail bound objectives","volume":"325","author":"Assimi","year":"2020","journal-title":"European Conference on Artificial Intelligence"},{"key":"2025060207554737100_B2","doi-asserted-by":"crossref","DOI":"10.1515\/9781400831050","volume-title":"Robust optimization","author":"Ben-Tal","year":"2009"},{"issue":"1","key":"2025060207554737100_B3","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1287\/mnsc.6.1.73","article-title":"Chance-constrained programming","volume":"6","author":"Charnes","year":"1959","journal-title":"Management Science"},{"key":"2025060207554737100_B4","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-030-29414-4_1","article-title":"Probabilistic tools for the analysis of randomized optimization heuristics","volume-title":"Theory of evolutionary computation\u2014Recent developments in discrete optimization","author":"Doerr","year":"2020"},{"key":"2025060207554737100_B5","first-page":"1460","article-title":"Optimization of chance-constrained submodular functions","author":"Doerr","year":"2020","journal-title":"Association for the Advancement of Artificial Intelligence"},{"key":"2025060207554737100_B6","doi-asserted-by":"publisher","first-page":"673","DOI":"10.1007\/s00453-012-9622-x","article-title":"Multiplicative drift analysis","volume":"64","author":"Doerr","year":"2012","journal-title":"Algorithmica"},{"key":"2025060207554737100_B7","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-29414-4","volume-title":"Theory of evolutionary computation\u2014Recent developments in discrete optimization","author":"Doerr","year":"2020"},{"issue":"4","key":"2025060207554737100_B8","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1162\/EVCO_a_00003","article-title":"Approximating covering problems by randomized search heuristics using multi-objective models","volume":"18","author":"Friedrich","year":"2010","journal-title":"Evolutionary Computation"},{"issue":"4","key":"2025060207554737100_B9","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1162\/EVCO_a_00159","article-title":"Maximizing submodular functions under matroid constraints by evolutionary algorithms","volume":"23","author":"Friedrich","year":"2015","journal-title":"Evolutionary Computation"},{"key":"2025060207554737100_B10","first-page":"1918","article-title":"Expected runtimes of a simple multi-objective evolutionary algorithm","volume":"3","author":"Giel","year":"2003","journal-title":"Proceedings of the Conference on Evolutionary Computation"},{"issue":"4","key":"2025060207554737100_B11","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0166-218X(81)90004-4","article-title":"Stochastic spanning tree problem","volume":"3","author":"Ishii","year":"1981","journal-title":"Discrete Applied Mathematics"},{"key":"2025060207554737100_B12","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17339-4","volume-title":"Analyzing evolutionary algorithms\u2014The computer science perspective","author":"Jansen","year":"2013"},{"issue":"4","key":"2025060207554737100_B13","doi-asserted-by":"publisher","first-page":"754","DOI":"10.1007\/s00453-012-9660-4","article-title":"Fixed-parameter evolutionary algorithms and the vertex cover problem","volume":"65","author":"Kratsch","year":"2013","journal-title":"Algorithmica"},{"issue":"2","key":"2025060207554737100_B14","doi-asserted-by":"publisher","first-page":"170","DOI":"10.1109\/TEVC.2004.823470","article-title":"Running time analysis of multiobjective evolutionary algorithms on pseudo-Boolean functions","volume":"8","author":"Laumanns","year":"2004","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"6","key":"2025060207554737100_B15","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1109\/TEVC.2013.2244898","article-title":"An efficient evolutionary algorithm for chance-constrained bi-objective stochastic optimization","volume":"17","author":"Liu","year":"2013","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"6","key":"2025060207554737100_B16","first-page":"1435","article-title":"Convex hull ranking algorithm for multi-objective evolutionary algorithms","volume":"18","author":"Monfared","year":"2011","journal-title":"Statistical Centre of Iran"},{"key":"2025060207554737100_B17","doi-asserted-by":"crossref","first-page":"404","DOI":"10.1007\/978-3-030-58112-1_28","article-title":"Optimising monotone chance-constrained submodular functions using evolutionary multi-objective algorithms","volume-title":"Parallel Problem Solving from Nature, (1)","author":"Neumann","year":"2020"},{"key":"2025060207554737100_B18","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1007\/978-3-031-14714-2_21","article-title":"Evolutionary algorithms for limiting the effect of uncertainty for the knapsack problem with stochastic profits","volume":"13398","author":"Neumann","year":"2022","journal-title":"Parallel Problem Solving from Nature, (1)"},{"issue":"3","key":"2025060207554737100_B19","doi-asserted-by":"publisher","first-page":"1620","DOI":"10.1016\/j.ejor.2006.08.005","article-title":"Expected runtimes of a simple evolutionary algorithm for the multi-objective minimum spanning tree problem","volume":"181","author":"Neumann","year":"2007","journal-title":"European Journal of Operational Research"},{"key":"2025060207554737100_B20","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1145\/3299904.3340315","article-title":"Runtime analysis of the (1 + 1) evolutionary algorithm for the chance-constrained knapsack problem","author":"Neumann","year":"2019","journal-title":"Foundations of Genetic Algorithms"},{"issue":"3","key":"2025060207554737100_B21","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/s11047-006-9004-x","article-title":"Minimum spanning trees made easier via multi-objective optimization","volume":"5","author":"Neumann","year":"2006","journal-title":"Natural Computing"},{"volume-title":"Bioinspired computation in combinatorial optimization\u2014Algorithms and their computational complexity","year":"2010","author":"Neumann","key":"2025060207554737100_B22"},{"key":"2025060207554737100_B23","first-page":"4800","article-title":"Runtime analysis of single- and multi-objective evolutionary algorithms for chance constrained optimization problems with normally distributed random variables","author":"Neumann","year":"2022","journal-title":"International Joint Conferences on Artificial Intelligence"},{"issue":"3","key":"2025060207554737100_B24","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1016\/j.ejor.2006.06.045","article-title":"Genetic algorithm based technique for solving chance constrained problems","volume":"185","author":"Poojari","year":"2008","journal-title":"European Journal of Operational Research"},{"key":"2025060207554737100_B25","first-page":"2613","article-title":"On subset selection with general cost constraints","author":"Qian","year":"2017","journal-title":"International Joint Conferences on Artificial Intelligence"},{"key":"2025060207554737100_B26","first-page":"1774","article-title":"Subset selection by Pareto optimization","author":"Qian","year":"2015","journal-title":"Advances in Neural Information Processing Systems"},{"key":"2025060207554737100_B27","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2021.103597","article-title":"Pareto optimization for subset selection with dynamic cost constraints","volume":"302","author":"Roostapour","year":"2022","journal-title":"Artificial Intelligence"},{"key":"2025060207554737100_B28","first-page":"4292","article-title":"The network data repository with interactive graph analytics and visualization","author":"Rossi","year":"2015","journal-title":"Association for the Advancement of Artificial Intelligence"},{"key":"2025060207554737100_B29","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1145\/3321707.3321869","article-title":"Evolutionary algorithms for the chance-constrained knapsack problem","author":"Xie","year":"2019","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025060207554737100_B30","first-page":"271","article-title":"Specific single- and multi-objective evolutionary algorithms for the chance-constrained knapsack problem","author":"Xie","year":"2020","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025060207554737100_B31","doi-asserted-by":"crossref","first-page":"1079","DOI":"10.1145\/3449639.3459382","article-title":"Heuristic strategies for solving complex interacting stockpile blending problem with chance constraints","author":"Xie","year":"2021","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025060207554737100_B32","doi-asserted-by":"crossref","first-page":"1187","DOI":"10.1145\/3449639.3459381","article-title":"Runtime analysis of RLS and the (1+1) EA for the chance-constrained knapsack problem with correlated uniform weights","author":"Xie","year":"2021","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2025060207554737100_B33","doi-asserted-by":"crossref","DOI":"10.1007\/978-981-13-5956-9","volume-title":"Evolutionary learning: Advances in theories and algorithms","author":"Zhou","year":"2019"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/2\/191\/2475941\/evco_a_00355.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/33\/2\/191\/2475941\/evco_a_00355.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T11:55:59Z","timestamp":1748865359000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/33\/2\/191\/123898\/Runtime-Analysis-of-Single-and-Multiobjective"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"references-count":33,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2025,6,2]]},"published-print":{"date-parts":[[2025,6,2]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00355","relation":{},"ISSN":["1063-6560","1530-9304"],"issn-type":[{"type":"print","value":"1063-6560"},{"type":"electronic","value":"1530-9304"}],"subject":[],"published-other":{"date-parts":[[2025]]},"published":{"date-parts":[[2025]]}}}