基于MATLAB的改进型基本蚁群算法
第 24卷 第 3期
2003年 9月
太 原 重 型 机 械 学 院 学 报
JOURNAL OF TAIYUAN HEAVY MACHINERY INSTrIrLJTE
V01．24 № 3
Sep．2003
文章编号 ：1000—159X(2003)O3—0201—04
基 于 MATLAB的改进型基本 蚁群算 法
李 虹 ， 孙 志毅
(太原重型机械 学院，太原 030024)
摘 要 ：蚁群算法是一种新型的模拟进化算法。是继 GA、SA、TS等算法之后 求解组
合优化 问题 的一种新思路。人工蚁群算法通过模拟蚁群搜 索食物 的行为 ，采 用正反馈 结
构、分布式计算与某种启发式算子相结合的方法 ，能够很快地发现较好 解。本文给 出一种
基于 MATLAB的改进型基本蚁群算法。有效地 降低 了算法的复杂度 ，缩短 了搜 索时间，具
有较强发现最好解的能力。 ·
关键词 ：蚁群算法；改进
中图分类号 ：TP301．6 文献标识码 ：A
0 引言
蚁群算法(Ant Colony Algorithm)是最近几年才
由意大利学者 M．Dorigo，V．Manierio，A．Collomi等
人提出的一种 新型 的模拟 进化算 法。受 到人们 对
自然界中真实蚁群集体行 为研 究成果的启 发 ，考虑
到蚁群搜索食物的过程与旅行 商问题 的相似性 ，利
用蚁 群 算 法 求 解 旅 行 商 问 题 (Traveling Salesman
Problem)、指派 问题 (Assignment Problem)和调度 问
题(Scheduling Problem)，取得 了一些 比较满 意的实
验结果。蚁群算法 是一种 适应性 好 、鲁棒性 强 。具
有正反馈结构的并行算法 。
1 蚁群 系统 基本原理
自然界 中像 蚂蚁这样几 乎没有视力 的 昆虫 有
很多 ，他们是如何找到 由其巢穴到食物源之最短路
径的?生物学家经过 长期大量 细致 的观 察研究后
发现 ：最初单个蚂蚁 的行为是随机 的。蚂蚁在运动
过程中会在其 经过的路径 上 留下一种 叫做外激 素
(Pheromone)的信息物质。蚂蚁个体之 间的信 息传
递就是依靠这种物质进行的。一方 面，每只蚂蚁在
其走过的线路上 留下一定量的信 息物质 ，且 留在路
径上的信息物质随时间逐渐衰减 。另一方面 ，后来
的蚂蚁能够感知这种 外激素并 以路径上残 留信息
量的多少指导其行 为 ，信息 量越 大的路径 ，被选 中
的概率也越大 。显然 ，蚁群搜索食 物源的过程是信
息量的一个正反馈过程。据此 ，蚁群可 以快 速地找
到由巢穴到食物源的最佳路径 。图 l所示为真实蚁
群系统搜索食物时的路线示意图。图 中 A是 蚁巢 ，
E是食物所在的位置 ，HC为障碍物 。
设 D和 。 和 之间的距离均为 2个单位 ，D
与 c、 与 c之间的距离为 1个单位 ，在一个时间单
元 内有 3O只蚂蚁 由A到达 点 ，同样有 3O只蚂蚁由
收稿 日期 ：2003—03—12
作者篱 介 ：李虹 (1965一 )，女 ，电子信息分 院副教授 ，研 究方向为控制理论 及其应用 。
维普资讯 http://www.cqvip.com
太 原 重 型 机 械 学 院 学 报 2003年
圈 l 蚁群搜 索食 物路线示意 圈
n昏1 An a叫唧 Ie 0f嗽 I am睡伽bny wldle霹锄d血啄t．伽d
到达 D点 ，蚂蚁运动的速度是 1单位距离 ／单位时
间 ，每 只蚂蚁在其走过的路径上 留下一个单位 的信
息量。假设初始时刻 t=0时各条路径 均无蚂蚁走
过 ，位于 和 D点 的各 30只蚂蚁选择所走路线的概
率是相同的，按 照统 计 规律 ，即有 l5只蚂蚁 选择
DIt(BH)，另外 l5只选择路径 (Be)。由于 d舢 =dBH
= 2dDc=2dec，所 以经过 1个单位时间后 ，走过路径
BC和 DC的蚂蚁个数是走过 BH、DH蚂蚁个数的两
倍。这些蚂蚁留在路径 上的信息量前者也是 后者的
2倍 。在 t=1时 ，新的30只蚂蚁位于 点 和D点 ，根
据信息量的多少 ，他们选择路径 pc(Bc)的概率是
选择 on( 日)的两倍 ，即有 20只蚂蚁选择前者 ，而
只有 lO只选择后者。这一过程一直继续下去 ，最终
所有的蚂蚁都将选择 由蚁穴至食物源的最短路径 。
2 人工蚁群 系统数 学模 型
我们不难 发现 蚁群寻找食 物 的过 程与旅 行商
问题的相似性 。利用蚁群 系统 原理求解 个城市 的
旅行商 问题 ，首 先应 建立 人工 蚁群 系统 的数 学模
型 。
在人工蚁群 系统 中，蚂蚁具 有下 面几个特 征 ：
以概率大小选择转移路线 ，概率则是城市之间距离
和路径上残 留信息量 的函数 ；有记忆 功能 ，在每一
次循环 中，每 只蚂蚁 的转移路径 只能是它没有走过
的；完成一次循环后 ，在其走 国 的路 径上 留下一定
量的信息物质 ；蚂蚁 留在路径上 的信息量 随时 间逐
渐衰减。
设 m是蚁群中蚂蚁的数量 ，用 d (i,j=1，2，k，
n)表示城市 和城市 之间的距离 ，下 (t)表示 t时刻
残 留在城市 √连线上的信息量。初始时刻 t=0，各
条路径上有少量的信息 r (0)即 。根据各条路径上
信息量的多少 ，t时刻位于某一城市的蚂蚁 k(k=1，
2，k，m)一次 只能选择其 中一个 目标城市 ，n次后 回
到起点。完成 一次循环 ，按下 面的公式修 改各 条路
径上的信息量 ：
丁 (t+n) =Ip丁 (t)+△丁 (1)
r
△r ={Lk本次循环中蚂蚁k经过连接城市 和 l
0
_『的路径 (2)
式 中0
信息量衰减 的系数 。 是蚂蚁 k在一次循环中走 过
路径 的总长度 ，Q是一个大于 0的常数。
综合考虑各 转移线路 上 的信 息量及 其距离 等
因素，用 allowed 表示蚂蚁 k在位置 上时允许的转
移 目标位置 ，定义蚂蚁 k在 t时刻 由位置 转移至位
置_『时的概率为 ：
P ： J．— 三 ∈a··。wed o㈤={
。
．[ 卢 一 。
【 0
(3)
启发因子 71 =1／d ， 是两个可 以调整的参
数 ，其值决定 了信息量 和启发 因子在蚂蚁选择路径
时所起作用的强弱程度 。P (￡)是蚂蚁在 t时刻选择
转移路径 的依据 。
3 基 于 MATLAB的 改 进 型 基 本 蚁 群
算法
基本蚁群算法 优点是具有 很强 的发 现较好解
的能力 ，不容 易陷入局部最 优 ，与其他一些 算法相
比能够较快地 收敛于解空 间 的某一 子集 。利用基
本蚁群算法求解 Oliver30 TSP的典型实验与其他一
些优化算法的对 比实验结果 (表 1)可 以说明这 一
点。但是 ，当种群 规模较 大时算 法复杂度 高 ，而且
搜索时间长 的问题就 显得 尤 为突 出。造 成这些 问
题的主要原因之一是随着解空间的增大 ，位于 点上
的蚂蚁个体在选择转移路径时 ，不同路径上的转移
概率相互接近的可 能性也越大 ，而基本蚁群算法在
每次进化时 ，只能 固定地选择其 中一条路径。若在
维普资讯 http://www.cqvip.com
第 24卷第 2期 李虹 ，等 ：基于 MATLAB的改进型基本蚁群算法 203
每一个点上都放置一只蚂蚁即 ，必然使算法复杂度
增加 ，搜索时间延长 。这里我们提 出一种对基本蚁
群算法进行改进的方法 ，令 即只在任意一个节点上
放置一只蚂蚁 ，并在算 法循环过 程 中，每次 随机选
取一个节点作为起点 ，这样可 以有效地 克服搜索停
滞 ，缩短搜索时间。
表 1 不 同算法求解 Oliver30 TSP实验结 果对照表 [1]
Tab．1 Experim ental result com parison using different
algortmm~to solve Oliver30 TSP[1]
达到收敛所 算 法 2
一 opt L—K
需循环 次数
ant colony system 420
near neighbor 587 437 42l
far insert 428 42l 420
near insert 5l0 492 4l0
spacefilling curve 464 43l 42l
sweep 486 426 420
random 1212 663 42l
MATLAB以矢量和矩阵为基本运算单元 ，基于
MATIz~B的改进型基本蚁群算法具有编程简单 、容
易实现等特点 。利用基本蚁群算法求解 n个城市的
旅行商 问题 ，在 MATIAB的图形窗 口下 ，可 以方便
地给出任意数 目、任意组 合 的点 阵 ，其分析结 果更
具一般性。经过计算找 到最 短路径后 ，有 MATIz~B
强大绘 图功能 的支持 ，将 所得路 径标注 出来 ，非常
直观。基于 MATIz~B的改进型 基本蚁群算 法程序
流程如下 ： ·
初始化 ：输入参数 rt，B，Q， ，卢，p及 随机数的种子数
在给定坐标系中输入 n个城市 的 TSP模型[X，Y]
X：[]；y=[]；
for Z =1：n
[xl，yl，button]=ginput(1)；
if(button～=1)break；end
plot(xl l， } black')
X=[X，x1]；
Y=[Y，yl J；
text(x(z)+0．5，Y(z)+0．5，num2str(z))
end
主程序 ：按输入顺序编号生成城市序列号矢量 c、计
算距离矩 阵 d
随机产生初始信息量矩阵
循环计数 ：
for b=l：B
随机选择起点位置即 c(1)=i
C(v)(v=2，3，?n)为允许选择的 目标城市
由起点开始计算转移路径 ：
for k=l：n
根据各条路径上的现有信息量计算最大
转移概率 j为 目标城市序列号 ：c(i+1)
= j
end
CB(b，：)=C，L分别为本次循环路径顺序及路径长
度矢量 ，
△T，T(b+1)=T(b)+△T分别为本次循环的信息量
增量及新的信息量矩阵
end
计算最佳路径 Lm=Min[L(b)：BcB]，获得最短路
径 的循环次数 及对应的路径顺序矢量 C8
在原图形上绘制最佳路径 ：
hold on
for k= 1：n
line([X(C8(k))，X(C8(k+1))]，[Y(C8(k))，Y(C8
(k+1))])；
end
line([X(C8(n))，x(c8(1))]，[Y(C8(n))，Y(C8
(1))])；
hold off；
clear
0 10 ∞ 30 40 ∞
图 2 16城 市 rIsP问题最好解
Fig．2 The best resolve of TSP witll 16 cities
4 实验与结论
选用 l6点的等距点阵和 30点的不规则点阵分
J
维普资讯 http://www.cqvip.com
204 太 原 重 型 机 械 学 院 学 报 2003年
／ ，f7 1● I’5 T—
． 6
a<
t
．3o
0
}
z — 一
～ 挚 — 埘
1
0 10 ∞ 3o ∞ ∞ ∞
图 3 改进型 基本蚁群算 法找到的最短路径
ng．3 The shortest route obtained by ．
im pm v~ algorithm
别进行仿真。
图 2的仿真结果表明 ：改进 型基本蚁群算法具
有发现问题最好解的能力。．
对 于 任 意 给 定 的 3 0点 TSP问 题 (如 图 3所
参 考文献 ：
[2]
[3]
示 )，当 =1， =1，P=0．5，Q=50，取 3O次仿真
的平均结果 ，找到 的最短路 径为 221．99，达到收敛
所需的进化代数为 126。实验结果表明 ：经过对基本
蚁群算法 的改进 ，具有较强 发现 最好解 的能力。并
且有效地缩短了搜索时间。
图 4 30点 TSP最好解进化 曲线
Fig．4 Evolution ofthe best length for 30 TSP
Marco Dorigo Vittorio Maniezzo and Alberto Colorni，Ant System：Optimization by a Colony of Cooperating Agents[C]，IEEE
Tram on SMC，1996，26(1)：28-41．
吴庆宏 ，张纪会 ，徐心和 ．具有 变异特征的蚁群算法 ，计算机 研究与发展 [J]，1999，36(10)31．34．
张纪会 ，高齐圣 ，徐心和 ．自适 应蚁群算法 [J]．控制 理论 与应用 ，2000，17(1)：15-17．
Im proved Basic Ant Colony Algorithm Based on M ATLAB
LI Hong ，SUN Zhi·yi
(Taiyuan Heavy Machinery Institute，Taiyuan 030024，China)
Abstra~ ：Ant colony algorithm is a novel with algorith m simulated evolutionary． It provides a new way to solve
complicated combinatorial optimization problems such as traveling salesman problem (TSP)，assignment problem，
job—shop etc as GA，SA，TS，and SO on．Having been enlightened by the behavior of ant colonyg searching for
food．positive feedback construction an d distributed computing combined with certain heuristics are adopted in the
algorith m．All that makes it eas ier to find be tter solution． In this paper，an improved basic an t colony algorithm is
propo sed． Using this meth od the lever of algorithmic complication is depressed and the searching time is reduced．
It has strong Ability in finding the best resolution．Based on MATLAB its program is simple an d it is convenient to
realize．
Key words：an t colony algorithm ；improvement
维普资讯 http://www.cqvip.com
基于MATLAB的改进型基本蚁群算法.pdf
