2023年7月29日发(作者：)

Python实现蚁群算法求解旅⾏商问题⽂章⽬录效果思路1.初始化步骤Step 1Step 2内容随机⽣成所有城市的坐标 (city_x, city_y)计算任意两城市之间的距离 (distance) 和能见度 (eta)步骤Step 3Step 4内容⽤贪婪算法得出初始路径计算得出并记录所有路径的信息素浓度(tau)2.多次迭代步骤Step 1Step 2Step 3Step 4Step 5Step 6Step 7Step 8Step 9Step 10Step 11Step 12Step 13Step 14Step 15内容第 t 次迭代第 t 次迭代, 初始化: 所有蚂蚁 (m) 的路径 (path[m][]), 出发城市 (path[m][0]),允许去的城市 (allowed[m][]) 即本次迭代中未去过的城市第 t 次迭代, 第 c 次选择下⼀个城市第 t 次迭代, 第 c 次选择下⼀个城市, 第 m 只蚂蚁选择下⼀个城市第 t, c, m 中, 初始化：估值函数 pij[0][], 估值的概率占⽐ pij[1][], ⽐例选择时的概率点 pij[2][]第 t, c, m 中, 获得蚂蚁 m 的允许去的城市 cho = []第 t, c, m 中, 计算蚂蚁 m 去城市 n 的 估值函数第 t, c, m 中, 计算蚂蚁 m 去城市 n 的 估值函数值 在所有估值函数值之和的占⽐第 t, c, m 中, 计算⽐例选择 (轮盘赌) 时, 去城市 n 还是城市 n+1 的概率选择点第 t, c, m 中, 模仿轮盘赌, 随机⽐例选择第 t 次迭代, 所有蚂蚁回到出发城市, 形成⼀条⾸尾相连的路径第 t 次迭代, 计算所有蚂蚁 (m) 的路径长 (mplen[m]), 途经城市 (taumnn[m][][])第 t 次迭代, 更新路径 (tau[i][j]) 的信息素 (蒸发剩下的 + 新留下的)第 t 次迭代, 选出所有蚂蚁 (m) 路径长度 (mplen[m]) 中的最短路径长度第 t 次迭代, 判断是否出现⽐全局最短路径更短的本次迭代最短路径, 并更新3.展⽰结果步骤Step 1Step 2Step 3Step 4Step 5内容输出 每次迭代的最短路径长度输出 全局最短路径长度 及其 ⾸次出现 的 迭代次数可视化展⽰ 所有城市 的 位置可视化展⽰ 全局最短路径可视化展⽰ 每次迭代的最短路径长度 的变化趋势代码rt mathimport randomimport copyimport as plt#

地图长度L = 100#

地图⾼度H = 80#

城市个数N = 20N = 20#

蚂蚁个数M = 20#

迭代次数T = 300#

地图的对⾓线长度LH = int((L*L + H*H))#

信息素的加权值alpha = 1#

能见度的加权值beta = 2#

信息素的蒸发率rho = 0.5#

城市的横坐标city_x = [0 for n in range(N)]#

城市的纵坐标city_y = [0 for n in range(N)]#

城市i和城市j之间的距离distance = [[0 for j in range(N)] for i in range(N)]#

能见度,

两点之间距离的倒数,

启发信息函数eta = [[0 for j in range(N)] for i in range(N)]#

当前时刻,

城市i和城市j之间的道路上信息素的值tau = [[0 for j in range(N)] for i in range(N)]# pathlen[t]

第 t

次迭代后得出的路径长度pathLen = []# pathCity[t]

第 t

次迭代后得出的路径pathCity = []#

第 best[0]

次迭代的路径最短,

全局最短路径的编号best = [0]#

全局最短路径上依次经过的城市的横坐标X = []#

全局最短路径上依次经过的城市的纵坐标Y = []#

初始化# Step 1:

随机⽣成所有城市的坐标 (city_x, city_y)# Step 2:

计算任意两城市之间的距离 (distance)

