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

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

控制理论与应用

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 加入方向引导后蚁群算法搜寻过程

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