第22卷 第7期
文章编号:1006-9348(2005) 07-0060-03
计 算 机 仿 真
2005年7月
基于蚁群算法求路径规划问题的新方法及仿真
王旭, 崔平远, 陈阳舟
(北京工业大学电子信息与控制工程学院, 北京100022)
摘要:该文提出了一种基于蚁群算法求解路径规划问题的新方法及其仿真, 蚁群算法就是对自然界中蚂蚁的寻食过程进行模拟而得出的一种模拟进化算法。与传统的算法相比, 该算法的主要特点是正反馈和并行性, 正反馈使得该算法能很快发现较好解, 并行性使得该算法易于实现并行计算。虽然蚁群算法在时间复杂度上可能不如传统的算法, 但是理论研究表明该方法是一种基于种群的鲁棒性较强的模拟进化算法。最后, 利用Java 语言对蚁群算法和改进的D ijkstra 算法进行了仿真, 并进行了比较。
关键词:蚁群算法; 路径规划问题; 模拟进化算法中图分类号:TP301. 6 文献标识码:A
A New M ethod and S i m ul a ti on for Pa th Pl ann i n g Proble m
Ba sed on An t Colony A lgor ith m
WANG Xu, CYI Ping -yuan, CHEN Yang -zhou
(School of Electr onic I nf or mati on &Contr ol Engineering, Beijing University of Technol ogy, Beijing 100022, China ) ABSTRACT:This paper puts f or ward a new method and si m ulati on f or path p lanning p r oble m (PPP ) based on ant col ony algorith m (AC A ) . AC A is a si m ulated evoluti onary algorith m (SE A ) of si m ulating t o seek food of ants in na 2ture . Comparing with conventi onal algorith m, it has several p ri m ary characteristics such as positive feedback and par 2allelis m. Positive feedback makes it faster t o find better s oluti ons . Parallelis m makes it easier t o realize parallel com 2puting . A lthough ACA is not as good as conventi onal algorith m on the comp lexity of ti m e, studies on the theory de m 2onstrate that it is a r obust SE A based on populati on . A t last, it is si m ulated by Java and compared with I m p r oved D i 2jkstra A lgorith m.
KE YWO RD S:Ant col ony algorith m (ACA ) ; Path p lanning p r oble m (PPP ) ; Si m ulated evoluti onary algorith m (SE A )
1 引言
路径规划问题(Path Planning Pr oble m, PPP ) 是在给定的城市道路网中寻找出一条从起始点到目标点之间的最优路径的问题。在如何解决这个问题方面各国学者已经做了大量的研究, 这其中包括D ijkstra 算法及其改进[1]、启发式搜索算法
[2]
了一种利用蚁群算法来解决路径规划问题的新方法并用Ja 2
va 语言实现了此算法。此方法虽然研究时间不长, 但是初步
研究已表明它是一种很有发展前景的算法。
2 蚁群算法原理概述
蚁群算法是对自然界蚂蚁的寻径方式进行模拟而得出的一种仿生算法。为了说明蚁群算法的原理, 本文首先简要介绍一下蚂蚁寻找食物的具体过程。
在蚂蚁寻找食物时, 它们总能找到一条从巢穴到食物之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素(Pher omone ) 。当它们碰到一个还没有走过的路口时, 就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长, 释放的信息素浓度就越低。当后来的蚂蚁再次碰到这个路口的时候, 选择信息素浓度较高路径的概率就会相对较大。最优路径上的信
、模糊算法
[3]
、神经网络
[4]
、遗传算法
[5]
等等。在20
世纪90年代, 意大利学者Marco Dorigo 等人从生物进化的机理中受到启发, 通过模拟自然界蚂蚁寻食的行为, 提出了一种全新的模拟进化算法(Si m ulated Evoluti onary A lgorith m,
SE A ) :蚁群算法(Ant Col ony A lgorith m, ACA ) , 并用该算法求
解了旅行商问题(Traveling Sales man Pr oble m, TSP ) 、JSP (Job
-shop Scheduling Pr oble m ) 和QAP (Quadratic A ssign ment Pr oble m ) 等问题, 取得了一系列较好的实验结果。本文提出
收稿日期:2004-04-16
息素浓度越来越大, 而其它的路径上信息素浓度却会随着时间的流逝而消减。不仅如此, 蚂蚁还能够适应环境的变化, 当蚁群运动路线上突然出现障碍物时, 蚂蚁能够很快地重新找到一条最优路径。这个过程和前面所描述的方式是一致的, 这里就不再赘述。在整个寻找食物的过程中, 虽然单个蚂蚁的选择能力有限, 但是通过信息素的作用, 整个蚁群之间交换着路径信息, 最终能找出最优路径。
蚁群算法就是对上面所描述的蚂蚁寻找食物的过程进行模拟而产生的算法, 它具有群体合作、正反馈和分布式计算等特点。顾名思义, 群体合作就是很多个主体Agent (这里所指的主体就是蚂蚁) 可以进行相互之间的协作而更好地完成寻优任务; 正反馈使得该算法能很快地发现较好解; 分布式计算使得该算法易于实现并行性。以上的特点使蚁群算法很适合解决复杂的组合优化问题, 而路径规划问题就是一种组合优化问题, 所以我们用蚁群算法来解决路径规划问题[6][7]。
用τij (t ) 表示在t 时刻路径(i, j ) 上的信息素浓度, 则在t
+1时刻此路径上的信息素浓度为:
m
ττ・ij (t +1) =ρij (t ) +
k =1
Δτ∑
k
ij
(1)
其中, ρ为一个取值范围在0到1之间的常数, 表示残留
) 则表示信息素的挥发。信息素的相对重要程度, 而(1-ρ
k
Δτij 是第k 只蚂蚁在时刻t 到t +1之间, 在路径(i, j ) 上增加
的信息素浓度。
k
τ在文献[7]中, M. Dorigo 介绍了3种不同实现Δij 的算
法, 分别称为ant -cycle 、ant -density 、ant -quantity 算法。而本文采用的是ant -quantity 算法:
k
Δτij =Q /d ij
(2)
其中, Q 是一个常量, 用来表示每只蚂蚁所释放的信息素总量, d ij 表示节点i 和j 之间的路径长度, 即增加的信息素浓度与所经过的路径的长度有关, 这很符合真实的蚂蚁释放信息素的过程。
定义在t 时刻位于节点i 的第k 只蚂蚁选择节点j 为下一个目标的概率为:
P (t ) =
k
ij
3 基于蚁群算法求解路径规划问题
3. 1 路径规划问题的描述
η][τ(t ) ]・[
l ∈allo w ed k
αβ
β
如果把城市道路网中的交叉路口表示为节点, 把道路近似表示为连接两节点的边, 把道路的长度、通行时间等属性表示为此边的权, 那么道路网就可以被抽象成为一个带权的有向图。给定一个带权的有向图G =(V, {E}) , 其中V 是包含n 个节点的集合, E 是包含h 条边的集合, 是E 中从节点i 至j 的边, d ij 是边的非负权值。设s, t 分别为
V 中的起始点和目标点, 则所谓路径规划问题就是指在带权
∑
ηil ][τil (t ) ]・[
α
if j ∈a llo w ed k (3)
其中, ηij 是由节点i 转移到节点j 的启发信息, 该启发信息是由要解决的问题给出的, 在本路径规划问题中取ηij =
1/d ij 。参数α和β分别用来控制信息素浓度和启发信息的相
对重要程度。a llo w ed k 是第k 只蚂蚁下一步可以选择的节点集合。
ρα、β的最佳组合可以由实在以上算法中, 参数m 、、Q 、验而确定。
3. 3 蚁群算法的实现
有向图中, 寻找从指定起始点s 到目标点t 的一条具有最小权值总和的路径。
3. 2 蚁群算法的描述
上述用来解决路径规划问题的蚁群算法的伪代码形式叙述如下:
Begin
给定一个有n 个节点的城市道路网的路径规划问题, 我们可以把指定的起始点s 假设为人工蚁群的巢穴, 把目标点t 假设为要寻找的食物, 则此路径规划问题就可以转化为人工蚁群寻找食物的路径寻优问题。假定人工蚂蚁(以下简称蚂蚁) 的数量为m 只, 则每只蚂蚁的行为要符合下列的规则:
1) 能够释放出两种类型的信息素:食物信息素和巢穴信
初始化, 将m 只蚂蚁放到起始节点s 上。
Loop
For k =1t o m do
蚂蚁k 判断与当前所在的节点i 连接的节点是否已
经走过;
按公式(3) 计算所有未走过的节点的概率, 并按此
概率随机选择下一个节点j;
(2) 更新节点i 和j 之间路径的信息素 按公式(1) 、
息素;
2) 根据与当前节点相连接的路径上的信息素浓度和路
径长度, 以相应的概率来选择下一个节点;
3) 不再选择已经走过的节点为下一个节点, 这可以通过
浓度;
I f 节点j 是目标节点t then
记录起始节点s 到目标节点t 之间的距离和路
径;
判断此距离是否小于近似最短距离, 若是则将此
距离设置为近似最短距离;
将起始节点s 与目标节点t 互换并清空所走过的
节点记录。
一个结构数组来实现;
4) 在寻找食物时, 通过食物信息素寻找下一个节点, 同
时释放巢穴信息素;
5) 在寻找巢穴时, 通过巢穴信息素寻找下一个节点, 同
时释放食物信息素;
6) 按一定的路径长度释放相应的信息素浓度, 并且所释
放的信息素浓度会随着时间的推移而逐步减少。
End
I f 近似最短距离小于给定的精度范围then exit Loop 并显示近似最短距离和路径。 Else got o Loop
End
的找到一条近似最优路径, 从这个角度也可以看出利用蚁群算法解决路径规划问题是可行的。
4 结束语及展望
上面我们介绍了利用蚁群算法解决路径规划问题的方
法及其仿真, 可以看出蚁群算法作为一种模拟进化算法, 具有群体协作、正反馈和分布式并行计算等特点。但是蚁群算法也有许多不足之处, 如计算时间相对较长, 搜索速度较慢, 且容易陷入局部最优解等缺点。为了克服以上的缺点, 提高算法的运算效率和计算精度, 许多学
9、10、11]
者提出了很多改进的蚁群算法[8、。
虽然蚁群算法在时间复杂度上不如一些传统算法, 如改进的D ijkstra 算法, 但是在空间复杂度上与传统算法相比是有优势可言的, 并且理论研究表明此算法是一种基于种群的鲁棒性较强的模拟进化算法。针对这些特点, 我们可以进一步地利用蚁群算法解决实际的动态路径规
图1 改进的D ijkstra
算法得到的仿真结果
划问题, 这样才能真正的体现出蚁群算法的优越性。总之, 蚁群算法是一种新兴的模拟进化算法, 在理论上还不完善, 但它已经显示出了良好的发展前景。在理论上对蚁群算法解决路径规划问题的进一步完善和在实际中的应用将是我们下一步要完成的工作。参考文献:
[1] 张其善, 吴今培, 杨东凯. 智能车辆定
位导航系统及应用[M].北京:科学出版社, 2002-7.
[2] Takahir o I keda, M in -Yao H su, H ir oshi
I m ai . A Fast A lgorithm for Finding Better Routes by A I Search Techniques [C ].I EEE Vehicle Navigati on &I nf or mati on Syste m s Conference Pr oceedings, 1994:291-296.
[3] 关桂霞, 赵剡, 刘莹青. 一种基于模糊
图2 蚁群算法得到的仿真结果ρ=0. 9、α=0. 5、β=0. 5) (m =20、Q =50000、
理论的最佳路径选择方法[J ].华北工学院学报, 2001, 22(1) :75-78.
本文以北京市城市道路网为例, 利用Java 语言对蚁群算法和改进的D ijkstra 算法进行了仿真, 并进行了比较, 如图1、
2所示。
[4] Fili pe A ra új o, Bernardete R ibeir o, Lu ís Rodrigues . A Neural Net 2
work f or Shortest Path Computati on [J ].
I EEE Transacti ons on
Neural Net w orks, Sep. 2001, 12(5) :1067-1073.
[5] M itsuo Gen, Runwei Cheng, D ing wei W ang . Genetic A lgorithm s
for Solving Shortest Path Pr oble m s[J ].I EEE, 1997:401-406. [6] 周勇, 陈洪亮. 蚁群算法的研究现状及其展望[J ].微型电脑
结果表明蚁群算法可以相对较快地找到一条近似最优路径, 这是由于蚁群算法是一种模拟进化算法, 所以得到的路径为近似最优路径。在实际的路径规划问题中, 人们往往关心的不是怎样能找到一条最优路径, 而是怎样能快速合理
应用, 2002, 18(2) :5-7. (下转第78页)
测试函数执行过程中, 会把测试数据记录在日志文件中, 存储在磁盘上。在被测试服务或协议接口的每个检测点上都会生成一条测试信息, 即这个检测点的测试是成功
(Pass ) 还是失败(Failure ) 。在所有的Test Case 运行完毕后, SCT 自带的一个报告生成器会检索所有的日志文件, 获取每
Specificati on[DB ].I ntel Cor porati on, htt p://devel oper . intel .
com /technoledge /efi,2003.
[3] EF I 1. 1D riverModel[DB].I ntel Cor porati on, htt p://developer .
intel . com /technoledge /efi,2001.
[4] EF I 1. 1D river L ibrary Specificati on [DB].I ntel Cor porati on, ht 2
t p://developer . intel . com /technoledge /efi, 2001.
[5] EF I 1. 1D riverW riter’s Guide[DB].I ntel Cor porati on, htt p://de2
vel oper . intel . com /technoledge /efi,2003. [6] EF I 1. 1Shell Commands Specificati on [DB ].
I ntel Cor porati on,
htt p://developer . intel . com /technoledge /efi, 2001.
[7] B I O S Boot Specificati on [DB ].Compaq Computer Cor porati on,
Phoenix Technol ogies L td . , I ntel Cor porati on, htt p://www. phoe 2nix . com /en/support/white+papers -s pecs,
1996.
个检测点的详细信息, 根据Pass 和Failure 进行归类统计, 生成最后CS V 格式的报表。CS V 格式的文件在W indows 平台与L inux 平台都有应用程序可解析。用户只需察看CS V 报表, 便可知道当前的EF I 实现的服务和协议的状况。
4 总结
综上所述, 基于EF I 的驱动-协议(D river -Pr ot ocol ) 模型的SCT 测试系统, 实现了良好的可扩展性和可移植性, 在实际工作中达到预期的测试效果。随着EF I 在B I O S 领域的地位逐渐稳固, 厂家迫切需要一个测试系统来对其实现进行验证, SCT 的出现满足了这一需求, 它为检验EF I 的实现提供了一整套有效的方案。SCT 必将在B I O S 领域获得广泛的应用。参考文献:
[1] EF I 1. 1Specificati on, ver . 1. 1[DB].I ntel Cor porati on, htt p://
devel oper . intel . com /technoledge /efi,2002.
[2] I ntel Platfor m I nnovati on Frame work for EF I Self Certificati on Test
[作者简介]
姚颉文(1978. 9-) , 男(汉族) , 上海人, 上海交通
大学软件工程硕士生, 方向:系统软件测试;
谢康林(1942. 2-) , 男(汉族) , 上海人, 搏导, 上海
交通大学计算机系教授, 方向:数据挖掘与决策支持系统, 模糊逻辑与嵌入式系统研究;
石勇军(1975. 10-) , 男(汉族) , 上海人, 硕士, I ntel 中国软件中心
资深软件工程师, 方向:系统软件开发;
曾文−(1978. 5-) , 女(汉族) , 上海人, 硕士, I ntel 中国软件中心软
件工程师, 方向:系统软件开发。
(上接第62页)
[7] 温文波, 杜维. 蚁群算法概述[J ].石油化工自动化, 2002,
(1) :19-22.
[8] 陈烨. 带杂交算子的蚁群算法[J ].计算机工程, 2001-12, 27
(12) :74-76, 176.
[9] 吴庆洪, 张纪会, 徐心和. 具有变异特征的蚁群算法[J ].计算
控制, 2002-6, 31(3) :198-
210.
[作者简介]
王 旭(1977. 11-) , 男(汉族) , 山东金乡人, 硕士
研究生, 主要研究方向为智能交通系统(I TS ) ;
机研究与发展, 1999-10, 36(10) :1240-1245.
[10] 郝晋, 石立宝, 周家启. 具有随机扰动特性的蚁群算法[J ].
崔平远(1961-) , 男(汉族) , 山东青岛人, 博士, 教
授, 博导, 主要研究方向为城市交通智能导航系统;
仪器仪表学报, 2001-8, 22(4) :350-352.
[11] 覃刚力, 杨家本. 自适应调整信息素的蚁群算法[J ].信息与
陈阳舟(1962. 5-) , 男(汉族) , 湖北荆州人, 博士,
教授, 博导, 电控学院副院长, 主要研究方向为智能交通系统(I TS ) 信息处理与控制。
(上接第65页)
[11] S Boyd, El Ghaoui, L. , E Freon and V Balarishnan . L inear ma 2
trix inequalities in syste m and contr ol theory[M].Philadel phia, P A:SI A M , 1994.
[12] Y W ang, L Xie, C E de Souza . Robust contr ol of a class of un 2
certain nonlinear syste m s[J ].System s Contr ol Lett . , 1992, 19:139-149.
[13] J H Lee, S W Ki m and W H K won . Me moryless contr ollers for
state delay system s[J ], I EEE Trans . Aut omatic . Contr ol, 1994, 39:159～162.
[14] Z D W ang, B Huang and H Unbehauen, Robust observer design
of linear ti m e -delay system s with para metric uncertainty [J ], Syste m s Contr ol Lett . , 2001, 42:303-312.
[作者简介]
于莉莉(1977. 1-) 女(汉族) , 山东东营人, 硕士研
究生在读, 工程师, 主要从事电厂设备故障在线监测与诊断;
姜 福(1975. 9-) 男(汉族) , 山东威海人, 硕士
研究生在读, 工程师, 主要从事电力生产自动化。