模拟退火算法的思想受启发于自然界中固体由高温到低温的过程中其内部分子状态及内部能量的变化规律。
退火 指物体 逐渐降温冷却 的物理现象。温度越低,物体的能量越低,在结晶状态是系统的能量状态到达最低。在自然中,缓慢降温(退火)可以导致结晶,而与之相对的快速降温(淬火)会导致不是最低能态的非晶体形态。
退火的过程可以表示为下图,左边为最初的非晶态状态;经过升温,系统能量增大后到达中间的状态;再缓慢降温到达晶体态,此时能量最小
我们用一个搜索函数最优解来直观表示:C为函数的全局最优解,在只采用贪心策略的情况下,如果从A点开始搜索,最终得到的解为B点,然而这只是一个局部的较好解。
为了避免陷入局部的最优解,模拟退火算法在搜索过程中加入了一个随机因素,会以一定的概率接收一个比当前解较差的解,因此就有可能越过B与C之间的高峰,到达全局最优解
在这里,可以将解(横坐标的值)理解为固体的状态,函数值理解为系统的内能。算法以固体所处的温度T为控制参数,随着T的下降使固体内能(目标函数值)也逐渐下降,直至趋于全局最小。
根据Metropolis准则,在温度为T时, 接受 能量从 的概率为P:
在特定温度下,经过充分转换,材料达到热平衡。这时材料处于状态的概率为
其中 表示材料当前的状态, 表示材料的状态集合, 为玻尔兹曼常数。根据上式可以得到以下结论
因此,如果我们运用退火思想放在优化问题上,在降温过程中问题的解进行充分地“热交换”,即进行充分地重新排列,同样可以帮助我们寻找最优解,理论上也会具有达到全局最优解的性能!
可以看出,算法实际上是两层循环嵌套,外层循环控制温度,内层循环来进行扰动产生新解。
随着温度逐渐降低,算法最终由可能收敛到全局最优,这里说有可能的原因是因为,在温度很低时,虽然从地内能状态跳到高内能状态的可能性不大,但是也有可能发生。
在已知的某个定义域内求函数最优值的问题通常有以下三种情况,以求最小值问题为例(求最大值可以转换为求最小值)
模拟退火算法就是为了应对第三种情况而提出的
参考资料:
https://www.cnblogs.com/ranjiewen/p/6084052.html
https://blog.csdn.net/weixin_40562999/article/details/80853418
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)