动态蚁群算法求解TSP问题
动态蚁群算法求解 TSP问题
李 勇 段 正澄
(华中科技大学国家数控 系统技术研 究中心 ，武汉 430074)
E-mail：liyonghust@sina．corn
摘 要 蚂蚁群体能完成 单个蚂蚁所无法 完成的工作。它们通过称 为信 息素的物质 交流信 息而协 同工作。蚂蚁在 觅食 活
动 中，在食物与 巢穴之 间的路径上 留下信 息素 ，较短路径信 息素相对较 浓 ，而蚂蚁倾 向于沿信 息素较浓的路径往返 于巢
穴与食物之 间。经过一段时间后 ，就可发现从巢穴到食 物的较短 的路径 。基 于此原理 ，Marco Dorigo提 出了蚁群算法 ，并
首 先 用 于求 解 TSP问题 。该 文从 更 多方 面 模 仿 真 实 自然界 中蚂 蚁 的行 为 ，更 为 合 理地 制 定信 息 素动 态挥 发 规 则 ，提 出 动
态蚁群算 法并 用于解决 TSP问题 ，实验表明 了该算法有较好 的性能 。
关键词 蚁群算法 旅行 商问题 组合优化
文章编号 1002—8331一(2003)17一O103-o4 文献标识码 A 中图分类号 TP301．6
A New Ant System for TSPs
Li Yong Duan Zhengcheng
(’rhe National NC System Engineering Research Center，HUST，Wuhan 430074)
Abstract： Ant colony call perform tasks that cannot be carried out by individual ants．Ants work together th~,c,h a
chemical substance-pheromone．Ants look for food and lay the way back to their nest with pheromone，and the other
ants Call follow the pheromone to find the food efficiently．Basing on these，Marco Dorigo pro posed the ant algorithm．This
paper presents dynamic ant colony system，a improved version of ant system (AS)．It shows better performance than the
original algorithm．
Keywords：ant system ，traveling salesman problems，combinatorial optimization
l 引言
蚂蚁系统是模仿蚁群 的行 为构建的人工系统。在 自然界中
蚂蚁几乎是瞎子 ，却能发现食物与蚁穴之间最短 的距 离。生态
学 家的研究表 明 ，蚂 蚁是借 助信息素 (pheromone)来 实现 这一
点 的。信息素是蚂蚁 分泌 的一种化学物质 ，蚂蚁 在寻找食 物过
程 中会分泌这种物质 。蚁群在寻找食物时 ，会 有一些蚂蚁 四处
游荡 ，当蚂 蚁发现食物并返 回巢穴过程 中会 在途中留下信 息
素 。如果假定所有蚂蚁 以相 同的速度前进的话 ，则第 一只返 回
巢穴的蚂蚁发现 的路径是 当前所有蚂蚁发现的路径中最好 的。
较短路径上信息素会 比较浓一些 ，而较 浓的信 息素能吸引更多
的蚂蚁走这条路径 ，从而发现 比较 好的路径 。图 1说 明了蚂蚁
如何发现最短路 径的基本原理 。图 l中两只蚂蚁在同时离开蚁
穴 ，分别走不 同的路径并在各 自的路径 留下信息 素。走较 短路
径 (下 面)的蚂蚁会首先返 回巢穴 。这条路径 由于 留下 比较多的
信息素 ，它会吸引其它蚂蚁走这条路线 。这种强化过 程使蚁群
发现最短路径 。基于这种原理 ，Marco Dorgio等人提 出了称 为
蚂蚁算法一种新 的启发式算法 。蚁群算法 已成 功应 用于求解
TSP问题 、调度 问题 着色问题 。并 在大规模集成电路设计 ，电
信路由控制方面表现 出较好的性能。
蚁群算 法是模拟蚂蚁的行为而提出一种启 发式算法 ，该文
从 更多方面模拟蚁群行为提出了一种改进 的蚁 群算 法 ，该文称
其为动态蚁 群算法 ，并用 于求解 TSP问题 (Traveling Salesman
Problem)。TSP问题 ，即旅行商问题 ，是一类 已被证明具有 NPC
计算 复杂性 的组 合优化 难题 ，它 的提 法是 ：给定 N个城 市 ，有
作者 简介：李勇 (1974一)，博 士生。
一 旅 行商从某一城 市出发 ，访问各城 市一次且 仅有 一次后 返回
原出发城市 ，要求找出一条最短的巡 回路径 。 该 文对蚁群算法
的改进主要在 以下三个方 面 ：(1)动态 目标城亩 选择 ；(2)信息
素挥 发系数动 态变化 ；(3)最差路线上 的信息素弱 化 ；实验表踞
改进 后 的 算 法 比基 本 蚁 群 算 法 及 改进 的 蚊 群 算 法 MMAS
(MAx—MIN Ant system)总体性 能有 了一 定的改善。该文首先
介绍 基本蚁群算法 (AS)和 改进 的蚁 群算法(MMAS)，然后说聪
改进 后的算法 ，最后进行实验结 果分析 比较及结论 。
．
图 1 蚂蚁路径长短与信息素强度 关系圈
2 蚁 群算 法 (AS)与 MMAS
2．1 AS
蚁群算法 (AS)是由 Dorigo和 Gambardella提出一 种新的
启发式算法 ，首先被应 用于 TSP问题 。这一节也将 以 TSP为例
说 明蚁群算法 。
在算法 的开始 ，首先 m 只蚂蚁基 于某种规则 (如随机 )置
计算机工程与应用 2003．17 103
维普资讯 http://www.cqvip.com
于 rt个城市上 ，位于城市 r上 的蚂蚁 k以 (r，s)为概率函数选
择 的 下 一 个 城 市 ，这 个 公 式 给 出蚂 蚁 k由城 市 r转 移 到城 市 s
的概 率 。
f if 五(r)
p ( )二{∑【T(r’u)】 ．【11(r'u)】 (1)
IⅡ ^(r
Lo， otherwise
(r)，蚂 蚁 k 还 未 访 问 的城 市 列 表 ；T(r，u)，边 (r，u)上 的
信息素浓度 ；11(r，u)=l／d~J，启 发函数 Ot，13，这两个参 数反映 了
信息素和启 发函数 的相对重要性 ；
第二 步 ，当所有蚂 蚁完成 环游 ，并按 公式 (3)进行信 息素
更 新
T(r，s) (1-p)·T(r，s)+△T (2)
AT--∑△T^(r，s)，p(o
^ = l
f} 当边(r，s)被蚂蚁k使用时 △ (
r，s)={L
IO 其 它
是第 只蚂蚁的环游长度 。这种信息素更新方式称为局
部信息素更新
最后看结束条件是否满足 ，如不满 足则返回第一 步。
2．2 M口ⅥAS
MMAS主要 在 以下 两 方 面 区 别 于 AS。
(1)当所有 的蚂蚁完成 环游 ，仅仅蚂蚁发现 的最 好路径 上
的信息素进行更 新 ，这种信息更新方式称 为全局信息素更新。
(2)每条边上 的信息素被限制在区间【T ，T一 内。
(3)信息素初始化为 T一。
对 每条边 上的信息 素浓 度的限 制有利 于减少早 熟现 象 。
MMAS中每条边 的信息素被初 始化为 T一，经过几次迭代之后 ，
每条路径上的信息素 因挥发而减小 ，而仅有每次迭代过程 中的
最好路 径上的信息素被允许增加 ，因而只有最好路径上 的信息
素保持一个 较高水准 。MMAS 性能优于 AS。
MMAS有 一 种 改 善 性 能 的机 制 称 之 为 pheromone trail
smoothing(PTS)，当 MMAS计算结果收敛 至一 个值停滞不变
时 ，按如下公式调整信息素 ：
T(r，s) T(r，s)+8·(T呲(r，s)一T(r，s))，其 中 0<8<1 (3)
这种机制是 在进 化接近停滞 的情况 下调总体上 的信息素
分布 ，其 中参数 8决定了对以前 信息素 的保 留的多少 。8=o，则
(a)
104 2003．17 计算机工程与应用
是 完全保 留 ，Fix3不起作 用 ；8=1则 完全去 掉 以前 的信息 素分
布 ，重新开始计算 。这种机制在长时间计算运算中有 比较好的
作 用 。
3 动 态蚁 群算 法
动态蚁群算法相对 AS和 MMAS主要改进 在于以下几点 。
AS和 MMAS算法依据信息 素和启 发函数选择 目标城市。如
何依据这两个因子选择城市对算 法的性能是非常关键的。动态
蚁群算 法在迭代过程 中 ，在选择 目标城市 的标准 时 ，不是 使用
一 个固定的标准 ，使之有利于减小进化停滞 现像 。在 AS中，对
信息素的强度没有限制，因而易于陷入局部最优点 。MMAS对
信息素的强度给予一定的限制 ，从而大大改善 了算法 的性能 。
动态蚁群算法中挥 发因子是动态变化 ，信息 素浓 度越 高挥发因
子越大 ，浓度越低挥 发因子越小 ，这样实 际对信息素浓度也进
行限制。使信息素不可能无限增大 ，也不可能为零。MMAS中仅
有最好蚂蚁所走路 径上的信息 素进行全局更新 ，如果能对更多
路径上的信息素进行更新则有可能加快演化的速度。为 了比较
算法的全 局收敛能力 ，在随后的计算中没有采用如 r-0pt(一般
用 2-opt或 3-opt)，Lin＆ kerninggan等局部优化方法 。
3．1 权 函数
AS和 MMAS依据 【T(r，s)】 【11(r，s)】 来选择 下一个转移
城 市， ，13是常数。在 自然界 中生物随着时 间的推移对环境适
应 之 后 ，不 再 对 环境 敏感 。基 于 此 原 理 ，可 认 为 蚂 蚁 随 着 时 间 的
推移对信息素慢慢变得不敏感。在算法 中体现为 ，【T(r，s)】 随
n ‘
着 时间相对 于 【11(r，s)】 ，减小 ，这样信 息素 的影 响减小 了 ，而
启发函数 的影响相对加大 ，这样 ，13由常数 就变成为与时间
有关的函数。在 TSP问题 中 (r，s)=l／d~ ，dr 是城市 r和 s之
间的距离 。为简化计算 ，文章置 a=l，而 13按迭代次数进行 如下
变 化
1-mn／3 次 迭 代 B=5；ran／3-mn／2次 迭 代 B---4；mn／2～
mn 2／3次迭代 13=3；mn*2／3～mn次 B=2；
inn是总 的迭代次数 。在该 文中循环次数 固定为 10o0o次。
3．2 动 态挥发 因子
在 AS中，挥发 因子是一个常数 。而在真实世界 中，信息素
浓度越 高 ，挥 发越快 ，信息素浓度越 低 ，挥 发越 慢 ，这样可 以防
止信息 浓度无限制地增 长 ，或 者变为零 ，减小陷入局部 最优的
可能 。在这样 情况下挥发 因子 由常数变成 以 T(r，u)为变量的
函数 。
(b)
维普资讯 http://www.cqvip.com
图 2 挥 发 函 数
局部信息素更新规则变为 ：
T(r，s)+-(1-p(q'(r，s))呵 (r，s)+coe(T(r，s))·△T (4)
挥发函数对算法的性 能有直接 的影响 ，在实验中曾试过如
图所示 4种类型 函数 (X轴为浓 度 ，Y轴为挥发 因子 )。实 验表
明图 2(d)所对应的挥发函数的效果 比较好 。事实上 MMAS可
以看作动态蚁群算法中的一个特例
3-3 最优 、最 差路 径信 息素 全局更 新
AS和 MMAS仅对最好路径 上的信息素进行 全局更新 ，仅
有一 只蚂蚁对全局信 息素的更新产生影响 。如果有多只的蚂蚁
对全局信息素的更新 产生影 响，则可加速 演化过 程。更新 规则
如 下 ：
T(r，s) (1-a(q'(r，s))·T(r，s)+coe(r，s)·A'r(r，s) (5)
该文对两只蚂蚁所走路上 的信息素进行更新 ，即对最 好路
径及最差路径上的信 素进行全局更新 ，则参数
f C (r，s)∈global_best tour
coe(r，s)={-C (r，s)∈global_worst_tour
L O (r，s)∈the_other
公式(5)变为 ：
T(r，s)+_(1---a('r(r，s))·T(r，s)+C·Aq'(r，s)．best
T(r，s)+_(1--a('r(r，s))·T(r，s)一C·△下(r，s)：worst
其 中
△T( )：J‘ ：if global_ r
【( )。if( )∈global_
worst tour
图 3 TSPLIB公布的最 好环游路径
(d)
是最 好蚂蚁所走路径长度 。 是最差蚂蚁所走路径长
度。n(T(r，s))是全局信息素挥发因子。
4 实验 结 果
从 TSPLIB (http：／／www．iwr．uni—heidelberg．de／groups／
comopt／software／I'SPLIB95／tsp／)中选取三个 TSP和 ATSP实例
进行 测试 。值得注意的是从 PUB数据 中取得 的数据 。对 TSP
问题 提供 是每个城市 的坐标 ，需要转化成城市之问 的距离 。并
且按四舍五入圆整为整数 。否则会 出现它提供最好环游 长度 ，
与所 提供 的环 游城 市之 间距 离 之和 不相 等 的情况 出 现 。以
eil51为例 ，公 布的最好 环游 路径如图 3所示 ，不进行 圆整 的结
果为 429．983，而公布的对应的最短环游 路径为 426，对城 市之
间的距 离进行 圆整后计算结果为 426。用动态蚁群算法计算并
且不进行 圆整 ，路径 长度为 428．872，如 图 4所示 。
在实验 中选择 的参数如下 ：
m=l0，toe(T(r，s))=O．I，C---O．1，Or=1，0(T(r，s))---0，8=0．5迭
代次数 mn=10000，挥发 函数选择如图(2)中(d)所示 函数。计算
结 果 如 表 1所 示 。
表 1中“最好解 ”指 目前所有算 法发现的最好解 。MMAS、
MMAS+pts和 AS计算结果从文献f161中得到 。表中所有数据是
25 次 独立 运 算 的 平 均结 果 。对 于 ACS和 MMAS迭 代 次=
n*10000次 ，n为城市数 目。MMAS使用 n蚂蚁。对于 P问题
3个 实例的计算结 果均 比 MMAS强 ，而对于 ATSP问题 ，仅有
图 4 用动态蚊群算法发现的最好瘩径
计算机工程与应用 2O03．17 lo5
维普资讯 http://www.cqvip.com
kro124实例 的计算结果 比 MMAS的结果差一些 。
表 1 TSP计算结果 比较
实锎 t好■ 动态蚊群算褪 动态蚁群算法+pts MMAs+ b MMAS AS
eil5l 426 426．24 42 憾 427．1 427．6 43703
kroal00 21282 2l299 32 2l捌 ．346 21291 6 2l320．3 22471．4
d198 15780 15970．2 l55 15956．8 15972．5 16702．1
ry48p 14422 14472．84 l4‘s5．2 l4523．4 14533_2 l5296．4
ft70 38673 38854．4 3嘲 2，．2 38992．7 39D}n2 395963
kro124p 3623o 36780．2 36578．346 3‘5 36773 5 38733．1
图 5 典型演化过程 (kroalO0 J
5 讨 论与结 论
与 MMAS相 比，在动态蚁群算法 中对 更多蚂蚁所走路 径
上 的信息 素更新 ，以加速收敛 ，另一方 面采用动态 目标城市 选
择标准和动态挥发因子来减小进化停滞现象 ，防止早熟 。从 计
算结果来看取得了比较好 的结果 。但在实验中发现参数选择 对
计算结果 影响很大 ，而且参数选择 没有特别 的依据 ，主要依 赖
试验结果进行选择 。在该算法 中参数 ，动态权 函数 数及挥 发函
数对算法的性 能影响非常关键 ，如何更合理地选择这 些函数 ，
及参数将是下一步的主要工作 。(收稿 日期 ：20o2年 5月)
参 考文献
1．Marco ~ rgio，Gianni Di Caro ．Ant Algorithms for Discrete Optimiza-
lion[J]．Artificial Life，1999；5(3)：137-172
2．Luca M Gambardella，Marco Dorgio．Ant—Q：A reinforcement I~arning
approach to the traveling salesman problem[C]．In：Proceeding of ML-
95，Twelfthlntem Conf on Machine Learning，Morgan Kanfmann，1995：
252-260
3．Hidenori KAWAMURA，Masahito YAMAMOTO，Keiji SUZUKI et a1．
Multiple Ant Colonies Algorithm Based on Colony Level Interactions[J]．
IEICE TRANS Fundamentals，2000；E83一A(2)
4．Shyh-jier Huang．Enhancement of hydroelectric Generation Scheduling
Using Ant Colony System Based Optimization Appronche~ IEEE Tran-
sac~ons on Energy Conversion ，2001；16(3)
5．Christian Blum，Andrea R0li，Marco Do,gio．HC-ACO Hyper-Cube
Framework for Ant Colny Optimization[C]．In：MIC7．O01 Metaheuri-
sties International Conf erence，2001：16-20
6．Giarmi di Care ．M arco Dorigo．AntNet：A Mobile Age nts Approach to
Adaptive Routing[R】．Technical Report。IRIDIA97-12，Univemite Libre
de Bmxelles，1998
7．M Dorigo ，L M Gambardella．Ant Colony Sytem ：A cclop目 Itive I．~anl-
ing Approach to the Travelling Salesman Problem[J]．IEEE Transactions
on Evolutionary Computation，1997；(1)：53--56
8．A Colomi，M Dorgio，F Ma仿0li et a1．HEURIs帆CS FR0M NATURE
FOR HARD C0MBINA I．0RIAL 0F，兀MIzATl0N PROBLEMS[M]．Pub-
lished in International Transactional in Operational R Iea ．1-21
9．Marco Dorgio，Vittorio Maniezzo，Alberto Colomi．Ant System ：Optimi-
zation by a Colony of Cooperating Agents[J]．瑾 E Transactions on
System，Man，Cybernetics-Part B：Cybernetics，1996；26(1)
10．Nicolas meuleau，Marco DoIgio．Ant Colony Optimization and Sto-
chastic Gradient Descent[R1．Technieal Report．NTR佃 ID^ O00 0OO一
36，2000
1IX Stutzle．H Hoos．The an t system and local search fortraveling sale9一
man problem[C]．In：a Proceeding of ICEC 9r7 IEEE 4‘International
conf erence of evolutionary，1997
12．T Stutzle．Marco Dorigo．ACO Algorith ms for the Traveling Salesman
problem[C]．In：K Miettinen，M Makla，P Neittaannmki el al eds．Evolu-
tionary Algorithms in Engineering an d computer Science，W iley，1999
13．Coello C A ，Hemandez A，Zavala R L et a1．An t Colony System for
the Design of Combinational Logic Cireuits[C]．In：Proceedings of the
International Confere nce on Evolvable Systems ，ICES2oo0，Edinburg，
Scotland，LNCS，S nger Verlag，2000：17-19
14．IJiu J Tng Y Y．An Evolutionary Autonomous Agents Approach to
Image Feature Extraction【J1．IEEE Transactions on Evolutionary Com-
putation，1997；1(2)：141-158
15．Derigo M．Di Caro G．Ant Colony Op timization：A New Meta-Heuris-
tie[J]．Proceedings of the Evolutionary Computation，Washington IX：，
1999：1470～1477
16．Thimas stuzle．MAX-MIN An t system．Preprint submitted to Elsevier
Science ，1999—1 1-30
17．吴斌，史盅埴．一种基于蚁群算法的1’sP问题分段求解算法【J】．计算
机学报 ，20ol；24(12)
18．马良，项培军．蚂蚁算法在组合优化中的应用们．管理科学学报 ，2001；
4(2)
(上 接 76页 )
另一个重要参数是数据缓冲区大小 ，数据缓 冲区太小 ，导
致 镜像线程 同压缩线程之间的数据缓 冲区传递频繁 ，系统的同
步互斥开销也增加。而数据缓 冲区太大 ，镜像线程和压缩线程
的并行性就会降低 ，因为当缓冲区很大时 ，虽然镜像线 程镜像
了很多数据 ，当缓 冲区未满时 ，即使 压缩 线程 空闲 ，也 只能等
待 ，从而降低 系统性能 。
对于这两个参数 ，采用动态调 整技术 ，他们都和 系统 的硬
件 配置 有关 ，服 务器生产时设置 一个初始值 ，主线程每次 统计
镜像压缩 的信息 ，通过这些历史记 录 ，主线 程会 逐步调整这 两
个参数 ，最终到达一个稳定的设置 ，当服务器硬件配置改变时 ，
他也会逐步适应。(收稿 日期 ：2002年 7月 )
lo6 2003．17 计 算 机 工 程 与 应 用
参 考文 献
1．庞丽萍．操作系统原理【M]．第二版 ，华 中理工大学出版社 ，1994--09
2．林福宗 ，陆达编著．多媒体与 CD-ROMiM]．清华 大学 出版社 ．1995
3．[英[Phil Comes著．Linux从入 门到精通【M】．电子工业出版社 ，1998．7
4．Michael Barabanov．A Linux-based Real-Time op enning System[D】．
M S Thesis．New Mexico Institute of Tec hnology．1997-06
5．[Watson95]Watson R，Coyne R．The Parallel I／O Architecture of the
High-Performance Storage System(HPSS)[C[．In：14th IEEE Sympo-
sium on Mass Storage systems ，1995-09
6．林福综编著．多媒体技术基础【M1．清华大学出版社 ，2000--08
7．[美l『0hn Goel'zen 著．Linux编程 宝典CM]．电子工业出版社 ，20O0-08
维普资讯 http://www.cqvip.com
动态蚁群算法求解TSP问题.pdf
