基于信息素改进的蚁群算法①

孙改平,刘春梅

(1.北京工业大学,北京 100124;2.华北科技学院,北京 东燕郊 101601)

基于信息素改进的蚁群算法①

孙改平1,2②,刘春梅1,2

(1.北京工业大学,北京 100124;2.华北科技学院,北京 东燕郊 101601)

蚁群算法是一种优秀的启发式算法,具有较强的鲁棒性。针对基本蚁群算法在求解过程中容易出现收敛时间过长以及容易陷入局部最优的不足。本文提出了一种改进的蚁群算法,该算法通过在信息素挥发系数上增加一个收敛函数,加快了收敛速度;通过信息素增量与优秀路径选择相结合,引导算法收敛到最优路径,实验结果表明,改进后的算法在收敛速度和全局寻优能力上有了较大的提高。

蚁群算法;信息素挥发系数;信息素增量

引言

蚁群算法(Ant Colony Algorithm,简称ACA)是20世纪90年代初由意大利学者Dorigo等人首先提出的一种新的启发式优化算法[1],是目前国内外启发式算法研究的热点和前沿课题,它已被成功地应用于求解TSP问题[2]、二次分配问题(QAP)[3]、车辆路径问题(VRP)[4]等NP完全问题。实验表明,蚁群算法在求解复杂优化问题方面具有较强的优越性和广阔的应用前景,但是由于蚁群算法也存在一些缺点,比如：收敛时间过长和容易陷入局部最优等。为了克服这些缺点,不少学者提出了许多改进的蚁群算法。例如：王颖,谢剑英[5]等指出的通过自适应地改变算法的挥发度等系数,在保证收敛速度的条件下提高解的全局性。赵宝江,李士勇[6]提出了一种基于自适应路径选择和信息素更新的蚁群算法,以求在加速收敛和防止早熟、停滞现象之间取得很好的平衡。朱立军,杨中秋[7]提出了提出一种动态调整路径上信息素的上下界,使路径上信息素永远保持在一个被允许的范围内,从而避免使算法过早陷入局部最优解等。在此基础上,本文提出了一种改进的蚁群算法,通过在信息素挥发系数上增加一个收敛函数,根据解的分布情况进行信息素的更新,从而调整各路径上的信息素强度,从而避免了局部收敛,提高全局搜索能力;通过信息素增量上的差别来增大优秀路径和其它路径之间的信息素量的差距,引导算法收敛到最优路径,同时加快算法的收敛速度。

1 基本蚁群算法模型

为了能够清楚地理解蚁群算法,以经典的TSP问题为例说明蚁群算法的基本模型。n个城市的TSP问题就是寻找通过n个城市各一次且最后回到出发点的最短路径。在模拟实际蚂蚁的行为时,为了表述方便,引进如下记号：设有n个城市组成的集合C,m只蚂蚁,用dij(i,j=1,2,…, n)表示城市i和城市j之间的距离,ij(t)表示t时刻在城市i和城市j之间的路径上残留的信息素强度。初始时刻,各条路径上信息素强度相等,设ij(0)=const(const为常数)。蚂蚁k(k=1, 2,…,m)在运动过程中,根据各条路径上的信息素强度决定转移方向,同时用禁忌表tabuk(k=1, 2,…n)来记录蚂蚁k当前已走过的城市,集合tabuk随着进化过程作动态调整。(t)表示在t时刻蚂蚁k由城市i转移到城市j的状态转移概率,其表示式为

其中,allowedk={C-tabuk}表示蚂蚁k下一步允许选择的城市;α为信息启发式因子,β为期望启发式因子,ηij(t)为启发函数,是路径长度的倒数,表示式为ηij(t)=1/dij。为了避免残留信息素过多引起残留信息淹没启发信息,在每只蚂蚁走完一个循环后,要对残留信息进行更新处理。其表达式为

式中Δ τij(t)表示蚂蚁k在本次循环中在城市i和城市j之间的路径上留下的信息素增量,其表达式为

式中：Q是信息素强度,它影响算法的收敛速度;Lk是蚂蚁k在本次循环中所走路径的长度。

2 蚁群算法的改进

在基本蚁群算法中,由于信息素挥发系数的存在,使那些从未被搜索过的路径上的信息量减小到接近于0,从而降低了算法在这些路径上的搜索能力,反之,当某条路径中信息素较大时,这些路径中的信息量增大,搜索过的路径再次被选择的机会就会变得较大,这也影响了算法的全局搜索能力,在此通过在信息系挥发系数上增加一个收敛函数来改变信息素值,其表达式为

其中ψ(m)是一个与收敛次数m成正比的函数,收敛次数m越多ψ(m)的取值越大,如：

ψ(m)=连续收敛次数m/ct

这里ct为常数,这样根据解的分布情况进行信息素的更新,从而调整各路径上的信息素强度,使蚂蚁既不过分集中也不过分分散,从而避免了局部收敛,提高全局搜索能力。

