- 1 -
基于蚁群算法求解 TSP问题的研究
吴璇
北京邮电大学计算机学院，北京（100876）
摘 要：蚁群算法(ant colony optimization, ACO)，是一种用来在图中寻找优化路径的机率型
技术，其利用多样性和正反馈性机制能够进行分布式并行查找，在求解NP完全问题中得到
广泛应用。蚁群算法是一种求解组合最优化问题的新型通用启发式方法，该方法具有正反馈、
分布式计算和富于建设性的贪婪启发式搜索的特点。通过建立适当的数学模型，即可将难题
变为一种非线性全局寻优问题。本文详细分析了蚁群算法的原理和实现要点，并以求解旅行
商问题（Traveling Salesman Problem ,TSP）为例，用C语言仿真实现了该算法。
关键词：蚁群算法；TSP；分布式计算
1．引言
蚁群算法(Ant Colony Optimization, ACO)是受自然界中蚂蚁搜索食物行为启发而提出的
一种智能优化算法，它由Marco Dorigo于1992年在他的博士论文中引入。
纵观自然界，单个蚂蚁是脆弱的， 但整个蚁群却能完成单个个体无法承担的工作， 蚂
蚁借助于信息素这种化学物质进行信息的交流和传递， 并表现出正反馈现象。也就是表现
在某段路径上经过的蚂蚁越多， 该路径被重复选择的概率就越高[1]。正反馈机制和通讯机
制是蚁群算法的两个重要基础。目前，这个新兴的算法也在组合优化问题， 如TSP(Traveling
Salesman Problem，旅行商问题)等诸多领域中得到广泛应用。
2．蚁群算法原理简述
蚁群算法起源于现实中蚂蚁寻找食物的现象，蚂蚁在没有人告诉它们食物在哪的情况下
开始寻找食物，当一只蚂蚁找到食物后，它会向环境释放一种信息素，吸引其他的蚂蚁过来，
这样越来越多的蚂蚁能找到食物。有些蚂蚁并没有像其它蚂蚁一样总重复同样的路，他们会
另辟蹊径，如果令开辟的道路比原来的其他道路更短，那么，渐渐，更多的蚂蚁被吸引到这
条较短的路上来。最后，经过一段时间运行，可能会出现一条最短的路径被大多数蚂蚁重复
着。
这看起来似乎蚂蚁具有智能的行为，而事实上并没有那么复杂，蚂蚁并不需要知道整个
世界的信息，它们只关心很小范围内的眼前的信息，并通过这些局部信息利用几条简单的规
则进行决策。这些简单的规则大致如下：
范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），
那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。
环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，
信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的
信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。
觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是
否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地
方走，并且每只蚂蚁多会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的
规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。
移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，
- 2 -
蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰
动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在
最近走过了，它就会尽量避开。
避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有
信息素指引的话，它会按照觅食的规则行为。
播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走
远的距离，播撒的信息素越来越少。
这些规则综合起来具有两个方面的特点：多样性；正反馈。
多样性保证了蚂蚁在觅食的时候不置走进死胡同而无限循环，正反馈机制则保证了相对
优良的信息能够被保存下来。我们可以把多样性看成是一种创造能力，而正反馈是一种学习
强化能力。正反馈的力量也可以比喻成权威的意见，而多样性是打破权威体现的创造性，正
是这两点小心翼翼的巧妙结合才使得智能行为涌现出来了。
在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有效的找
到食物呢？这要归功于蚂蚁的移动规则，尤其是在没有信息素时候的移动规则。首先，它要
能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动（开始，这个前方是随机固定的一个方
向），而不是原地无谓的打转或者震动；其次，蚂蚁要有一定的随机性，虽然有了固定的方
向，但它也不能像粒子一样直线运动下去，而是有一个随机的干扰。这样就使得蚂蚁运动起
来具有了一定的目的性，尽量保持原来的方向，但又有新的试探，尤其当碰到障碍物的时候
它会立即改变方向，这可以看成一种选择的过程，也就是环境的障碍物让蚂蚁的某个方向正
确，而其他方向则不对。这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到
隐蔽得很好的食物。
当然，在有一只蚂蚁找到了食物的时候，其他蚂蚁会沿着信息素很快找到食物的。蚂蚁
如何找到最短路径的？这一是要归功于信息素，另外要归功于环境，具体说是计算机时钟。
信息素多的地方显然经过这里的蚂蚁会多，因而会有更多的蚂蚁聚集过来。假设有两条路从
窝通向食物，开始的时候，走这两条路的蚂蚁数量同样多（或者较长的路上蚂蚁多，这也无
关紧要）。当蚂蚁沿着一条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时
间就短，这也意味着重复的频率就快，因而在单位时间里走过的蚂蚁数目就多，洒下的信息
素自然也会多，自然会有更多的蚂蚁被吸引过来，从而洒下更多的信息素……；而长的路正
相反，因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。也许有人
会问局部最短路径和全局最短路的问题，实际上蚂蚁逐渐接近全局最短路的，为什么呢？这
源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方走而另辟蹊径，这可以
理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙述的原理，更多的蚂蚁会被吸
引过来。
3．TSP问题
TSP问题是单回路运输问题最为典型的一个模型，全称是Traveling saleman problem,也叫
旅行商问题。TSP问题（Travelling Salesman Problem）是数学领域中著名问题之一。假设有
一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访
一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之
中的最小值。
TSP模型可以如下描述：给定 n 个城市，寻找一条闭合路径，使得每个城市刚好经过
- 3 -
一次且总的旅行距离最短。即寻找一条闭合路径 1 2( , , )nr c c c= L， ，使得下列目标函数
最小。
n-1
1 1
i=1
( ) = ( , ) ( , )i i nf r d c c d c c+ +∑ （1）
上式中 ic 为城市号， ( , )d i j 表示城市 i与城市 j之间的距离。
TSP问题是一个典型的NP完全问题。对于n个城市的TSP问题，其可能的路径组合数为
( 1)!/ 2m − 。这样，TSP最优解的搜索空间将随着城市数n成指数型增长（所谓的“指数爆炸”），
因此，TSP问题虽易于描述，但找出其最优解却是非常困难的。目前求解TSP问题的主要方
法有：蚂蚁算法、模拟退火法以及遗传算法。其中蚂蚁算法利用正反馈机制可以进行并行分
布式的全局搜索，是目前解决各种优化问题的有效方法。
4．用蚁群算法求解TSP问题
曾给出了三种不同模型，分别称之为 Ant Cycle System, Ant Quantity System,
Ant Density System, 其中 Ant Cycle System（蚂蚁圈模型）是全局优化较好的蚂蚁算法。求
解 n个城市 TSP问题的蚁群系统模型如下：设 m为蚂蚁数量，假如 t时刻城市 i与城市 j连
线上的信息素轨迹强度为 ijτ ,蚂蚁 k 在城市(i,j)连线上留下的单位长度轨迹信息素数量 kijτΔ ,
轨迹的持久性 (0 1ρ ρ≤ < ），则轨迹信息量强度的更新方程为
( 1) ( ) ( )kij ij ijt t tτ ρ τ τ+ = + Δ∑�
设 kZ 为第 k只蚂蚁在本次循环中所走的路径的长度,则 ( ) /
k
ij kt Q ZτΔ = ，其中 Q是一个
常数。如果设 ijη 为边路径(i,j)的能见度，一般取为1/ ijd ，这里 ijd 为路径(i,j)的长度,路径可
见度的相对重要性 ( 0)β β ≥ ，路径轨迹的相对重要性 ( 0)α α ≥ ，U 为可行顶点集,蚂蚁 k
在 t时刻由城市 i转移到城市 j的概率为 ( )
k
ijp t ，则 ( )
k
ijp t 可定义如下
[ ] [ ]
( )
, ,
( ) ( )
0 ,
i j i j
k
i j i l i ll U
t
j U
p t t
α β
α β
τ η
τ η∈
⎧ ⎡ ⎤ ⎡ ⎤⎣ ⎦⎣ ⎦⎪ ∈⎪= ⎨⎪⎪⎩
∑
其 他
(2)
5．仿真结果分析
本文程序采用蚂蚁算法实现了寻找最优解，以TSPLIB中的实例作为输入，对不同TSP
问题进行仿真，本文数据是在PC机上（Celeron CPU Ghz，256M内存）用C语言编程得
出。根据表1的仿真结果有如下分析：
(1) 蚁群算法中蚂蚁数目不是越多越好，取值与具体问题有关。
(2) 启发因子 α， 期望启发因子 β和信息保留程度 ρ的组合配置很关键， 如果配置不
当， 会导致求解速度很慢， 并且导致所得解的质量很差，[2]中推荐配置为1，10，，本
文实际应用中发现配置为1，，时效果更好。
(3) 当城市数量增加，本算法很难求出与已知最好解相近的结果，算法本身需要改进。
- 4 -
表 1 用蚂蚁算法求解 TSP问题的仿真结果
问题名称 蚂蚁数目 α β ρ 运行时间(s) 仿真结果 TSPLIB结论
25 1 6
30 1 8 Oliver30
25 1 10 6
423
25 1 22
41 1 36 eil51
25 1 10 22 475
426
问题名称 蚂蚁数目 α β ρ 运行时间(s) 仿真结果 TSPLIB结论
56 1 115
62 1 166 st70
62 1 10 129 778
675
表中TSPLIB结论是TSP库中给出的迄今为止最好的结果。
参考文献
[1] 丁建立，陈增强，袁著祉. 遗传算法与蚂蚁算法的融合[J]. 计算机研究与发展, 2003, 40(9):1531-1536.
[2] 蔡光跃，董恩清. 遗传算法和蚁群算法在求解TSP问题上的对比分析[J]. 计算机研究与应用, 2007, 43(10)
The Research of Traveling Salesman Problem Based on Ant
Colony Optimization
Wu Xuan
College of Computer Science, Beijing University of Posts and Telecommunication,
Beijing (100876)
Abstract
Ant Colony Optimization is a kind of technology which is used to compute the optimization path in a
graph. It can have distributed paralleling searching with its diversity and positive reactivity characters,
so it had been widely applied in dealing with NP problems. Ant Colony Optimization is a novel
heuristic method to deal with assembling optimization problem. It is with the attributes of positive
reactivity, distributed computing and constructive heuristic searching. By setting up proper
mathematics model, it can be transferred to a non-linearity global optimization problem. This paper
mainly does research on the principle and implementation key points of Ant Colony Optimization, and
takes Traveling Salesman Problem for example to simulate this algorithm in C language.
Keywords: ACO; TSP; Distributed Computing
作者简介：吴璇，女，1984年生，硕士研究生，主要研究方向是网络安全和高性能计算。
