蚁群算法在旅行商问题的应用

Applying Ant Colony Optimisation to the Travelling Salesman Problem

problem description

旅行推销员问题：如果旅行推销员希望精确访问一次m个城市列表中的每个城市（其中，从城市i到城市j的旅行成本为cij），然后返回到本国城市，可能的最短路径是多少。

Algorithm

Ant Colony Optimization

ACO算法基于蚂蚁的行为，尝试寻找两点之间的最佳路径。

这是通过发送大量蚂蚁波来遍历图形来实现的。第一波蚂蚁随机地或基于一种简单的启发式方法（例如从任何节点走最短路径）遍历该图。

然后，信息素会沿着成功的路径分布，那些通过评分函数确定为相对较好的路径将接收更多量的信息素。然后，将进一步的蚂蚁发送出去遍历图，同时考虑信息素的水平和启发式，然后再次将信息素放置在与路径得分成比例的路径上。

这样，最优化的路径将累积最多量的信息素，并且更有可能被后代的蚂蚁选择。

Implementation

迭代阶段涉及迭代一定数量的世代，并在每次迭代中执行以下操作：

1. 为每个蚂蚁生成一条路线。该路线由以下步骤生成：
   
   a. 随机选择一个起点
   
   b. 根据信息素图和启发式因素的组合选择下一个要访问的位置。具体来说，使用以下公式为每个未访问的位置评分：
   𝑠𝑐𝑜𝑟𝑒 = 𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒𝛼**α ∗ ℎ𝑒𝑢𝑟𝑖𝑠𝑡𝑖𝑐**β 同时: 𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = 从当前位置到未访问位置的路径上的信息素数量。
   
   α = 信息素权重影响的比例因子。
   
   ℎ𝑒𝑢𝑟𝑖𝑠𝑡𝑖𝑐 = 从当前位置到未访问位置的启发式值（在此解决方案中为1 /距离）。
   
   β = 启发值权重影响的比例因子.
   
   c. 将下一个位置添加到路线并将其从未访问位置列表中删除。
   
2. 根据行进的总距离对路线进行评分。 (cost= fun.decodingFun(RouteData,popsize,dmat,N))
   
3. 当找到更好的路线，将bestsolution更新
   
4. 将分数标准化到 [100, 200]。
   
5. 生成信息素图，以沿着蚂蚁的路线分布。该值由路径上每条路径的信息素𝑞 / 𝑠𝑐𝑎𝑙𝑒𝑑 𝑠𝑐𝑜𝑟𝑒决定，其中q是某个比例因子
   
6. 衰减现有信息素并使用以下公式添加所需的新信息素：
   𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = 𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 ∗ (1 − ⍴) + 𝑛𝑒𝑤𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒(Tau=Tau*(1-rho)+detaTau)
𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = 更新后的信息素值
   𝑐𝑢𝑟𝑟𝑒𝑛𝑡𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = 在这条路线上现有的信息素值
   ⍴ =信息素衰减因子.
   𝑛𝑒𝑤𝑃ℎ𝑒𝑟𝑜𝑚𝑜𝑛𝑒 = 根据路线分数添加的信息素.
   

>

所有迭代完成后， 将会得到：

1. 最优路线
2. 每次迭代的最优分数
3. 在每次迭代中所有路线分数的总和

Sample Result:

预设值

MaxGen=100 #Iteration
popsize=20 #population of ants
alpha=4 #α
beta=1 #β
rho=0.5 #ρ
Q=5 #q