{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:37:48Z","timestamp":1759847868226},"reference-count":42,"publisher":"MIT Press","issue":"3","content-domain":{"domain":["direct.mit.edu"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We present an empirical study of a range of evolutionary algorithms applied to various noisy combinatorial optimisation problems. There are three sets of experiments. The first looks at several toy problems, such as OneMax and other linear problems. We find that UMDA and the Paired-Crossover Evolutionary Algorithm (PCEA) are the only ones able to cope robustly with noise, within a reasonable fixed time budget. In the second stage, UMDA and PCEA are then tested on more complex noisy problems: SubsetSum, Knapsack, and SetCover. Both perform well under increasing levels of noise, with UMDA being the better of the two. In the third stage, we consider two noisy multiobjective problems (CountingOnesCountingZeros and a multiobjective formulation of SetCover). We compare several adaptations of UMDA for multiobjective problems with the Simple Evolutionary Multiobjective Optimiser (SEMO) and NSGA-II. We conclude that UMDA, and its variants, can be highly effective on a variety of noisy combinatorial optimisation, outperforming many other evolutionary algorithms.<\/jats:p>","DOI":"10.1162\/evco_a_00320","type":"journal-article","created":{"date-parts":[[2023,2,28]],"date-time":"2023-02-28T19:50:13Z","timestamp":1677613813000},"page":"259-285","update-policy":"http:\/\/dx.doi.org\/10.1162\/mitpressjournals.corrections.policy","source":"Crossref","is-referenced-by-count":2,"title":["Evolutionary and Estimation of Distribution Algorithms for Unconstrained, Constrained, and Multiobjective Noisy Combinatorial Optimisation Problems"],"prefix":"10.1162","volume":"31","author":[{"family":"Aishwaryaprajna","sequence":"first","affiliation":[{"name":"School of Computer Science, University of Birmingham, Birmingham, United Kingdom aishwaryaprajna@gmail.com"}]},{"given":"Jonathan E.","family":"Rowe","sequence":"additional","affiliation":[{"name":"School of Computer Science, University of Birmingham, Birmingham, United Kingdom"},{"name":"The Alan Turing Institute, London, United Kingdom J.E.Rowe@cs.bham.ac.uk"}]}],"member":"281","published-online":{"date-parts":[[2023,9,1]]},"reference":[{"key":"2023090105043973900_B1","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1145\/3319619.3321955","article-title":"Noisy combinatorial optimisation by evolutionary algorithms","author":"Aishwaryaprajna","year":"2019","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference Companion (GECCO)"},{"key":"2023090105043973900_B2","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/j.tcs.2015.04.008","article-title":"Analysis of runtime of optimization algorithms for noisy functions over discrete codomains","volume":"605","author":"Akimoto","year":"2015","journal-title":"Theoretical Computer Science"},{"key":"2023090105043973900_B3","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1145\/1527125.1527135","article-title":"Black-box search by elimination of fitness functions","author":"Anil","year":"2009","journal-title":"Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms"},{"key":"2023090105043973900_B4","author":"Baluja","year":"1994","journal-title":"Population-based incremental learning: A method for integrating genetic search based function optimization and competitive learning"},{"issue":"2","key":"2023090105043973900_B5","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/s11047-008-9098-4","article-title":"A survey on metaheuristics for stochastic combinatorial optimization","volume":"8","author":"Bianchi","year":"2009","journal-title":"Natural Computing"},{"issue":"2","key":"2023090105043973900_B6","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/nav.3220400203","article-title":"An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns","volume":"40","author":"Carraway","year":"1993","journal-title":"Naval Research Logistics"},{"issue":"3","key":"2023090105043973900_B7","doi-asserted-by":"publisher","first-page":"428","DOI":"10.1007\/s00453-015-0103-x","article-title":"Runtime analysis of non-elitist populations: From classical optimisation to partial information","volume":"75","author":"Dang","year":"2016","journal-title":"Algorithmica"},{"key":"2023090105043973900_B8","doi-asserted-by":"crossref","first-page":"62","DOI":"10.1145\/2725494.2725508","article-title":"Efficient optimisation of noisy fitness functions with population-based evolutionary algorithms","author":"Dang","year":"2015","journal-title":"Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII"},{"key":"2023090105043973900_B9","doi-asserted-by":"crossref","first-page":"1467","DOI":"10.1145\/3205455.3205563","article-title":"A new analysis method for evolutionary optimization of dynamic and noisy objective functions","author":"Dang-Nhu","year":"2018","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference"},{"issue":"2","key":"2023090105043973900_B10","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1109\/4235.996017","article-title":"A fast and elitist multiobjective genetic algorithm: NSGA-II","volume":"6","author":"Deb","year":"2002","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2023090105043973900_B11","doi-asserted-by":"publisher","first-page":"619","DOI":"10.1007\/978-3-030-58115-2_43","article-title":"Exponential upper bounds for the runtime of randomized search heuristics","volume":"12270","author":"Doerr","year":"2020","journal-title":"International Conference on Parallel Problem Solving from Nature"},{"key":"2023090105043973900_B12","doi-asserted-by":"crossref","first-page":"242","DOI":"10.1145\/3321707.3321837","article-title":"When resampling to cope with noise, use median, not mean","author":"Doerr","year":"2019","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference"},{"key":"2023090105043973900_B13","first-page":"1088","article-title":"Analysis of the (1+1) ea for a noisy onemax","author":"Droste","year":"2004","journal-title":"Genetic and Evolutionary Computation Conference"},{"issue":"2","key":"2023090105043973900_B14","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/3376916","article-title":"Indicator-based multi-objective evolutionary algorithms: A comprehensive survey","volume":"53","author":"Falc\u00f3n-Cardona","year":"2020","journal-title":"ACM Computing Surveys"},{"issue":"1","key":"2023090105043973900_B15","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1109\/TEVC.2014.2304415","article-title":"The rolling tide evolutionary algorithm: A multiobjective optimizer for noisy optimization problems","volume":"19","author":"Fieldsend","year":"2015","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2023090105043973900_B16","doi-asserted-by":"crossref","first-page":"1157","DOI":"10.1109\/CEC.2006.1688440","article-title":"An improved dimension-sweep algorithm for the hypervolume indicator","author":"Fonseca","year":"2006","journal-title":"IEEE International Conference on Evolutionary Computation"},{"issue":"1","key":"2023090105043973900_B17","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10107-012-0520-4","article-title":"Stochastic binary problems with simple penalties for capacity constraints violations","volume":"138","author":"Fortz","year":"2013","journal-title":"Mathematical Programming"},{"key":"2023090105043973900_B18","doi-asserted-by":"crossref","first-page":"140","DOI":"10.1007\/978-3-662-48971-0_13","article-title":"The benefit of recombination in noisy evolutionary search","volume-title":"Algorithms and computation","author":"Friedrich","year":"2015"},{"issue":"3","key":"2023090105043973900_B19","first-page":"477","article-title":"The compact genetic algorithm is efficient under extreme Gaussian noise","volume":"21","author":"Friedrich","year":"2017","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"3","key":"2023090105043973900_B20","doi-asserted-by":"crossref","first-page":"462","DOI":"10.1007\/s00453-015-0072-0","article-title":"Robustness of populations in stochastic environments","volume":"75","author":"Gie\u00dfen","year":"2016","journal-title":"Algorithmica"},{"issue":"8","key":"2023090105043973900_B21","doi-asserted-by":"publisher","first-page":"5960","DOI":"10.1016\/j.eswa.2010.02.008","article-title":"An investigation on noise-induced features in robust evolutionary multi-objective optimization","volume":"37","author":"Goh","year":"2010","journal-title":"Expert Systems with Applications"},{"key":"2023090105043973900_B22","article-title":"Genetic algorithms, noise, and the sizing of populations","volume":"51","author":"Goldberg","year":"1991","journal-title":"Urbana"},{"issue":"4","key":"2023090105043973900_B23","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1109\/4235.797971","article-title":"The compact genetic algorithm","volume":"3","author":"Harik","year":"1999","journal-title":"IEEE Transactions on Evolutionary Computation"},{"issue":"5","key":"2023090105043973900_B24","doi-asserted-by":"publisher","first-page":"820","DOI":"10.1287\/opre.38.5.820","article-title":"Risk criteria in a stochastic knapsack problem","volume":"38","author":"Henig","year":"1990","journal-title":"Operations Research"},{"issue":"2","key":"2023090105043973900_B25","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"},{"key":"2023090105043973900_B26","first-page":"1","article-title":"Efficient noisy optimisation with the multi-sample and sliding window compact genetic algorithms","author":"Lucas","year":"2017","journal-title":"IEEE Symposium Series on Computational Intelligence"},{"issue":"3","key":"2023090105043973900_B27","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1162\/evco.1997.5.3.303","article-title":"The equation for response to selection and its use for prediction","volume":"5","author":"M\u00fchlenbein","year":"1997","journal-title":"Evolutionary Computation"},{"key":"2023090105043973900_B28","first-page":"663","article-title":"Multiobjective hboa, clustering, and scalability","author":"Pelikan","year":"2005","journal-title":"Proceedings of the 7th Annual Conference on Genetic and Evolutionary Computation"},{"issue":"9","key":"2023090105043973900_B29","doi-asserted-by":"crossref","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","article-title":"Where are the hard knapsack problems?","volume":"32","author":"Pisinger","year":"2005","journal-title":"Computers & Operations Research"},{"key":"2023090105043973900_B30","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1145\/2725494.2725498","article-title":"Run-time analysis of population-based evolutionary algorithm in noisy environments","author":"Pr\u00fcgel-Bennett","year":"2015","journal-title":"Proceedings of the 2015 ACM Conference on Foundations of Genetic Algorithms XIII"},{"issue":"2","key":"2023090105043973900_B31","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1162\/evco_a_00201","article-title":"On the effectiveness of sampling for evolutionary optimization in noisy environments","volume":"26","author":"Qian","year":"2018","journal-title":"Evolutionary Computation"},{"key":"2023090105043973900_B32","first-page":"117","article-title":"Noisy fitness evaluation in genetic algorithms and the dynamics of learning","volume-title":"Foundations of Genetic Algorithms","author":"Rattray","year":"1997"},{"issue":"7","key":"2023090105043973900_B33","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1109\/26.31166","article-title":"The stochastic knapsack problem","volume":"37","author":"Ross","year":"1989","journal-title":"IEEE Transactions on Communications"},{"key":"2023090105043973900_B34","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1145\/3299904.3340305","article-title":"The benefits and limitations of voting mechanisms in evolutionary optimisation","author":"Rowe","year":"2019","journal-title":"Proceedings of the 15th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms"},{"issue":"1","key":"2023090105043973900_B35","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/s10479-015-2017-z","article-title":"Using multi-objective evolutionary algorithms for single-objective constrained and unconstrained optimization","volume":"240","author":"Segura","year":"2016","journal-title":"Annals of Operations Research"},{"issue":"1","key":"2023090105043973900_B36","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1162\/EVCO_a_00066","article-title":"Multiobjective optimization with estimation of distribution algorithm in a noisy environment","volume":"21","author":"Shim","year":"2013","journal-title":"Evolutionary Computation"},{"issue":"11","key":"2023090105043973900_B37","doi-asserted-by":"publisher","first-page":"1025","DOI":"10.1057\/jors.1980.189","article-title":"Preference order stochastic knapsack problems: Methodological issues","volume":"31","author":"Sniedovich","year":"1980","journal-title":"Journal of the Operational Research Society"},{"issue":"2","key":"2023090105043973900_B38","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1057\/jors.1979.27","article-title":"A preference order dynamic program for a knapsack problem with stochastic rewards","volume":"30","author":"Steinberg","year":"1979","journal-title":"Journal of the Operational Research Society"},{"key":"2023090105043973900_B39","doi-asserted-by":"crossref","first-page":"1415","DOI":"10.1145\/3071178.3071216","article-title":"Upper bounds on the runtime of the univariate marginal distribution algorithm on onemax","author":"Witt","year":"2017","journal-title":"Proceedings of the Genetic and Evolutionary Computation Conference (GECCO)"},{"key":"2023090105043973900_B40","first-page":"1","article-title":"On crossing fitness valleys with majority-vote crossover and estimation-of-distribution algorithms","author":"Witt","year":"2021","journal-title":"Proceedings of the 16th ACM\/SIGEVO Conference on Foundations of Genetic Algorithms"},{"issue":"4","key":"2023090105043973900_B41","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1109\/TEVC.2017.2667713","article-title":"Stochastic runtime analysis of the cross-entropy algorithm","volume":"21","author":"Wu","year":"2017","journal-title":"IEEE Transactions on Evolutionary Computation"},{"key":"2023090105043973900_B42","first-page":"292","article-title":"Multiobjective optimization using evolutionary algorithms\u2014A comparative case study","author":"Zitzler","year":"1998","journal-title":"International Conference on Parallel Problem Solving from Nature"}],"container-title":["Evolutionary Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/3\/259\/2155639\/evco_a_00320.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/direct.mit.edu\/evco\/article-pdf\/31\/3\/259\/2155639\/evco_a_00320.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,1]],"date-time":"2023-09-01T05:05:11Z","timestamp":1693544711000},"score":1,"resource":{"primary":{"URL":"https:\/\/direct.mit.edu\/evco\/article\/31\/3\/259\/115045\/Evolutionary-and-Estimation-of-Distribution"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"references-count":42,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2023,9,1]]},"published-print":{"date-parts":[[2023,9,1]]}},"URL":"https:\/\/doi.org\/10.1162\/evco_a_00320","relation":{},"ISSN":["1530-9304"],"issn-type":[{"value":"1530-9304","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2023]]},"published":{"date-parts":[[2023]]}}}