蚁群算法

蚁群算法 Ant Colony Optimization（ACO）是一种用来寻找优化路径的概率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。

蚂蚁集体寻食行为

当蚂蚁在通往食物的路上面临选择（有一条路会比另外的更短），他们的选择完全是随机的。但是那些通过更短的路更快找到食物的蚂蚁，他们会更多地选择从这条路通过

人工蚂蚁代表受实际蚂蚁行为启发的多智能体方法。 基于信息素的蚂蚁交流通常是主要被考虑的蚂蚁行为。人工蚂蚁和局部搜索算法的结合已成为众多优化任务的一种选择方法，这些优化任务涉及某种图形，例如车辆路线 Vehicle routing 和互联网路线 Iinternet routing。 该领域蓬勃发展：在学术界，许多专门针对蚁群算法的会议吸引大量学者参与到蚁群算法的讨论；在商业界，诸如AntOptima之类的专门公司把蚁群算法应用到商业实战中，充分发挥蚁群算法的市场价值。

在群体智能方法中，该算法是蚁群算法家族的成员，它构成了一些元启发式优化。 Marco Dorigo最初于1992年在其博士学位论文中提出，这种算法旨在根据蚂蚁在蚁穴和食物来源之间寻找路径的行为来在图中寻找最佳路径。

这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是进化算法中的一种启发式全局优化算法。

背景

算法起源

• 蚁群系统 Ant System 是由意大利学者Dorigo、Maniezzo等人于1991年首先提出来的，用于解决TSP问题。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。

这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为 “信息素 pheromone” 的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

• 1995年Gramdardella和Dorigo提出Ant-Q算法，建立了AS和Q-learning的联系；
• 1996年又提出Ant Colony System；
• 1997年又提出Max-Min Ant System；
• 1996年Dorigo等人把先前各种算法归结为Ant Colony Optimization meta-heuristic的统一框架下，给出抽象而规范的算法描述；

算法原理

• 蚂蚁在运动过程中，能够在它所经过的路径上留下外激素，并且可以再运动过程中感知外激素的存在和强度，并且以此指导自己的运动方向——外激素强度越高蚂蚁选择走该路径的概率就越大；

• 由大量蚂蚁组成的一群的集体行为便表现出一种信息正反馈现象：从某一路径上走过的蚂蚁越多，那么后来者选择该路径的概率就越大。蚂蚁个体之间就是通过这种信息的交流达到搜索食物的目的。

简化版蚂蚁寻食过程

假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时，ABD路线往返了2趟，每一处的信息素为4个单位，而ACD的路线上往返了一趟，每一处的信息素为2个单位，其比值为2 : 1。

然后，蚂蚁继续寻找食物，按照信息素指导，蚂蚁在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然有一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3 : 1。

若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁，再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4 : 1。

继续进行，按照信息素指导，最终所有的蚂蚁都会放弃ACD路线，而都选择ABD路线，即正反馈效应。

人工蚁群算法

基于以上一群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题（如TSP问题）。

蚁群觅食	蚁群优化算法
蚁群	搜索空间的一组有效解（表现为种群规模N）
信息素	信息素浓度变量
蚁巢到食物的一条路径	一个有效解
找到的最短路径	问题的最优解

算法内容

基本思想

1. 根据具体问题设置多只蚂蚁，分头并行搜索。
2. 每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。
3. 蚂蚁路径的选择根据信息素强度大小（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。
4. 每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。
5. 所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。
6. 更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。
7. 达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。

总结后的要点即为 1. 状态转移 2. 信息素更新

基本蚁群算法原理推导

定义算法的关键参数如下：

[math]\displaystyle{ {m} }[/math] ：蚂蚁数量

[math]\displaystyle{ {M} }[/math] ：城市数量

[math]\displaystyle{ {\rho} }[/math] ：信息素挥发因子，表示信息素的持久度，推荐值为[0,1]

[math]\displaystyle{ {Q} }[/math] ：常量，表示信息素浓度

[math]\displaystyle{ {L_k} }[/math] ：表示第k只蚂蚁在本次迭代中路程的代价

[math]\displaystyle{ {\alpha} }[/math] ：信息素启发因子，表示在搜索中，信息量的相对重要程度

[math]\displaystyle{ {\beta} }[/math] ：期望启发因子，表示在搜索中，启发式信息的相对重要程度

一般：

[math]\displaystyle{ {m=1.5\times M} }[/math]

[math]\displaystyle{ {\rho \in [0.2,0.5] } }[/math]

[math]\displaystyle{ {Q \in [10,100] } }[/math]

[math]\displaystyle{ {\alpha \in [0,5] } }[/math]

[math]\displaystyle{ {\beta \in [0,5] } }[/math]

