蚁群算法解决TSP问题

import numpy as np import matplotlib.pyplot as plt import math import random matplotlib.rcParams['font.family'] = 'STSong'

city_name = [] city_condition = [] with open('30城市的坐标.txt','r',encoding='UTF-8') as f: lines = f.readlines()

for line in lines:
    line = line.split('

')[0] line = line.split(',') city_name.append(line[0]) city_condition.append([float(line[1]), float(line[2])])

city_condition = np.array(city_condition) 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

AntCount = 200 city_count = len(city_name) alpha = 1 beta = 2 rho = 0.1 iter = 0 MAX_iter = 200 Q = 1 pheromonetable = np.ones((city_count, city_count))*(1.0/city_count) #初始信息素矩阵为平均数 candidate = np.zeros((AntCount, city_count)).astype(int) path_best = np.zeros((MAX_iter, city_count)) distance_best = np.zeros( MAX_iter) etable = 1.0 / Distance

while iter < MAX_iter: # first：蚂蚁初始点选择 if AntCount <= city_count: candidate[:, 0] = np.random.permutation(range(city_count))[:AntCount]

else:
    m =AntCount -city_count
    n =2
    candidate[:city_count, 0] = np.random.permutation(range(city_count))[:]
    while m >city_count:
        candidate[city_count*(n -1):city_count*n, 0] = np.random.permutation(range(city_count))[:]
        m = m -city_count
        n = n + 1
    candidate[city_count*(n-1):AntCount,0] = np.random.permutation(range(city_count))[:m]
length = np.zeros(AntCount)#每次迭代的N个蚂蚁的距离值

# second：选择下一个城市选择
for i in range(AntCount):
    # 移除已经访问的第一个元素
    unvisit = list(range(city_count))
    visit = candidate[i, 0]
    unvisit.remove(visit)
    for j in range(1, city_count):
        protrans = np.zeros(len(unvisit))
        # 下一城市的概率函数
        for k in range(len(unvisit)):
            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() #在[0,1]区间内产生一个均匀分布的伪随机r；
        # 求出离随机数产生最近的索引值
        k = unvisit[list(cumsumprobtrans > 0).index(True)] #若q[1]-r>0，则选择个体1;index()返回查找对象的索引位置,此处返回q[1]-r>0为真的位置
        # 下一个访问城市的索引值
        candidate[i, j] = k
        unvisit.remove(k)
        length[i] += Distance[visit][k]
        visit = k
    length[i] += Distance[visit][candidate[i, 0]]

"""
更新路径等参数
"""
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

print("改进蚁群算法的最优路径",path_best[-1]+1) print("迭代", MAX_iter,"次后","改进蚁群算法求得最优解",distance_best[-1])

路线图绘制

fig = plt.figure() plt.title("Best roadmap") 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() plt.title("Distance iteration graph") plt.plot(range(1, len(distance_best) + 1), distance_best) plt.xlabel("Number of iterations") plt.ylabel("Distance value") plt.show()