论文标题
使用进化多目标算法优化单调偶然受限的下函数
Optimizing Monotone Chance-Constrained Submodular Functions Using Evolutionary Multi-Objective Algorithms
论文作者
论文摘要
许多现实世界的优化问题可以用supporular功能表示。此外，这些现实世界中的问题通常涉及不确定性，可能导致违反给定的限制。最近已经分析了帕累托优化方法后的许多进化多目标算法，并将其应用于具有不同类型约束的子模块问题。我们提出了基于帕累托优化的进化多目标算法的第一个运行时分析，该算法是针对机会受到限制的次要函数的。这里的约束涉及随机组件，只有较小的α可能性才能违反约束。我们使用尾部边界研究了两种不同的双向目标配方的经典GSEMO算法，以确定溶液的可行性。我们表明，该算法GSEMO可为单调性函数获得与最近分析的贪婪算法相同的最坏情况性能，用于均匀的IID权重，并在使用适当的生物目标表格时具有相同的分散体的均匀分布重量。作为研究的一部分，我们还指出了情况，即在第一个双目标配方中使用尾巴界限可以防止GSEMO在均匀分布的权重的情况下，如果目标函数是supper函数，则由于均匀分布但由于单个元素而导致单个元素会影响单调性。此外，我们研究了进化多目标算法GSEMO，NSGA-II和SPEA2在不同的子模块限制的网络问题上的行为。我们的实验结果表明，与最先进的贪婪算法相比，进化多目标算法的使用可显着提高性能。
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 alpha. 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.
