基于改进蚁群算法的最短路径问题研究

《自动化技术与应用》２００９年第２８卷第６期

控制理论与应用

Control Theory and Applications

基于改进蚁群算法的最短路径问题研究*

张学敏,张 航

（中南大学 信息科学与工程学院,湖南 长沙 410075）

摘 要:最短路径问题是智能交通:交通网络分析中的一个重要问题。文章分析了基本蚁群算法在求解交通网络两点之间最短路径时

所出现的问题,并针对这些问题,在方向引导及信息素更新等方面对算法进行了改进。实验证明,改进后的方法较基本蚁群算法能准确快速地找到交通路网中两点间的最短路径,是切实可行的。

关键词:智能交通;最短路径;蚁群算法

中图分类号:TP301.6 文献标识码:A 文章编号:1003-7241(2009)06-0004-04

Research An Improved Ant Colony Algorithm of the

Optimal Routing Problem

ZHANG Xue-min, ZHANG Hang

( School of Information Science and Engineering, Central South University, Changsha 410075 China )

Abstract: Search for the shortest path in transportation network is one of the most important problem of ITS. This paper analyzes

the basic ant colony algorithm and presents an improved algorithm on the heuristic direction information and renewal ofpheromone. The results of the experimentation proved that the improved algorithm could find the shortest path moreaccurately and quickly than the basic algorithm, and it’s feasible.

Key words: intelligent transport system(ITS); shortest path; ant colony algorithm

1 引言

最短路径问题是智能交通中交通网络分析中的一个重要问题,也是一个研究热点。它是资源分配、路线设计及分析等优化问题的基础,具有重要理论意义和实际应用价值。有许多研究者曾对最短路径算法进行了大量的研究,并取得了很大的进展,提出了很多解决这类问题的方法。其中传统的算法有,Dijkstra算法、A*算法及其改进算法等等;还有近几十年来,通过模拟或揭示某些自然现象而产生了一些新颖的启发式智能算法,如遗传算法、模拟退火算法、禁忌搜索算法、蚁群算法等。

城市道路网中的交叉路口,连接两节点之间的边表示道路路线,并将路线的长度、通行时间、路况等属性表示为该边的权值,那么就可以把道路网络抽象为一个带权有向图。

给定一个带权有向图G为二元组G=(V,{E}),其中V是包含n个节点的集合,E是包含h条边(弧段)的集合,<i, j>是E中从节点i至j的边,wij是边<i,j>的非负权值。设S,T 分别为V中的起始节点和目标节点,则最优路径问题就是指在带权有向图G中,寻找从指定起始节点到目标节点的一条具有最小权值总和的路径。

2 交通最短路径问题描述

城市道路网有道路路线、交叉路口等物理属性,同时也具有路线长度、通行时间、路况等各种其它逻辑属性。用节点来表示

3 蚁群算法的基本原理及存在的问题

蚁群算法就是受蚂蚁觅食行为的启发,以人工蚂蚁模拟真实蚂蚁行为来求解组合优化问题的方法。在20世纪90年代初期,由意大利学者Dorigo Macro等首先提出[1] 。其原理在于[5],蚂

＊基金项目：湖南省科学技术与科技计划（编号２００６ＧＫ３１３０）；湖南省自然科学基金奖资助项目（编号０５ＪＪ３０１２１）收稿日期：２００８－１１－１０

T蚁在所经过的路径上留下一种称为信息素的挥发性分泌物,在觅食过程中蚂蚁能够感知这种物质的存在及其强度,并以此来指导

控制理论与应用

Control Theory and Applications

《自动化技术与应用》２００９年第２８卷第６期

自己的运动方向,同时它们倾向于朝着信息素浓度高的方向移动。信息素浓度越高的路径,被选择的机会就越多,蚂蚁在其上留下的信息素就更多,而更多的信息素又能吸引更多的蚂蚁,从而形成一种正反馈。通过这种正反馈,大部分的蚂蚁最终都会走上同一条最优路径。

由蚁群算法的基本原理可以得出,蚁群算法是一类基于多主体的智能算法,各主体之间通过相互协作来更好地适应环境。蚁群算法利用了正反馈原理,具有很强的发现较好解的能力。然而当利用蚁群算法来求解交通网络中的最短路径时,将发现存在如下的问题:

(1) 由于在基本蚁群算法中没有方向引导,导致搜索没有方向性,使得搜索过程中出现“之”字形路径,影响了搜索的速度。

