阈值接收算法

发布于:2021-10-17 18:50:03



目录
阈值接收算法的提出阈值接收算法的思想阈值接收和模拟退火的区别阈值接收的伪代码


阈值接收算法的提出

阈值接收算法最早是由GUNTER DUECK 和TOBIAS SCHEUER两人提出,它的思路和模拟退火算法相似。感兴趣的同学可以在谷歌学术搜索这篇论文Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing.由于这里我只是借用阈值接收算法这个工具,所以我就不一一细讲。


阈值接收算法的思想

阚值接收算法(Threshold accepting, TA)是由Dueek和Scheuer提出的一-种 SA算法的变形,在SA算法的基础上产生的- -种启发式算法。是对被广泛应用的SA算法-种改进。TA 不仅接收更好的解,而且为了跳出局部最优也接收更差的解,然而SA算法是用一一个概率接收准则来决定是否爬坡“uphill move”, TA 使用一个阈值接收收准则来缩小搜索范围:无论新的解改进目标函数或者减低目标函数都没有超过一个给定的阙值范围,新的解减小目标函数值范围超过阙值,新解就被拒绝。阚值在迭代的过程中不是保持不变,而是形成一个阈值序列,具有自适应的特点,在早期迭代中准则相当宽松,在后期迭代过程中准则逐渐变得严格。通过这个策略,算法逐渐趋向全局最优。


阈值接收和模拟退火的区别

TA采取预先设置阈值而以确定性的方式接受候选解,阙值接收算法把初始温度to变成初始阈值To,也就是没有温度这个参数,SA算法以Metropolis准则的方式接受候选解,具体地说,SA除无条件接受优质解外,还以一~定的概率接受劣质解,使接受劣质解的概率慢慢趋向于0;而TA除无条件接受优质解外,还无条件地接受与当前解的差异小于某个阈值的劣质解,阈值一般随着迭代趋向0。由于TA不用计算接受概率,计算速度较SA快,同时,需要设置的参数可能更少。


阈值接收的伪代码

相关推荐

最新更新

猜你喜欢