基于自适应蚁群算法的公交查询算法设计

摘要:公交查询系统的设计可以解决在庞大的公交网络中公交路线选择的问题。该文将利用蚁群算法设计公交查询系统的核心算法,即如何搜索出一条从起始站点到目的站点的最优路径。该文将公交网络按直达关系抽象成有向图,用蚂蚁在各个节点之间的行走代表公交线路的选择。针对基本蚁群算法收敛速度和早熟之间的矛盾,提出了自适应信息素更新的蚁群算法,并设计了迟滞更新信息素的方法,使得运算量大大减少。

关键词:公交;换乘;自适应蚁群算法

中图分类号:TP18文献标识码:A文章编号:1009-3044(2009)34-9799-02

Bus Travel Transit Path Query Algorithm Designing Based on Adaptive Ant Colony Algorithm

SUN Li-na1, ZHANG Li1, WANG Lin2

(1.Minsheng College, Henan University, He'nan 475004, China; 2.School of Humanities and Social Science, Beijing Institute of Technology, Beijing 100081, China)

Abstract: Bus travel transit path query system can deal with the problem of searching the best routine among the huge and complex bus net. This paper applies Ant Algorithm on designing the kernel of Bus travel transit path query system, which is how to search out the best routine from start stop to end stop. We transform city bus net to directed graph based on nonstop relation and use the walk of ant among nodes to denote the selection of routine. To solve the contradictory between convergence and precocity in the basic ant colony algorithm, an adaptive updating pheromones ant colony algorithm is presented. We also design a delayed updating pheromones method reducing the computational complexity sharply.

Key words: bus; walk; ant algorithm

这些年来,北京市的公交线路已达800条以上,使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。为此需要设计公交线路选择问题的自主查询计算机系统以方便人们的出行选择。

1 蚁群算法

蚁群算法是近年来兴起的高效的启发式算法[1-2]。蚁群算法(Ant Colony Algorithm, ACA)是M.Dorigo等人于1991年提出的。经观察发现,蚂蚁个体之间是通过一种称之为信息素(pheromone)的物质进行信息传递的。在运动过程中,蚂蚁能够在它所经过的路径上留下该种信息素,而且能够感知信息素的浓度,并以此指导自己的运动方向,倾向于朝着信息素浓度高的方向移动[3]。

基本蚁群算法的程序大致如下:

Step 1:参数初始化。循环次数N=0,设置最大循环次数Nmax,将G个蚂蚁分别放在起始站点上,初始化有向图的每条边(Si,Sj)的信息量,将每个蚂蚁的禁忌表置为空。

Step 2:循环次数N=N+1;

Step 3:按照一定的规则为每个蚂蚁选择下一个节点。

Step 4:修改该蚂蚁的禁忌表;

Step 5:若还有蚂蚁没有选完,转Step 3;

Step 6:根据每个蚂蚁走过的路径,由此更新每条路上的信息量;

Step 7:若循环次数N>Nmax结束程序,否则转Step 2。

基本蚁群算法有诸多的缺点,如收敛速度慢,容易出现早熟,停滞现象。许多学者[4-6]提出自适应蚁群算法来克服基本蚁群算法的缺点。在利用自适应蚁群算法之前,假设我们已经知道每条公交线路经过的站点信息,对站点进行编号,编号为i的站点记为Si(i=1,…,m),用Tij表示站点Si到站点Sj的直达关系,Tij=1表示从站点Si到站点Sj有公交车直达,否则Tij=0(在这里,规定Tii=0),并用Di表示站点Si可以直达到的站点编号的集合,即满足Tij=1的j的集合。将公交网络抽象成有向图,节点表示站点,当Tij=1时,节点i有指向j的有向弧。并用Start和End分别表示要查询的起始站点和目的站点的编号。

为每个蚂蚁建立一个标志位,标志它是否到达目的站点,初始化为0,并且为每个蚂蚁建立一个禁忌表,记录它走过的站点,初始化为空。用τij(t)表示t时刻弧(Si,Sj)上的信息量,初始化为同一常数。

1.1 选择站点

假设进行到第k+1步,已经知道前k个站点,要为每只蚂蚁选择第k+1个站点,设其中一只蚂蚁经过的站点依次是Sstart,Si1,…,Sik,按下列规则产生第k+1个站点:

若Tik,End=1,即Sik可以直达到SEnd,则令Sik+1=SEnd,并且将该蚂蚁的标志位置为1。

若Tik,End=0,按下列公式计算转移概率

(1)

其中t表示时间,这里以一次完整的迭代为一个时间步长。α与β分别表示蚂蚁在运动过程中所积累的信息量及启发式因子在蚂蚁选择路径中所起的不同作用。ηij(t)是t时刻从站点i到j的启发因子,显然,出度数大的节点可以直达的站点多,为了能尽快搜索到目的站点,应尽可能让蚂蚁往节点度数大的节点运动,所以令ηij (t)=(di+dj)/2,(i,j=1,…,m)。运用转赌规则求第k+1个站点。设置一个上限来限制蚂蚁的选择站点数目。设这一上限为K,当k

1.2 信息素的自适应更新

在基本蚁群算法中,当所有的蚂蚁选择完后,需要更新信息量:

(2)

其中ρ表示信息素挥发系数,因为信息量τij(t)会随着时间的流逝衰减。

在基本蚁群算法中,加速收敛与防止早熟,停滞现象是一对矛盾。这里面信息素的挥发系数ρ的大小是平衡两者的关键。ρ表示信息的消逝程度,而1-ρ就表示信息的残留比例。当ρ比较大时,信息挥发得快,使得那些未被搜索到的路径上的信息素迅速的降为0,下一次的迭代蚂蚁就不会走这些路径,算法会很快的收敛,但全局搜索能力比较弱,会出现早熟,停滞现象。当ρ比较小时,路径上的残留信息占主导地位,信息的正反馈比较弱,算法的随机性和全局搜索能力比较强,但收敛的速度就会慢。因此可以引入动态的ρ来平衡收敛速度与算法的全局搜索能力。令ρ(0)=ρmax。

ρ(t)∈[ρmax,ρmin],因此(1)式变为:

(3)

其中:

Δτgij(t)表示第g只蚂蚁在本次迭代中在站点i和j之间留下的信息量。关于Δτgij(t)的计算方法,则可以按下式计算

(4)

其中Q为常数,函数f(v)表示对路径v的评价,它可以根据不同的目标而设定。

假设求出的路线v是Sstart-Si1-…-Sik-SEnd,其中‘-’表示直达关系,可以按下列方法找出最小换乘数目和途径的站点总数:

Step 1:count1 = 0,它用来记录换乘次数,count2=0,用来记录途径的站点总数。Ori = Start,用来记录换乘之后的出发点,Fnal=i1。

Step 2:判断Fnal是否为End,

如果是,则输出count,退出。

如果不是,执行下一步。

Step 3:用Fnal+1表示路线v中Fnal的下一站,比如Fnal=i1,则Fnal+1=i2。判断Tori,Fnal是否为1,如果为1,则Fnal = Fnal+1,如果为0,则count1 = count1+1,count2=count2+Ori到Fnal-1之间所有直达车的所经过的最短站点数。Ori = Fnal,Fnal = Fnal+1。

判断之后转Step 2

Step 4:输出count1,以及count2=count2+Ori到End之间所有直达车的所经过的最短站点数。

统计表明人们出行首先考虑的是换乘的次数,其次是途径的站点数,我们把换乘次数最少,途经站点数最少的乘车路线称为最优的。所以可以令f(v)=c*2count1*count2,c是常数。F(v)的值越小则该条路径越好,由(4)算出来Δτgij(t)越大,信息的正反馈越强。

在实际操作时,笔者发现当公交站点数m比较大时,信息素矩阵的规模为m2,每次按(3)式更新信息素矩阵都要耗费很多的时间。通过对公交网络的特点考察发现,在寻找起始站点与目的站点之间的路径时,蚂蚁途径的站点相比于m来说是很小的一部分,每次更新信息素矩阵有绝大部分路径直接按(3)式挥发了,而只有少数路径需要加上信息素的增量。笔者设计了迟滞更新信息素的方法来减少运算,具体来说为每个τij增加一个标示πij,πij=k表示τij更新到了第k次迭代。每次更新路径τij时,若当前迭代产生的Δτij,则不需要更新,否则检查当前迭代次数N是否与πij+1吻合,如果吻合,则按(3)式更新,若不吻合,首先将τij乘以ρ(πij+1),再乘以ρ(πij+2)等等直到ρ(N-1),然后按(3)式更新。每次更新完之后,将πij置为当前的迭代次数。另外,当按(1)式计算转移概率时,对用到的τij需要先检查πij是否为当前的迭代次数N-1,如果是,则可以直接用来计算转移概率,如果不是,需要先按上述方法更新τij至N-1代。

该算法的主要思想是将选择公交车的过程视为动态规划,因为走完路线v的方法有很多种,所以最后花费的费用也不一样。根据动态规划的最优策略原则:无论过去的状态和决策如何,对前面的决策所形成的当前状态而言,余下的诸决策必须构成最优策略。

2 结束语

与公交查询的其它方法相比,本文所设计的方法具有更快的速度,更好的寻找最优解的能力以及更广泛的适应范围。究其原因主要有两点,第一,启发式的蚁群算法能避免隐式枚举带来的复杂度。第二,自适应蚁群算法使得能够兼顾收敛速度与避免早熟。

参考文献:

[1] 闫小勇,牛学勤.公交网络多路径选择启发式算法研究[J]. 城市交通,2005(3):23-26.

[2] 李文勇,王炜,陈学武.公交出行路径蚂蚁算法[J].交通运输工程学报,2004,4(4):102-105.

[3] 段海滨,蚁群算法原理及其应用[M].北京:科技出版社,2005:34-37.

[4] 赵宝江,李士勇,金俊.给予自适应路径选择和信息素更新的蚁群算法[J].计算机工程与应用,2007,43(3):12-14.

[5] 徐晓华,陈峻.一种自适应的蚂蚁聚类算法[J].软件学报,2006,17(9):385-389.

[6] 钱雪忠,丁秀明,郭庆北.基于自适应蚁群优化的供应链调度算法研究[J].微计算机信息,2007,23(10):226-228.