和能见度 (eta)# Step 3:

⽤贪婪算法得出初始路径# Step 4:

计算得出并记录所有路径的信息素浓度(tau)def init(): # ------------------------------------------- Step 1 #

遍历所有城市 for n in range(N): #

随机横坐标 x = t(0, L-1) #

随机纵坐标 y = t(0, H-1) #

记录城市 n

的横坐标 city_x[n] = x #

记录城市 n

的纵坐标 city_y[n] = y # ------------------------------------------- Step 2 #

从城市 i

出发 for i in range(N): #

到达城市 j

for j in range(N): #

城市 i

和城市 j

之间的距离 dij = (city_x[i] - city_x[j], 2) dij = (city_x[i] - city_x[j], 2) dij = dij + (city_y[i] - city_y[j], 2) dij = (dij) #

记录两城市之间的距离 distance[i][j] = dij #

计算能见度 #

如果 i

等于 j if i == j: #

城市到⾃⼰的能见度为 0 eta[i][j] = 0 else: #

两城市之间的能见度为两城市之间距离的倒数 eta[i][j] = 1 / dij # ------------------------------------------- Step 3 #

允许去的城市,

即未去过的城市 # 0:

不允许, 1:

允许 allow = [1 for n in range(N)] #

假设：从城市0出发 allow[0] = 0 #

路径 apath = [0] #

当前位置 apos = 0 #

下⼀步去的城市 acity = 0 #

与下⼀个城市的距离 away = 0 #

总路径长度 alen = 0 #

第 c

次去往下⼀个城市 for c in range(N-1): #

设置去往下⼀个城市的距离,

最⼤值 away = LH #

选择去往哪⼀个城市 for n in range(N): #

如果允许去城市 n if allow[n] == 1: #

如果去城市 n

的距离

⼩于

当前要去的城市的距离 if distance[apos][n] < away: #

更新要去的城市 acity = n #

更新要去的城市的距离 away = distance[apos][n] #

更新所在的位置 apos = acity #

更新路径 (apos) #

更新总路径长度 alen = alen + away #

更新允许去的城市 allow[apos] = 0 #

回到出发点 (0) #

更新总路径长度 alen = alen + distance[apos][0] #

添加初始路径长度 (alen) #

添加初始路径经过的城市 (py(apath)) # ------------------------------------------- Step 4 #

获得信息素的初始浓度值 tau0 = M / alen #

设置所有城市之间路径的信息素浓度 for i in range(N): for j in range(N): tau[i][j] = tau0 tau[i][j] = tau0 #

城市到本⾝⽆路径,

信息素浓度为 0 for n in range(N): tau[n][n] = 0#

多次迭代# Step 1:

第 t

次迭代# Step 2:

第 t

次迭代,

初始化:

所有蚂蚁 (m)

的路径 (path[m][]),

出发城市 (path[m][0]),#

允许去的城市 (allowed[m][])

即本次迭代中未去过的城市# Step 3:

第 t

次迭代,

第 c

次选择下⼀个城市# Step 4:

第 t

次迭代,

第 c

次选择下⼀个城市,

第 m

只蚂蚁选择下⼀个城市# Step 5:

第 t, c, m

中,

初始化：估值函数 pij[0][],#

估值的概率占⽐ pij[1][],#

⽐例选择时的概率点 pij[2][]# Step 6:

第 t, c, m

中,

获得蚂蚁 m

的允许去的城市 cho = []# Step 7:

第 t, c, m

中,

计算蚂蚁 m

去城市 n

的

估值函数# Step 8:

第 t, c, m

中,

计算蚂蚁 m

去城市 n

的

估值函数值

在所有估值函数值之和的占⽐# Step 9:

第 t, c, m

中,

计算⽐例选择 (轮盘赌)

时,

去城市 n

还是城市 n+1

的概率选择点# Step 10:

第 t, c, m

中,

模仿轮盘赌,

随机⽐例选择# Step 11:

第 t

次迭代,

所有蚂蚁回到出发城市,

