１ 基本蚁群算法
以求解平面ｎ 个城市的旅行商问题（Ｔｒａｖｅｌｉｎｇ Ｓａｌ－ ｅｓｍａｎ Ｐｒｏｂｌｅｍ，ＴＳＰ）说明基本蚁群算法。 引入以下
记号:设 ｍ 为蚁群中蚂蚁数量; ｄｉ（ ｊ ｉ，ｊ ＝０，１，…，ｎ － １）为城市ｉ 到城市 ｊ 的距离;τｉ（ｊ ｔ）为时刻 ｔ 路径（ｉ，ｊ） 上的信息素量。 初始时刻各条路径上的信息素量相
Abstract: Ｔｈｅ ｐａｐｅｒ ｉｎｔｒｏｄｕｃｅｓ ｔｈｅ ａｎｔ ａｌｇｏｒｉｔｈｍ ａｎｄ ｉｔｓ ｐｒｉｎｃｉｐｌｅｓ， ａｌｇｏｒｉｔｈｍ ｍｏｄｅｌ ａｎｄ ｈｏｗ ｔｏ ｒｅａｌｉｚｅ ｉｔ， ａｎａｌｙｚｅｓ ｔｈｅ ｒｅａｓｏｎｓ ｏｆ ｔｈｅ ｐｒｅｍａｔｕｒｅ ｓｔａｇｎａｔｉｏｎ ｐｈｅ－ ｎｏｍｅｎｏｎ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ｐａｐｅｒ ｔｈｅｎ ｐｒｅｓｅｎｔｓ ａ ｍｏｄｉｆｉｅｄ ｖｅｒｓｉｏｎ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ ｂｙ ｉｎｔｒｏｄｕｃｉｎｇ ｐｒｉｎｃｉｐｌｅｓ ｏｆ ｕｐｄａｔｅ ｏｆ ｐｈｅｒｏｍｏｎｅｓ ｗｉｔｈ ｔｈｅ ｂｅｓｔ ａｎｄ ｔｈｅ ｗｏｒｓｔ ｒｏｕｔｅｓ ａｓ ｗｅｌｌ ａｓ ｏｐｔｉｍｉｚｅｄ ｌｏｃａｌ ｓｅａｒｃｈｉｎｇ， ｓｏ ａｓ ｔｏ ｅｘ－ ｐａｎｄ ｔｈｅ ｓｃｏｐｅ ｏｆ ｆｅａｓｉｂｌｅ ｓｏｌｕｔｉｏｎ ｆｏｒ ｔｈｅ ｐｕｒｐｏｓｅ ｏｆ ｐｒｅｖｅｎｔｉｎｇ ｐｒｅｍａｔｕｒｅ ｓｔａｇｎａｔｉｏｎ ａｎｄ ａｃｃｅｌｅｒａｔｉｎｇ ｃｏｎ－ ｖｅｒｇｅｎｃｅ ｓｐｅｅｄ ｏｆ ｔｈｅ ａｌｇｏｒｉｔｈｍ． Ｔｈｅ ｅｘａｍｐｌｅ ｏｆ ＴＳＰ ｓｈ－ ｏｗｓ ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｉｍｐｒｏｖｅｄ ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ． Key words: ａｎｔ ｃｏｌｏｎｙ ａｌｇｏｒｉｔｈｍ； ＴＳＰ； ｒｏｕｔｅ； ｐｈｅｒｏｍｏｎｅ
铁道运输与经济 RAILWAY TRANSPORT AND ECONOMY 文章编号：１００３－１４２１（２００９）０２－００８３－０３ 中图分类号：Ｏ２９：Ｕ４９２．２＋２ 文献标识码：Ａ
研究与建议
改进蚁群算法在 旅行商问题中的应用
Application of Improved Ant- Algorithm in TSP
８０
６
Ｃ
４
２
１０ Ｊ
Ｂ Ｉ
Ｌ １２
Ｈ
Ｍ
１３
１４
Ａ
Ｎ
０
Ｇ Ｄ
Ｆ １１ Ｋ
Ｅ
-２ -５ ０ ５ １０ １５
图 ４ 改进蚁群算法的最优路径图
次就基本趋于稳定，收敛速度加快，而未改进的基本 蚁群算法迭代１４ 次才趋于稳定，收敛速度较前者慢。
合;ｔａｂｕｋ 为禁忌表，记录蚂蚁 ｋ 已经走过的城市。
［τｉ（ｊ ｔ）］α［ηｉ（ｊ ｔ）］β Ｐｉｋ（ｊ ｔ）＝ ［ τｉ（ｓ ｔ）］α［ηｉ（ｓ ｔ）］β
ｊ
∈
ａｌｌｏｗｅｄ ｋ
⑵
０ｓ∈ ａ ｌ ｌｏ ｗ ｅ ｄ ｋ 否则
图 ２ 基本蚁群算法的平均节点分支与迭代次数的进化曲线
改进后蚁群算法的目标函数随迭代次数的进化 曲线如图 ３（其中横坐标表示迭代次数，纵坐标表示目 标函数）所示，最优路径如图 ４ 所示。 其最优路径为: Ａ →Ｋ →Ｆ →Ｅ →Ｇ →Ｄ →Ｊ →Ｃ →Ｂ →Ｉ →Ｌ →Ｈ →Ｍ →Ｎ →Ａ。最优路径的距离为 ４５．８１８ ４。
很显然，改进蚁群算法的结果（最短路径长度为 ４５．８１８ ４）比未改进的基本蚁群算法的结果（最短路径 长度为４６．３３４ ９）要好。而且蚁群算法改进后，迭代１０
参考文献： ［１］ 刘志硕，申金升，柴跃廷.基于自适应蚁群算法的车辆路径问
题研究［Ｊ］.控制与决策，２００５，２０（５）: ５６２-５６６. ［２］ 郭倩倩，黄天民，施继忠.一种改进的蚁群算法及其在旅行商
⑺
式中:ξ ∈ ［０，１］ 是一个参数，τ０ ＝ １ ／ ｎ Ｌｂｅｓｔ，Ｌｂｅｓｔ 为该
次循环中最短路径长度。
２．３ 信息素量限定规则
４９
４８
４７
４６ ０ ５ １０ １５ ２０ ２５
⑴
式中:ηｉ（ ｊ ｔ）为 ｔ 时刻的能见度，反映由城市ｉ 转移到 城市 ｊ 的启发程度; β 为启发信息的重要程度;ｑ 是在
［０，１］区间均匀分布的随机数; ｑ０为一个参数（０ ≤ｑ０≤
１ ）;ｓ 为由公式⑵决定的随机变量;ａ ｌ ｌ ｏ ｗ ｅ ｄ ｋ ＝｛ ０ ，
１，…，ｎ －１｝－ｔａｂｕｋ 表示蚂蚁 ｋ 当前能选择的城市集
着算法的重复执行，信息素都积累在这条局部最优路
（７） 对最长路径和最短路径按公式⑸和公式⑹进
径上，使该条路径上的信息素量远大于其他路径的信 行全局更新。
息素量，导致所有的蚂蚁都集中到ｃｍａｘ，则循环结束并输出计
上，出现停滞现象［１］。为此，对基本蚁群算法的信息素 算结果，否则转到第（２）步。
［τｍｉｎ，τｍａｘ］ 之间，这样可以有效抑制由于最短路径和最 长路径信息素量差距加大而引起的停滞现象。 ２．４ 算法步骤
２ 改进的蚁群算法
在基本蚁群算法中，蚁群的转移是由路径上留下 的信息素量和城市间的距离来引导的。 蚁群的运动
（１） 参数初始化。令 ｔ ＝０ 和循环次数Ｎｃ ＝０，设 置最大循环次数 Ｎ ｃｍａｘ，将 ｍ 只蚂蚁随机地放到 ｎ 个城 市，设每条边（ｉ，ｊ）上的信息素量为常数，且 ∆τｉｊ ＝ ０， 将出发点城市设置到禁忌表中。
每只蚂蚁选择一个城市（走完一个边）以后，按公
式⑶更新该边上的信息素量。
τｉ（ｊ ｔ＋１）＝（１－ξ）τｉ（ｊ ｔ）＋ξ τ０
⑶
式中:ξ ∈ ［０，１］ 是一个参数;τ０ 为常数。
当所有蚂蚁走完全部城市后，各路径上的信息素
量按公式⑷更新。
τｉ（ｊ ｔ＋ｎ）＝（１－ρ）τｉ（ｊ ｔ）＋∆τｉｊ
⑷
其中，∆τｉｊ＝
更新方式及局部搜索策略进行改进。 ２．１ 全局更新规则
３ 实例计算
计算该循环中所有蚂蚁经由的路径距离，找出最
以旅行商问题为例，对 １ ４ 个城市的 Ｔ Ｓ Ｐ 进行计
短路径和最长路径，对最短路径和最长路径上的信息 算，其各城市所在位置对应的平面图坐标分别为: Ａ（８，
素量按公式⑸和公式⑹进行更新［２］。
信息素量更新后，将每条边上的信息素量限定在
图 １ 基本蚁群算法的目标函数随迭代次数的进化曲线
84
第 ３１ 卷 第 ２ 期
改进蚁群算法在旅行商问题中的应用 李成兵 等
研究与建议
铁道运输与经济
４
３．５
３
１４
２．５
２ ０ ５ １０ １５ ２０ ２５
改进蚁群算法通过改变信息素量的更新方式，加 快了收敛速度，同时在搜索过程中引入局部最优搜索 策略，使改进蚁群算法解的性能得到较大提高，并应 用仿真手段证明了改进蚁群算法的实用性与高效性。
７０
６０
５０
４０ ０ １０ ２０ ３０ ４０ ５０ ６０ ７０ ８０ ９０ １００ 图 ３ 改进蚁群算法的目标函数随迭代次数的进化曲线
摘 要： 介绍蚁群算法及其原理，算法模型和实 现过程，分析基本蚁群算法易出现早熟停滞现象 的原因。 在原有算法基础上引入最优、最差信 息素更新策略和局部最优搜索策略，从而扩大可 行解的范围，避免算法过早停滞，同时加快算法 的收敛速度。以旅行商问题为例进行仿真计算， 说明改进蚁群算法的性能。 关键词：蚁群算法;旅行商问题;路径;信息素
素就不一定能反映最优路径的方向，不能保证蚁群创
（５） 计算每只蚂蚁找出的路径长度，保留最长和
建的第一条路径能引导蚁群走向全局最优路径。 而 最短路径。
在第一次循环中，蚁群留下的信息素会因正反馈作用
（６） 对最短路径采用２－ｏｐｔ策略，把得到的最短路
使这条路径可能不是最优，且得不到应有的增强。 随 径作为最优解。
１／Ｌｇｂ （ ｉ，ｊ）∈全局最优路径 ０ 否则
式中: ρ 为信息素挥发系数，则 １ －ρ 为信息素残留因
83
第 ３１ 卷 第 ２ 期
研究与建议
铁道运输与经济
改进蚁群算法在旅行商问题中的应用 李成兵 等
子，为防止信息素量的无限积累，通常设置 ０ ＜ρ ＜１; ∆τｉｊ为本次循环中路径（ｉ，ｊ）上的信息素增量;Ｌｇｂ为到 目前为止找出的全局最优路径。
总是趋向于信息素最强的路径，所以信息素最强的路
（２） 按公式⑴选择下一个城市。
径与最优路径比较接近。 由于各路径上的初始信息
（３） 按公式⑺进行局部信息素量更新。
素量相同，蚁群创建第一条路径的引导信息素主要是
（４） 循环执行第（２）步和第（３）步，直到每只蚂蚁
城市间的距离，这样蚁群在所经过的路径留下的信息 都生成一条路径。
等，设τｉ（ｊ ｔ）＝Ｃ（Ｃ 为常数），则 ｔ 时刻位于城市 ｉ 的蚂 蚁ｋ（ｋ ＝１，２，…，ｍ）按公式⑴选择下一个城市 ｊ。
Ｓ ＝ ａｒｇ ｊ ∈ ａｍｌｌａｏｘｗｅ ｄ ｋ ｛［τｉ（ｊ ｔ）］［ηｉ（ｊ ｔ）］β｝ ｑ≤ｑ０ ｓ 否则
局部信息素量更新的作用是使已选的边对后来 示，得到最优路径的距离为 ４６．３３４ ９。
的蚂蚁具有较小的吸引力，从而使蚂蚁对没有被选中 ５１
的边有更强的探索能力。当蚂蚁从城市 ｉ 转移到城市 ５０
ｊ 后，路径（ｉ，ｊ）上的信息素量按公式⑺进行更新［２］。
τｉ（ｊ ｔ＋１）＝（１－ξ）τｉ（ｊ ｔ）＋ξ τ０
Ｌ（９，４），Ｍ（１１，３），Ｎ（１３，２）（单位略）。 以 ＭＡＴＬＡＢ
∆τｉｊ＝ -Ｌｗｏｒｓｔ／Ｌｂｅｓｔ （ ｉ，ｊ）∈最长路径 ０ 否则
⑹ ７．０ 编制程序，在 Ｐ ４ ３．０ Ｇｈｚ１ Ｇ 内存计算机中运行， 实验参数设置: ｍ ＝ １ ２ ０，Ｎｃｍａｘ ＝ １ ０ ０，α ＝ １，β ＝ ５，