自适应分组差分变异狼群优化算法

张强,王梅

(东北石油大学计算机与信息技术学院,黑龙江大庆163318)

自适应分组差分变异狼群优化算法

张强,王梅

(东北石油大学计算机与信息技术学院,黑龙江大庆163318)

针对狼群优化算法寻优精度不高和易陷入局部收敛区域的缺点,结合云模型在知识表达时具有不确定中带有确定性的特性,提出一种自适应分组差分变异狼群优化算法.其思想是采用佳点集理论对狼群进行初始化,通过云模型理论来完成个体游猎行为,在围攻行为中考虑狼个体的自身能量,最后利用差分进化算法和混沌理论完成个体变异,并进行探索全局最优位置.典型复杂函数测试表明,该算法能有效找出全局最优解,特别适宜于多峰值函数寻优.

狼群优化算法;佳点集;差分变异;混沌

0 引言

狼群算法是通过模拟狼群捕食行为而提出的,不同学者针对不同理解的捕食行为提出了不同的进化原理.Liu等[1]将捕食过程分为游猎、围攻与食物分配等行为,实验表明与粒子群算法、遗传算法相比,其所提的算法具有更高的求解精度和收敛速度;吴虎胜等[2]则将捕食过程分为游走、召唤、围攻3种行为,以及“胜者为王”的头狼产生规则和“强者生存”的狼群食物分配机制,其所提算法与经典鱼群算法、粒子群算法、遗传算法相比具有较强的鲁棒性和全局寻优能力,尤其在处理多峰、高维复杂函数中效果明显;周强等[3]提出通过头狼引领狼群进化;李国亮等[4]对游走行为和召唤行为引入交互策略改进搜索策略;吴虎胜等[5]又提出一种二进制狼群算法,扩展了狼群算法的应用.但狼群算法同样存在收敛速度慢、易陷入局部最优等不足,分析其主要原因有以下3点∶①狼个体在游猎过程中都是以一定的步长通过随机探索指定步数来产生新个体,随机性虽利于增加全局搜索能力但缺少确定性,容易产生一些多余的试算,同时步长设置的大小也会对算法性能产生影响,很多情况都是通过试算给出;②食物分配过程中都是通过重新初始化,虽然可以起到增加个体多样性的作用,但又会对收敛速度产生影响;③全邻域狼群算法收敛速度快,但易于陷入局部最优,采用局部邻域则可有效的避免陷入局部最优.因此,本文提出一种自适应分组差分变异狼群优化算法(Adaptive Grouping Dif f erence Variation Wolf Pack Algorithm,AGDV-WPA),首先采用佳点集理论对狼群进行初始化,利用自分组策略对狼群进行分子群寻优,通过云模型算法来改进狼个体的游猎行为,在围攻行为中考虑狼个体的自身能量,以求消耗更低的能效来获得更多的食物,最后利用差分进化算法和混沌理论完成狼个体变异.

1 基本狼群算法

综述以上学者所提狼群算法的优化原理,可大致抽象成3种行为.

(1)游猎行为∶狼个体在当前位置附近搜索局部最优值,如果优于当前个体则替换,否则继续游猎到指定次数h,计算公式为

其中,rand()是区间[-1,1]内均匀分布的随机数,xstepa为游猎步长,xid为第i匹狼第d维的当前位置.

(2)围攻行为∶狼群经过游猎后,在狼群中找到最优狼个体,通过召唤和围攻利用最优狼个体的信息搜索全局最优值,计算公式为

其中,rand()是区间[-1,1]内均匀分布的随机数,xstepb为移动步长,xid为第i匹狼第d维的当前位置,xgd为最优狼个体第d维位置.

(3)食物分配∶依据优胜劣汰原则,通过随机产生新个体来替换狼群中适应度差的狼个体,进而增加狼群的多样性,避免陷入局部最优.

2 自适应分组差分变异狼群优化算法原理

2.1 基于佳点集理论的种群初始化

