import random
# import matplotlib.pyplot as plt # 画图用具
# plt.rcParams['font.sans-serif'] = ['SimSun'] # 图上出现的中文也好用
N = 4 # 城市数量
M = 4 # 蚂蚁数量
Q = 10 # 信息素浓度
T = 10 # 迭代次数
a = 2 # 信息素启发因子
b = 1 # 启发因子
r = 0.3 # 挥发因子
path = [[0, 3, 6, 7], [5, 0, 2, 3], [6, 4, 0, 2], [3, 7, 5, 0]] # 路径向量
tal = [[0, Q, Q, Q], [Q, 0, Q, Q], [Q, Q, 0, Q], [Q, Q, Q, 0]] # 信息素浓度矩阵
result = [[] for c in range(T)] # 每次迭代的最短爬行路径
mint = 0 # 记录最短路径的那一次迭代的索引
minr = [0 for c in range(T)] # 记录每一轮最短路径和 / y轴初始数据集
for t in range(T): # 迭代
arriving = [[] for c in range(M)] # 该轮M个蚂蚁的初始路径列表
for i in range(M): # 每一只蚂蚁开始找路
city = []
for c in range(N): # 把城市添加到该轮的city列表
city.append(c)
city.remove(i) # 蚂蚁从第i个城市开始，删除i
arriving[i].append(i) # 第i只蚂蚁的到达队列中添加该城市
s = i # s表示开始城市是i
while len(city) > 0: # city一开始是4个城市，第一个开始减一，一直到城市都走完
p = [0 for c in range(N)] # 选择每个城市概率的分子函数
sump = 0.0 # 留作分母用
for j in city: # 剩下城市里按照概率选择
# 路径越短 概率应该越高，所以用1 / path[s][j]
p[j] = (tal[s][j] ** a) * ((1 / path[s][j]) ** b) # 第j个城市被选择的概率的分子
sump += (tal[s][j] ** a) * ((1 / path[s][j]) ** b) # 所有城市的分子函数加在一起是分母函数
x = random.random() # 随即生成一个概率（0-1之间）
lower = 0 # 开始轮盘赌，先从0数值位置开始，分第一个城市的概率
for j in city: # 遍历每个城市的概率设计轮盘
p[j] = p[j] / sump # 第j个城市被选中的概率（对应的分子比分母）
upper = lower + p[j] # 该城市在轮盘上的上限数值
if lower <= x < upper: # 如果随机数落在这个城市的的概率范围内，就选择他作为下一个要走的城市
arriving[i].append(j) # 将城市添加到这只蚂蚁的到达队列
city.remove(j) # 城市移除
s = j # 城市从j开始了
break # 堵上了，跳出循环，开始寻找下一个城市
lower = upper # 这个城市没选上，准备设计下一个城市的轮盘
arriving[i].append(i) # 因为遍历完每一个城市，还要返回起点，所以再把起点加进去
# 所有的蚂蚁，都走完了自己的路径，信息素更新
for i in range(N):
for j in range(N):
tal[i][j] = tal[i][j] * (1 - r) # i城市到j城市路径上的信息素更新
minp = [0 for i in range(M)] # 这一轮迭代中，看看哪只蚂蚁走过的路径最短（最优解）
mini = 0 # 走出来最优解的蚂蚁的索引
for i in range(M): # 看看蚂蚁们都是怎么走的
for j in range(len(arriving[i]) - 1): # 看看蚂蚁走的城市
x1 = arriving[i][j] # 蚂蚁i走过的第j个城市
x2 = arriving[i][j + 1] # 蚂蚁i走过的第j+1个城市
tal[x1][x2] += Q / path[x1][x2] # 这两个城市之间路径上的信息素增加
minp[i] += path[x1][x2] # 算蚂蚁i走出来的解
if minp[i] < minp[mini]: # 蚂蚁i走出来的解是不是最好的？
mini = i # 是就更新，不是就还是之前的
print(arriving) # 打印看看该轮迭代蚂蚁们都是怎么走的
result[t] += arriving[mini] # 第t轮迭代的最优蚂蚁
minr[t] = minp[mini] # 第t轮迭代的最短路径值
if minr[t] < minr[mint]: # 轮次t的解是不是最好的解？
mint = t # 是就更新，不是就还是之前的
print(result[mint]) # 打印整个T轮下来的最短路径
# x = range(1, T+1) # x轴范围
# plt.plot(x, minr, label="蚁群算法", color="blue", line, marker="s", markersize=4)
# plt.ylim(0, 20) # 设定y轴显示的区间
# plt.xlim(0, T + 1) # 设定x轴显示的区间
# plt.xlabel("迭代次数")
# plt.ylabel("最短路径")
# xlabel = []
# for t in range(T):
# xlabel.append(t+1)
# plt.title("蚁群算法解决tsp问题的最短路径曲线")
# plt.grid(color='r', linestyle=':')
# plt.legend()
# plt.savefig("191491428zwx.pdf")
# plt.show()
思路全在代码里，非常好理解的蚁群算法。
