# 模拟退火算法
参考博客:
![](https://www.writebug.com/myres/static/uploads/2022/7/27/765256e9d248dfb3204bb1cabc89c9da.writebug)
算法原理:模拟退火算法(Simulated Annealing, SA)的思想借鉴于固体的退火原理,当固体的温度很高的时候,内能比较大,固体的内部粒子处于快速无序运动,当温度慢慢降低的过程中,固体的内能减小,粒子的慢慢趋于有序,最终,当固体处于常温时,内能达到最小,此时,粒子最为稳定。模拟退火算法便是基于这样的原理设计而成。
模拟退火算法从某一较高的温度出发,这个温度称为初始温度,伴随着温度参数的不断下降,算法中的解趋于稳定,但是,可能这样的稳定解是一个局部最优解,此时,模拟退火算法中会以一定的概率跳出这样的局部最优解,以寻找目标函数的全局最优解。如上图中所示,若此时寻找到了 A 点处的解,模拟退火算法会以一定的概率跳出这个解,如跳到了 D 点重新寻找,这样在一定程度上增加了寻找到全局最优解的可能性。
![](https://www.writebug.com/myres/static/uploads/2022/7/27/0376b1ab5ad375ba867b353a57c0668e.writebug)
算法伪代码:
![](https://www.writebug.com/myres/static/uploads/2022/7/27/d3de1c24dec38b4aea6fb58093b28a67.writebug)
算法应用举例:
问题模型:将一个虚拟网络请求映射到给定的物理网络中,要求满足虚拟节点的计算资源需求和虚拟链路的带宽资源请求,并使得总的资源开销(优化目标)最小。
求解模型:
- 解空间:包含两部分,分别是节点映射结果数组和链路映射结果集合,其中节点映射结果存储在一个整形数组中,数组下标对应虚拟节点的值,数组中的元素为下标所映射的物理节点值。链路映射集合为一个 hashmap,key 为虚拟链路的序号,value 为保存物理映射路径的整型数组,存储路径上物理节点的序号代表一条路径。
- 新解产生函数:在当前解的基础上,随机选取一个虚拟节点进行重映射,要求重映射满足两点:(1)物理节点的计算资源满足虚拟节点的需求 (2)不能映射在原来的物理节点上;完成节点重映射后,通过最短路径算法进行链路的重映射,产生新解。
- 能量评价函数:用于比较当前解和新解的性能好坏,通常将其设为目标函数,在这个问题中即为虚拟映射的总资源开销,开销越低,能量越低,解越稳定。
- 差解的接受概率:
![](https://www.writebug.com/myres/static/uploads/2022/7/27/08c4aa6818d1ba844a386477e20202f0.writebug)
如上面这个公式所示,当(新解能量-当前解能量)<0,也就是新解的资源开销少于当前解的资源开销,则百分百接受新解作为新的当前解。否则,以一定概率接受这个新解。接受概率与温度有关,随着温度越来越低,粒子也逐渐趋于稳定,接受差解的概率也越来越小。
- 降温策略:0< 降温系数 <1,每次迭代之后,温度在一定程度上降低,直到最后迭代完成,温度冷却,算法结束。
![](https://www.writebug.com/myres/static/uploads/2022/7/27/0d0d041184973f561a5612a5fd582d03.writebug)