目录
- 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_{i=1}^{n}K\left(\frac{z-z_i}{h}\right)f^(z)=nh1i=1∑nK(hz−zi)
其中，n nn为样本数，h hh为带宽，K ( ⋅ ) K(\cdot)K(⋅)为核函数。带宽控制平滑程度，过小会噪声大，过大会抹平结构。KDE 可视为直方图的平滑推广。
对某个元启发式A \mathcal AA和实例I \mathcal II，KDE-STOP 用算法近期产生的目标值估计密度f ^ \hat ff^。若要判断是否可能得到低于z ′ z'z′的解，其概率为：
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_b+1Nb+1次迭代开始检查当前最好值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_stop
5.参考文献
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
