模拟退火SA | 彩潭有鲤的札记

type

status

date

slug

summary

原理

退火这个词，其实是铁匠发明的。它的意思很简单，就是将铁匠炉烧热后，再把下边的火撤掉，让金属在炉子里边慢慢冷却。人们发现，这个缓慢的降温过程能消除金属内部的各种缺陷，使得其恢复能量最低的状态。后来，受到退火工艺的启发，研究人员把将退火的缓慢的降温思路推广开来，用于寻找复杂函数的全局最优值。举个简单的例子，氦原子在金属中空位附近运动时，其势能函数大概长这样：

把势能函数看成一个轨道，再把氦看成一个小球放到这个轨道上。那么，小球的高度就是它的重力势能。求这个函数的全局最小值，其实就是让小球滚到最深那个坑过程：

由于函数中存在非常多局域极小值（浅坑），常见的贪心算法（如梯度下降法，就是闭着眼睛沿坡往下滚）会陷入最近的局域极小值，错过到全局最小值（深坑）。那么，怎么才能让滚进深坑呢？我们先晃一晃整个体系，让小球随机动起来。我们把晃动的剧烈程度称为温度。在足够长的时间内。小球出现在点的概率呈玻尔兹曼分布，与点的高度(势能)和温度密切相关：

温度为0时，小球出现在全局最小值的概率为100%

那么，把温度设为0不就行了？当然不行。上面的概率成立的前提是提供无穷长的时间，使得小球能够遍历整个函数。实际中，无穷长的时间当然是不现实的。小球从低概率区向高概率区转移，这个过程是需要消耗时间的。高温下，转移速度快。但另一方面，高温下，小球落在各个坑里的概率差别比较小。为了让小球能够尽快的转移到最低点，我们可以采取一个降温策略：

先设定一个较高的温度，使得小球有足够的能量越过能垒，小球到处乱跑的概率比较大。

随机移动小球的位置，检查其移动前后的能量差。若，小球能量降低，则接受此次移动。若，小球能量升高，有一定概率接受此次移动，概率为： (k为一个随机数) 。这个判定方法称为Metropolis判据。

逐渐降低温度T，使得小球滑向低处的概率逐渐增大，直到小球缓缓收敛到最低点，不再晃动

模拟退火时有三个参数，分别是初始温度、降温系数、终止温度

温度更新函数是指退火温度缓慢降低的实现方案，也称冷却进度表；状态产生函数是指由当前解随机产生新的候选解的方法；状态接受函数是指接受候选解的机制，通常采用Metropolis准则；外循环是由冷却进度表控制的温度循环；内循环是在每一温度下循环迭代产生新解的次数，也称Markov链长度

基本流程如下：

（1）初始化：初始温度T，初始解状态s，迭代次数L；（2）对每个温度状态，重复 L次循环产生和概率性接受新解：（3）通过变换操作由当前解s 产生新解s′；（4）计算能量差 ∆E，即新解的目标函数与原有解的目标函数的差；（5）若∆E <0则接受s′作为新的当前解，否则以概率exp(-∆E/T) 接受s′ 作为新的当前解；（6）在每个温度状态完成 L次内循环后，降低温度 T，直到达到终止温度

代码

多变量连续函数优化

化问题中的约束条件，模拟退火算法有几种常用的处理方法：

1.决策变量取值的上下限约束。此类约束条件比较容易处理，只要设定初始解、新解在决策变量取值的上下限之间就可以解决。例如:

（1）设置产生新解的随机数的上下限为决策变量的上下限，即；

（2）设置产生新解的随机数的上下限为当前解与决策变量的上下限，即；

（3）通过条件判断，当新解超出决策变量上下限，则令其取上下限，即。当然，这些处理方式，都会影响随机数的概率分布，因而也影响模拟退火算法的优化性能。

2.检验法处理不等式约束问题在模拟退火算法的迭代过程中，将每次产生的新解代入每个不等式约束函数，判断是否满足约束条件；如果新解不满足约束条件，则舍弃这个新解，返回重新产生一个新解进行检验，直到产生的新解满足全部约束条件为止。这个方法的思路简单，每次迭代都在可行域内进行，但是对于约束条件众多、苛刻的复杂问题，多次产生的新解都不能满足约束条件，会使计算时间很长，甚至停滞不前。

3.消元法处理等式约束问题。对于等式约束，很难通过随机产生的新解满足约束条件，通常不能使用检验法处理。消元法是通过解方程将等式约束中的某个决策变量表示为其它决策变量的线性关系后，代入目标函数和不等式约束条件中，从而消去该约束条件。消元法不仅解决了等式约束问题，而且减少了决策变量的数量，从而有效简化了优化问题的复杂度，是一举两得的处理方法。但是，对于非线性等式约束，求解非线性方程组也是非常困难的，消元法并不是普遍都能适用的。

4.更为通用的处理约束条件的方法是惩罚函数法:

惩罚函数法是一类常用的处理约束条件的技术，在模拟退火算法中处理约束条件非常有效。方法的思想是将约束条件转化为惩罚函数，附加在原有的目标函数上构造新的目标函数；当不满足约束条件时，通过惩罚函数使新的目标函数变差而被舍弃。

惩罚函数法有外点法和内点法:

外点法对可行域外的点（即不满足约束的点）施加惩罚，对可行域内部的点不惩罚，从而使迭代点向可行域D逼近。

内点法是在可行域内部进行搜索，约束边界起到类似围墙的作用，使目标函数无法穿过，就把搜索点限制在可行域内了，因此只适用于不等式约束

考虑约束优化问题：满足限制:

惩罚函数法将问题转化成如下无约束问题:

其中：

在上述方程，称为外部罚函数，称为惩罚因子。在每一次迭代中，都增大，然后求解该无约束问题。将每一次迭代的结果将组成一个序列，此序列的极限即为原约束问题的解。

test.py

8.2KB

整数规划

只要将产生初值/新解的随机实数发生器 random.uniform、random.normalvariate 改为随机整数发生器 random.randint即可：

TSP问题

调库实现SA

SA输入参数

SA and SAFast and SABoltzmann and SACauchy

入参	默认值	意义
func	-	目标函数
x0	-	迭代初始点
T_max	100	最大温度
T_min	1e-7	最小温度
L	300	链长
max_stay_counter	150	冷却耗时
lb	ㅤ	每个自变量的最小值
ub	ㅤ	每个自变量的最大值