蚁群优化解决经典的非对称旅行商问题

引言

旅行推销员问题（TSP）是计算机科学中一类优化问题，通过从一个非常大的离散解集中找到最佳解来解决。TSP 可以很容易地用一个推销员以最短距离访问 N 个城市的类比来描述。非对称一词意味着从 A 到 B 的距离可能与从 B 到 A 的距离不同。TSP 的概念可以应用于各种现实世界的应用，如网络路由、物流等（有关 TSP 的更多信息可以在 http://simple.wikipedia.org/wiki/Travelling_salesman_problem 找到）。

蚁群优化（ACO）是可用于解决旅行推销员问题的一种计算智能技术。ACO 的灵感来自蚂蚁（通过信息素）找到其蚁群和食物来源之间最短路径的能力。在这种计算技术中，我们通过系统地添加更小的子组件，以概率方式构建解决方案。然后根据元启发式评估构建的解决方案，并将评估结果作为反馈应用于下一次迭代。因此，在 N 次迭代中，通过前几次迭代的反馈，解决方案得到了改进。

在本文中，我解释了一个用于解决非对称旅行推销员问题的 ACO 的 python 实现。我使用的数据是常用的 ry48p 数据集。TSP 网站上发布的 ry48p 最佳解决方案是 14422，尽管我只达到了 15473。但考虑到算法的随机性，该算法甚至可以给出更好的解决方案。我还发布了为测试算法在不同参数值下的性能而进行的实验结果。所有实验结果都是通过 20 次试运行的平均值得出的。

背景

蚁群优化最早由 Dorigo 于 1992 年提出，因此与其他计算智能技术相比，它是一种相对较新的技术。对蚂蚁进行了真实生活研究，以研究它们的物流行为。Deneubourg 在其关于双桥实验的论文中发表了一篇文章，描述了蚂蚁的这些特征。该实验最初是使用阿根廷蚁的实验室蚁群进行的。已知这些蚂蚁在离开和返回巢穴时都会留下信息素。实验结果发现，蚂蚁利用其信息素强度作为与其他蚂蚁交流其巢穴和食物来源之间最短可能距离的手段。

Using the Code

源代码可在以下网址下载： https://aco-travelling-salesman.googlecode.com/files/aco-travelling-salesman.zip

算法使用以下参数初始化

• Ant_count：将探索种群的蚂蚁数量
• Iterations：蚂蚁寻找解决方案的代数
• PheromoneConstant：根据其旅行长度计算单个蚂蚁施加的信息素强度时用作常数的足够值
• DecayConstant：信息素在路径中衰减的强度
• Alpha：寻找下一个城市时的信息素强度
• Beta：寻找下一个城市时的启发式强度
• Initialization：如何初始化第一个种群，是随机还是从特定城市开始

# Algorithm paramters
ant_count = 10
iterations = 500
PheromoneConstant = 1.0
DecayConstant = 0.2
Alpha = 1   # Pheromone constant
Beta = 1   # Heuristic constant

RANDOM = 1
CITY0 = 0 
initialization = RANDOM

函数 readTsp() 负责读取输入数据。目前，它解析包含标准 ry48p 格式数据的文本文件。此函数可以根据需要轻松修改，以读取任何格式的数据。

def readTsp():
   pathmatrix = []
   tspfile = open('tsp_matrix.atsp', 'r')
   for cities in range(48):
      city = []

      line1 = tspfile.readline()
      for node in line1.split():
         city.append(int(node.strip()))

      line1 = tspfile.readline()
      for node in line1.split():
         city.append(int(node.strip()))

      line1 = tspfile.readline()
      for node in line1.split():
         city.append(int(node.strip()))

      line1 = tspfile.readline()
      for node in line1.split():
         city.append(int(node.strip()))
      
      pathmatrix.append(city)
return pathmatrix

算法的核心功能编码在方法“def shortestPath(cities_matrix, ant_count, iterations)”中。在内部 for 循环中，蚁群中的每只蚂蚁根据启发式和信息素强度找到图中下一个可用的节点。所有蚂蚁移动到下一个可用节点后，会更新遍历路径上的信息素。外部 while 循环现在将迭代重复相同的过程，直到所有蚂蚁都到达目的地。一旦所有蚂蚁都到达目的地，最外层的 for 循环将根据算法参数中指定的迭代次数进行迭代。结果取自每次迭代的最佳解决方案。