设第[math]\displaystyle{ {k} }[/math]只蚂蚁现在城市[math]\displaystyle{ {i} }[/math]，城市[math]\displaystyle{ {i} }[/math] 到[math]\displaystyle{ {j} }[/math]，[math]\displaystyle{ {j \in [1, M] } }[/math] 的距离为[math]\displaystyle{ {d_{ij}} }[/math]，从城市[math]\displaystyle{ {i} }[/math] 到[math]\displaystyle{ {j} }[/math]的信息素浓度为[math]\displaystyle{ {\rho_{ij}} }[/math]。当蚂蚁[math]\displaystyle{ {k} }[/math]选择下一个将要前往的城市时，则根据各城市距离和信息素计算前往该城市的概率为：

[math]\displaystyle{ {q_{ij}=p_{ij}^{\alpha}\times ({\frac{1}{d_{i,j}})}^{\beta}} }[/math]

当蚂蚁k走完所有的城市，就得出了一条对应的搜索路径，先更新信息素浓度：

[math]\displaystyle{ {p_{ij}=\rho*p_{i,j}+\frac{Q}{sum}} }[/math]

其中sum为每一个蚂蚁走过的距离之和。 然后将该搜索路径和其他蚂蚁对比，选择长度最短的那个蚂蚁，作为“最优蚂蚁”路径查找结果，本轮迭代结束，进入下一轮。

算法流程图

下面给出蚁群算法的算法流程图：

ACO蚁群算法流程图“CSDN——ACO 蚁群算法”，其中初始化和其他群算法一致，唯一区别在于，蚁群算法的位置更新根据上述计算的概率进行选择。

蚁群算法程序实现

程序基本信息

• 作者：张江
• 源代码：蚁群算法代码压缩包Antcolony.zip

蚁迹寻踪

程序运行说明

• 配置说明：

浏览器支持java applet，且能正常加载此程序

• 程序运行描述：

按开始按钮，蚂蚁们开始从窝里出动了，寻找食物；他们会顺着地形爬满整个画面，直到找到食物再返回。

浅蓝色的点表示食物，黄色的点表示窝，雾状的点表示蚂蚁留下的信息素，红色的点表示障碍物，白色的动点就是蚂蚁了。

按设置按钮你可以更改一些环境变量，也可以更改单个蚂蚁的属性。

在设置参数窗口中显示了整个蚂蚁群中找到的从它的窝到食物的最短路径。

使用环境参数设置和个体蚂蚁的设置可以让你观察到这些参数是怎样影响蚂蚁的行为的。其中信息素的大小和消散的快慢直接决定了蚂蚁找到食物的快慢。（具体见后面的参数说明）

编辑地图让你能够随心所欲的更改蚂蚁的环境，并且无论你怎样精心巧妙的设计地图，小蚂蚁最终都能找到食物！地图库如下，它可以自动调出不同的地图。

预期的结果

各个蚂蚁在没有事先告诉他们食物在什么地方的前提下开始寻找食物。当一只找到食物以后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，这样越来越多的蚂蚁会找到食物！有些蚂蚁并没有象其它蚂蚁一样总重复同样的路，他们会另辟蹊径，如果新开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复着。

具体原理解释

为什么小小的蚂蚁能够找到食物？他们具有智能么？设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！太复杂了，恐怕没人能够完成这样繁琐冗余的程序。

然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！下面对这个简单规则详细说明：

1. 范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径VR（一般是3），那么它能观察到的范围就是VR*VR个方格世界，并且能移动的距离也在这个范围之内。
2. 环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
3. 觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
4. 移动规则： 每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。
5. 避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。
6. 播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。

问题剖析

说了这么多，蚂蚁究竟是怎么找到食物的呢？ 在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食物。

当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。

蚂蚁如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的。为什么呢？这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸引过来。

蚁迹寻踪

上图说明了这个过程，从a出发到e有两条路，左边的较长，右边的较短，在这两个图中，开始的时候（左图）蚂蚁选择两条路的机会是均等的，当时间流逝以后（右图所示），更多的蚂蚁聚集到右边的较短的路上来。

引申

通过上面的原理叙述和实际操作，我们不难发现蚂蚁之所以具有智能行为，完全归功于它的简单行为规则，而这些规则综合起来具有下面两个方面的特点：

1. 多样性
2. 正反馈

多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。

引申来讲，大自然的进化，社会的进步、人类的创新实际上都离不开这两样东西，多样性保证了系统的创新能力，正反馈保证了优良特性能够得到强化，两者要恰到好处的结合。如果多样性过剩，也就是系统过于活跃，这相当于蚂蚁会过多的随机运动，它就会陷入混沌状态；而相反，多样性不够，正反馈机制过强，那么系统就好比一潭死水。这在蚁群中来讲就表现为，蚂蚁的行为过于僵硬，当环境变化了，蚂蚁群仍然不能适当的调整。

