自适应动态双种群蚁群算法

摘要:基本蚁群算法容易陷于局部最优解是其较为突出的缺点。针对这一问题,文章提出使用双种群蚁群同时进行搜索。在迭代过程中,若判断出算法陷入可能局部最优时,则交换不同种群对应路径上的信息素,并且同时双向动态自适应调整信息素挥发系数的改进策略。通过信息素的震荡变化和挥发系数的自适应调整,扩大搜索空间,提高算法搜索的全局性。通过实验仿真,证明了此算法改进是可行和有效的。

关键词:蚁群算法;自适应;双种群;局部最优解;挥发系数

中图分类号:TP301文献标识码:A文章编号:1009-3044(2010)01-181-03

Adaptive Dynamic Dual Population Ant Colony Algorithm

RAO Yue-dong

(Wuhan University of Technology, Wuhan 430070, China)

Abstract: The prominent shortcoming of the basic ant colony algorithm is easily trapped into local optimal solution. Dual population searching at the same time strategy is proposed in this paper in order to solve this problem. In the iterative process, when the algorithm is trapped into a local optimum, then change the pheromone of the corresponding path of different populations. At the same time, bi-directional dynamic adjust adaptively the volatile coefficient of the pheromone. The concussion change of the pheromone and the adaptive adjustments of the volatile coefficient can expand the search space and improve the overall searching performance .It is proved that the algorithm is feasible and effective in the emulation experiments.

Key words: ant colony algorithm; adaptive; dual population; local optimal solution; volatile coefficient

蚁群算法(Ant Colony Optimization algorithm,ACO)是由意大利学者Marco Dorigo等人在20世纪90年代初通过模拟自然界中蚂蚁集体觅食的行为而提出的一种基于种群的启发式仿生类算法[1-2]。它是继遗传算法、神经网络、模拟退火等算法以后的又一种应用于组合优化问题的启发式搜索算法。蚁群算法最早成功应用于解决TSP问题,经过多年的研究与发展,蚁群算法已经成功运用于许多经典组合优化问题,如网络路由、机器人路径规划、车辆路径、图形着色等问题[3-6]。作为一种新兴的仿生优化算法,蚁群算法具有分布式并行计算、启发式搜索、鲁棒性强和易于与其他算法结合等优点,但搜索时间较长、收敛速度较慢、易陷于局部最优解等也成为其最为突出的缺点。近年来,众多学者对蚁群算法尝试了各种方法的改进,力求提高其收敛速度,扩大搜索空间,从而提高算法的寻优能力,改善算法的全局收敛性,使其能更好的应用于各个领域[7-8]。在分析算法的基本原理和大量的改进方法后发现,对信息素浓度的控制是改善算法性能的关键。对此,文章提出采用双种群蚁群进行同时迭代,在迭代过程中,如若发现算法陷入局部最优,则交换两种群对应路径上的信息素,通过信息素的震荡来扩大算法的搜索空间。同时,对于各个种群的信息素挥发系数,进行双向动态自适应调整,以提高算法搜索的全局性,使其解尽可能收敛于全局最优。

1 基本蚁群算法数学模型

为了能够清楚地理解蚁群算法的数学模型,本文借助了经典的对称TSP问题。设n表示TSP的规模即城市数量,m为蚁群中蚂蚁的总数目,dij (i,j=1,2,…n)表示城市i和城市j之间的距离,τij(t)表示在时刻t城市i和城市j之间的路径上的信息素浓度。在初始时刻各条路径上的信息素浓度相等,蚂蚁k(k=1,2,…m)在运动过程中,根据各条路径上的信息素浓度决定其转移方向,同时用禁忌表tabuk (k=1,2…n)来记录蚂蚁k当前己经走过的城市,集合随着tabuk进化过程作动态调整。在搜索过程中,蚂蚁根据各条路径上的信息量及路径的启发信息来计算状态转移概率[9]。Pijk(t)表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率,其表达式为:

式中:allowedk ={C-tabuk}表示蚂蚁k下一步允许选择的城市,α为信息启发式因子,反映了蚂蚁在运动过程中所积累的信息量在指导蚁群搜索中的相对重要程度,其值越大蚂蚁选择以前走过路径的可能性就越大。β为期望启发式因子,反映了启发信息在指导蚁群搜索过程中的相对重要程度,其大小反映了蚁群寻优过程中先验性、确定性因素的作用强度。ηij(t)为启发函数,表达式为ηij(t)=1/dij。

为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一步或者完成对所有n个城市的遍历后,要对残留信息进行更新处理, t+n时刻在路径(i,j)上的信息量可按如下规则进行调整:

