模拟退火算法解决旅行商问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import math
import random

#为了调整格式,测试数据
matplotlib.rcParams['font.family'] = 'STSong'
np.set_printoptions(linewidth=400)
np.set_printoptions(threshold=np.inf)

"""
载入数据
----------------------
重庆,106.54,29.59
拉萨,91.11,29.97
乌鲁木齐,87.68,43.77
银川,106.27,38.47
呼和浩特,111.65,40.82
南宁,108.33,22.84
哈尔滨,126.63,45.75
长春,125.35,43.88
沈阳,123.38,41.8
石家庄,114.48,38.03
太原,112.53,37.87
西宁,101.74,36.56
济南,117,36.65
郑州,113.6,34.76
南京,118.78,32.04
合肥,117.27,31.86
杭州,120.19,30.26
福州,119.3,26.08
南昌,115.89,28.68
长沙,113,28.21
武汉,114.31,30.52
广州,113.23,23.16
台北,121.5,25.05
海口,110.35,20.02
兰州,103.73,36.03
西安,108.95,34.27
成都,104.06,30.67
贵阳,106.71,26.57
昆明,102.73,25.04
香港,114.1,22.2
澳门,113.33,22.13
"""
city_name = []
city_condition = []
with open('data.txt','r',encoding='UTF-8') as f:
lines = f.readlines()
for line in lines:
line = line.split('\n')[0]
line = line.split(',')
city_name.append(line[0])
city_condition.append([float(line[1]), float(line[2])])
city_condition = np.array(city_condition)

"""
地图展示
"""
def map_show():
fig = plt.figure()
ax1 = fig.add_subplot()
ax1.set_title('城市分布图')
plt.scatter(city_condition[:,0],city_condition[:,1])
plt.xlabel('经度')
plt.ylabel('纬度')
plt.show()

#距离矩阵
city_count = len(city_name)
Distance = np.zeros([city_count+1, city_count+1])
for i in range(1,city_count+1):
for j in range(1,city_count+1):
Distance[i][j] = math.sqrt((city_condition[i-1][0] - city_condition[j-1][0]) ** 2 + (city_condition[i-1][1] - city_condition[j-1][1]) ** 2)

"""
全局参数设计
"""
#path_new 代表着新的路径,distance代表着路径的和,即适应度。
#起始温度和最终温度
t2 = (1,100)
#马尔可夫的长度
alpha = 0.98
markovlen = 200
#存放路径的组合
# path_new = np.array([i for i in np.arange(1,city_count+1)])
path_new = np.array([1, 3,7, 2,18, 9, 29, 19, 20, 10, 21, 14, 15, 8, 25, 26, 11, 23,28, 27, 16, 17, 22, 30, 24,5, 12, 13, 4, 6,31])
# path_new = np.array([1, 3,7, 2,18, 9, 11, 19, 20, 10, 21, 14, 15, 8, 25, 26, 29, 28, 27, 16, 17, 22, 23, 30, 5, 12, 13, 4, 6, 24,31])
path_current = path_new.copy()
#赋予初始值
value_current = 99000
#最优路径
path_best = path_new.copy()
#最优解
value_best = 99000
t = t2[1]
"""
总距离,适应度计算
"""
def get_total_distance(path_new):
distance = 0
for i in range(city_count-1):
#count为30,意味着回到了开始的点,此时的值应该为0.
distance += Distance[path_new[i]][path_new[i+1]]
distance += Distance[path_new[-1]][path_new[0]]
return distance
"""
外循环的终止条件是最终温度
内循环的终止条件是马尔科夫的长度,种群数量。
"""
"""
交叉变异,迭代,降温
"""
result = []#记录过程中最优的值
while t > t2[0]:
j = 1
for i in np.arange(markovlen):
j += 1
if np.random.rand() > 0.5:
while True:
#双交换
loc1 = np.int(np.ceil(np.random.rand()*(city_count-1)))
loc2 = np.int(np.ceil(np.random.rand()*(city_count-1)))
if loc1 != loc2:
break
path_new[loc1],path_new[loc2] = path_new[loc2],path_new[loc1]
else:
while True:
#三交换
loc1 = np.int(np.ceil(np.random.rand() * (city_count - 1)))
loc2 = np.int(np.ceil(np.random.rand() * (city_count - 1)))
loc3 = np.int(np.ceil(np.random.rand() * (city_count - 1)))
if ((loc1 != loc2) & (loc2!=loc3) & (loc1 != loc3)) :
break
if loc1 > loc2:
loc1,loc2 = loc2,loc1
if loc2 > loc3:
loc2,loc3 = loc3,loc2
if loc1 >loc2:
loc1,loc2 = loc2,loc1
#思想参考l1>l2,借用的t,片段互换,注意换片段的位置。这里可以讲讲思想
path_list = path_new[loc1:loc2].copy()
path_new[loc1:loc3-loc2+loc1] = path_new[loc2:loc3].copy()
path_new[loc3-loc2+loc1:loc3] = path_list.copy()
distance = get_total_distance(path_new)
if distance < value_current:
value_current = distance
#路径也复制
path_current = path_new.copy()
if distance < value_best:
value_best = distance
path_best = path_new.copy()
else:
if np.random.rand() < np.exp(-(distance-value_current)/t):
#一定概率接受
value_current = distance
path_current = path_new.copy()
else:
path_new = path_current.copy()
t = alpha * t # 降温
j = j +1

result.append(value_best)#记录过程中最优的值。即每次迭代的最优值,最短路径也是从这里面产生的。
"""
主函数
"""
def main():
# 输出部分
print("模拟退火算法解决tsp问题")
print("最优值是:", value_best)
print("最优路径:", path_best)
map_show()
# 距离迭代图
fig = plt.figure()
ax3 = fig.add_subplot()
ax3.set_title('距离迭代图')
plt.plot(np.array(result))
plt.xlabel('迭代次数')
plt.ylabel('距离值')
plt.show()

# 路线图绘制
fig = plt.figure()
ax2 = fig.add_subplot()
ax2.set_title('最佳路线图')
x = []
y = []
path = []
for i in range(len(city_name)):
x.append(city_condition[path_best[i] - 1][0])
y.append(city_condition[path_best[i] - 1][1])
path.append(path_best[i])
x.append(x[0])
y.append(y[0])
path.append(path[0])
for i in range(len(x)):
plt.annotate(path[i], xy=(x[i], y[i]), xytext=(x[i] + 0.3, y[i] + 0.3))
plt.plot(x, y, '-o')
plt.show()

if __name__ =="__main__":
main()
0%