(2) 因为算法搜索过程中的概率性以及正反馈作用,有时容易陷入局部最优解,即当搜索循环到一定次数后,由于局部最优解产生的信息素浓度的增加,造成了所有搜索都趋于一个局部最优解。

受蚁群算法的启发,本文充分利用蚁群算法智能搜索、群体之间相互协作等优点,结合交通最短路径问题自身的特点,针对上述两个问题,提出了一种改进的交通最短路径算法。

mk

τijt+ t=ρ τijt+1 ρ ∑ τij (2)

k=1

()()()

经过一段时间△t后,蚂蚁完成一次循环,以前留下的信息素将逐渐挥发,用参数ρ表示信息素挥发的程度,ρ是一个取值范围在0～1的常数,△τkij表示第k只蚂蚁在本次循环中留在路径ij上的信息素的增量。M.Dorigo曾提出三种信息素增量的算法[3]:蚁周模型(Ant-Cycle system)、蚁密模型(Ant-Density system)、蚁量模型(Ant-Quantity System)。这三种模型的区别在于后两种模型中利用的是局部信息,而前者利用的是全局信息。有研究表明蚁周模型在求解TSP问题时有较好的表现[2,4]。

在蚁周模型(Ant-Cycle system)中:

τkij=

QLk

0

如果蚂蚁k在本次循环中经过路径(i,j)

否则

(3)

这里,Q为一个常量,Lk为蚂蚁k在本次走过的路径所花费的总代价。

初始化时,将m个蚂蚁放置在起始节点上,赋予每条边上的信息素浓度τij(0)=C(C为常数)。每只蚂蚁的禁忌表的第一个元素为起始节点。当蚂蚁们完成了一次完整的寻径过程后,利用式(2)计算并更新每条边上的信息素浓度。然后开始新一轮的循环。当循环的次数达到事先定义好的最大循环次数时或者所有的蚂蚁都选择了同一条路径时,整个程序终止。

4 算法的实现与仿真

4.1 基本蚁群算法描述

给定n个节点的城市道路网络,人工蚂蚁数量为m,这些蚂蚁具有以下特征:

(1) 根据信息素浓度和启发式信息,用相应的转移概率选择下一个节点。

(2) 将已经走过的节点放入禁忌表中,禁忌表里的节点将不再被选择为下一个节点。

(3) 完成一次循环后,更新走过的路径上的信息素。蚂蚁选择下一个节点的转移概率为[2]:

áâ