式中,ρ表示信息素挥发系数,则1-ρ表示信息素残留因子;Δτij(t)表示本次循环中路径(i,j)上的信息素增量,Δτijk(t)表示第k只蚂蚁在本次循环中留在路径(i,j)上的信息量。

根据信息素更新策略的不同,Dorigo M提出了三种不同的基本蚁群算法模型,分别称之为Ant-cycle模型、Ant-quantity模型和Ant-density模型,其差别在于Δτijk(t)的求法不同。

Ant-cycle (3)

Ant-quantity (4)

Ant-density (5)

在蚁周模型中,Q表示信息素强度,它在一定程度上影响算法的收敛速度;Lk表示第k只蚂蚁在本次循环中所走路径的总长度。蚁量和蚁密模型利用的是局部信息,即蚂蚁完成一步后更新路径上的信息素;而蚁周模型利用的是整体信息,即蚂蚁完成一个循环后更新所有路径上的信息素,在求解TSP时性能较好,因此通常采用蚁周模型作为蚁群算法的基本模型。

2 自适应动态双种群蚁群算法

通过对基本蚁群算法仿真TSP问题结果分析发现,算法很容易陷入局部最优解。即搜索进行到一定程度后,所有的个体发现的解基本完全一致,出现停滞现象,不能再对解空间进一步搜索,导致可能无法找到全局最优解。产生这一现象的根本原因是局部路径上的信息素过量堆积,当许多蚂蚁选中同一条路径时,该路径中的信息量就会陡然增大,造成该路径和其他路径之间的信息素差异加大,从而使得后续的蚂蚁都会集中到这一条路径上,造成一种堵塞和停滞现象,表现在算法求解结果上就是导致算法早熟和局部收敛。因此,如何控制信息素浓度,在算法收敛速度和收敛空间之间找到平衡点就成为蚁群算法优化的关键。

定义:在算法迭代过程中,当求出的最优解出现连续ω(ω为常数)代相同时,则认为算法求解陷入可能局部最优。

2.1 双种群蚁群搜索

针对单一种群蚁群迭代时,由于信息素正反馈机制容易导致算法早熟这一现象,本文提出在算法运行初始阶段即采用双种群蚁群同时独立搜索,由于不同种群的初始参数环境设置不同,因此迭代过程中各条路径上的信息素分布也不会相同。当算法运行过程中,一旦判断出陷入可能局部最优时,则将两个种群相对应路径上的信息素交换。这样,通过信息素的反复震荡,扩大算法的搜索空间,在一定程度上改善算法的全局性。

2.2 双向自适应调整信息素挥发系数

根据公式2分析,信息素挥发系数ρ的大小直接关系各条路径上信息素的大小分布,从而直接影响到蚁群算法的全局搜索能力及其收敛速度。在基本蚁群算法中,ρ的值是固定的,若ρ的值选取不当,则处理问题规模较大时会使那些从来没有被搜索到的路径上的信息量减小接近于O,这不利于寻找更好的解,容易使算法陷入局部最优。对此,本文在双种群蚁群搜索的基础上,提出一种双向动态自适应调整信息素挥发系数的算法改进方法。基本思想是:对于两个独立种群的信息素挥发系数值ρ,其取值范围均设置在(0,1)之间。在算法运行初始阶段,将两个种群的ρ值分别一个设置为较小值(如ρ=0.1),一个设置为较大值(如ρ=0.9)。在算法迭代过程中,当出现求解陷入可能局部最优时,则分别自适应地动态调整两个种群的ρ值,调整方法是初始阶段ρ值设置较小种群的ρ值逐渐增大,而初始阶段ρ值设置较大种群的ρ值逐渐减小。这样,不同的种群通过ρ值的变化来扩大各自算法的搜索空间,避免搜索过度集中在某些较优的路径上,以此来寻找更优的路径。而对于不同种群来说,由于初始阶段的ρ值设置存在较大差异,而使得迭代过程中不同种群各自路径上的信息素存在较大差异,所以当算法陷入局部最优,两种群对应路径上的信息素交换的时候,才可能发生较大的震荡变化,从而进一步拓展算法的搜索空间,使搜索结果收敛于全局最优解。

因此,当算法迭代过程中出现求解陷入可能局部最优时,不同种群的ρ采用以下公式6进行自适应调整,设两个种群的挥发系数分别为ρA和ρB,并且ρA的初始值设为较小值,ρB的初始值设为较大值,则:

