一、概念

模拟退火算法(SA)来源于固体退火原理，是一种基于概率的算法。

将固体加温至充分高的温度，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，分子和原子越不稳定。而徐徐冷却时粒子渐趋有序，能量减少，原子越稳定。在冷却（降温）过程中，固体在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。
模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。

二、爬山算法，或者说梯度下降算法
模拟退火与基于贪心算法的爬山算法（Hill Climbing）不同的是，模拟退火算法在一些情况下可能会克服陷入局部最优解而非找到全局最优解的情况。

爬山算法容易陷入局部最优

 三、模拟退火算法

模拟退火算法包含两个部分即Metropolis算法和退火过程，分别对应内循环和外循环，模拟退火算法的本质是双层循环。

Metropolis算法：概率接受差解

举例上图搜索最小值，假设开始状态在A，多次迭代之后更新到B的局部最优解，这时发现更新到B时，能力比A要低，则说明接近最优解了，因此百分百转移，状态到达B后，发现下一步能量上升了，如果是梯度下降则是不允许继续向前的，如果我们采用一定的概率来接受这个差解，就有概率继续搜索。

公式如下图所示，如果我们找到的下一个解是比之前的解小的，那我们就接受这个差解，如果我们找到的解反而比现在的解要大，那么我们才去一定的概率去接受这个差解，即我们有可能接受，也有可能不接受。

 

对该公式的再解释：是一个简单的函数 ，其函数图像如下图所示，这样能保证了接受差解的概率是属于[0,1]的，而公式中的T（温度）是由物理模型退火演变过来的，在这里我们无需知道其物理的具体含义，而是数学的角度角度进行解释。

在一开始我们需要T值较大，这样根据函数的单调性，我们可以看出接受差解的P是较大的，便于我们对全局进行搜索，而在后期温度下降，T值变小，当温度趋于零时，只能接受目标函数下降的，这有利于我们尽快结束收敛，完成迭代。

四、模拟退火中的参数控制

（1）初始的温度T应选的足够高，保证在一开始的时候差解有大概率被接受，方便对全局进行搜索。初始温度越高，获得高质量的解的概率越大，耗费的时间越长。

（2）退火速率，即温度下降，最简单的下降方式是指数式下降：
T(n) = αT(n) ,n =1,2,3,…
（3）程序终止：满足其一即可

• 达到指定的迭代次数，例如迭代 200 次；
• 达到终止温度：例如温度小于 0.000001；如果温度下降到终止温度或者达到用户设定的阈值，则退火完成
• 我们找到的最优解连续 M（例如 30 次）次迭代都没有变化

五、模拟退火算法的主要步骤

模拟退火算法本质是两层循环，外层循环控制温度由高向低变化；内层循环中，温度固定，对旧解添加随机扰动得到新解，并按一定规则接受新解。

① 解的编码：如果该解的表示简单，采用实数编码即可。

② 确定初始解：随机生成一个解 A, 计算解 A 对应的目标函数值 f(A) ，可以判断一下在不在定义域内

③ 邻域新解的生成：在 A 附近随机生成一个解 B，计算解 B 对应的目标函数值 ，没有统一规定新解的生成方式，但生成新解后需要判断是还在定义域内

④ 确定能量函数：在使用时为了方便，我们可以直接用上图的函数

能量越低，被接受的概率越高。因此，当求解最大值目标函数时，可以以目标函数的倒数作为能量函数；当求解最小值目标函数时，可以直接以目标函数作为能量函数

⑤ Metropolis准则：如果 f(B)>f(A), 则将解 B 赋值给解 A，然后重复上面步骤（爬山法的思想）；如果 f(B)≤f(A), 那么我们计算接受 B 的概率p，然后我们生成一个[0,1]之间的随机数 r，如果 r<p，我们就将解 B 赋值给解 A，然后重复上面的步骤；否则我们返回第三步，在原来的 A 附近再重新生成一个解 B，然后继续下去。

⑥ 搜索最优解，存储最优解

六、新解的产生方法

新解的产生方式是最为重要的

对于TSP问题中，如果有这些城市的话，可以采用下图的方法，但具体问题具体分析

 

七、代码实例python：模拟退火算法求解TSP模型

① 解的编码 

求解TSP模型采用自然数编码，0节点代表初始城市，1-7节点表示其他7座城市。如 1，7，6，3，2，5，4 表示从0出发依次经过城市1、7、6、3、2、5、4最后回到0

