基于拓展性和魔方变换的自适应蚁群算法

第38卷第4期 中国矿业大学学报 V ol.38N o.42009年7月 Jour nal of China U niversit y of M ining &T echnolog y Jul.2009

收稿日期:2008-04-24

基金项目:国家自然科学基金项目(60775044)作者简介:马小平(1961-),男,四川省绵阳市人,教授,博士生导师,工学博士,从事自动控制和信息融合等方面的研究.E -mail:xpma@https://www.doczj.com/doc/5b17014171.html, Tel:139********

基于拓展性和魔方变换的自适应蚁群算法

马小平1

,金 珠

1,2

(1.中国矿业大学信息与电气工程学院,江苏徐州 221116;2.中国矿业大学计算机科学与技术学院,江苏徐州 221116)

摘要:针对传统蚁群算法在求解过程中搜索时间过长、易于出现早熟停滞的缺陷,提出一种具有拓展性的自适应蚁群算法.蚁群综合启发式信息、信息素轨迹和拓展性信息自适应地调整状态转移规则,并采用全局信息素非均匀更新策略,有效增强了蚁群的全局搜索能力.同时,受魔方变换的启发,提出了一种新颖的魔方变异策略,以加快对迭代最优解进行局部优化的速度.旅行商问题仿真验证了文中改进蚁群算法的有效性,其收敛速度、稳定性远高于传统蚁群算法.关键词:蚁群算法;魔方变换;变异;旅行商问题中图分类号:TP 301文献标识码:A 文章编号:1000-1964(2009)04-0503-06

A daptive A nt Colony A lgorithm Based on Ex pandability and

Magic Cube T ransformation

M A Xiao -ping 1

,JIN Zhu

1,2

(1.Schoo l of Info rmatio n and Electrical Eng ineering ,China U niversity of M ining &T echnolog y,

Xuzho u,Jiang su 221116,China; 2.Schoo l of Co mputer Science and T echno log y,China U niver sity o f M ining &T echno log y,Xuzho u,Jiang su 221116,China)

Abstract:T here are the shortcomings such as lo ng er co mputing time and precocity and stag na -tion in classical ant colo ny algor ithm.Based on the ex pandability,an adaptive ant colony algo -r ithm is presented.The alg orithm dy namically adjusts state transitio n rule by integrating ex -pandability w ith heuristics and pher omone.M eanw hile,an uneven strategy based on the g lobal pheromo ne updating is ado pted to enhance the ant .s ex cellent ability in sear ching the w ho le

best solution.In addition,a no vel magic cube mutation strategy,inspired by the magic cube tr ansform ation,is em ploy ed to accelerate ev olutio n speed after each iteration.The experimen -tal results on T SP demo nstr ate that the propo sed alg orithm has much hig her convergence speed and stability than that of classical ant co lony alg orithm.

Key words:ant co lony alg orithm ;mag ic cube transformation;mutation;traveling salesman pro blem

蚁群算法是人们受自然界蚁群觅食行为启发而提出的一种新型启发式搜索算法,本质上是并行算法,具有很强的灵活性和鲁棒性,易于与其它智能计算技术相结合,已被广泛应用于求解组合优化问题、武器目标分配问题、网络路由选择、机器人路

径规划以及模糊规则学习等领域[1].蚁群算法利用正反馈机制使得待解问题向全局最优解不断进化,通过数次迭代最终得到全局最优解.但在多次迭代

后,由于信息素的大量沉积,算法易陷入早熟停滞,且优化效率较低.针对蚁群算法的不足,文献[2]结

中国矿业大学学报第38卷

合遗传算法中逆转变异算子提出具有变异特征的蚁群算法,以加速解的进化速度;文献[3]在传统的增强型蚁群算法中引入遗传算法中的交叉和变异操作,但这些变异方法都比较单一,且难以并行化,对于算法效率的提高有一定的局限性;文献[4]依据优化过程中解的分布均匀度,自适应地调整路径选择概率和信息素更新策略,但在选择路径时仅关注与当前结点相连备选边上的蚂蚁聚集程度,未考虑选择这些备选边后下一步搜索空间的可扩展性,在一定程度上不利于避免算法的早熟停滞.本文改进蚁群算法综合启发式信息、信息素轨迹和拓展性信息自适应地调整状态转移规则,并采用魔方变换策略进行变异,从而可以有效地避免早熟收敛,提高求解效率.

