⽂章⽬录
模拟退⽕算法介绍、分析与应⽤
模拟退⽕原理
火焰检测
固体退⽕
固体加温⾄充分⾼，再使其以⾜够慢的速度冷却，⽤原⼦或晶格空位的移动来释放内部残留应⼒，通过这些原⼦排列重组的过程来消除材料中的差排。加温时，固体内部粒⼦随温度升⾼变为⽆序状，内能增⼤，⽽缓慢冷却时粒⼦趋于有序，在每个温度都达到平衡态，按照物理规律，最终在常温时达到基态，内能减为最⼩ 模拟退⽕
模拟退⽕算法思想源于固体退⽕原理，⾼温下进⾏搜索，此时各状态出现概率相差不⼤，可以很快进⼊“热平衡状态”，这时进⾏的是⼀种“粗搜索”，也就是⼤致到系统的低能区域。随着温度的逐渐降低，各状态出现概率的差距逐渐被扩⼤，搜索精度不断提⾼。这就可以越来越准确的到⽹络能量函数的全局最⼩点 通俗理解
算法的基础还是贪⼼算法，但是贪⼼会导致局部最优解，不到总体最优。 模拟退⽕其实也是⼀种贪⼼算法，但是它的搜索过程引⼊了随机因素。模拟退⽕算法以⼀定的概率来接受⼀个⽐当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以图为例，模拟退⽕算法在搜索到局部最优解A后，会以⼀定的概率接受到E的移动。也许经过⼏次这样的不是局部最优的移动后会到达D点，于是就跳出了局部最⼤值A
当物体的**状态（能量）随着温度的改变⽽改变，随着温度达到了平衡状态状态也不会产⽣变化，这⾥可能会陷⼊局部最优解。那么我们就需要让它退⽕（降温），**这样就可以跳出局部最优解。在局部优解能概率性地跳出并最终趋于全局最优。
如果你知道NN中梯度下降的动量Momentum机制的话，那么模拟退⽕算法其实和动量机制想法是⼀样的都是跳出局部最优解
模拟退⽕是在局部最优解去做随机优化，让其跳出局部最优解。
动量机制是普通的梯度下降法的⽅向相同，则会加速。反之，则会减速
解释
硫酸铜晶体1. 固体退⽕过程中，温度恒定不变得情况下就会达到热平衡的状态
符号说明
分⼦能量的⼀个随机变量状态r的能量Boltzmannn常数概率分布的标准化因⼦T 温度，可以理解为⼀个⾃变量
算法思想
E
E r
k
Z (T )
ΔC =E −j E i
Metropolis
1. 若在温度T，当前状态 →新状态
2. 若，则接受为当前状态
3. 否则，以概率⼤于[0,1)区间的随机数，则扔接受状态为当前的状态。间的随机数则保留状态i为当前状态
4. 由的定义可知，⾼温下可接受与当前状态能差较⼤的状态为重要状态，⽽在低温下只能接受与当前状态能差较⼩的新状态为重要状态。在温度趋于零时，就不再接受 的新状态 了。
SAA 机制与原理
1. 优化问题的解视为固体的状态；
2. 随机给定优化问题的初始解；
3. 给定初始温度；
4. 根据当前的解产⽣新的解；
5. 依据Metropolis准则对两个解进⾏取舍；
6. 重复以上两步直到达到热平衡；
7. 降低温度继续上述过程直到温度降到最低，最后的状态就认为是问题的解。
伪代码
糖康福散i j
E <j E i j r =e
−K T B E −E j i j p <[0,1)p =e −K T B E −E j i青少年保护法
算法组成与分析
（2）设计⾼效的退⽕历程；
（3）避免状态的迂回搜索；
（4）采⽤并⾏搜索结构；
（5）避免陷⼊局部极⼩，改进对温度的控制⽅式；
（6）选择合适的初始状态；
（7）设计合适的算法终⽌准则。涡流纺纱
解决实际问题
SAA求解TSP
旅⾏商问题 ( TSP , Traveling Salesman Problem ) ：有N个城市，要求从其中某个问题出发，唯⼀遍历所有城市，再回到出发的城市，求最短的路线。旅⾏商问题属于所谓的NP完全问题，精确的解决TSP只能通过穷举所有的路径组合，其时间复杂度是O(N!) 。
使⽤模拟退⽕算法可以⽐较快的求出TSP的⼀条近似最优路径。（使⽤遗传算法也是可以的，我将在
下⼀篇⽂章中介绍）模拟退⽕解决TSP 的思路：
1. 产⽣⼀条新的遍历路径P(i+1)，计算路径P(i+1)的长度L( P(i+1) )
2. 若L(P(i+1)) < L(P(i))，则接受P(i+1)为新的路径，否则以模拟退⽕的那个概率接受P(i+1) ，然后降温
3. 重复步骤1，2直到满⾜退出条件
产⽣新的遍历路径的⽅法有很多，下⾯列举其中3种：
1. 随机选择2个节点，交换路径中的这2个节点的顺序。 2. 随机选择2个节点，将路径中这2个节点间的节点顺序逆转。
3. 随机选择3个节点m，n，k，然后将节点m与n间的节点移位到节点k后⾯。
无用师卷参考
义如 模拟退⽕算法PPT
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议