任务描述

本关任务：利用蚁群算法编写一个解决 TSP 问题的程序。

相关知识

为了完成本关任务，你需要掌握蚁群算法及其步骤。

蚁群算法简介

蚁群算法的基本原理来源于自然界蚂蚁觅食的最短路径原理，它是由意大利学者 Dorigo M 等人于 1991 年首先提出，并首先使用在解决 TSP （旅行商问题）上。之后，专家又系统研究了蚁群算法的基本原理和数学模型。根据昆虫学家的观察，发现自然界的蚂蚁虽然视觉不发达，但它可以在没有任何提示的情况下找到从食物源到巢穴的最短路径，并且能在环境发生变化（如原有路径上有了障碍物）后，自适应地搜索新的最佳路径。

经研究发现，蚁群觅食时，总存在信息素跟踪和信息素遗留两种行为，即一方面蚂蚁会按照一定的概率沿着信息素较强的路径觅食，另一方面，蚂蚁会在走过的路上释放信息素，使得在一定范围内的其他蚂蚁能够察觉到并由此影响它的行为。当一条路上的信息素越来越多，后来的蚂蚁选择这条路的概率也越来越大，从而进一步增加该路径的信息素强度，而其他路径上蚂蚁越来越少时，这条路径上的信息素会随着时间的推移逐渐减弱。这种选择过程称为蚂蚁的自催化过程，其原理是一种正反馈机制，所以蚂蚁系统也称为增强学习系统。

在蚁群算法中，蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。综上所述，算法基本原理如下：

1. 蚂蚁在路径上释放路径长度有关的信息素；
2. 路径较短的蚂蚁释放的信息素量较多。随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多；
3. 最优路径上的信息素浓度越来越大；
4. 整个蚂蚁会在正反馈的作用下集中到最佳的路径上，最终蚁群找到最优寻食路径。

蚁群算法路径构建与信息素更新

如何实现蚁群算法两个最重要的问题就是，如何实现单个蚂蚁寻路的过程以及如何实现信息素浓度的更新。

路径构建包括初始城市的选择和下一个到达城市的选择。每个蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆表，用来存放该蚂蚁依次经过的城市。

蚂蚁在构建路径的每一步中，按照轮盘赌法选择下一个要到达的城市。其中 t 时刻，蚂蚁 k 从 i 城市到 j 城市的转移概率是按照下列公式来进行计算的：

式中 α 和 β 是调节因子，用于调节τ_ij和 η_ij 之间的作用。此外 callowed _k表示蚂蚁 k 还没有走过的路径，这里采用禁忌表来存储已经走过的路径（禁忌表是用来防止搜索过程中出现循环，避免陷入局部最优的），通过这种存储可以保证所有解的逻辑可行。如果路径 i 到 j 上的信息浓度τ_ij(t) 的值越大，该路径被选择的概率也就越大；同样，如果该路径长度越短，则 ητ_i =1/dτ_ij 越大，该路径被选择的概率也越大。
其次就是信息素的更新。迭代过程中，问题空间中的所有路径上的信息素都会发生改变。其中第一部分是信息素的蒸发；然后，所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素，公式如下：

等式右边第一部分代表了信息素自身挥发后剩余的信息素，第二部分是每只蚂蚁经过路径(i,j)留下的信息素。

参数设置：

蚂蚁数目：10
信息素重要程度因子：1
启发函数重要程度因子：5
挥发速度：0.1
信息素释放总量：1
迭代次数：200

测试说明

平台会对你编写的代码进行测试， 最优值低于 160 即可通过测试。

预期输出1：

迭代次数： 200
蚁群算法的最优路径 [ 9. 8. 7. 17. 18. 23. 19. 21. 20. 22. 31. 30. 24. 6. 28. 1. 27. 29.

  2.  3. 12. 25.  4. 26. 14. 11.  5. 10. 13. 15. 16.]
蚁群算法求得最优解 159.85051311802158
路径长度符合要求

预期输出2：

迭代次数： 200
蚁群算法的最优路径 [ 5. 10. 13. 16. 15. 17. 18. 23. 19. 21. 20. 22. 31. 30. 24.  6. 28.  1.
 27. 29.  2.  3. 12. 25.  4. 26. 14. 11.  9.  8.  7.]
蚁群算法求得最优解 157.76584289194773
路径长度符合要求

参考资料

1.蚁群算法解决 TSP 问题
2.蚁群算法原理
3.蚁群算法实例

代码如下

student.py

import numpy as np
import math
import random
import time

# 31个城市的坐标
city_condition=[[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.0,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.0,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_count = 31
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

#适应度计算
def get_total_distance(path_new):
    distance = 0
    # ********** Begin **********#

    # ********** End **********#
    return distance
"""
两个难点
1.城市的选择：初始城市选择和下一个城市的选择设计
2.信息素的更新
"""
def main():
    ##参数设计
    # 蚂蚁数量
    AntCount = 10
    # 城市数量
    city_count = 31
    # 信息素
    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：蚂蚁初始点选择
        # ********** Begin **********#

        # ********** End **********#

        ## 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城市的信息素
                    # ********** Begin**********#

                    # ********** End **********#
                # 累计概率，轮盘赌选择
                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/当前蚂蚁行走的总距离的信息素
                # ********** Begin **********#

                # ********** End **********#
            #最后一个城市和第一个城市的信息素增加量
            changepheromonetable[candidate[i, j + 1]][candidate[i, 0]] += Q / length[i]
        #信息素更新的公式：

        # ********** Begin **********#

        # ********** End **********#
        iter += 1
    return distance_best,path_best,iteration

main.py

from student import *
if __name__ == '__main__':
    distance_best, path_best, iteration = main()
    print("迭代次数：", iteration)
    print("蚁群算法的最优路径", path_best[-1] + 1)
    print("蚁群算法求得最优解", distance_best[-1])
    if distance_best[-1] < 160:
        print("路径长度符合要求")
    else:
        print("路径长度太长")