形成⼀条⾸尾相连的路径# Step 12:

第 t

次迭代,

计算所有蚂蚁 (m)

的路径长度 (mplen[m]),

途经城市 (taumnn[m][][])# Step 13:

第 t

次迭代,

更新路径 (tau[i][j])

的信息素 (蒸发剩下的 +

新留下的)# Step 14:

第 t

次迭代,

选出所有蚂蚁 (m)

路径长度 (mplen[m])

中的最短路径长度# Step 15:

第 t

次迭代,

判断是否出现⽐全局最短路径更短的本次迭代最短路径,

并更新def iteration(): # ------------------------------------------- Step 1 #

第 t

次迭代 for t in range(1, T+1): # --------------------------------------- Step 2 #

所有蚂蚁的路径 path = [[] for m in range(M)] #

蚂蚁 m

从

城市 m

出发 for m in range(M): path[m].append(m) #

蚂蚁允许去的城市 allowed = [[0 if i == j else 1 for j in range(N)]for i in range(N)] #

第 c

次去往下⼀个城市,

除了出发城市,

有 N-1

个城市 # --------------------------------------- Step 3 for c in range(N-1): # ----------------------------------- Step 4 #

第 m

只蚂蚁选择下⼀个城市 for m in range(M): # ------------------------------- Step 5 #

估值函数,

估值的概率占⽐,

⽐例选择时的概率点 pij = [[0 for j in range(N)] for i in range(3)] #

去往的下⼀个城市的编号 city = 0 #

在第 c

次选择城市时,

可选城市的编号 # ------------------------------- Step 6 cho = [] #

判断城市 n

是否可选 for n in range(N): #

如果可选 if allowed[m][n] == 1: #

添加⼊ cho (n) # ------------------------------- step 7 #

遍历所有可去城市 for n in cho: #

蚂蚁 m

所处的当前城市 x = path[m][-1] #

蚂蚁 m

下⼀步去从城市 n

的概率 pij[0][n] = (tau[x][n], alpha) pij[0][n] = pij[0][n] * (eta[x][n], beta) # -------------------------------step 8 # -------------------------------step 8 #

求和 p1 = sum(pij[0]) #

归⼀化 for n in cho: #

蚂蚁 m

去从城市 n

的概率

占

所有概率之和的⽐例 pij[1][n] = pij[0][n] / p1 # ------------------------------- Step 9 #

⽐例选择法（轮盘赌法）的第⼀个概率点 p2 = 0 #

遍历所有可去城市 for n in cho: #

获得所有概率点 pij[2][n] = p2 + pij[1][n] p2 = pij[2][n] # ------------------------------- Step 10 #

模仿轮盘,

随机选择 rand = () #

遍历所有可去城市 for n in cho: #

如果概率点落在去城市 n

的扇⾯内 if pij[2][n] > rand: #

则去城市 n city = n #

结束遍历 break #

更新路径 path[m].append(city) #

更新允许去的城市 allowed[m][city] = 0 # --------------------------------------- Step 11 #

回到出发城市 for m in range(M): #

添加路径 path[m].append(m) # --------------------------------------- Step 12 #

所有蚂蚁⾛完所有城市的路径长度 mplen = [] #

蚂蚁 m

是否经过城市 i

到城市 j

的路径,

留下信息素 taumnn = [] #

遍历所有蚂蚁 for m in range(M): #

初始设置:

蚂蚁 m

没有经过城市 i

到城市 j

的路径 taunn = [[0 for i in range(N)] for j in range(N)] #

总路径长度为 0 plen = 0 #

遍历蚂蚁 m

经过的城市 for p in range(N): #

出发城市 x = path[m][p] #

到达城市 y = path[m][p+1] #

更新路径长度 plen = plen + distance[x][y] #

在城市 x

到城市 y

的路径上留下信息素 taunn[x][y] = 1 #

更新所有蚂蚁的路径总长度的列表 (plen) #