1基本原理

111动态状态转移策略

蚁群算法是一种正反馈机制,依据路径上积累的信息素和启发式信息选择搜索方向,信息素浓度越高的较短路径对蚂蚁越有吸引力,通过信息素轨迹局部和全局更新机制不断强化已知最优解,使整个系统向全局最优方向演化,这是蚂蚁个体自催化行为体现出的群体效应.但在一定次数的迭代之后,蚁群倾向选择少数几条沉积了大量信息素的路径,不再搜索新的解,算法易陷入早熟停滞.

研究发现,信息素是一种具有局部特性的物质,这主要是从蚂蚁个体和解个体两方面进行考虑:蚂蚁个体在其找出的最短路径上会释放出较多信息素,虽然该路径上的边可能并不被其它蚂蚁所认可,但可能在路径选择中起主导作用,蚁群算法在搜索的每一步总是以较大概率选择信息素和启发式信息较大的路径,因而找出的解易陷入局部最优.本文引入拓展性信息以均衡信息素的局部特性在蚂蚁选择路径过程中的影响作用,蚂蚁选择下一个城市结点的时候,不仅要考虑与当前结点相连的边上信息素和启发式信息,还要考虑解空间的可拓展性:如果与当前结点i相连的各边信息素波动比较大,个别路径上信息素浓度过高,此时若与这条浓度较高路径相连的各边上的信息素差距仍然很大,则此时拓展性就比较小,蚂蚁的选择范围将局限于少数几条信息素较强路径,易引起早熟停滞,因此,应增加当前结点i上备选路径拓展性信息的权重系数,使得与下一个结点j相连各边的信息素波动小一些的路径被选择的概率增加;相反,如果与当前结点i相连的各边信息素波动比较小,可供选择的路径就多一些,未能体现较优路径上信息素指导作用,为了加快收敛,应减小当前结点i上备选路径拓展性信息的权重系数,使得蚂蚁把注意力集中到信息素和启发式信息上来.通过这样的改进,可以有效均衡蚂蚁在少数几条信息素较浓路径上的聚集,解的性能明显提高,避免了算法的早熟停滞.

假设有路径(i,j),结点j与s个结点相连,定义路径(i,j)的拓展性信息K c ij为:与结点j相连的未被搜索过且信息素非零的n k条边上的信息素波动值的倒数,即

K c ij=1/1

n k-1

E n k

s=1

(S js-S k c)2

;

