通过随机扰动+最陡下降,有效避开局部最优解。
SPGD: Steepest Perturbed Gradient Descent Optimization
- 结合梯度下降与周期性均匀扰动,生成候选解并选最陡下降方向。
- 在3D元件布局等复杂非凸问题上优于四种主流方法。
- 适合处理多维非凸优化、复杂地形响应曲面的场景。
优化算法在科学与工业领域至关重要,但常受困于局部极小值、鞍点和平台区(平坦区域),导致难以收敛到合理或近似最优解。本文提出一种新型算法——最陡扰动梯度下降(SPGD),创新性地将梯度下降原理与周期性均匀扰动采样相结合,有效规避上述障碍,尽可能获得更优解。SPGD通过生成一组候选解,选择相对于当前解损失下降最陡的方向进行更新,增强了传统梯度下降的探索能力,显著提高逃离次优局部极小值的概率,并有效导航复杂优化景观。该方法在保持梯度下降定向高效性的同时,融合了随机扰动的探索优势,实现对全局最优解的更全面搜索。我们在3D元件布局这一NP-hard挑战中验证了SPGD的有效性,初步结果表明其在复杂地形响应曲面及多维非凸连续优化问题上,显著优于四种现有方法。与2D基准函数的对比分析进一步证明了其卓越性能,凸显其作为广泛优化问题通用工具的巨大潜力。
原文摘要 · Abstract (English)
Optimization algorithms are pivotal in advancing various scientific and industrial fields but often encounter obstacles such as trapping in local minima, saddle points, and plateaus (flat regions), which makes the convergence to reasonable or near-optimal solutions particularly challenging. This paper presents the Steepest Perturbed Gradient Descent (SPGD), a novel algorithm that innovatively combines the principles of the gradient descent method with periodic uniform perturbation sampling to effectively circumvent these impediments and lead to better solutions whenever possible. SPGD is distinctively designed to generate a set of candidate solutions and select the one exhibiting the steepest loss difference relative to the current solution. It enhances the traditional gradient descent approach by integrating a strategic exploration mechanism that significantly increases the likelihood of escaping sub-optimal local minima and navigating complex optimization landscapes effectively. Our approach not only retains the directed efficiency of gradient descent but also leverages the exploratory benefits of stochastic perturbations, thus enabling a more comprehensive search for global optima across diverse problem spaces. We demonstrate the efficacy of SPGD in solving the 3D component packing problem, an NP-hard challenge. Preliminary results show a substantial improvement over four established methods, particularly on response surfaces with complex topographies and in multidimensional non-convex continuous optimization problems. Comparative analyses with established 2D benchmark functions highlight SPGD's superior performance, showcasing its ability to navigate complex optimization landscapes. These results emphasize SPGD's potential as a versatile tool for a wide range of optimization problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。