蚁群算法解决旅行商问题

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)