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

控制理论与应用

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