狼群进化算法从随机初始化狼群个体开始迭代寻优,若存在某些狼个体在最优解附近,则在一定程度上能够加速算法收敛和提高寻优性能.佳点集理论[6]已证明近似计算函数在s维欧氏空间单位立方体上的积分时,用n个佳点构成的加权和比采用任何其他n个点所得到的误差都要小.已有学者[7-8]将其应用到种群初始化,取得了很好的寻优效果,具体定义如下.

设Gs是s维欧氏空间中的单位立方体,如果r∈Gs,形为pn(k)=≤k≤n},其偏差φ(n)满足φ(n)=C(r,ε)n-1+ε,其中,C(r,ε)是只与r和ε(ε＞0)有关的常数,则称pn(k)为佳点集,r为佳点.一般情况下,取r={2cos(2πk/p),1≤k≤s},p是满足(p-s)/2≥s的最小素数.

2.2 自适应狼群分组策略

自然界中的狼群具有领域性,其活动范围通常相对固定,数量一般在5～12只.随着食物的减少或是迁移其领域范围、狼群规模和子群个数会随之发生变化.本文提出一种自适应分组策略来模拟狼群的领域性,进而避免算法快速陷入局部最优.分组方式如下.

(1)将整个狼群分成m个子群,每个子群包含n只狼个体.

(2)把狼群内的个体按适应值降序排列,将前m只狼个体依次分配给m个子群,则第m+1只狼进入第一个子群.

(3)每迭代一次计算子群内狼个体的方差.用方差来衡量子群内个体的离散程度,方差越小说明离散程度越小,表明或是找到最优解,或是陷入局部最优. (4)递减子群个数m.为第t次迭代后的方差,k∈(1,···,i-1,i+ 1,···,m)小很多,则说明该子群内的个体或是找到最优解,或是陷入局部最优,则可以将该子群的个体分散到其他子群中,即m1=m-1.针对寻优过程中可能存在各个子群内的相差不大的情况,为了加速迭代需计算m2=m-(m-1)×sin取整函数,m为初始的分组个数,迭代后期分组数设置为1.最后取m=min{m1,m2},这样使得在进化初期狼群以子群方式在各自的领域觅食,到了进化后期食物资源减少(相当于接近最优值)则合并为整个狼群进行寻优.

2.4 基于云模型的狼群个体游猎行为

社会学原理指出,在优秀个体附近较易发现更优个体,也就是说局部最优值附近往往存在更优值.在基本狼群算法中,狼个体的游猎行为是通过计算向周围h个方向移动位置,若找到比当前位置更优的位置则代替,否则保持原个体.从公式(1)中可以看出h的取值对算法的性能会产生相应的影响,个体生成具有的随机性虽然可以保持个体的多样性,但同时也导致个体移动的盲目性.云模型在知识表达时具有不确定中带有确定性、稳定之中又有变化的特点,体现了自然界物种进化的基本原理[9-11].本文采用正态云模型算法完成狼个体的游猎行为,将每只狼个体视作一个云滴C(Ex,En,He),用其计算出h个云滴,若存在比原个体更优的个体,则取代原个体.改进后的游猎行为定义为∶将狼个体作为期望(Ex)表示搜索中心;用当代适应度方差σ2作为熵(En)来动态改变寻优搜索范围;用超熵(He)来控制h个云滴的离散度;迭代初期加大随机性,迭代后期加强稳定性,为λ的取值区间,t为当前迭代次数,T为总的迭代次数.

2.4 基于自身能量的狼群围攻行为

狼群在围攻行为中狼个体是以一定移动步长随机向着头狼(最优值)处行进,这样虽然可以加快收敛速度,但也可能在奔袭过程中错过全局最优值而陷入局部最优,所以在奔袭过程中应考虑距离最优值较远的狼个体能以耗费较低的能量来获得更多的体能,这也符合最优觅食理论中所表述的∶为获取更好的觅食效果,动物更趋向在觅食过程中以消耗更低的能效耗费来获得更多的猎物[12-13].计算狼个体间的能效吸引力公式为