参数说明

• 最大信息素：蚂蚁在一开始拥有的信息素总量，越大表示程序在较长一段时间能够存在信息素。
• 食物释放信息素的半径：在食物点和窝点附近都会释放相应的信息素以便蚂蚁能更快的找到它们。这个半径越大，则越容易被蚂蚁找到。
• 信息素消减的速度：随着时间的流逝，已经存在于世界上的信息素会消减，这个数值越大，那么消减的越快。

参数修改说明

• 在设置蚂蚁个体属性的时候，选择特定的蚂蚁编号，可以对这只蚂蚁的属性进行修改。
• 错误概率表示这个蚂蚁不往信息素最大的区域走的概率，越大则表示这个蚂蚁越有创新性。
• 速度半径表示蚂蚁一次能走的最大长度，也表示这个蚂蚁的感知范围。
• 记忆能力表示蚂蚁能记住多少个刚刚走过点的坐标，这个值避免了蚂蚁在本地打转，停滞不前。而这个值越大那么整个系统运行速度就慢，越小则蚂蚁越容易原地转圈。
• 按钮（应用于所有蚂蚁）：是把当前更改的所有蚂蚁的个体属性应用到所有的蚂蚁身上。

算法应用——以TSP问题为例

蚁群算法具有鲁棒性强、全局搜索、并行分布式计算、易于其他问题结合等优点。近年来，蚁群算法应用领域不断扩张——从旅行商问题 Traveling Salesman Problem、指派问题、图着色问题 Graph Coloring Problem、网络路由问题 Network Routing Problem 到车间调度问题、车辆路径问题 Vehicle Routing Problem、分配问题等等，这些问题总结起来主要是NP难的组合优化问题，用传统算法难以求解或者无法求解。

下面以最经典的TSP问题为例，使用蚁群算法进行求解[1]。

问题说明

旅行商问题，即TSP问题 Traveling Salesman Problem 又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。 问题：假设有一个旅行商人要拜访N个城市（表示为有向图[math]\displaystyle{ {G = (N, A)} }[/math]，其中[math]\displaystyle{ {N = {1,2,\cdots,n}} }[/math]，[math]\displaystyle{ {A=\left \{ \right.(i,j)| i,j \in N\left. \right \}} }[/math]，城市之间距离 ），他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 目标函数为：

