目录1.摘要2.基于 KDE 停止规则3.计算实验结论5.参考文献6.算法辅导·应用定制·读者交流1.摘要元启发式常用于求解难处理优化问题但效率很大程度取决于是否能避免无效计算。KDE-STOP 在算法初期收集目标函数值用核密度估计这些值的分布再计算继续获得更优解的概率。当该概率低于阈值时算法提前终止。实验覆盖多种元启发式和组合优化问题表明 KDE-STOP 能在较小质量损失下显著缩短时间。2.基于 KDE 停止规则KDE 是非参数概率密度估计方法不预设数据服从何种分布。给定样本z i z_izi估计密度为f ^ ( z ) 1 n h ∑ i 1 n K ( z − z i h ) \hat f(z)\frac{1}{nh}\sum_{i1}^{n}K\left(\frac{z-z_i}{h}\right)f^(z)nh1i1∑nK(hz−zi)其中n nn为样本数h hh为带宽K ( ⋅ ) K(\cdot)K(⋅)为核函数。带宽控制平滑程度过小会噪声大过大会抹平结构。KDE 可视为直方图的平滑推广。对某个元启发式A \mathcal AA和实例I \mathcal IIKDE-STOP 用算法近期产生的目标值估计密度f ^ \hat ff^。若要判断是否可能得到低于z ′ zz′的解其概率为p ∫ L B z ′ f ^ ( z ) d z p\int_{LB}^{z}\hat f(z)\,dzp∫LBz′f^(z)dz实际停止时算法每N b N_bNb次迭代重新估计一次密度并从第N b 1 N_b1Nb1次迭代开始检查当前最好值z ˉ \bar zzˉ是否仍可能按比例π \piπ改进p ∫ L B z ˉ − π z ˉ f ^ ( z ) d z p\int_{LB}^{\bar z-\pi\bar z}\hat f(z)\,dzp∫LBzˉ−πzˉf^(z)dz积分用q qq个等距点的梯形公式计算。若p τ p\taupτ说明继续获得所需改进的概率过低搜索停止。主要参数为基线迭代数N b N_bNb、所需改进比例π \piπ、概率阈值τ \tauτ、积分点数q qq和核函数K KK。3.计算实验实验用于检验 KDE-STOP 是否能在不同问题和不同元启发式中取得稳定的时间—质量平衡测试包括四类组合优化问题分别代表调度、设施选址、路径和覆盖。结论KDE-STOP不假设目标值分布形状只根据搜索过程中观察到的目标函数值估计继续改进概率。四类组合优化问题实验表明KDE-STOP 能显著缩短运行时间同时只带来有限质量损失并在排名分布上表现稳定。论文开源地址https://github.com/fdaniele85/kde_stop5.参考文献Ferone D, Festa P, Pastore T. Enhancing optimization algorithms with Kernel Density Estimation: A statistical learning strategy for smarter metaheuristics[J]. Computers Operations Research, 2026: 107539.6.算法辅导·应用定制·读者交流xx