ôij(t)][çij(t)][ ∑[ô(t)]á[ç(t)]â

Pij(t)= isis

s∈allowedk 0

4.2 算法的改进

在本节中将针对第二节中描述的基本蚁群算法在求解交通最短路径问题时所出现的两个问题,对算法进行改进。在转移规则中引入了方向引导信息,解决搜索的方向性问题;两个更新规则充分利用蚁群之间相互协作的特点,解决搜索收敛于局部最优解的问题,提高搜索的准确性。

4.2.1 转移规则

在改进的算法中,蚂蚁选择下一节点的转移概率仍然用式(1)计算,针对第二节中提到的搜索没有方向性的问题,对式(1)中的能见度ηij进行了改进,此处取ηij=1/(1+wij*θjit),其中wij

j∈allowedkotherwise

(1)

为弧<i,j>的非负权值,θjit为节点i、j和终点t所组成的∠jit的大小,此处称其为方向引导信息,取值范围为0~π。从ηij的计算式中可以得出,wij和θjit越小ηij的值就越大,综合式(1)可以看出搜索能够优先考虑那些路径权值较小、信息素浓度大且指向终点的路径,从而保证了优先搜索可能性较大的路径,加强了搜索的方向性。

式中τij (t)为t时刻路径(i,j)上的信息素浓度;allowedk={0,1,…,n-1}-tabuk表示蚂蚁k当前能选择的节点集合;tabuk为禁忌表,它记录蚂蚁k己走过的节点;α为信息素启发因子,表示信息素轨迹的相对重要性;ηij(t)为t时刻的能见度,反映由节点i转移到节点j的期望程度,其中ηij(t)=1/dij,dij为经过路段(i,j)所需的花费;β为期望启发因子,表示能见度的相对重要性。

信息素更新[2,6]:

4.2.2 信息素局部更新规则

在信息素更新过程中,当蚂蚁k完成一条搜索路径后,在其经过的路段上按照局部更新原则更新该路段的信息素浓度。局部更新原则由式(4)给出:

τ'ij=τijk

τij

(4)

| 5

《自动化技术与应用》２００９年第２８卷第６期

控制理论与应用

Control Theory and Applications

其中τij为路段<i,j>上更新前的信息素浓度,τ‘ij为更新后的信息素浓度,△τkij 的计算参考蚁周模型(Ant-Cyclesystem),即式(3),将Lk改为Wk——蚂蚁k本次所经路段的权值总和。为了避免某条路段因为信息素浓度过低而不能被蚂蚁选择,每条道路上的信息素浓度设立取值的下限τmin,当某路段上的信息素浓度小于下限τmin时,则将其强制更正为τmin。

局部更新的引入,能够抑制某一条路径上的信息素的过度累积。通过调节式（3）中的Q,能够适当调节同一条路径被其他蚂蚁搜索的概率,从而达到扩大搜索范围,尽可能遍历更多的路径,减少陷入局部最优解的可能性。

Step5:如果已经连续20轮搜索后没有更新最优路径,则循环结束,输出最短路径及其长度;否则将所有蚂蚁放回起始点,返回Step2。

4.3 算法的仿真

4.2.3 信息素全局更新规则

当所有的蚂蚁都完成一次搜索后,如果在本轮搜索中产生了比此前更优的路径,则对本轮搜索中产生的当前最优路径及与当前最优路径中各节点相连的路段的信息素浓度按式(5)所示的全局更新原则进行更新;否则不更新。

此处与一般的更新方法不同的是:在更新时同样更新了与当前最优路径相连的路段的信息素浓度。这是因为,如果当前最优路径还不是全局的最优路径,则全局最优路径出现在当前最优路径的附近的可能性将较大。而当无法找到更优路径时,选择不进行全局更新,有利于在较大范围改变搜索的方向,从而搜索更多的路径。

'

τij=τij+σ* τij

τ

(5)

(6)

图1 无向带权网络

本文利用图1所示的无向带权网络来进行算法的分析与仿真,可将其视为弧段正反向权值相等的有向带权网络。该网络与我们当前实际的城市交通网络较为接近。各路段的权值为走完该路段所需的时间,单位为(min),各路段的权值均已标示在路段上,此处需要寻找一条从节点1到节点30的最短路径。在此图中存在唯一的最优路径:

1→7→13→19→25→26→27→28→29→30;总权值:11min。

经过多次实验,算法的各参数设置为:蚂蚁数m=5,α=1.0、β=0.1、σ=5.0、Q=0.8,初始信息素浓度τij(0)=0.6、τmin=0.1,算法有较好的效果。由于算法本身的随机性,此处给出的实验结果也是随机产生的。

图2给出了仅加入方向引导参数后的蚁群算法的一次收敛于局部最优解的搜索过程。从图中可以看出,加入方向引导信息后,走完全程的最大花费时间不超过30min,比起基本蚁群算法求解中出现的耗时超过60min的路径,加入方向引导信息后,蚂蚁少走了不少弯路,提高了搜索效率。从图2中也可以看出,由于信息素更新的原因,算法可能会收敛于局部最优解。

ij

1

=

W0

gb

如果(i,j)∈当前最优路径或与之相连

否则

同样τij为路段<i,j>上更新前的信息素浓度,τ‘ij为更新后的信息素浓度,σ为信息素更新参数;Wgb为当前最优路径的总权值。比较式(3)和(6)可得,在式(3)中着眼每一只蚂蚁对其所走过的路径上的信息素的作用,而在式(6)中关注的是与当前最优路径相关的全局信息。令Q=1,当蚂蚁k所走过的路径为当前最优路径时△τij=△τkij。此处将式(3)中的Q提取出来表示为式(5)中的σ,这样就可以通过调节Q和σ的大小来分别调节信息素局部更新和全局更新过程。

4.2.4 算法执行步骤:

Step1:初始化各参数,将所有蚂蚁放置于起始点。Step2:取第k只蚂蚁,根据式(1)计算转移概率,确定下一个节点j,并更新禁忌表。

Step3:如果j为终点,则按局部更新规则更新路径的信息素浓度,且如果所得的路径较当前最优路径优,则更新当前最优路径;否则返回Step2。

Step4:如果所有蚂蚁都完成了本轮搜索,则按全局更新规则进行信息素更新;否则,取下一只蚂蚁,返回Step2。

T图2 加入方向引导后蚁群算法搜寻过程

在实验中利用改进的蚁群算法求解当前问题,每次执行均

控制理论与应用

Control Theory and Applications

《自动化技术与

应

用

》２

０

０

９

年第

２８卷第６期

能准确地找到全局最优路径。图3给出了改进算法的一次搜索过程,其中实心圆点图案表示当前求得的最优路径,空心圆圈为单轮搜索中求得的最短路径。从图中可以看出,在方向引导以及信息素更新的作用下,算法准确地找到了全局最优路径,并且在信息素更新的作用下,在找到最优路径以后,还在不断探索新路径。这充分说明了,改进算法在新的信息素更新规则的作用下,较基本蚁群算法遍历了更多的路径,从而更可能找到全局最优解。

短路径。

参考文献:

[1] COLORM A,DORIGO M,MINIEZZO V.Distributed op-timization by ant colonies[C].Proceeding of the First European

Conference on Artificial Life.Paris France:Elsevier Publishing,1991:134-142.

[2] DORIGO M,GAMBARDELLA L M.Ant colony system:a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation,1997,1(1):53-66.

[3] ZHONGZHEN YANG,BIN YU,CHUNTIAN CHENG.A parallel ant colony algorithm for bus network optimization[J].Computer-Aid Civil and Infrastructure Engineering,2007,22(1):44-55.

[4] ATTIRATANASUNTHRON NATTAPAT,FAKCHAROENPHOL JITTAT.A running time analysis of an antcolony optimization algorithm for shortest paths in directed acyclicgraphs[J].Information Processing Letters,2008,105(3):88-92.

[5] 夏立民,王华.基于蚁群算法的最优路径选择问题的研究[J].计算机工程与设计,2007,28(16):3957-3959.

[6] 程世娟,卢伟.基于蚁群算法的最短路径搜索方法研究[J].科学技术与工程,2007,7(21):5706-5708.

图3 改进算法搜寻过程

5 结束语

本文在启发信息以及信息素更新等方面对蚁群算法进行了改进。改进算法不仅能优先搜索可能性较大的路径,而且能够有效扩大蚂蚁的搜索范围,避免在搜索过程中陷入局部最优解。试验证明,与基本蚁群算法相比,改进算法能够准确快速地找到最(上接第3页)

仿真中,隐含层传数为tansig函数,输出层为线性函数purelin,用trainlm方法对网络进行训练,模型参数在训练的权值系数中。为了加快训练时间,考虑实际工艺条件,由一次训练后接近实际系统的权值和阈值作为设计模型的初始值。由曲线可知,用神经网络进行辨识结果温度误差在1.5度之内。系统采样时间为2.5s,而经过初始权值和阈值选择之后再进行训练测试的时间为1.276s。

[1] 张殿华,刘文红,刘相华,王国栋,张志强,张中平,焦景民.

热连轧层流冷却系统的控制模型及控制策略[J].钢铁,2004,39(2):43-47．

[2] 彭良贵,刘相华,王国栋.热轧带钢层流冷却的控制策略及其应用[J].钢铁研究学报,2005,17(6):5-9．

[3] 任雪梅,高为炳.基于神经网络非线性系统辨识和控制的研究[J].控制理论与应用,1995,12(2):147-153．

[4] NICHOLAS.S.SAMARAS,SIMAAN,M.A.Novel ControlStructure for Runout Table Coiling Temperature Control[J]. SteelTechnology.2001,(6):55-59．

[5] 刘国栋.用神经网络辨识非线性大滞后系统的研究.信息与控制,2000,29(3):225-229．

[6] CHEN,S.J.,BISWAS.S.K.,HAN.L.F.,SATYANARAYANA.A.Modeling and analysis of controlled coolingfor hot moving metal plates[J].Monitoring and control for manu-facturing processes,American society of mechanical engineers,1990,44(6):465-473．

作者简介：张学敏（１９８３－），男，硕士研究生，研究方向：智能控制、智能交通等。

5 结束语

针对层流冷却系统精冷区非线性的特点进行基于人工神经网络的辨识,仿真结果表明,用改进的BP神经网络用于系统辨识有很高的拟和程度,能很好的描述非线性系统过程,获得了复杂的非线性处理能力。且改进算法避免了其陷入局部最小的缺点。此系统的层流冷却控制中,下一步的工作是对其进行合理的控制,利用辨识的过程对象进行控制,以达到更高的控制精度。

参考文献:

作者简介：李莉美（１９８２－），女，工学硕士，研究方向：控制理

论与控制工程。

| 7

本文来源：https://www.bwwdw.com/article/le64.html