② 确定初始解

随机生成一个由数字1-7各出现一次的数列。

#numbers为需要经过的其他城市的数量
def initialization(numbers):path_random = np.random.choice(list(range(1, numbers + 1)), replace=False, size=numbers)path_random = path_random.tolist()return path_random

③ 邻域新解的生成

采用两点逆转的方法，即对数列设置两个点，然后数列在这两点中发生逆转，改变数列。逆转操作如下：假设数列为A=1,4,5,2,3,6,7，随机生成两个点2和6，那么A1=4,5,2,3,6，逆转后A1=6,3,2,5,4，A=1,6,3,2,5,4,7。

def generate_new(path):numbers = len(path)#随机生成两个不重复的点positions = np.random.choice(list(range(numbers)), replace=False, size=2)lower_position = min(positions[0], positions[1])upper_position = max(positions[0], positions[1])#将数列中段逆转mid_reversed = path[lower_position:upper_position + 1]mid_reversed.reverse()#拼接生成新的数列new_path = path[:lower_position]new_path.extend(mid_reversed)new_path.extend(path[upper_position + 1:])return new_path

④ 确定能量函数

TSP模型以最短路径为目标函数，因此直接以路径长度为能量函数即可。

#length_mat为各个节点之间的最短距离矩阵
def e(path, length_mat):numbers = len(path) - 1length = length_mat[0][path[0]] + length_mat[path[-1]][0]for i in range(numbers):length += length_mat[path[i]][path[i + 1]]return length

⑤ 新解接受准则

采用标准的Metropolis准则。

def metropolis(e, new_e, t):if new_e <= e:return Trueelse:p = math.exp((e - new_e) / t)return True if random.random() < p else False

⑥ 搜索最优解

根据已生成的所有解的能量，搜索能量最低的解，即为模拟退火算法的最优解
 

def search(all_path, length_mat):best_e = 0xffffbest_path = all_path[0]for path in all_path:ex = e(path, length_mat)if ex < best_e:best_e = exbest_path = pathreturn best_path

 7.模拟退火算法主函数

#t0为初始温度，t_final为终止温度，alpha为冷却系数，inner_iter为内层迭代次数
#city_numbers为所需要经过的其他城市，length_mat为各个节点之间的最短距离矩阵
def sa(t0, t_final, alpha, inner_iter, city_numbers, length_mat):all_path = []all_ex = []init = initialization(city_numbers)all_path.append(init)all_ex.append(e(init, length_mat))t = t0while t > t_final:path = search(all_path, length_mat)ex = e(path, length_mat)for i in range(inner_iter):new_path = generate_new(path)new_ex = e(new_path, length_mat)if metropolis(ex, new_ex, t):path = new_pathex = new_exall_path.append(path)all_ex.append(ex)t = alpha * treturn all_path, all_ex

8.主程序：先通过Floyd算法求每个节点的最短路径

graph = nx.Graph()
graph.add_nodes_from(range(0, 8))
edges = [(0, 1, 3), (0, 4, 2),(1, 4, 3), (1, 5, 4), (1, 7, 2),(2, 3, 5), (2, 4, 1), (2, 5, 4), (2, 6, 3),(3, 6, 1),(4, 5, 5),(5, 6, 2), (5, 7, 4),(6, 7, 4)]
graph.add_weighted_edges_from(edges)
shortest_length = dict(nx.shortest_path_length(graph, weight='weight'))
length_mat = []
for i in range(0, 8):i_j = []for j in range(0, 8):i_j.append(shortest_length[i][j])length_mat.append(i_j)

 9.调用模拟退火

all_path, all_ex = sa(3000, pow(10, -1), 0.98, 200, 7, length_mat)
print(search(all_path, length_mat), round(e(search(all_path, length_mat), length_mat)))
iteration = len(all_path)
all_path = np.array(all_path)
all_ex = np.array(all_ex)
plt.xlabel("Iteration")
plt.ylabel("Length")
plt.plot(range(iteration), all_ex)
plt.show()

参考：模拟退火算法（Python）_Zengwh_02的博客-CSDN博客_模拟退火算法python

模拟退火算法详细讲解（含实例python代码）_Eterbity的博客-CSDN博客_模拟退火算法原理图

数学建模清风第二次直播：模拟退火算法 https://www.bilibili.com/video/BV1hK41157JL