在基本蚁群算法中,所有路径的更新方法都是一样的,没有体现出优秀路径与包括较差路径在内的其它路径在信息素量增加上的区别,尤其是当路径长度较长时,每次迭代过后各条路径上的信息素量的增量的差别并不明显,因此各条路径上的信息素量在一定的时间内并没有明显的差距,这会降低信息素对蚂蚁寻优的引导作用,导致蚂蚁对下个节点的选择主要受到路径长度的影响,这种情况下,蚂蚁移动的盲目性大大增加,这在很大程度上降低了算法的收敛速度,同时各条路径上信息素量差别的不明显,使得优秀路径很难脱颖而出,而较差的路径却很容易干扰蚂蚁的寻优,导致算法收敛于局部最优。

为了通过信息素增量上的差别来增大优秀路径和其它路径之间的信息素量的差距,引导算法收敛到最优路径,同时加快算法的收敛速度。根据路径的优秀程度的不同,在此对信息素的增量Δ τij(t)进行改进,其表达式为

式中,BestL为从开始至当前代所找出的最优路径值,Lk为当前代中蚂蚁k所找出的路径值。

这种改进可以快速增加优秀路径上的信息量,而对非优秀路径上的信息素增加则不明显,每次迭代后,每条路径都会根据本身值的优劣来获得相应的信息素增量,这样,越优秀的路径每次迭代后都会获得比较多的信息素增量,而比较差的路径的信息素增量则相应的较少,多次迭代后优秀路径和较差路径上的信息素量就有会一定差别,这有利于排除较差路径的干扰,大大加快了算法的寻优速度,有利于算法快速收敛到最优值。

改进蚁群算法的实现步骤为：

(1)参数初始化

令时间t=0,循环次数Nc=0,设置最大循环次数Ncmax,将m只蚂蚁随机分配到n个城市,信息量τij(0)=const,初始时刻τij(0)=0,其中const为常数。

(2)循环次数Nc=Nc+1;

(3)蚂蚁数目k=k+1;

(4)蚂蚁根据公式(1)计算的概率选择城市j并前进;

(5)修改禁忌表,将蚂蚁移动到新的城市;

(6)若城市未遍历完,则跳转到(4)继续执行;

(7)若k＜m,则跳转到(3)继续执行;

(8)根据改进公式(5)(6)更新每条路径上的信息量;

(9)如果蚂蚁全部收敛到一条路径或循环次Nc＞Ncmax,则结束,并输出程序结果,否则清空禁忌表并跳转到(2)。

3 仿真实验结果

为了验证改进算法的有效性,通过对TSP20、TSP30、TSP50问题进行实验仿真,参数设置为α=1,β=5,Ncmax=400,n=100,m=100,平均运行50次作为仿真结果。本文改进的蚁群算法与基本蚁群算法比较结果见表1。

表1 改进的蚁群算法与基本蚁群算法比较

4 结语

本文针对基本蚁群算法收敛时间过长和容易陷入局部最优的不足,通过对信息素挥发系数和信息素增量的改进,从实验结果来看,较好地解决了基本蚁群算法在解决TSP问题是容易陷入局部最优的问题,提高了算法的收敛速度,增强了算法的全局寻优能力。

[1] Dorigo M,Maniezzo V,Colorni A.Ant system：optimization by a colony of cooperating agents [J].IEEETransactions onS MC,1996,26 (1)：12-41

[2] DorigoM,Gambardella L M.Ant colony system：a cooperative learning approach to the traveling sales man problem[J].IEEE Transactions on Evolutionary Computing,1997(1)：53-66

[3] Talbi E G,Roux O,Fonlupt C,et al.Parallel ant colonies for the quadratic assignment problem [J].Future Generation Computer Systems,2001, 17(4)：441-449

[4] BullnheimerB,Hartl R F,Strauss C.An improved ant system algorithm for the vehicle routing problem[J].Annals of Operations Research,1999 (89)：319-328

[5] 王 颖,谢剑英.一种自适应蚁群算法及其仿真研究[J].系统仿真学报,2002,(1)：31 -33

[6] 赵宝江,李士勇,金俊.一种基于自适应路径选择和信息素更新的蚁群算法[J].计算机工程与应用,2007,43(3)：12-15

[7] 朱立军,杨中秋.一种引入信息素上下界自适应机制的蚁群算法[J].沈阳化工学报,2009 (3)：65-68

Ant Colony Algorithm Based on Pheromone Improving

SUN Gaiping1,2,L IU Chunm ei1,2

(1.BeijingUniversity of Technology,Beijing 100124
2.North China Institute Science and Technology,Yanjiao Beijing-East 101601)

AntColonyAlgorithm is an excellent heuristic algorithm and has strong robustness.The algorithm easily gets into long convergence time and may be trapped in a local optimum.The papermakes some improvement on adding a convergence function to the pheromone volatilization coefficients,improving the convergence rate;and on guiding the algorithm converges to the optimal path by being combined pheromone incrementwith the outstanding routing.The experiment results indicate that the improved algorithm not only increases the convergence rate and also enhances the ability of searching the global optimal solution.

ant colony algorithm;the pheromone volatilization coefficients;the pheromone incremental

TP301.6

A

1672-7169(2010)01-0076-03

2009-12-27

孙改平(1969-),女,山西阳泉人,华北科技学院副教授,北京工业大学在读硕士研究生,研究方向：计算机网络和数据库。