设对狼个体xi产生最大Fjk的狼个体为xnx.依据最优觅食理论改进狼个体的围攻行为,即更新狼个体要同时参照全局最优狼个体xg和xnx,进行更新的方式为

其中,rand()是[-1,1]的随机数,step为围攻步长,w为狼个体间的吸引系数.

从公式(4)可知,w的取值会影响寻优性能,在算法运行初期种群的多样性较多,这时如果适应度较差的狼个体可能离最优狼个体较远,其应该在向最优狼个体靠近时先获取足够的能量,故此时w的取值应该较大;而在进化后期多数个体已经趋于最优值的附近,此时w的取值应该较小加快收敛速度.本文给出w的自适应取值公式为

其中,[a,b]为w的取值范围.

2.5 基于差分变异和混沌变异的食物分配原则

已有狼群算法的狼群食物分配原则都是最精壮的狼优先获取猎物,接着再分配给较为弱小的狼.算法运行时的实际处理方式通常是按照一定的比例选择狼群中若干最差个体,以随机方式重新初始化来避免狼群陷入局部最优,但在自然界的狼群体中,并不是所有瘦弱的狼都会被抛弃,会有若干个体狼与其分享一些食物,这样会使某些瘦弱狼获得一定的能量进而有机会继续生存下去.本文提出将差分进化算法中的变异策略引入到食物分配原则中来.差分进化算法已被证明是进化算法中简单而最高效的算法,具有原理简单、受控参数少的优势[14-15],其主要的变异操作在很大程度上影响着该算法的性能.常用的变异算子存在或全局搜索能力弱、或局部搜索能力弱的局限性[16].本文采用改进的差分变异策略来分配食物∶让瘦弱狼个体从周围的狼个体获取一定的能量,若其适应度得到改善则继续进入下一次迭代;若其适应度得不到改善,说明其需要被淘汰,可以使用混沌理论产生新个体进入下一次迭代.使用混沌映射产生的个体呈现遍历性、随机性和多样性[17],可有效地在收敛区域以外空间搜索全局最优位置,进而更好地保持种群多样性.采用k阶Chebyshev混沌映射对淘汰的狼个体随机初始化,文献[18]已证明偶数阶Chebyshev混沌映射的个体随机性较好,对于较差的个体采用公式(5)进行更新.

其中,r1,r2,r3,r4为从狼群中随机选择的互不相同且不同于该更新个体的整数,F为比例缩放因子.如果适应度相差很小,说明两个狼个体在空间中相隔很近,Fi应取较大值,以防止扰动量过小;如果适应度相差很大,说明两个狼个体在空间相隔很远,Fi应取较小值,以限制扰动量过大.Fi确定方式为

最后利用狼群个体的适应度来确定需要变异的狼个体数量,方法如下.

第一步∶计算所有狼群个体适应度值的平均值favg.

第二步∶计算小于favg的所有狼个体适应度的平均值

第三步∶计算个体适应度值小于f′avg的狼个体的个数Num.

第四步∶在算法进化中起到变异作用的狼个体不宜取过多,所以需要设定一个变异个数上限Nummax,对于Num/2≤Num≤Nummax使用公式(5.1),对于0＜Num＜Num/2使用公式(5.2).

3 自适应分组差分变异狼群优化算法流程

第一步∶参数初始化,设置迭代次数t=1,最大迭代次数T,子群内迭代次数limit和误差精度.

第二步∶采用佳点集理论初始化狼群个体.

第三步∶采用第2.2节的方法完成狼群的分组,对每个子群分别执行limit次第四步到第六步;

第四步∶采用第2.3节的方法完成狼群个体的游猎行为.

第五步∶采用第2.4节的公式(3)和公式(4)完成狼群的围攻行为.

第六步∶采用第2.5节的公式(5.1)、公式(5.2)和公式(6)完成基于差分变异和混沌变异的食物分配原则.

第七步∶t=t+1,达到最大迭代次数或是满足误差精度则退出,否则跳转到第三步继续迭代计算.

4 实验仿真