[math]\displaystyle{ {f(w)=\sum_{l=1}^{n} d_{i_{l-1} i_l'}} }[/math]

其中[math]\displaystyle{ {w=(i_1,i_2,\cdots, i_n)} }[/math] 为城市[math]\displaystyle{ {1,2,\cdots,n} }[/math]的一个排列，[math]\displaystyle{ {i_{n+1}=i_l} }[/math]。

蚁群算法思路

• TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而通过协作得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：信息素值和可见度（即先验值）；

• 信息素的更新方式有两种：一是挥发，也就是所有路径上的信息素以一定的比率减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值为正反馈（有蚂蚁走过）的边增加信息素；

• 蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所有节点存储的信息，计算出下一步可到达节点的概率，并按照此概率实现一步移动，按此循环，越来越接近最优解；

• 蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。

基本流程

主要分为两步：路径构建和信息素更新。

（1）路径构建

每个蚂蚁都随机选择一个城市作为其出发城市，并维护一个路径记忆向量，用来存放该蚂蚁依次经过的城市。蚂蚁在构建路径的每一步中，按照一个随机比例规则选择下一个要到达的城市。随机比例规则：

[math]\displaystyle{ {P_{ij}^k(t)=\begin{cases} \frac{{ \left [ \tau_{ij}(t) \right ]}^{\alpha}\times {\left [ \eta_{ij}(t) \right ]}^{\beta}}{\sum_{k\in allowed_k}{ \left [ \tau_{ij}(t) \right ]}^{\alpha}\times {\left [ \eta_{ij}(t) \right ]}^{\beta}} , & \text{if} \quad j \in allowed_k\\ 0 , & \text{others} \end{cases}} }[/math]

其中：

• [math]\displaystyle{ {i,j} }[/math]分别为起点和终点；
• [math]\displaystyle{ {\eta_{i,j}=\frac{1}{d_{ij}}} }[/math]为能见度，是两点路i，j距离的倒数；
• [math]\displaystyle{ {\tau_{i,j}(t)} }[/math] 为时间t时由 i 到 j 的信息素浓度；
• [math]\displaystyle{ {allowed_k} }[/math] 为尚未访问过的节点集合；
• [math]\displaystyle{ {\alpha} }[/math]和 [math]\displaystyle{ {\beta} }[/math] 为两常数，分别是信息素和能见度的加权值。

（2）信息素更新

• 初始化信息素浓度：[math]\displaystyle{ {\tau_{ij}(t)=C} }[/math]

注：如果[math]\displaystyle{ {C} }[/math]太小，算法容易早熟，蚂蚁会很快的全部集中到一条局部最优的路径上；相反，如果[math]\displaystyle{ {C} }[/math]太大，信息素对搜索方向的知道作用太低，也会影响算法性能。所以一般，[math]\displaystyle{ {C} }[/math]的取值为：

[math]\displaystyle{ {C=\frac{m}{C^{mn}}} }[/math]

• 浓度更新：为了模拟蚂蚁在较短路径上留下更多的信息素，当所有蚂蚁到达重点时，必须把各路径的信息素浓度重新更新一次，信息素的更新也分两个步骤：首先，每一轮过后，问题空间中的所有路径上的信息素都会发生蒸发；然后，所有的蚂蚁根据自己构建的路径长度在它们本轮经过的边上释放信息素。更新过程如下：

[math]\displaystyle{ {t_{ij}(t)=(1-\rho) \tau_{ij}+\sum_{k=1}^m \Delta \tau _{ij}^k } }[/math]

其中[math]\displaystyle{ {m} }[/math]为蚂蚁个数，[math]\displaystyle{ 0\lt \rho \leq 1 }[/math]为信息素的蒸发率（通常为0.5），为第[math]\displaystyle{ {k} }[/math]只蚂蚁在路径 [math]\displaystyle{ {i} }[/math] 到 [math]\displaystyle{ {j} }[/math] 所留下来的信息素，其中：

[math]\displaystyle{ {\Delta \tau _{ij}^k=\begin{cases} {(C_k)}^{-1} ,& \text{ if the } k^{th} \text{ant travers} (i,j) \\ 0 ,& \text{others} \end{cases}} }[/math]

[math]\displaystyle{ {C_k} }[/math]是第[math]\displaystyle{ {k} }[/math]只蚂蚁走完整条路径后所得到的总路径长度。

伪代码

--------------*Pseudocode code of ACO for TSP *-------------------------
   Procedre AS
      for each edge 
         set initial pheromone value t0
      end for 
      while not stop 
         for each ant k
            randomly choose an initial city
            for I=1 to n
              choose next city j with probability 
            end for 
         end for 
         compute the length Ck of the tour constructed by the nth ant 
         for each edge 
             update the pheromone value 
         end for 
      end while 
      print results 
   end procedure

举例

（1）问题——四个城市之间的TSP问题： 距离矩阵和城市图示如下：

（2）求解

设共有[math]\displaystyle{ {m=3} }[/math]只蚂蚁，参数[math]\displaystyle{ {\alpha=1, \beta=2,\rho=0.5} }[/math]

步骤1：初始化

先使用贪心法得到路径（ACDBA），则有：

[math]\displaystyle{ {C_{nm}=1+2+4+3=10} }[/math]

求得：

[math]\displaystyle{ {\tau_0=\frac{m}{C_{mn}}=0.3} }[/math]

[math]\displaystyle{ {\tau(0)=(\tau_{ij}(0))=\begin{pmatrix} 0 & 0.3 & 0.3 & 0.3 \\ 0.3 & 0 & 0.3 & 0.3 \\ 0.3 & 0.3 & 0 & 0.3\\ 0.3 & 0.3 & 0.3 & 0 \end{pmatrix}} }[/math]

步骤2：随机选择每个蚂蚁的出发城市

设蚂蚁1选择城市A，蚂蚁2选择城市B，蚂蚁3选择城市D。

步骤3.1：选择每个蚂蚁的下一访问城市

以蚂蚁1为例，当前城市[math]\displaystyle{ {i=A} }[/math]，可访问城市集合，计算蚂蚁1访问各个城市的概率：

[math]\displaystyle{ {A=\begin{cases} B: \tau_{AB}^{\alpha} \times \eta_{AB}^{\beta}=0.3^1\times (1/3)^2=0.033 \\ C: \tau_{AC}^{\alpha} \times \eta_{AC}^{\beta}=0.3^1\times(1/1)^2=0.300 \\ D: \tau_{AD}^{\alpha} \times \eta_{AD}^{\beta}=0.3^1 \times (1/3)^2=0.075 \end{cases}} }[/math]

[math]\displaystyle{ { \begin{array}{lcl} p(B) = 0.033/(0.033+0.3+0.075) = 0.018 \\ p(C) = 0.3/(0.033+0.3+0.075) = 0.74 \\ p(D) = 0.075/(0.033+0.3+0.075) = 0.18 \\ \end{array} } }[/math]

用轮盘赌法选择下一个访问城市。假设产生的随机数[math]\displaystyle{ {q=0.05} }[/math]，则蚂蚁1会选择城市B。同样，假设蚂蚁2选择城市D，蚂蚁3选择城市A。

步骤3.2：再选择每个蚂蚁的下一访问城市

同样，以蚂蚁1为例，当前城市[math]\displaystyle{ {i=B} }[/math]，路径记忆向量 [math]\displaystyle{ {R^t=(AB)} }[/math] ，可访问城市集合[math]\displaystyle{ {J_1(i)=\left [ C, D\right ]} }[/math] ，计算蚂蚁1访问C,D城市的概率：

[math]\displaystyle{ {B\Rightarrow \begin{cases} C: \tau_{BC}^{\alpha}\times \eta_{BC}^{\beta}=0.3^1\times {(1/5)}^2=0.012\\ D: \tau_{BD}^{\alpha}\times \eta_{BD}^{\beta}=0.3^1 \times {(1/4)}^2=0.019 \end{cases}} }[/math]

[math]\displaystyle{ { \begin{array}{lcl} p(C) = 0.012/(0.012+0.019) = 0.39 \\ p(D) = 0.019/(0.012+0.019) = 0.61 \\ \end{array} } }[/math]

用轮盘赌法选择下一个访问城市。假设产生的随机数q = 0.67，则蚂蚁1会选择城市D。同样，假设蚂蚁2选择城市C，蚂蚁3选择城市D。 至此，所有蚂蚁的路径均构造完毕——蚂蚁1：ABDCA，蚂蚁2：BDCAB，蚂蚁3：DACBD

步骤4：信息素更新

计算每只蚂蚁构建的路径长度：

[math]\displaystyle{ { \begin{array}{lcl} C1 = 3 + 4 + 2 + 1 = 10 \\ C2 = 4 + 2 + 1 + 3 = 10 \\ C3 = 2 + 1 + 5 + 4 = 12 \\ \end{array} } }[/math]

更新每条边上的信息素：

[math]\displaystyle{ { \begin{array} {lccl} \tau_{AB}=(1-\rho)\times \tau_{AB}+\sum_{k=1}^3\Delta \tau_{AB}^k=0.5\times 0.3 +(1/10+1/10)=0.35 \\ \tau_{AC}=(1-\rho)\times \tau_{AC}+\sum_{k=1}^3\Delta \tau_{AC}^k=0.5\times 0.3 +(1/12)=0.16\\ \cdots \end{array} } }[/math]

步骤5：如果满足条件，则输出全局最优结果并结束程序，否则转向步骤2继续执行。

解决TSP问题的Python 代码实现

先创建一个文件命名为MyFuncTool.py，在这里定义函数 GetData，主要用来提取数据：城市位置和城市间距离。定义函数ResultShow用来输出最后结果。函数draw用于最后画结果图[2]。

# -*- coding: utf-8 -*-
"""
	基于贪心算法的旅行商问题解法Python源码
	
	Author:	Greatpan
	Date:	2018.9.30
"""
import pandas
import numpy as np
import math
import matplotlib.pyplot as plt 

class Node:
	"""
		类名：Node
		类说明：	城市节点类
	"""
	def __init__(self,CityNum):
		"""
		函数名：GetData()
		函数功能：	从外界读取城市数据并处理
			输入	无
			输出	1 Position：各个城市的位置矩阵
				2 CityNum：城市数量
				3 Dist：城市间距离矩阵
		其他说明：无
		"""
		self.visited=[False]*CityNum    #记录城市是否走过
		self.start=0                    #起点城市
		self.end=0                      #目标城市
		self.current=0                  #当前所处城市
		self.num=0                      #走过的城市数量
		self.pathsum=0                  #走过的总路程
		self.lb=0                       #当前结点的下界
		self.listc=[]                   #记录依次走过的城市

def GetData(datapath):
	"""
	函数名：GetData()
	函数功能：	从外界读取城市数据并处理
		输入	无
		输出	1 Position：各个城市的位置矩阵
			2 CityNum：城市数量
			3 Dist：城市间距离矩阵
	其他说明：无
	"""
	dataframe = pandas.read_csv(datapath,sep=" ",header=None)
	Cities = dataframe.iloc[:,1:3]
	Position= np.array(Cities)				#从城市A到B的距离矩阵
	CityNum=Position.shape[0]				#CityNum:代表城市数量
	Dist = np.zeros((CityNum,CityNum))		#Dist(i,j)：城市i与城市j间的距离

	#计算距离矩阵
	for i in range(CityNum):
		for j in range(CityNum):
			if i==j:
				Dist[i,j] = math.inf
			else:
				Dist[i,j] = math.sqrt(np.sum((Position[i,:]-Position[j,:])**2))
	return Position,CityNum,Dist

def ResultShow(Min_Path,BestPath,CityNum,string):
	"""
		函数名：GetData()
		函数功能：	从外界读取城市数据并处理
			输入	无
			输出	1 Position：各个城市的位置矩阵
				2 CityNum：城市数量
				3 Dist：城市间距离矩阵
		其他说明：无
	"""
	print("基于"+string+"求得的旅行商最短路径为：")
	for m in range(CityNum):
		print(str(BestPath[m])+"—>",end="")
	print(BestPath[CityNum])
	print("总路径长为："+str(Min_Path))
	print()

def draw(BestPath,Position,title):
	"""
		函数名：draw(BestPath,Position,title)
		函数功能：	通过最优路径将旅行商依次经过的城市在图表上绘制出来
			输入	1 	BestPath：最优路径
				2	Position：各个城市的位置矩阵
				3	title:图表的标题
			输出	无
		其他说明：无
	"""
	plt.title(title) 
	plt.plot(Position[:,0],Position[:,1],'bo')
	for i,city in enumerate(Position): 
		plt.text(city[0], city[1], str(i)) 
	plt.plot(Position[BestPath, 0], Position[BestPath, 1], color='red') 
	plt.show()

这里开始代码的主要部分：

# -*- coding: utf-8 -*-
"""
	基于回溯法的旅行商问题解法Python源码
	
	Author:		Greatpan
	Date:		2018.10.10
"""

from MyFuncTool import GetData,ResultShow,draw
import time
import numpy as np

def ant():
	"""
		函数名：ant()
		函数功能：蚁群算法核心
		输入    1: 无
		输出    1: 无
		其他说明：无
	"""
	numant = 25          # 蚂蚁个数
	numcity = CityNum   # 城市个数
	alpha = 1           # 信息素重要程度因子
	rho = 0.1           # 信息素的挥发速度
	Q = 1
	
	iters = 0
	itermax = 500
	
	etatable = 1.0/(Dist+np.diag([1e10]*numcity))       # 启发函数矩阵，表示蚂蚁从城市i转移到矩阵j的期望程度
	pheromonetable  = np.ones((numcity,numcity))        # 信息素矩阵
	pathtable = np.zeros((numant,numcity)).astype(int)  # 路径记录表
	
	lengthaver = np.zeros(itermax)          # 各代路径的平均长度
	lengthbest = np.zeros(itermax)          # 各代及其之前遇到的最佳路径长度
	pathbest = np.zeros((itermax,numcity))  # 各代及其之前遇到的最佳路径

	while iters < itermax:
		#  随机产生各个蚂蚁的起点城市
		if numant <= numcity:   # 城市数比蚂蚁数多
			pathtable[:,0] = np.random.permutation(range(0,numcity))[:numant]
		else:                   # 蚂蚁数比城市数多，需要补足
			pathtable[:numcity,0] = np.random.permutation(range(0,numcity))[:]
			pathtable[numcity:,0] = np.random.permutation(range(0,numcity))[:numant-numcity]
		
		length = np.zeros(numant)       # 计算各个蚂蚁的路径距离
		
		for i in range(numant):
			visiting = pathtable[i,0]   # 当前所在的城市
			
			# visited = set()                 # 已访问过的城市，防止重复
			# visited.add(visiting)           # 增加元素
			unvisited = set(range(numcity))   # 未访问的城市
			unvisited.remove(visiting)        # 删除元素
			
			for j in range(1,numcity):        # 循环numcity-1次，访问剩余的numcity-1个城市
				# 每次用轮盘法选择下一个要访问的城市
				listunvisited = list(unvisited)
				probtrans = np.zeros(len(listunvisited))
				
				for k in range(len(listunvisited)):
					probtrans[k] = np.power(pheromonetable[visiting][listunvisited[k]],alpha)\
						*np.power(etatable[visiting][listunvisited[k]],alpha)
				cumsumprobtrans = (probtrans/sum(probtrans)).cumsum()
				cumsumprobtrans -= np.random.rand()
				
				k = listunvisited[np.where(cumsumprobtrans>0)[0][0]] # 下一个要访问的城市
				pathtable[i,j] = k
				unvisited.remove(k)
				#visited.add(k)
				length[i] += Dist[visiting][k]
				visiting = k
			
			length[i] += Dist[visiting][pathtable[i,0]] # 蚂蚁的路径距离包括最后一个城市和第一个城市的距离
		
		
		# 包含所有蚂蚁的一个迭代结束后，统计本次迭代的若干统计参数
		lengthaver[iters] = length.mean()
		if iters == 0:
			lengthbest[iters] = length.min()
			pathbest[iters] = pathtable[length.argmin()].copy()      
		else:
			if length.min() > lengthbest[iters-1]:
				lengthbest[iters] = lengthbest[iters-1]
				pathbest[iters] = pathbest[iters-1].copy()
			else:
				lengthbest[iters] = length.min()
				pathbest[iters] = pathtable[length.argmin()].copy()    
		
		# 更新信息素
		changepheromonetable = np.zeros((numcity,numcity))
		for i in range(numant):
			for j in range(numcity-1):
				changepheromonetable[pathtable[i,j]][pathtable[i,j+1]] += Q/length[i]
			changepheromonetable[pathtable[i,j+1]][pathtable[i,0]] += Q/length[i]
		pheromonetable = (1-rho)*pheromonetable + changepheromonetable
		
		# 迭代次数指示器+1
		iters += 1 

	path_tmp=pathbest[-1]
	BestPath=[]
	for i in path_tmp:
		BestPath.append(int(i))
	BestPath.append(BestPath[0])
	
	return BestPath,lengthbest[-1]

##############################程序入口#########################################
if __name__ == "__main__":
	Position,CityNum,Dist = GetData("./data/TSP25cities.tsp") #此处可以更改为你的数据所在的路径和文件名
	
	start = time.clock()                # 程序计时开始
	BestPath,Min_Path = ant()
	end = time.clock()                  # 程序计时结束
	
	print()
	ResultShow(Min_Path,BestPath,CityNum,"蚁群算法")
	draw(BestPath,Position,"Ant Method")

在这个问题中，我们把城市的数据存在csv文档中，并把文档命名为TSP25cities.tsp。

1 2374 197
2 2166 878
3 644 5
4 268 3149
5 706 2256
6 2180 2557
7 1397 771
8 1356 42
9 430 1110
10 2827 1530
11 762 2418
12 1150 1031
13 2227 1932
14 690 2003
15 514 1034
16 310 397
17 1506 2494
18 506 1023
19 2832 366
20 12 2743
21 408 1154
22 2189 3038
23 220 703
24 849 2570
25 2424 392

基于上述代码的实现结果如下所示： 基于蚁群算法求得的旅行商最短路径为：

3—>19—>10—>4—>13—>20—>8—>17—>14—>22—>15—>2—>7—>6—>11—>1—>24—>0—>18—>9—>12—>5—>21—>16—>23—>3
总路径长为：13489.663390290067

其结果图如下：

根据蚁群算法得出的TSP问题路线图

常见算法变形

这里展示了一些常见的蚁群算法的变形算法。

蚂蚁系统 Ant System (AS)

蚂蚁系统是第一个蚁群算法家族的算法，这个算法就是以上介绍的算法思想，由Dorigo提出。

蚁群系统 Ant Colony System (ACS)

在蚁群系统算法中，原始的蚁群系统在三个方面进行了修改：

（i）边缘选择偏向开发（即倾向于选择具有大量信息素的最短边缘的可能性）;

（ii）在构建解决方案时，蚂蚁通过应用局部信息素更新规则来更改其选择的边缘的信息素级别；

（iii）在每次迭代结束时，仅允许最佳蚂蚁通过应用修改后的全局信息素更新规则来更新路径。

精英蚂蚁系统 Elitist Ant System

在这个算法里，全局最优解和其他的蚂蚁一样在每一次迭代后在他的路径上留下信息素（即使这条路径没有被再次访问）。

Max-Min 蚂蚁系统 Max-Min Ant System(MMAS)

该算法控制每个路径上的最大和最小信息素量。 仅允许全局最佳巡回或迭代最佳巡回将信息素添加到其踪迹中。 为了避免搜索算法的停滞，将每条路径上可能的信息素数量的范围限制为间隔[math]\displaystyle{ {\left [ \tau_{max},\tau_{min} \right ]} }[/math]。 将所有边都初始化为[math]\displaystyle{ \tau_{max} }[/math]以强制对解进行更高的探索。 临近停滞时，这些路径会重新初始化为[math]\displaystyle{ \tau_{max} }[/math]。

基于排序的蚁群系统 Rank-based Ant System(ASrank)

所有解决方案均根据其长度进行排名。 此迭代中只允许固定数量的最佳蚂蚁更新其路径。 对解根据其信息素量加权，以使路径较短的解比路径较长的解具有更多的信息素。

连续正交的蚂蚁系统 Continuous Orthogonal Ant Colony(COAC)

COAC的信息素沉积机制是为了使蚂蚁能够协同有效地寻找解决方案。 通过使用正交设计方法，可行域中的蚂蚁可以快速有效地探索其选择的区域，并能够增强全局搜索能力和搜索准确性。 正交设计方法和自适应半径调整方法也可以扩展到其他优化算法，从而在解决实际问题上具有更广泛的优势。

递归蚁群优化 Recursive Ant Colony Optimization

它是蚂蚁系统的一种递归形式，它将整个搜索域划分为几个子域，并解决了这些子域的目标。比较所有子域的结果，并将其中最好的几个提升到下一个级别。 进一步细分对应于所选结果的子域，并重复该过程，直到获得所需精度的输出为止。 该方法已经在不适定的地球物理反演问题上进行了测试，并且效果很好。

历史

发明蚁群算法的人是Frans Moyson和Bernard Manderick。该领域的先驱包括Marco Dorigo，Luca Maria Gambardella。

蚁群优化算法的时间顺序

• 1959年，皮埃尔·保罗·格拉斯（ Pierre·Paul· Grassé ）发明了电光能理论 stigmergy 来解释白蚁筑巢的行为 ；

• 1983年，Deneubourg及其同事研究了蚂蚁的集体行为；

• 1988年，Moyson Manderick和Moyson Manderick发表了一篇关于蚂蚁自组织的文章；

• 1989年，Goss，Aron，Deneubourg和Pasteels对阿根廷蚂蚁的集体行为进行研究，提出了蚁群优化算法的思想：

• 1989年，埃布林（Ebling）及其同事实施了食品行为模型；

• 1991年，M.Dorigo在其博士论文中提出了蚂蚁系统（该论文发表于1992年）。五年后，V。Maniezzo和A. Colorni 共同撰写了一篇摘自论文的技术报告；

• 1995年，Gambardella和Dorigo提出了ant-q 作为蚁群系统的第一个扩展形式的蚁群系统的初始版本；

• 1996年，Gambardella和Dorigo提出了蚁群系统；

• 1996年，发表了有关蚂蚁系统的文章；

• 1997年，Dorigo和Gambardella提出了一种通过局部搜索进行杂交的蚁群系统；

• 1998年，Dorigo发起了第一次有关ACO算法的会议；

• 1998年，Stützle提出了初始并行实施；

• 1999年，Gambardella，Taillard和Agazzi提出了macs-vrptw，这是第一个应用于带有时间窗的车辆路径问题的多蚁群系统；

• 1999年，博纳波（Bonabeau），多里戈（Dorigo）和塞拉拉兹（Theraulaz）出版了一本主要涉及人造蚂蚁的书；

• 2000年，关于蚂蚁算法的《未来计算机系统》杂志特刊出版；

• 2000年，Gutjahr提供了蚁群算法收敛的第一个证据；

• 2001年，公司（Eurobios和AntOptima）首次使用COA算法；

• 2002年，Bianchi和她的同事第一个提出了解决随机问题的算法；

• 2004年，Dorigo和Stützle与麻省理工学院出版社出版了《蚁群优化》一书；

• 2004年，Zlochin和Dorigo证明了某些算法等效于随机梯度下降，交叉熵方法和估计分布的算法；

• 2012年，Prabhakar及其同事发表了与不带信息素的串联通信的单个蚂蚁的操作有关的研究，反映了计算机网络组织的原理。该通信模型已与传输控制协议进行了比较；

• 2016年，首次应用于肽序列设计；

• 2017年，成功将多准则决策方法PROMETHEE集成到ACO算法（HUMANT算法）中。

相关链接

• 百度百科
• 知乎——蚁群算法原理和代码实现(python)
• CSDN——ACO 蚁群算法（算法流程，TSP例子解析）
• 蚁群算法解决TSP问题python代码

编者推荐

无人机集群“圆舞曲”

蚁群优化算法Ant Colony Optimization

该书由Marco Dorigo编辑，描述了关于蚁群算法家族的理论发现，主要算法和目前应用。

10分钟搞懂蚁群算法慕课手记

笔者用比较简练的语言介绍蚁群算法，同时有python代码实战和分析。

蚁群算法创始人Prof.Marco Dorigo分享集群机器人的研究进展和成果

本课程中，蚁群算法创始人 Marco Dorigo将介绍布鲁塞尔自由大学人工智能实验室IRIDIA所做的集群机器人研究项目，以及其参与的两个欧洲研究项目的主要成果，让同类和异类集群机器人从行为上和思维上合作，执行若干不同的任务。通过课程可以更加深入了解集群算法的应用。

---

本中文词条由许菁参与编译，木子二月鸟总审校，费米子编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。