Improved Smoothed Analysis of Multiobjective Optimization
Improved Smoothed Analysis of Multiobjective Optimization
复制标题
多目标优化的改进平滑分析
DOI：
10.1145/2699445
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
H. Röglin
中科院分区：
文献类型：
--
作者：
T. Brunsch;H. Röglin
本文给出了多目标优化问题光滑分析的几个新结果。由于最坏情况分析与实际经验之间的差异，这一研究领域在过去十年中受到了广泛关注。我们考虑的问题，其中dlinear和一个任意的目标函数是一个集S <${0，1} n的可行解进行优化。我们改进了以前已知的光滑Pareto最优解的个数的界到O（n2 d φd），其中φ表示扰动参数.此外，我们还证明了对任意常数c，光滑Pareto最优解的个数的阶矩有界于O（（n2 d φd）c）.这提高了以前最好的已知bounds. Further，我们解决的批评，在平滑分析的扰动破坏零结构的问题表明，帕累托最优解的平滑数量保持多项式有界，即使为保零扰动。这拓宽了平滑分析所捕获的问题的类别，并且对非线性目标函数具有影响。我们的结果的一个推论是，帕累托最优解的平滑数量是多项式有界的多项式目标函数。我们的结果也扩展到整数优化问题。
We present several new results about smoothed analysis of multiobjective optimization problems. Motivated by the discrepancy between worst-case analysis and practical experience, this line of research has gained a lot of attention in the last decade. We consider problems in whichdlinear and one arbitrary objective function are to be optimized over a setS⊆ {0, 1}nof feasible solutions. We improve the previously best known bound for the smoothed number of Pareto-optimal solutions toO(n2dφd), where φ denotes the perturbation parameter. Additionally, we show that for any constantcthecth moment of the smoothed number of Pareto-optimal solutions is bounded byO((n2dφd)c). This improves the previously best known bounds significantly.Furthermore, we address the criticism that the perturbations in smoothed analysis destroy the zero-structure of problems by showing that the smoothed number of Pareto-optimal solutions remains polynomially bounded even for zero-preserving perturbations. This broadens the class of problems captured by smoothed analysis and it has consequences for nonlinear objective functions. One corollary of our result is that the smoothed number of Pareto-optimal solutions is polynomially bounded for polynomial objective functions. Our results also extend to integer optimization problems.
登录
查看更多内容
DOI：
--
发表时间：
2009
期刊：
2009 50th Annual IEEE Symposium on Foundations of Computer Science
影响因子：
--
作者：
Heiko Röglin;S. Teng
通讯作者：
S. Teng
使用 DINAS 寻找双标准和三标准网络流问题的整数有效解决方案
影响因子：
4.6
作者：
A. Mustafa;M. Goh
通讯作者：
M. Goh
路径交易：快速算法、平滑分析和硬度结果
DOI：
--
发表时间：
2011
期刊：
The Sea
影响因子：
--
作者：
A. Berger;Heiko Röglin;R. V. D. Zwaan
通讯作者：
R. V. D. Zwaan
DOI：
--
发表时间：
2011
期刊：
Foundations of Software Technology and Theoretical Computer Science
影响因子：
--
作者：
Navin Goyal;Luis Rademacher
通讯作者：
Luis Rademacher
DOI：
--
发表时间：
2004
期刊：
影响因子：
--
作者：
René Beier
通讯作者：
René Beier