以8个函数极值优化为例,并通过与粒子群算法(Particle Swarm Optimization,PSO)、遗传算法(Genetic Algorithm,GA)、文献[1]的狼群算法(Wolf Colony Algorithm,WCA)和文献[2]的狼群算法(Wolf Pack Algorithm,WPA)对比,验证本文算法的优化性能.种群大小均为100,最大迭代代数均为5 000,每个函数独立运行20次;PSO参数设置[19]为惯性因子0.729 8、自身因子1.496 18、全局因子1.496 18;GA参数设置为交叉概率Pc=0.95,变异概率Pm=0.05;然后比较5种算法的最优结果、最差结果、平均结果、平均运行时间和方差,其中,最优结果、最差结果反映解的质量,平均结果显示算法所能达到的精度,平均时间反映算法的收敛速度,方差反映算法的稳定性和鲁棒性.8个函数如下.该函数是二维复杂函数,具有无数个极小值点,最小值0.

f2该函数存在许多局部极小点,全局最小值0.

f.该函数全局最小值0.

f4该函数有一个全局最小值0.

f5该函数存在许多局部极小点,全局最小值0.

f632.768,n=10.该函数有一个全局最小值0.

f7该函数存在许多局部极小点,数目与问题的维数有关,全局最小值0.

f8该函数是个多峰值的函数,全局最小值0.

表1 f1运行仿真结果对比Tab.2 f1run simulation results comparison

表2 f2运行仿真结果对比Tab.2f2run simulation results comparison

表3 f3运行仿真结果对比Tab.3 f3run simulation results comparison

表4 f4运行仿真结果对比Tab.4 f4run simulation results comparison

表5 f5运行仿真结果对比Tab.5 f5run simulation results comparison

表6 f6运行仿真结果对比Tab.6 f6run simulation results comparison

表7 f7运行仿真结果对比Tab.7 f7run simulation results comparison

表8 f8运行仿真结果对比Tab.8 f8run simulation results comparison

从仿真结果对比可以看出,本文所提的自适应分组差分变异狼群优化算法(AGDV-WPA)具有很好的求解精度和求解速度,分析原因主要有以下两个方面∶①从最优结果、最差结果、平均结果可以看出,PSO和GA的寻优效果较差,WCA和WPA次之,AGDV-WPA最优,这是因为AGDV-WPA算法采用佳点集理论初始化狼群,增加了狼个体接近最优解的机会,并且游猎行为个体的更新采用云模型,其稳定倾向性有利于保护最优个体对附近更优个体进行自适应定位,其随机性有利于保持狼个体的多样性,采用的自适应分组策略有利于提升避免算法陷入局部最优的能力,加快了算法的进化速度和寻优性能,同时基于差分变异和混沌变异的食物分配原则使算法进化后期很好的避免陷入局部最优,有利于获得全局最优解,进而解决了算法在一些复杂函数时容易陷入早熟收敛、收敛速度慢、易陷入局部最优的缺点.②从平均运行时间和方差可以看出,WCA、WPA和AGDV-WPA速度较快,但是AGDV-WPA更快些,WPA次之,分析其原因除了AGDV-WPA的种群初始化可以获得更加均匀分布解外,主要是狼群个体游猎行为过程中WCA、WPA都是采用随机试探的方式,虽有利于维护种群的多样性,但容易造成多余的试算,而基于云模型的游猎行为可以完成确定性中包含随机性的搜索,而且AGDV-WPA在狼群围攻行为中引入的自身能量能在一定程度上限制由于个体围攻的步长过大而错过最优解.

5 结束语

狼群算法通过个体游猎和群体围攻来完成进化计算的核心功能,游猎的随机性有利于获取全局最优解,但也增加了一些试算,缺少针对性的搜索.本文应用佳点集理论和云模型算法克服随机算法中因个体位置分布不合理带来的局限性,进而加速对解空间进行全局寻优,利用差分混沌变异来避免陷入局部最优位置,较好地改进了狼群算法中随机试算和围攻步长而带来的易陷入局部最优解和选择压力过大造成的早熟收敛等问题.仿真结果表明∶该算法具有精度高、收敛速度快等优点.