for iteration in range(iterations):

   # Initialize ants with a random city
   paths = initialize_ants(ant_count,cities_count)

   while not isAllCompletedTour(paths,cities_count):   # End iteration when all ants have completed the tour
      # For each ant in the colony
      for ant in range(ant_count):   

         # Termination criteria
         if len(paths[ant]) < cities_count:
               
            paths[ant].append(nextCity(cities_matrix, pheromone_trail,paths[ant]))   # Find next town

   # After all ants have completed the tour - Update pheromone
   updatePheromone(pheromone_trail, paths,cities_matrix)
   (globalBest,path) = iterationResult(iteration,paths,cities_matrix,(globalBest,path))

关注点

进行了以下实验，以测试算法在不同参数值下的性能。所有实验结果都是通过 20 次试运行的平均值得出的。

实验 1：最佳蚁群数量和迭代次数

文献中没有明确的值建议蚁群数量和迭代次数的正确值。因此，我进行了一项实验，以测试蚁群数量和迭代次数的最佳组合。用于 ant_count 的值列表是 1, 10, 50, 100, 150, 200。用于迭代次数的值列表是 10, 50, 100, 250, 500, 1000。对列表中的所有 36 种组合进行了实验，并将实验中有趣的值单独绘制在图 1 中。

从图 1 可以看出，随着蚁群数量的增加，算法的性能更好。单只蚂蚁当然无法收敛到任何更好的解决方案，但它会随机探索搜索空间并给出随机解决方案。随着蚁群数量的增加，算法肯定会趋于收敛。当蚁群数量为 10 时，它在大约 70 处收敛；当蚁群数量为 50 时，它在大约 20 处收敛。当进一步将蚁群数量增加到 100 和 200 时，在大约 10 次迭代时实现收敛，在这种情况下，可能不值得考虑任何大的蚁群数量。

关于迭代次数，从图 1 可以看出，对于足够大的蚁群数量（50 及以上），收敛范围在 10 到 25 之间。仅仅增加迭代次数可以增加蚂蚁探索新随机解的概率，但收敛性将保持不变。

图 2a 和 2b 分别比较了蚁群数量和迭代次数这两个变量的计算开销。从这些图中可以看出，执行时间与变量成正比，并随变量线性增加。

图 2a。蚁群数量时间复杂度	图 2b。迭代次数复杂度

因此，考虑到蚁群数量和迭代次数的收敛性和执行时间分析，似乎 50 只蚂蚁运行 200 次迭代足以解决这个问题。

实验 2：衰减常数分析

本实验比较了算法在不同衰减常数值下的收敛时间。最初考虑了五个值用于分析衰减常数，它们是 0.01、0.25、0.5、0.75 和 1.0。结果如图 3 所示。衰减值为 1 意味着不保留任何先前的值，只使用第 n-1 轮信息素。

正如我们所见，衰减常数为 1.0 需要很长时间才能改进结果。另一方面，衰减常数为 0.01 意味着蒸发非常少，因此搜索空间中的探索也较少。从趋势来看，最佳值似乎是 0.25，因为它显示出合理的利用（逐渐改进）以及偶尔的探索（波动）。

实验 3：信息素常数分析

本实验比较了算法在不同信息素常数值下的收敛时间。用于分析信息素常数的五个值为 0.01、1、10、100、1000。从图 4 可以清楚地看出，较高的信息素常数 100 和 1000 会导致更快的收敛。这主要是因为增加信息素常数将间接增加路径中的信息素强度，从而导致收敛。

实验 4：Alpha Beta 分析

Alpha 控制选择路径时信息素的强度，而 Beta 控制选择路径时启发式的强度。从图 5 可以看出，高 Alpha 值和低 Beta 值的趋势比低 Alpha 值和高 Beta 值的趋势显示出更好的收敛性。

历史

• 2014 年 12 月 20 日：初始版本