蚁群算法解决旅行商问题

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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
import numpy as np
import matplotlib.pyplot as plt
import matplotlib
import math
import random
import time

start = time.time()

matplotlib.rcParams['font.family'] = 'STSong'
np.set_printoptions(linewidth=400)
np.set_printoptions(threshold=np.inf)

"""
data.txt数据载入
---------------
重庆,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('城市分布图')
for i in range(city_count):
plt.annotate(i+1,xy=(city_condition[i][0], city_condition[i][1]), xytext=(city_condition[i][0] + 0.3, city_condition[i][1] + 0.3))
plt.scatter(city_condition[:, 0], city_condition[:, 1])
plt.xlabel('经度')
plt.ylabel('纬度')
plt.show()

"""
距离矩阵和总距离的计算
"""
#距离矩阵
city_count = len(city_name)
Distance = np.zeros((city_count, city_count))
for i in range(city_count):
for j in range(city_count):
if i != j:
Distance[i][j] = math.sqrt((city_condition[i][0] - city_condition[j][0]) ** 2 + (city_condition[i][1] - city_condition[j][1]) ** 2)
else:
Distance[i][j] = 100000
# print(Distance[0][1])
# print(Distance)
# 适应度计算
def get_total_distance(path_new):
distance = 0
for i in range(city_count-1):
#count为30,意味着回到了开始的点,此时的值应该为0.
distance += Distance[int(path_new[i])][int(path_new[i+1])]
distance += Distance[int(path_new[-1])][int(path_new[0])]
return distance

"""
两个难点
1.城市的选择:初始城市选择和下一个城市的选择设计
2.信息素的更新
"""
def main():
##参数设计
# 蚂蚁数量
AntCount = 10
# 城市数量
city_count = len(city_name)
# 信息素
alpha = 1 # 信息素重要程度因子
beta = 5 # 启发函数重要程度因子
rho = 0.1 #挥发速度
iter = 0 # 迭代初始值
iteration = 200 # 最大迭代值
Q = 1
# 初始信息素矩阵,全是为1组成的矩阵
pheromonetable = np.ones((city_count, city_count))
# print(pheromonetable)
# 候选集列表
candidate = np.zeros((AntCount, city_count)).astype(int) # 存放100只蚂蚁的路径(一只蚂蚁一个路径),一共就Antcount个路径,一共是蚂蚁数量*31个城市数量
path_best = np.zeros((iteration, city_count)) # path_best存放的是相应的,每次迭代后的最优路径,每次迭代只有一个值
# 存放每次迭代的最优距离
distance_best = np.zeros(iteration)
#怎么处理对角线的元素是0的情况
etable = 1.0 / Distance # 倒数矩阵

while iter < iteration:
"""
路径创建
"""
## first:蚂蚁初始点选择
if AntCount <= city_count:
candidate[:, 0] = np.random.permutation(range(city_count))[:AntCount]
else:
candidate[:city_count, 0] = np.random.permutation(range(city_count))[:]
candidate[city_count:, 0] = np.random.permutation(range(city_count))[:AntCount - city_count]
length = np.zeros(AntCount)#每次迭代的N个蚂蚁的距离值

## second:选择下一个城市选择
for i in range(AntCount):
# 移除已经访问的第一个元素
unvisit = list(range(city_count)) # 列表形式存储没有访问的城市编号
visit = candidate[i, 0] # 当前所在点,第i个蚂蚁在第一个城市
unvisit.remove(visit) # 在未访问的城市中移除当前开始的点
for j in range(1, city_count):#访问剩下的city_count个城市,city_count次访问
protrans = np.zeros(len(unvisit))#每次循环都更改当前没有访问的城市的转移概率矩阵1*30,1*29,1*28...
# 下一城市的概率函数
for k in range(len(unvisit)):
# 计算当前城市到剩余城市的(信息素浓度^alpha)*(城市适应度的倒数)^beta
# etable[visit][unvisit[k]],(alpha+1)是倒数分之一,pheromonetable[visit][unvisit[k]]是从本城市到k城市的信息素
protrans[k] = np.power(pheromonetable[visit][unvisit[k]], alpha) * np.power(
etable[visit][unvisit[k]], (alpha + 1))

# 累计概率,轮盘赌选择
cumsumprobtrans = (protrans / sum(protrans)).cumsum()
cumsumprobtrans -= np.random.rand()
# 求出离随机数产生最近的索引值
k = unvisit[list(cumsumprobtrans > 0).index(True)]
# 下一个访问城市的索引值
candidate[i, j] = k
unvisit.remove(k)
length[i] += Distance[visit][k]
visit = k # 更改出发点,继续选择下一个到达点
length[i] += Distance[visit][candidate[i, 0]]#最后一个城市和第一个城市的距离值也要加进去
"""
更新路径等参数
"""
# 如果迭代次数为一次,那么无条件让初始值代替path_best,distance_best.
if iter == 0:
distance_best[iter] = length.min()
path_best[iter] = candidate[length.argmin()].copy()
else:
# 如果当前的解没有之前的解好,那么当前最优还是为之前的那个值;并且用前一个路径替换为当前的最优路径
if length.min() > distance_best[iter - 1]:
distance_best[iter] = distance_best[iter - 1]
path_best[iter] = path_best[iter - 1].copy()
else: # 当前解比之前的要好,替换当前解和路径
distance_best[iter] = length.min()
path_best[iter] = candidate[length.argmin()].copy()

"""
信息素的更新
"""
#信息素的增加量矩阵
changepheromonetable = np.zeros((city_count, city_count))
for i in range(AntCount):
for j in range(city_count - 1):
# 当前路径比如城市23之间的信息素的增量:1/当前蚂蚁行走的总距离的信息素
changepheromonetable[candidate[i, j]][candidate[i][j + 1]] += Q / length[i]
#Distance[candidate[i, j]][candidate[i, j + 1]]
#最后一个城市和第一个城市的信息素增加量
changepheromonetable[candidate[i, j + 1]][candidate[i, 0]] += Q / length[i]
#信息素更新的公式:
pheromonetable = (1 - rho) * pheromonetable + changepheromonetable
iter += 1
return distance_best,path_best,iteration

def draw(distance_best,path_best,iteration):
end = time.time()
print("Time used:", end - start)
print("蚁群算法的最优路径",path_best[-1]+1)
print("迭代",iteration,"次后","蚁群算法求得最优解",distance_best[-1])

# # 路线图绘制
fig = plt.figure()
ax2 = fig.add_subplot()
ax2.set_title('最佳路线图')
x = []
y = []
path = []
for i in range(len(path_best[-1])):
x.append(city_condition[int(path_best[-1][i])][0])
y.append(city_condition[int(path_best[-1][i])][1])
path.append(int(path_best[-1][i])+1)
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')

# 距离迭代图
fig = plt.figure()
ax3 = fig.add_subplot()
ax3.set_title('距离迭代图')
plt.plot(range(1, len(distance_best) + 1), distance_best)
plt.xlabel('迭代次数')
plt.ylabel('距离值')
plt.show()
if __name__ == '__main__':
distance_best, path_best, iteration = main()
draw(distance_best, path_best, iteration)
0%