本站原创文章，转载请说明来自《老饼讲解-BP神经网络》www.bbbdata.com
模拟退火算法(Simulated Annealing，SA)是求解策略中的一种随机寻优算法
通过本文可以初步掌握模拟退火算法，包括模拟退火算法的思想和具体的算法流程
本节通过介绍模拟退火解决什么问题，它的思想原理是什么，
以此来初步了解模拟退火算法是什么
模拟退火算法解决什么问题
模拟退火算法是一个借鉴物理退温过程设计的算法
它是一种用于寻找优秀解的算法
例如问题：已知, 求一 使得值最小
在无法求得精确解的情况下，则可用模拟退火算法对其寻找一个优秀解
备注：(1)找到的不一定是最优的解，但至少局部最优
(2) 这里的 f(x) 不要求有表达式，可以是一个规则，更不要求可偏导
模拟退火算法的背景意义
物理退温原理
一个高温物体，如果一下子把物体温度降下来，这样的物体是比较脆的，
因为内部各个粒子并未找到一个能量较小的位置
但如果让它缓慢降温，
粒子会在温度缓慢下降过程中，不断寻找能量更低的位置，
最终，每个粒子都能找到一个能量较低的位置，从而使物体更加紧固
（物体能量低，要改变它的结构，就需要更大能量，也即更紧固）
为什么急速降温不行，而要缓慢降温呢？
因为急速降温每个粒子被迫马上收缩到一定位置
而缓慢降温过程则不相同，
当每个粒子温度还很高时，它可以转移到不同位置，哪怕是跃迁到能量更高的位置，
因为温度还很高，有足够的能量支持它的跃迁
但随着温度下降，它能跃迁的概率越来越小，
随着缓慢降温，粒子刚开始的时候比较活跃，后慢慢的更倾向于收缩
可以看到，缓慢降温时，每个粒子在整个过程中有足够多的机会去找到更好的位置
物理退温迁移到数学寻找极小值问题
借鉴这一思想，迁移到我们的问题来，就是
x 对应 粒子
目标函数 对应 能量
我们的里的每个，就相当于物体的粒子，
刚开始的时候，设置一个温度，在温度高的时候，x的调整比较自由，哪怕x的调整会让目标函数值更高，我们也用一定的概率接受它
随着温度慢慢下降，接受更差的解的概率也降低，慢慢的，让每个x找到更好的位置，使整体目标函数值更小
本节展示模拟退火算法的具体流程
模拟退火算法流程
一、初始化
1.1. 初始化初始解
1.2. 初始化温度
二、外循环
2.1 内循环（直接循环N次）：
(1) 生成新解
从x的邻域随机选择一个x作为新解
(2) 计算新解的能量
(3) 根据能量差按概率接受新解
(3.1) 计算新解与旧解的能量差
(3.2) 根据能量差决定接受新解的概率
(3.3) 如果 则接受新解,否则放弃新解，进入下一轮
每次接受新解时，需要更新以下信息：
👉更新当前解
👉更新当前能量
👉更新历史最优解
👉更新本轮内循环找到的最优最差解所需的能量
2.2 降温
2.3 判断终止条件
如果本轮找到的最优、最差解的能量差异不大，则终止循环
三、输出历史找到的最优解
关于概率公式的解释
在模拟退火算法中，对于是否接受新解使用了下述公式
该公式是非常巧妙的，下面我们分步讨论它的意义
当新解比旧解更优秀时
当新解比旧解更优秀时，即时
而此时，则,
因此，不管随机数是多少，条件一定成立，
这意味着，只要新解不比旧解差，就一定接受新解
当新解比旧解更差时
当新解比旧解更差时，即时，
此时
p的取值受当前温度T与能量差两者的影响
当新解越差时，能量差就越大，此时p越小
但同时，温度T作为分母，T越大时，p越大，
也就是说，当温度很高时，即使能量差很大，也有很大的概率接受新解
所以说，这个公式非常的巧妙，仅仅用一个公式，就蕴含了多个机制
End