Neumann Aneta, Neumann Frank
Optimisation and Logistics, The University of Adelaide, Adelaide, Australia
Evol Comput. 2024 Sep 24:1-35. doi: 10.1162/evco_a_00360.
Many real-world optimization problems can be stated in terms of submodular functions. Furthermore, these real-world problems often involve uncertainties which may lead to the violation of given constraints. A lot of evolutionary multi-objective algorithms following the Pareto optimization approach have recently been analyzed and applied to submodular problems with different types of constraints. We present a first runtime analysis of evolutionary multi-objective algorithms based on Pareto optimization for chance-constrained submodular functions. Here the constraint involves stochastic components and the constraint can only be violated with a small probability of α. We investigate the classical GSEMO algorithm for two different bi-objective formulations using tail bounds to determine the feasibility of solutions. We show that the algorithm GSEMO obtains the same worst case performance guarantees for monotone submodular functions as recently analyzed greedy algorithms for the case of uniform IID weights and uniformly distributed weights with the same dispersion when using the appropriate bi-objective formulation. As part of our investigations, we also point out situations where the use of tail bounds in the first bi-objective formulation can prevent GSEMO from obtaining good solutions in the case of uniformly distributed weights with the same dispersion if the objective function is submodular but non-monotone due to a single element impacting monotonicity. Furthermore, we investigate the behavior of the evolutionary multi-objective algorithms GSEMO, NSGA-II and SPEA2 on different submodular chance-constrained network problems. Our experimental results show that the use of evolutionary multi-objective algorithms leads to significant performance improvements compared to state-of-the-art greedy algorithms for submodular optimization.
许多现实世界中的优化问题都可以用次模函数来表述。此外，这些现实世界的问题通常涉及不确定性，这可能导致违反给定的约束条件。最近，许多遵循帕累托优化方法的进化多目标算法已被分析并应用于具有不同类型约束的次模问题。我们首次对基于帕累托优化的进化多目标算法在机会约束次模函数上的运行时间进行了分析。这里的约束涉及随机成分，并且约束只能以α的小概率被违反。我们使用尾界来确定解的可行性，针对两种不同的双目标公式研究经典的GSEMO算法。我们表明，当使用适当的双目标公式时，对于单调次模函数，算法GSEMO获得的最坏情况性能保证与最近针对均匀独立同分布权重以及具有相同离散度的均匀分布权重情况分析的贪心算法相同。作为我们研究的一部分，我们还指出，在目标函数由于单个元素影响单调性而次模但非单调的情况下，对于具有相同离散度的均匀分布权重，在第一个双目标公式中使用尾界可能会阻止GSEMO获得良好的解。此外，我们研究了进化多目标算法GSEMO、NSGA-II和SPEA2在不同次模机会约束网络问题上的行为。我们的实验结果表明，与用于次模优化的现有贪心算法相比，使用进化多目标算法可显著提高性能。
