模拟退火算法详细讲解（含实例python代码）

最近老师要求做模拟退火算法实验，看了很多博客之后感觉还是不太清楚，最后问了老师之后才搞明白。想把自己的理解写下来，帮助大家更好的理解。本篇文章是在另一篇博客的基础上加了一下自己的理解，然后又把我们在实验中的实例写下来，还有参考代码。希望大家看了之后能够加深对模拟退火算法的理解。

另一篇博客链接: 深度学习 — 模拟退火算法详解.

（一）模拟退火算法简介

（二）模拟退火算法原理

Metropolis算法就是如何在局部最优解的情况下让其跳出来（如图中B、C、E为局部最优），是退火的基础。1953年Metropolis提出重要性采样方法，即以概率来接受新状态，而不是使用完全确定的规则，称为Metropolis准则，计算量较低。

假设开始状态在A，多次迭代之后更新到B的局部最优解，这时发现更新到B时，能力比A要低，则说明接近最优解了，因此百分百转移，状态到达B后，发现下一步能量上升了，如果是梯度下降则是不允许继续向前的，而这里会以一定的概率跳出这个坑，这各概率和当前的状态、能量等都有关系。所以说这个概率的设计是很重要的，下面从数学方面进行解释。

从上式我们可以看到，如果能量减小了，那么这种转移就被接受（概率为1），如果能量增大了，就说明系统偏离全局最优值位置更远了，此时算法不会立刻将其抛弃，而是进行概率操作：首先在区间【0,1】产生一个均匀分布的随机数$ϵ$，如果$ϵ$ 用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件Tf。而温度的作用就是来计算转移概率P的。当温度每次下降后，转移概率也发生变化，因此在所有温度下迭代L次的结果也都是不相同的。在每个温度下迭代L次来寻找当前温度下的最优解，然后降低温度继续寻找，直到到达终止温度，即转移概率P接近于0.

接受状态的三条原则：

（1）在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；

（2）随着温度的下降，接受使目标函数上升的解的概率要逐渐减小；

（3）当温度趋于零时，只能接受目标函数下降的解。

（三）退火过程中参数控制

（1）初始的温度T(0)应选的足够高，使的所有转移状态都被接受。初始温度越高，获得高质量的解的概率越大，耗费的时间越长。

（四）算法步骤

1.模拟退火的基本思想:

(1) 初始化：初始温度T(充分大)，初始解状态S(是算法迭代的起点)，每个T值的迭代次数L

(2) 对k=1, …, L做第(3)至第6步：

(3) 产生新解S′

(4) 计算增量ΔT=C(S′)-C(S)，其中C(S)为目标函数,C(S)相当于能量

(5) 若ΔT<0则接受S′作为新的当前解，否则以概率exp(-ΔT/T)接受S′作为新的当前解.

(6) 如果满足终止条件则输出当前解作为最优解，结束程序。

第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。

第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。

第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是Metropolis准则: 若ΔT<0则接受S′作为新的当前解S，否则以概率P接受S′作为新的当前解S。

第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。

（五）实例分析

import math from random import random import matplotlib.pyplot as plt def func(x, y): #函数优化问题 res= 4*x2-2.1*x4+x6/3+x*y-4*y2+4*y4 return res #x为公式里的x1,y为公式里面的x2 class SA: def __init__(self, func, iter=100, T0=100, Tf=0.01, alpha=0.99): self.func = func self.iter = iter #内循环迭代次数,即为L =100 self.alpha = alpha #降温系数，alpha=0.99 self.T0 = T0 #初始温度T0为100 self.Tf = Tf #温度终值Tf为0.01 self.T = T0 #当前温度 self.x = [random() * 11 -5 for i in range(iter)] #随机生成100个x的值 self.y = [random() * 11 -5 for i in range(iter)] #随机生成100个y的值 self.most_best =[] """ random()这个函数取0到1之间的小数 如果你要取0-10之间的整数（包括0和10）就写成 (int)random()*11就可以了，11乘以零点多的数最大是10点多，最小是0点多 该实例中x1和x2的绝对值不超过5（包含整数5和-5），（random() * 11 -5）的结果是-6到6之间的任意值（不包括-6和6） （random() * 10 -5）的结果是-5到5之间的任意值（不包括-5和5），所有先乘以11，取-6到6之间的值，产生新解过程中，用一个if条件语句把-5到5之间（包括整数5和-5）的筛选出来。 """ self.history = { 
    'f': [], 'T': []} def generate_new(self, x, y): #扰动产生新解的过程 while True: x_new = x + self.T * (random() - random()) y_new = y + self.T * (random() - random()) if (-5 <= x_new <= 5) & (-5 <= y_new <= 5): break #重复得到新解，直到产生的新解满足约束条件 return x_new, y_new def Metrospolis(self, f, f_new): #Metropolis准则 if f_new <= f: return 1 else: p = math.exp((f - f_new) / self.T) if random() < p: return 1 else: return 0 def best(self): #获取最优目标函数值 f_list = [] #f_list数组保存每次迭代之后的值 for i in range(self.iter): f = self.func(self.x[i], self.y[i]) f_list.append(f) f_best = min(f_list) idx = f_list.index(f_best) return f_best, idx #f_best,idx分别为在该温度下，迭代L次之后目标函数的最优解和最优解的下标 def run(self): count = 0 #外循环迭代，当前温度小于终止温度的阈值 while self.T > self.Tf: #内循环迭代100次 for i in range(self.iter): f = self.func(self.x[i], self.y[i]) #f为迭代一次后的值 x_new, y_new = self.generate_new(self.x[i], self.y[i]) #产生新解 f_new = self.func(x_new, y_new) #产生新值 if self.Metrospolis(f, f_new): #判断是否接受新值 self.x[i] = x_new #如果接受新值，则把新值的x,y存入x数组和y数组 self.y[i] = y_new # 迭代L次记录在该温度下最优解 ft, _ = self.best() self.history['f'].append(ft) self.history['T'].append(self.T) #温度按照一定的比例下降（冷却） self.T = self.T * self.alpha count += 1 # 得到最优解 f_best, idx = self.best() print(f"F={f_best}, x={self.x[idx]}, y={self.y[idx]}") sa = SA(func) sa.run() plt.plot(sa.history['T'], sa.history['f']) plt.title('SA') plt.xlabel('T') plt.ylabel('f') plt.gca().invert_xaxis() plt.show() 

运行结果：