,(1)式中:;为影响因子,用以控制拓展性信息影响作用范围;S k c为与结点j相连边上信息素均值,S k c= (E

n k

s=1

S js)/n k,n k[s,S js为路径(j,s)上的信息素轨迹.

若与结点j相连的边上信息素分布波动比较大,则少数路径上信息素浓度较大,此时蚂蚁可选择的路径比较少,路径(i,j)的拓展性就比较差,蚂蚁选择(i,j)后很难拓展新的解空间;如果与j 相连边上信息素分布波动较小,则可供选择的路径相对较多,此时解空间的可拓展性就比较强.

定义结点i处的拓展性信息权重系数W k为:在结点i处,备选路径上拓展性信息对蚂蚁个体选择路径的影响程度

W k=U V i/(S c+V i),(2)式中:U为拓展性信息的权重修正系数;S c为与结点i相连的边上信息素均值,S c=(E

n

c

j=1

S ij)/n c,n c 为与结点i相连的信息素非零且未被搜索过边的数目;V i为结点i处备选路径上的信息素波动值,且

V i=1

n c-1

E n c

j=1

(S ij-S c)2

N

,

式中N为控制信息素波动值的影响因子.

结点i处备选路径上信息素和启发式信息对蚂蚁个体选择路径的作用权重为

W q=

由于V i中影响因子N的作用,控制了W k值的相对范围,使其不至于过大以冲淡信息素和启发式信息的权重系数W q,保证了信息素的全局指导作用,使系统向着全局最优解的方向收敛,N值的确

504

第4期马小平等:基于拓展性和魔方变换的自适应蚁群算法

定主要依赖于仿真实验获得.

在综合了结点i处的信息素、启发式信息以及

拓展性信息之后,第j条备选边的综合权重为

A ij=W q Q ij+W k K ij,(4)

式中:Q ij为归一化后的路径(i,j)的信息素浓度及

启发式信息,Q ij=(S A ij G B ij)/E k I I S A ik G B ik,其中I为当前

可访问的城市结点集合,S ij为路径(i,j)上的信息

素浓度,G ij为路径(i,j)上的启发式信息,A,B分别

为蚂蚁在搜索过程中积累的信息素及启发式信息

对其选择路径所起的不同作用;K ij为归一化后路

径(i,j)的拓展性信息,K ij=K c ij/E u I I K c iu.

蚂蚁K将按如下的概率以赌轮盘规则选择下

一个城市结点j

P K ij=

A ij

E

k I I

A ik

(j I I),

(其它).

(5)

由式(2)可知,如果在结点i处信息素波动比较大,个别路径上的信息素浓度相对较高,V i值就相对较大,备选路径上拓展性信息对蚂蚁选择路径的影响程度W k就会大一些,而信息素和启发式信息的影响W q就会相对小一些,在按式(4)确定备选边的综合权重后,与i相连边上拓展性值K ij较大的边被选择中的概率大大增加,这就促进了解的多样性,有效防止了早熟停滞;若结点i处信息素波动较小,各备选项路径上的信息素浓度相差无几,V i 值相对较小,收敛速度较慢,则备选路径上信息素和启发式信息对蚂蚁个体选择路径的权重系数W q 相对较大,蚂蚁个体选路策略着重于路径上信息素和启发式信息,加速了解的收敛速度,当各路径上的信息素均匀分布于各边上时,此时V i达到最小值为0,W q达到最大值,式(4)退化为A ij=U Q ij,式(5)等价于下式的基本蚁群算法中概率选择公式[1]

P K ij=

S A ij G B ij

E

k I I

S A ik G B ik

(j I I),

(其它).

112信息素非均匀更新策略

蚁群系统中,每次迭代后信息素要进行全局更新,这是一种均匀更新机制,即只要边(r,s)I L b(迭代最优解),则(r,s)间信息素浓度就会均匀增加1/L b,这种更新机制忽略了边(r,s)上启发式信息的影响,较短边和较长边对迭代最优解信息素沉积的贡献是不同的,较短路径对蚁群有较大的吸引力,在搜索的过程中会以较大的概率被选中,其上较浓的信息素轨迹会逐渐抑制系统对新解空间的探索,而较远路径被选中的概率要相对小得多.因此,在信息素的全局更新策略上,改进算法采用将每次迭代最优解上的边按长度非均匀更新,总体原则:在增强迭代最优解上信息素轨迹的同时,使得启发式信息较大边上的信息素沉积速度小于启发式信息较小边上的信息素沉积速度,以加强信息素的全局指导作用,这样蚂蚁个体采用式(5)的动态状态转移规则时就能够充分利用信息素的全局指导作用,增加了解的多样性,加快系统的全局搜索速度.

改进后的信息素全局更新公式为

S new ij=(1-Q)S old ij+Q$S ij L b

L b-D(i,j)

W

,(6) $S ij=

1

L b

((i,j)I G),

(其它),

(7)

式中:L b为当前迭代最优解;D(i,j)为返回(i,j)间的距离;W I[0,1]为非均匀更新时的影响因子,用于控制非均匀更新信息素沉积量的作用范围; $S ij为迭代中路径(i,j)上信息素的增量;Q为信息素轨迹挥发系数;G为迭代最优解的城市结点集合.

假设经过某次迭代得到最优解L b为430,路径(r,s)I L b,路径(u,m)I L b,且r X u,s X m, L(r,s)=10,L(u,m)=50,取W=015,则(r,s)边上信息素轨迹增量为11011835Q$S ij,(u,m)边上信息素轨迹增量为11063757Q$S ij.若L b为1000,则(r,s)边上信息素轨迹增量为11005037Q$S ij,(u, m)边上信息素轨迹增量为11025978Q$S ij.可见,较优解上的信息素轨迹增量也较大,同时解中较短边上信息素沉积速度小于较长边,有效均衡了蚂蚁在较短路径上的大量聚集,增强了信息素的全局指导作用,提高了解的质量.

113迭代最优解变异策略

利用遗传算法的快速全局搜索能力,在蚁群算法迭代最优解中引入适当的变异策略进行局部寻优,算法性能将会显著提高.研究发现,通过魔方变换,魔方状态函数中简单的转动操作序列就可以得到丰富的魔方状态,受此启发,改进算法利用魔方变换对迭代最优解进行变异操作,本质上是并行变换,增加了变异的多样性,加快最优解的进化速度,促进解的全局收敛性.

改进算法首先用迭代最优解初始化变换魔方.

505

中国矿业大学学报 第38卷

为了减少运算复杂性,文中选择的魔方模型取消了心块、边块和角块,魔方上每一个小块代表路径中的一个城市结点.魔方六个表面的命名方式为[5]:W (上)、S(下)、R(后)、G(前)、Y(左)、B(右),其结构图和箱式展开图如图1,2所示

.

图1魔方结构

Fig.1Str uctur e o f magic

cube

图2箱式展开Fig.2Box expand map

以魔方六面体几何中心为原点,沿B,R 和W 面外法线方向为x ,y ,z 轴正向建立魔方笛卡儿坐标系,为了方便描述魔方转动操作,假设该坐标系相对于观察者是固定的,并按右手规则确定坐标轴上转层的旋转方向,如图1坐标轴圆环上箭头所指方向.

假设迭代所得城市结点序列为:A 0A 1,A n -1,(A 0,A 1,,,A n -1I {0,1,2,,,n -1}),其中n 为城市个数,魔方边长a =7|n/6?.初始化时,A 0A 1,A a a-1以/S 0型填充B

面矩阵,

A aa A aa +1,A 5a a-1以/Z 0型填充R,W ,G,S 面矩阵,剩下的结点以/S 0型填充Y 面矩阵.填充过程中,多余的矩阵元素均以/-10填充(如图3,实线为城市结点填充线段,虚线为转折点连线).

沿表面F 指向魔方外部的法线方向共有a +2个转层(F -1,F 0,F 1,,,F a -1,F a ),F I {B,W ,R},其中F -1,F a 为表面转层,沿转轴可正向旋转1(90b ),2(180b ),3(270b )转角(360b 相当于没有转动);F 0,F 1,,,F a -1为a 个环面转层,每个转层沿

转轴可正向旋转4a-1转角,每个转角为P /(2a),

这些转动操作为单次转动.

图3魔方初始化箱式展开Fig.3Init ial box ex pand ma p

单次转动的有序操作队列为魔方的序列转动

操作,如:R 30W 2-1B 2

a -1表示首先将魔方沿R 面外法线上第0个转层旋转3P /(2a)转角,再将W 面外法线上第-1转层旋转2(180

b )转角,最后将B 面外法线上第a-1转层旋转2P /(2a)转角.

将旋转后的魔方结点按初始化轨迹排列,略去其中值为-1的结点,得到变异后城市结点序列,评价路径长度L c ,如果L c 小于迭代最优解,则变异有效,否则反变异.114

算法基本步骤

在算法的具体实现中,参照最大最小蚁群系

统(MM AS)将信息素范围限制在区间[S

min ,S max ]内,避免了路径上信息素过分悬殊,并将信息素轨

迹初始化为S max ,增加搜索初始阶段解的多样性,基于拓展性和魔方变换的自适应蚁群算法步骤如

下:

Step 1 以任一城市为起始结点,利用贪心算法找出距离最近的结点序列,求出其长度L 0,则

S

max =C/L 0(C 为常数),用于控制信息素轨迹最大值相对于L 0的范围,将所有路径上的信息素轨迹

初始化为S max ,取S min =S max /n;将m 只蚂蚁随机放置于各个城市结点上,设置迭代计数器N C =0,并将A ,B ,Q 等参数赋初值.

Step 2

第K 只蚂蚁在时刻t 按下式选择下

一个城市结点j

arg m ax j I I

S A ij (t)G B

ij (t)按式(5)概率选择

(q [q 0),(其它),

(8)

式中:q 为(0,1)间的随机数;q 0为一个参数,q 0I [0,1],计算结点被选择的概率,并按赌轮盘规则选择下一个城市结点.

Step 3

按下式对信息素轨迹进行局部更新

S ij (t +1)=Q S ij (t)+$S ij (t,t+1),

(9)

506

第4期 马小平等:基于拓展性和魔方变换的自适应蚁群算法

(Q I (0,1)).

Step 4

在所有m 只蚂蚁都选择完结点之后,

返回Step2,继续选择下一个结点,反复执行,直至蚁群完成对所有城市结点的遍历.

Step 5对迭代最优解进行魔方变异.首先利用本次迭代最优解L i 初始化变换魔方,随机生成一个转动操作序列并执行转动操作,评价适应度L s

Step 6

按式(6)进行全局信息素更新.

Step 7将本次遍历所得最优解与全局最优解相比较,保存较优结果为全局最优解,按Step1重新计算S max 和S min ,对各条路径上的信息素轨迹进行全局更新,并检测信息素浓度是否位于区间

[S min ,S max ]内,若S ij >S max ,则S ij =S max ;若S ij

Step 8迭代计数器值增1,初始化禁忌表,重

复上述过程,直至N C 达到最大值.

2仿真实验及结果分析

为了验证改进算法的有效性,选取T SPLIB

[6]

中的Eil51(51个城市)、Oliver30(30个城市)、Kroa100(100个城市A Krolak/Felts/N elson)3个TSP 问题在PC 机上用V C++610进行仿真验证,实验结果如表1所示.实验中各参数的设置为:初始化蚂蚁数目m 等于城市结点数目,信息素初

始化为S max ,A =1,B =5,Q =015,Q =1,;=113,

<=011,U =011,N =1/4,W =015.实验运行5000次循环,对10次结果取平均值,表1中最优值为统计中的最小值,平均值为对各次最优解求平均得到的结果.

表1 改进蚁群算法和其它蚁群算法对比Table 1Comparison of our algorithm with other

improved ant colony algorithm

测试TSP 问题

Eil513426[7]4Oliver303420[7]4Kroa100321282[7]4ACS

最优值 平均值 迭代次数4331411[6]4381061802[6]423174[9]424174[9]1470[1]22468[10]226011442944[10]M M AS

+PT S 最优值 平均值 迭代次数42642711[8]

18742042312121212822129116[8]

553本文改进算法

最优值 平均值 迭代次数

4264261460

4204201215

21282212901273

注:/340内的数据为T SPLIB 中的已知最优解,迭代次数为蚁

群找到最优解所需要的代数.

由表1中数据可以看出,改进算法有较强的全局搜索能力,平均值较稳定且能够快速收敛,算法的稳定性高于A CS 和MM AS.

不同算法优化Eil51和Kroa100问题的收敛性实验对比曲线如图4所示.图中数据表明对于Eil51和Kro a100问题我们改进算法仅需要60次和73次即可收敛于最优解,远少于传统蚁群算法和M MAS 算法.改进算法具有较强的全局最优解搜索能力,大幅减少了迭代次数,能够在提高收敛性和防止早熟之间取得较好平衡

.

(a)Eil51(b)Kroa100

图4不同算法收敛性对比曲线

F ig.4

Compariso n o f co nverg ent featur es o f the o pt imized

3结论

蚁群算法中蚂蚁依据信息素浓度和启发式信息确定下一个路径结点,经过一段时间后,蚁群会在路径上释放大量信息素,导致算法易早熟停滞,收敛速度慢,改进算法借助拓展性信息均衡蚂蚁选路过程中信息素和启发式信息的影响范围,并根据迭代最优解上的启发式信息非均匀更新全局信息素,以增强信息素的全局指导作用,同时,采用魔方

变换进行变异,增加了解的多样性,加速迭代较优解向全局最优解的进化速度.仿真实验结果表明改进算法性能明显好于传统蚁群算法,能够以较快的速度收敛于全局最优解,有较强的鲁棒性.

作为一种新型模拟进化算法,蚁群算法本身还有很多需要改进的地方,例如:实验过程中各参数的确定缺乏系统的理论依据,实际应用过程中还有许多问题有待解决.随着人们研究的深入,相信蚁群算法必将趋于完善.

507

中国矿业大学学报第38卷

参考文献:

[1]李士勇.蚁群算法及其应用[M].哈尔滨:哈尔滨工

业大学出版社,2004:9.

[2]吴庆洪,张纪会,徐心和.具有变异特征的蚁群算法

[J].计算机研究与发展,1999,36(10):1240-1245.

WU Q ing-hong,ZHA N G J-i hui,XU Xin-he.A n ant

colony algo rit hm w it h mut ation feat ur es[J].Jo ur nal

of Computer Research and Dev elo pment,1999,36

(10):1240-1245.

[3]陈宏建,陈崚,徐晓华,等.改进的增强型蚁群算

法[J].计算机工程,2005,31(2):176-178.

CHEN H ong-jian,CH EN L ing,X U Xiao-hua,et al.

A n impr oved augment ant colony alg or ithm[J].Com-

puter Eng ineer ing,2005,31(2):176-178.

[4]陈崚,沈洁,秦玲,等.基于分布均匀度的自

适应蚁群算法[J].软件学报,2003,14(8):1379-

1387.

CHEN L ing,SHEN Jie,Q IN L ing,et al.An adap-

tiv e ant colony algo rithm based o n equilibr ium o f dis-

tributio n[J].Journal of So ftwar e,2003,14(8):

1379-1387.

[5]李世春.魔方的科学和计算机表现[M].北京:石油

大学出版社,2003:4.

[6]胡勇.动态跃迁转移蚁群算法[J].计算机工程,

2005,31(1):167-168.

H U Y ong.A n ant colony alg or ithm based o n dynam-

ic tr ansition[J].Com puter Eng ineer ing,2005,31

(1):167-168.

[7]REIN EL T G.T SPL IB[EB/O L](2007-05-22)

[2007-11-15]http://w ww.iwr.un-i heidelberg.de/

g roups/como pt/so ftw are/T SPL IB95.

[8]曹浪财,罗键,李天成.智能蚂蚁算法:蚁群算法

的改进[J].计算机应用研究,2003(10):62-64.

CA O L ang-cai,L U O Jian,LI T ian-cheng.Intellig ent

ant system:an impr oved alg or ithm o ver A CS[J].

A pplicatio n Resear ch of Co mputers,2003(10):62-

64.

[9]M ARCO D,LU CA M G.A nt co lo ny system:a co-

operat ive lea rning approach to the t raveling salesman pro blem[J].IEEE T ransactions on Evo lutio nar y Computatio n,1997,1(1):53-65.

[10]朱海梅,朱庆保,胡勇.具有自适应杂交特征的

蚁群算法[J].计算机工程与应用,2004,40(22):

81-83.

ZH U Ha-i mei,ZH U Q ing-bao,HU Yo ng.An ant

colo ny alg or ithm w ith adaptiv e crossov er featur es

[J].Co mputer Eng ineering and A pplications,2004,

40(22):81-83.

(责任编辑邓群)

508