用MMD度量帕累托前沿距离,提出新优化方法提升多目标求解精度。
MMD-Newton Method for Multi-objective Optimization
- 将帕累托前沿近似集与参考集视为经验分布,用MMD衡量其距离。
- 推导MMD梯度与海森矩阵,构建基于牛顿法的Set-Oriented优化器。
- 结合进化算法预热,显著提升11个基准问题的求解精度。
最大均值差异(MMD)被广泛用于度量概率分布间的距离。本文提出利用MMD解决连续多目标优化问题(MOP)。传统方法通常最小化近似帕累托前沿集与参考集之间的距离(如豪斯多夫距离)。将这两组视为经验测度,本文采用MMD来度量它们之间的距离。为最小化MMD值,我们推导了其关于搜索变量的解析梯度与海森矩阵,并据此设计了一种新型的、面向集合的基于MMD的牛顿法(MMDN)。同时分析了MMD梯度与海森矩阵的理论性质,包括一阶驻点条件及海森矩阵特征谱,用于验证MMDN的正确性。针对复杂问题,提出将MMDN与多目标进化算法(MOEAs)结合:先用进化算法运行若干代以接近全局帕累托前沿,再以进化结果作为初始解启动MMDN,高效精炼近似解。在11个常用基准测试问题上的实验表明,该混合算法(MMDN + MOEA)在相同计算预算下,相比纯进化算法获得更高的优化精度。
原文摘要 · Abstract (English)
Maximum mean discrepancy (MMD) has been widely employed to measure the distance between probability distributions. In this paper, we propose using MMD to solve continuous multi-objective optimization problems (MOPs). For solving MOPs, a common approach is to minimize the distance (e.g., Hausdorff) between a finite approximate set of the Pareto front and a reference set. Viewing these two sets as empirical measures, we propose using MMD to measure the distance between them. To minimize the MMD value, we provide the analytical expression of its gradient and Hessian matrix w.r.t. the search variables, and use them to devise a novel set-oriented, MMD-based Newton (MMDN) method. Also, we analyze the theoretical properties of MMD's gradient and Hessian, including the first-order stationary condition and the eigenspectrum of the Hessian, which are important for verifying the correctness of MMDN. To solve complicated problems, we propose hybridizing MMDN with multiobjective evolutionary algorithms (MOEAs), where we first execute an EA for several iterations to get close to the global Pareto front and then warm-start MMDN with the result of the MOEA to efficiently refine the approximation. We empirically test the hybrid algorithm on 11 widely used benchmark problems, and the results show the hybrid (MMDN + MOEA) can achieve a much better optimization accuracy than EA alone with the same computation budget.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。