一、模拟退火算法解TSP问题
import random
import numpy as np
from math import e, exp
import matplotlib.pyplot as plt# 31个城市的坐标
city_loc = [(1304, 2312), (3639, 1315), (4177, 2244), (3712, 1399), (3488, 1535),(3326, 1556), (3238, 1229), (4196, 1004), (4312, 790), (4380, 570),(3007, 1970), (2562, 1756), (2788, 1491), (2381, 1676), (1332, 695),(3715, 1678), (3918, 2179), (4061, 2370), (3780, 2212), (3676, 2578),(4029, 2838), (4263, 2931), (3429, 1908), (3507, 2367), (3394, 2643),(3439, 3201), (2935, 3240), (3140, 3550), (2545, 2357), (2778, 2826), (2370, 2975)]T0 = 50000#初始温度
T_end = 15#结束温度
q = 0.98#退火速率
L = 1000#迭代次数# 两个城市的距离
def dist(a, b):x1 = city_loc[a][0]x2 = city_loc[b][0]y1 = city_loc[a][1]y2 = city_loc[b][1]distance = ((x2 - x1)**2 + (y2 - y1)**2)**0.5return distance# 路程总长
def totaldistance(a):value = 0for j in range(30):value += dist(a[j], a[j + 1])value += dist(a[30], a[0])return value# 初始化一个解 [0,1,2,3..30]
def init_ans():ans = []for i in range(31):ans.append(i)return ans# 产生新解
def creat_new(ans_before):ans_after = ans_before[:]cuta = random.randint(0, 30)cutb = random.randint(0, 30)ans_after[cuta], ans_after[cutb] = ans_after[cutb], ans_after[cuta]return ans_afterif __name__ == '__main__':ans0 = init_ans()T = T0cnt = 0trend = []while T > T_end:for i in range(L):newans = creat_new(ans0)old_dist = totaldistance(ans0)new_dist = totaldistance(newans)df = new_dist - old_distif df >= 0:rand = random.uniform(0, 1)if rand < 1 / exp(df / T): #关键步骤，通过概率控制是否将当前产生的新解当作退火分支ans0 = newanselse:ans0 = newansT = T * qcnt += 1now_dist = totaldistance(ans0)trend.append(now_dist)#print(cnt, "次降温，温度为：", T, " 路程长度为：", now_dist)distance = totaldistance(ans0)print(distance, ans0)# 绘制温度与距离变化图plt.plot(trend)plt.title("Temperature vs. Distance")plt.xlabel("Iteration")plt.ylabel("Distance")plt.show()# 绘制最佳路径图fig, ax = plt.subplots(1, 2, figsize=(12, 5), facecolor='#ccddef')# 定义子图1标题ax[0].set_title("Best route")# 画线x_coords = [city_loc[i][0] for i in ans0] + [city_loc[ans0[0]][0]]y_coords = [city_loc[i][1] for i in ans0] + [city_loc[ans0[0]][1]]ax[0].plot(x_coords, y_coords)# 画点ax[0].scatter(x_coords, y_coords, color='r')plt.show()
二、算法介绍
模拟退火算法（Simulated Annealing, SA）是一种用于全局优化问题的随机搜索算法，灵感来自金属退火过程中的物理现象。它通过允许在一定概率下接受较差解，以避免陷入局部最优解，逐渐趋近全局最优解。
模拟退火算法的基本概念
- 状态空间：所有可能解的集合。
- 目标函数：需要优化的函数，用于评价解的好坏。
- 温度参数（T）：控制算法接受较差解的概率，温度逐渐降低。
- 邻域（Neighborhood）：当前解的相邻解集合，通过一定规则生成。
模拟退火算法是一种强大的全局优化方法，通过模拟物理退火过程，在搜索空间中进行广泛探索，逐步收敛到全局最优解。尽管计算复杂度较高，但其简单灵活的特点使其在解决复杂优化问题时具有重要应用价值。根据具体问题的需求，可以灵活调整算法参数和策略，以达到最佳优化效果。
)