更新所有蚂蚁留下信息素的路径列表 (py(taunn)) # --------------------------------------- Step 13 #

城市 i

出发 for i in range(N): #

到达城市 j for j in range(N): #

蚂蚁留下的信息素 #

蚂蚁留下的信息素 taumij = 0 #

遍历所有蚂蚁留下信息素的路径 for m in range(M): #

如果蚂蚁 m

在城市 i

到城市 j

的路径上留下信息素 if taumnn[m][i][j] == 1: #

更新该段路径留下的的信息素之和 taumij = taumij + 1 / mplen[m] #

更新该路径的信息素（蒸发剩下的 +

新留下的） tau[i][j] = (1-rho) * tau[i][j] + taumij # --------------------------------------- Step 14 #

路径总长度的最⼤值

⼩于

对⾓线长度的城市个数倍 pathlent = LH * N #

蚂蚁 ant

在本次迭代中⾛的路径最短 ant = 0 #

遍历所有蚂蚁 for m in range(M): #

如果蚂蚁 m

⾛的路径长度

⼩于

本次迭代的最短路径 if mplen[m] < pathlent: #

更新最短路径 pathlent = mplen[m] #

更新蚂蚁编号 ant = m #

添加本次迭代的最短路径 (pathlent) #

添加本次迭代的最短路径经过的城市 (py(path[ant])) # --------------------------------------- Step 15 #

判断是否出现⽐全局最短路径更短的本次迭代最短路径 if pathlent < pathLen[best[0]]: #

更新全局最短路径的编号 best[0] = len(pathLen)

#

展⽰结果# Step 1:

输出

每次迭代的最短路径长度# Step 2:

输出

全局最短路径长度

及其

⾸次出现

的

迭代次数# Step 3:

可视化展⽰

所有城市

的

位置# Step 4:

可视化展⽰

全局最短路径# Step 5:

可视化展⽰

每次迭代的最短路径长度

的变化趋势def showResult(): # ------------------------------------------- Step 1 #

遍历所有的迭代结果 for t in range(T+1): #

输出 t

次迭代的最短路径长度 print("{0:>3} {1:>16}".format(t, pathLen[t])) # ------------------------------------------- Step 2 #

输出全局最短路径及其长度,

⾸次出现的迭代次数 print("n全局最短路径: ", pathCity[best[0]], " 长度: ", pathLen[best[0]]) print("⾸次出现在第 ", best[0], "次迭代") # ------------------------------------------- Step 3 #

画布 () #

⼦图 1 t(2, 1, 1) #

散点图展⽰所有城市的位置 r(city_x, city_y, color='b') #

遍历所有城市 for n in range(N): #

城市 n

的坐标信息 msg = "({},{})".format(city_x[n], city_y[n]) #

需标注的城市的坐标 x = city_x[n] y = city_y[n] #

⽂本标注的位置 #

⽂本标注的位置 xt = x + 0.5 yt = y + 0.5 #

标注 te(msg, xy=(x,y), xytext=(xt,yt)) # ------------------------------------------- Step 4 #

遍历全局最短路径经过的城市 for p in pathCity[best[0]]: #

横坐标 (city_x[p]) #

纵坐标 (city_y[p]) #

折线图展⽰:

全局最短路径 (X, Y, color='c') # x

轴标签 ("city_x") # y

轴标签 ("city_y") #

标题 ("Global shortest path") #

添加⽹格线 () # ------------------------------------------- Step 5 #

⼦图 2 t(2, 1, 2) #

折线图展⽰:

每次迭代路径最短长度的变化趋势 ([t for t in range(T+1)], pathLen) # x

轴标签 ("T iteration") # y

轴标签 ("The shortest length") #

标题 ("Changing trend") #

展⽰输出 ()# ********************

程序开始 *********************print("START !")#

初始化init()#

多次迭代iteration()#

展⽰结果showResult()# ********************

程序结束 *********************print("END !")留⾔提出不⾜之处，后续改进，感谢⽀持如果有你要的内容，给个赞吧！