式中k表示迭代的代数,μ1,μ2分别为两个种群信息素挥发系数的动态改变参数,此时由于已设ρA初始值为较小值,ρB初始值为较大值,因此μ1应大于1,而μ2应小于1。根据实验结果分析,μ1取值在(1,1.5),μ2取值在(0.5,1)之间对算法优化较好。

同时,为了防止算法迭代过程中多次陷入可能局部最优,而使得挥发系数ρ值改变过大或过小造成局部路径上信息素差异过大的情况,可在算法运行初始阶段设定路径上信息素的最大最小值,这样不仅能提高收敛速度,更有利于搜索结果收敛于全局最优解。

2.3 算法编程步骤

step1 初始化两个种群参数:αA、βA、ρA、QA、mA、αB、βB、ρB、QB、mB、 NCmax,其中ρA∈(0,1)且取较小值,ρB∈(0,1)且取较大值;

step2 while NC

step3 将两种群mA、mB只蚂蚁分别随机放置于初始城市位置上,并且分别根据公式1计算选择概率选择下一个到达城市,完成各自的周游;

step4 分别记录A,B两个种群本次迭代的最佳(最短)路径;

step5 进入保优函数,比较两个种群本次迭代的最佳路径,取其短者为算法在本轮迭代的最佳路径;

step6 两种群分别根据公式2更新信息素,同时设定信息素的最大最小值;

step7 当算法陷入可能局部最优时,进入种群通信函数,交换A,B种群对应路径上的信息素;

step8 当算法陷入可能局部最优时,根据公式6动态改变ρA和ρB的值;

step9 两个种群的禁忌表TabuA、TabuB分别清零,NC=NC+1;

step10 循环结束;

step11 输出最优路径及最短距离。

3 算法仿真分析

本文采用MATLAB作为仿真工具,通过对TSP问题中Oliver30问题进行仿真实验,验证改进的自适应动态双种群蚁群算法比基本的蚁群算法具有更好的全局搜索能力和稳定性。实验中NC_max设定为200,ω设定为10,即当搜索结果连续出现10代相同时,则认为算法求解陷入可能局部最优。其他各项参数设置如表1所示:

表1 Oliver30问题实验参数 表2 仿真结果对比表

图1 本文改进算法最优解及其进化曲线图 图2 基本蚁群算法最优解及其进化曲线图

实验分别用本文改进的蚁群算法和基本蚁群算法针对Oliver30问题进行20次求解,得到三组数据(表2):算法运行的最优解(优化结果及进化曲线见图1和图2),运行20次仿真结果的平均解以及平均进化代数。根据实验结果可以看出,改进的蚁群算法在最优解和平均进化代数上均较基本蚁群算法有所提高,表明经改进的算法能够搜索到更优的解,全局收敛性得到了增强。并且从平均解上看,本文改进算法也较基本蚁群算法有较大提高,表明改进算法在稳定性上也得到增强。

4 结束语

本文提出双种群蚁群同时独立搜索,当算法迭代陷入可能局部最优时交换信息素,并且双向动态自适应调整信息素挥发系数的改进策略,在算法搜索的全局性和稳定性上都有了显著提高。在仿真实验过程中,我们发现不同种群参数的设置对优化结果的稳定性有较大影响,因此,如何合理配比参数,提高收敛结果的稳定性是我们下一步要继续研究的工作。

参考文献:

[1] Colorni A,Dorigo M,Maniezzo V,et al.Distributed optimization by ant colonies[A].Proceedings of the 1st European Conference on Artificial Life[C],1991,134-142.

[2] DorigoM,ManiezzoV,ColoniA.Ant system:optimization by a colony of cooperating agents[J].IEEE Transactions on Systems,Man,and Cyberneties一PartB,1996:26(1):29-41.

[3] SCHOONDERWOERD R.Ant-based load balancing in telecommunications networks[J].Adaptive Behavior,1996,5(2):169-207.

[4] 金飞虎,洪炳熔,高庆吉.基于蚁群算法的自由飞行空间机器人路径规划[J].机器人,2002,24(6):526-529.

[5] 侯立文,蒋馥.一种基于蚂蚁算法的交通分配方法及其应用[J].上海交通大学学报,2001,35(6):930-933.

[6] COSTA D, HERTZ A. Ants can colour graphs[J].Journal of the operational Research Society,1997,48(3):295-305.

[7] 郝晋,石立宝,周家启.求解复杂TSP问题的随机扰动蚁群算法[J].系统工程理论与实践,2002,(9):88-91.

[8] 胡勇.动态跃迁转移蚁群算法[J].计算机工程,2005,31(1):167-168.

[9] 段海滨.蚁群算法原理及应用[M].北京:科学出版社,2005.