[1]LIU C A,YAN X H,LIU C Y.The wolf colony algorithm and its application[J].Chinese Journal of Electronics, 2011,20(2):212-216.

[2]吴虎胜,张凤鸣,吴庐山.一种新的群体智能算法—狼群算法[J].系统工程与电子技术,2013,35(11):2430-2438.

[3]周强,周永权.一种基于领导者策略的狼群搜索算法[J].计算机应用研究,2013,30(9):2629-2632.

[4]李国亮,魏振华,徐蕾.基于改进搜索策略的狼群算法[J].计算机应用,2015,35(6):1633-1636.

[5]吴虎胜,张凤鸣,战仁军.求解0–1背包问题的二进制狼群算法[J].系统工程与电子技术,2014,36(8):1660-1667.

[6]华罗庚,王元.数论在近似分析中的应用[M].北京:科学出版社,1978.

[7]刘香品,宣士斌,刘峰.引入佳点集和猴群翻过程的人工蜂群算法[J].模式识别与人工智能,2015,28(1):80-89.

[8]毕晓君,张磊.基于混合策略的双种群约束优化算法[J].控制与决策,2015,30(4):715-720.

[9]张英杰,邵岁锋,Niyongabo Julius.一种基于云模型的云变异粒子群算法[J].模式识别与人工智能,2011,24(1):90-96.

[10]马颖,田维坚,樊养余.基于云模型的自适应量子免疫克隆算法[J].计算物理,2013,30(4):627-632.

[11]李翠明,龚俊,牛万才,等.基于改进隶属云模型蚁群算法的喷涂机器人喷枪轨迹组合优化[J].上海交通大学学报,2015,49(3): 387-391.

[12]孙儒泳.动物生态学原理:第三版[M].北京:北京师范大学出版社,2001.

[13]崔志华,曾建潮.微粒群优化算法[M].北京:科学出版社,2011.

[14]彭虎,吴志健,周新宇.基于三角的骨架差分进化算法[J].计算机研究与发展,2015,52(12):2776-2788.

[15]李章维,周晓根,张贵军.一种动态自适应差分进化算法[J].计算机科学,2015,42(6):52-56.

[16]孔祥勇,高立群,欧阳海滨,等.求解大规模可靠性问题的改进差分进化算法[J].东北大学学报(自然科学版),2014,35(3): 328-332.

[17]胥小波,郑康锋,李丹,等.新的混沌粒子群优化算法[J].通信学报,2012,33(1):24-37.

[18]刘金梅,屈强.几类混沌序列的随机性测试[J].计算机工程与应用,2011,47(5):46-49.

[19]POLI R,KENNEDY J,BLACKWELL T.Particle swarm optimization[J].Swarm Intelligence,2007(1):33-57.

(责任编辑：李艺)

Adaptive grouping dif f erence variation wolf pack algorithm

ZHANG Qiang,WANG Mei
(School of Computer and Information Technology,Northeast Petroleum University, Daqing Heilongjiang163318,China)

Due to the shortcomings that wolf pack algorithm is not high solving precision and easy to fall into the local convergence region,adaptive grouping dif f erence variation wolf pack algorithm is proposed based on the excellent characteristics of cloud model transformation between qualitative and quantitative.Individual wolves are initialized by good-point set.Individual hunting behavior is accomplished through the cloud model theory and the self energy of the wolf is considered in the siege behavior.Finally,the differential evolution algorithm and the chaos theory are used to complete the individual variation to explore the global optimal location.The simulation results show that the proposed algorithm has f i ne capability of f i nding global optimum,especially for multi peak function.

wolf pack algorithm;good-point set;differential variation;chaos

TP301.6

A

10.3969/j.issn.1000-5641.2017.03.008

1000-5641(2017)03-0078-09

2016-05-13

张强,男,副教授,博士,研究方向为进化算法.E-mail：dqpi zq@163.com.