论文标题
多目标优化中帕累托曲线的平滑分析
Smoothed Analysis of Pareto Curves in Multiobjective Optimization
论文作者
论文摘要
在多物体优化问题中，如果无法改善标准而不降低至少一个其他标准之一，则解决方案称为帕托托最佳选择。计算所有帕累托最佳解决方案的集合是多目标优化的常见任务，可以过滤不合理的权衡。 对于大多数问题，帕累托最佳解决方案的数量仅随着应用中的输入大小而适度增加。但是，对于几乎每个多目标优化问题，都有最坏情况的实例，并具有指数数量的帕累托最佳解决方案。为了解释这一差异，我们在平滑分析模型中分析了大量的多目标优化问题，并证明了帕托托最佳解决方案的预期数量。 我们还提出了用于计算不同优化问题的帕累托最佳解决方案集的算法，并讨论了优化问题平滑复杂性的相关结果。
In a multiobjective optimization problem a solution is called Pareto-optimal if no criterion can be improved without deteriorating at least one of the other criteria. Computing the set of all Pareto-optimal solutions is a common task in multiobjective optimization to filter out unreasonable trade-offs. For most problems the number of Pareto-optimal solutions increases only moderately with the input size in applications. However, for virtually every multiobjective optimization problem there exist worst-case instances with an exponential number of Pareto-optimal solutions. In order to explain this discrepancy, we analyze a large class of multiobjective optimization problems in the model of smoothed analysis and prove a polynomial bound on the expected number of Pareto-optimal solutions. We also present algorithms for computing the set of Pareto-optimal solutions for different optimization problems and discuss related results on the smoothed complexity of optimization problems.
