【数学建模】实验二【一】Python实现模拟退火算法

关于模拟退火算法

这个网上的教程已经很多很详细了，比如

现代优化算法 （一）：模拟退火算法 及应用举例

这里摘取部分，不详述

应用举例

例 已知敌方 100 个目标的经度、纬度如表 1 所示。

数据集下载

链接：https://pan.baidu.com/s/1AmLRAZ4ypbUkUOijWmbCvQ
提取码：ygtl

Python代码

我们编写如下的 Python 程序如下：

from math import pi, sin, cos, acos, exp

import matplotlib.pyplot as plt
import pandas as pd
import numpy as np

# 读取数据
sj = pd.read_csv('../sj.csv').values
x = sj[..., 0:8:2].reshape(100, 1)
y = sj[..., 1:9:2].reshape(100, 1)
sj = np.concatenate([x, y], axis=1)
# 设置起始结束的经纬度为(70，40)
d1 = np.array([70, 40])
sj = np.vstack((d1, sj, d1))
# 单位化成弧度
sj = sj * pi / 180
# 初始化距离矩阵d
d = np.zeros((102, 102))
for i in range(101):
	for j in range(i + 1, 102):
		temp = cos(sj[i, 0] - sj[j, 0]) * cos(sj[i, 1]) * cos(sj[j, 1]) + sin(sj[i, 1]) * sin(sj[j, 1])
		d[i, j] = 6370 * acos(temp)
d = d + d.T
S0, Sum = [], float("inf")
rng = np.random.default_rng()
for j in range(1, 1001):
	S = np.hstack((0, rng.permutation(100) + 1, 101))
	temp = 0
	for i in range(101):
		temp = temp + d[S[i], S[i + 1]]
	if temp < Sum:
		S0, Sum = S, temp
e, L, at, T = 0.1 ** 30, 20000, 0.999, 1
# 模拟退火过程
for k in range(1, L):
	# 产生新解
	c = 1 + np.floor(100 * np.random.random(2)).astype(int)
	c = sorted(c)
	c1, c2 = c[0], c[1]
	# 计算代价函数值
	df = d[S0[c1 - 1], S0[c2]] + d[S0[c1], S0[c2 + 1]] - d[S0[c1 - 1], S0[c1]] - d[S0[c2], S0[c2 + 1]]
	# 接受准则
	if df < 0:
		S0 = np.hstack((S0[0:c1], S0[c2:c1 - 1:-1], S0[c2 + 1:103]))
		Sum += df
	elif exp(-df / T) > np.random.random(1):
		S0 = np.hstack((S0[0:c1], S0[c2:c1 - 1:-1], S0[c2 + 1:103]))
		Sum += df
	T = T * at
	if T < e:
		break
# 输出巡航路径及路径长度
print("S0={}, Sum={}".format(S0, Sum))
# 画出路径图
for i in range(101):
	dx, dy = [sj[S0[i]][0], sj[S0[i + 1]][0]], [sj[S0[i]][1], sj[S0[i + 1]][1]]
	plt.plot(dx, dy)
plt.show()

结果截图

计算结果为 44 小时左右。其中的一个巡航路径如图 1 所示。