School of Computer Science, University of Birmingham, Birmingham, United Kingdom
School of Computer Science, University of Birmingham, Birmingham, United Kingdom.
Evol Comput. 2023 Sep 1;31(3):259-285. doi: 10.1162/evco_a_00320.
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.
我们进行了一系列应用于各种噪声组合优化问题的进化算法的实证研究。共有三组实验。第一组研究了一些玩具问题，如 OneMax 和其他线性问题。我们发现 UMDA 和配对交叉进化算法（PCEA）是仅有的能够在合理的固定时间预算内稳健应对噪声的算法。在第二阶段，UMDA 和 PCEA 随后在更复杂的噪声问题上进行了测试：子集和、背包和集合覆盖。随着噪声水平的提高，两者都表现良好，UMDA 是两者中更好的一个。在第三阶段，我们考虑了两个噪声多目标问题（CountingOnesCountingZeros 和集合覆盖的多目标公式）。我们将 UMDA 的几种多目标问题的自适应方法与 Simple Evolutionary Multiobjective Optimiser (SEMO) 和 NSGA-II 进行了比较。我们的结论是，UMDA 及其变体可以在各种噪声组合优化中非常有效，优于许多其他进化算法。
