基于混沌搜索与精英交叉算子的磷虾觅食算法

王 磊,张汉鹏

(西南财经大学a.经济信息工程学院;b.工商管理学院,成都610074)

基于混沌搜索与精英交叉算子的磷虾觅食算法

王 磊a,张汉鹏b

(西南财经大学a.经济信息工程学院;b.工商管理学院,成都610074)

为解决磷虾觅食(KH)优化算法在处理高维多模态函数优化问题时存在局部搜索能力不强、收敛速度慢等问题,利用一种贪婪的精英交叉算子加速其收敛速度,使用基于逻辑自映射函数的混沌搜索算子避免局部极值的吸引,采用对立搜索算子提高初始种群的质量。结合上述3种算子提出一种改进的磷虾觅食算法。在7个标准测试函数上的仿真实验结果表明,与KH及其改进算法相比,该算法在寻优精度和收敛速度方面均得到明显增强。

磷虾觅食算法;局部搜索能力;对立策略;精英交叉算子;混沌搜索;收敛速度

1 概述

仿生群体智能算法在优化过程中具有易于实现、适于并行处理、不受搜索空间条件的限制、鲁棒性强等优点,在科学计算和工程技术领域日益受到广泛的应用。近些年来,人们在研究生物群体智能行为和自然规律过程中受到启发,相继提出了一些新颖的仿生群体智能算法。例如蚁群算法(ACO)［1］、蝙蝠算法(BA)［2］、生物地理优化算法(BBO)［3］、和声搜索算法(HS)［4］、布谷鸟搜索算法(CS)［5］等。

2012年,Gandomi等人在研究磷虾觅食过程中虾群结构的形成规律时,发现个体的运动行为明显受到它所估计的食物位置和附近群体(倾向于形成高密度虾群)的吸引。这样每个磷虾个体结合自身估算的全局食物信息和个体之间交换的局部位置信息,不断向全局最优(食物)位置移动。他们使用一种Lagrangian模型来描述这种行为,并在此基础上

提出了一种新颖的仿生群体智能算法——磷虾觅食算法(Krill Herd,KH)［6］。

由于同时考虑全局探索和局部搜索能力,KH算法在连续空间的非线性优化性能强于目前大多数群体智能算法,并具有控制参数少、易于实现等优点。然而,最新实验研究表明,KH算法在处理一些高维多模态优化问题时(如30维的Fletcher函数),容易出现早熟、陷入局部最优、后期收敛速度慢等不足,即算法的局部搜索能力不强。针对这些问题,文献［7］利用混合DE算子增强种群多样性和局部搜索能力;文献［8］采用基于和声搜索的变异算子提高了算法的逃离极值的能力,取得了一定的效果;类似的工作还包括文献［9］。文献［10］受SGA算法的启发提出一种SSC交叉算子,以贪婪地方式与当前最优解进行交叉,提出的SKH算法在收敛速度和局部搜索能力有明显提升。

作为最新的仿真群体智能算法之一,KH算法的理论和应用研究刚刚起步。本文将从增强KH算法的局部搜索性能和收敛速度的视角出发,设计和联合使用精英交叉、混沌搜索和对立搜索3种算子,提出一种新颖的改进KH算法,并在多个标准测试函数上验证其性能。

2 磷虾觅食算法

2.1 基本的磷虾觅食算法原理

研究发现［11］,磷虾通常形成一定的群体结构进行觅食,虾群密度和食物吸引是群体形成的2个主要因素。磷虾个体的移动位置可以用Lagrangian模型进行建模:

在文献［6］给出的KH算法中,认为每个个体不仅受到周围磷虾个体的局部吸引(以便维持高的虾群密度),也受到当前全局最优个体的吸引。因此,模型中的运动向量Ni定义为:

其中,Nmax是最大移动步长;ωn是惯性权重;代表受周围邻居吸引的运动向量;代表受当前最优个体吸引的运动向量。

觅食运动向量Fi受到当前估计的食物位置和前一次觅食活动及位置的影响,因此,Fi可以由式(3)描述:

物理扩散运动向量Di表示磷虾个体的随机搜索行为,可以由下式估计:

其中,Dmax代表最大扩散速度值;δ表示随机扩散方向向量;r和rmax分别表示当前迭代次数和最大迭代次数。

此后,磷虾个体的位置更新公式为:

其中,Δt是具体应用相关的时间间隔常量。更具体的KH算法步骤及参数取值方法参见文献［6］。值得注意的是,磷虾觅食行为的Lagrangian模型已经有深入的实验研究,KH算法的大多数参数都可以根据模型和大量实验观测结果经验地选取［6,11］,而Δt是算法唯一需要结合具体应用确定的参数。

2.2 KH算法分析

通过对上述3种运动分析,磷虾个体在搜索食物位置时,不仅具有全局探索能力(与和食物吸引度值有关),而且具有局部搜索能力(与和有关)。在这些因素的共同作用下,个体经过多次迭代不断向适应度最优的位置移动。

然而近期的研究表明,基本的KH算法在处理一些高维多模态优化问题时(如30维的Fletcher函数),容易出现早熟、陷入局部最优、后期收敛速度慢等不足［7-9］,算法的局部搜索能力不强。经过分析,归纳的主要原因如下:

(1)KH算法一旦在迭代后期陷入局部极值,磷虾个体周围的邻居由于已经聚集在极值点附近(形成高密度虾群),对个体的影响力趋于同质(群体多样性降低)。因而运动向量Ni更主要地受到局部极值点的影响,不具备强的局部搜索能力。

(2)食物的位置(代表全局最优值)实际是由所有磷虾的当前位置估计出的。当虾群被局部极值吸引时,觅食运动向量Fi难以摆脱其影响,因而个体的局部搜索能力变差。

(3)出于算法收敛的考虑,扩散运动向量Di在算法迭代的后期影响逐渐衰减,因而也不具备强的局部搜索能力。

在文献［6］给出的KH变体算法中,通过增加自适应交叉算子和变异算子来增强KH的局部搜索能力及群体多样性,然而,采用的交叉和变异行为具有

明显随机性特点,且当种群聚集在局部极值点附近时,交叉和变异概率非常低,使得这些算子难以发挥有效作用。

为有效提高KH算法局部搜索能力和收敛速度,本文联合使用精英交叉、基于逻辑自映射函数的混沌局部搜索和对立搜索3种算子对KH算法进行改进,大幅增强其处理复杂优化问题的能力。

3 改进的KH算法

3.1 精英交叉算子

在KH变体算法中,磷虾个体以一定交叉概率同随机挑选的个体进行交叉操作,这种方式显然效率十分低下,不仅收敛速度慢而且局部探索能力弱。受SGA算法采用的贪婪搜索的策略启发［12］,本文提出一种新的精英交叉算子SEL,在KH算法利用式(5)更新位置后,进一步对个体的适应度进行优化,以达到快速收敛的目的,如式(6)所示:

其中,f(·)是适应度函数;crossover(·,·)表示任意交叉操作,如单点交叉、双点交叉等;向量Xe表示当前迭代中的精英集合中的任意一个精英个体。精英集合{Xelitst}由当前适应度最低的前a%磷虾个体向量组成,本文取值为a=10。

显然,与KH变体算法采用的随机交叉算子相比,SEL交叉算子使得个体贪婪地朝当前精英所在的位置靠近,搜索方向更具目的性,有利于加快算法的全局寻优速度。文献［10］采用的SSC交叉算子仅选用当前最优个体进行交叉操作。与之相比, SEL算子与精英集合的任意个体进行交叉操作,该方式有利于保持虾群的多样性,一定程度避免算法陷入局部极值。

3.2 基于逻辑自映射的混沌局部搜索算子

在KH的变体算法中,采用自适应的变异算子进行局部搜索,效率很低［6］。

混沌是非线性系统特有的一种非周期运动现象,具有随机性和遍历性的特点。实验研究结果表明,用混沌序列替代元启发式智能算法中的随机搜索,能够有效提高算法的局部搜索性能［13］。在本文研究中,将采用逻辑自映射函数来产生混沌序列。该函数产生的混沌序列的遍历性通常优于常用的Logistic映射, Circle映射,Tent映射等函数［9,13］,如下所示:

文献［9］通过混沌序列调整KH的模型参数来增强局部搜索能力。文基于逻辑自映射函数设计出一种新的混沌局部搜索算子CHS,如下所示:

CHS算子:

(4)除当前最优个体X∗外,所有磷虾个体按式(8)进行混沌局部搜索并更新位置。其中,符号/和∗表示向量的点除和点乘运算;向量L是搜索空间的位置下限,即L=(l1,l2,…,ln),向量U为相应的位置上限。

其中,rand是区间(0,1)之间的随机数;Cchaos是局部搜索系数,在(0,1)区间内取值,用于控制个体进行局部搜索的活跃度。它的值越小,个体的局部搜索行为越活跃。本文取值为Cchaos=0.2。

显然,利用混沌搜索的轨道遍历性,使得群体容易摆脱局部极值的束缚,从而具备良好的局部搜索能力。

3.3 基于对立搜索算子的种群初始化

任意的n维空间中的点Xi,它的对立点唯一存在且定义为:

KH算法在搜索空间中随机确定初始虾群的位置。然而,文献［14］已经从理论上证明了利用对立点能比随机选择更快地找到最优位置,相关实验也表明对立搜索比随机搜索更为有效。因此,为了加快KH算法的收敛速度,本文借鉴文献［15］的方法,采用一种简单的对立搜索算子OPP用于磷虾种群的初始化,如式(10)所示:

显然,对立搜索算子将使得随机选取的磷虾个体具有更好适应度值,无疑有利于算法的收敛。

3.4 基于3种算子的CO-KH算法

为了提高KH算法的局部搜索能力和收敛速度,本文基于前文提出的3种算子给出了一种新的改进算法——CO-KH,主要步骤描述如下:

CO-KH算法:

初始化:确定算法参数;随机产生P个磷虾个体,并利用OPP算子完成初始化;

(1)r=1,计算磷虾个体的适应度值,并确定当

前最优的磷虾位置X∗;

(2)针对每个个体按式(2)～式(4)计算其运动向量;并按式(5)更新其位置;

(3)更新个体的适应度值并排序,选取前a%作为精英集合,执行SEL算子;

(4)执行CHS算子;

(5)r=r+1,更新体的适应度值,确定当前最优磷虾位置X∗;

(6)如果r小于最大迭代次数rmax,返回步骤(2);

(7)输出最优位置X∗及对应的适应度值。算法的参数包括时间间隔Δt,最大移动步长Nmax,最大觅食速度Vf,最大扩散速度Dmax,惯性权重ωn和ωf。其中,Δt可以按式(11)确定,它与具体应用问题相关。其他参数可以依据磷虾群体的Lagrangian行为模型,经验地取常量值(具体取值情况参见文献［11］的表1)。

其中,时间常量Ct∈(0,2］,控制了磷虾群体的觅食活动的运动幅度。

此外,假设评价个体适应度值1次的时间复杂度为O(f),则CO-KH算法执行1次迭代的时间复杂度为2P·O(f)+O(PlogP)+O(nP),与原始KH算法在同一数量级。其中,为了计算本文算法步骤(3)、步骤(4)中的SEL算子和CHS算子,相对于KH算法需要增加的时间开销为P·O(f)+O(PlogP)+O(nP)。但考虑到达到相同收敛精度时CO-KH算法所需的迭代次数更少(参见实验结果),它具有非常快的运行速度。

4 仿真实验与结果分析

为了检验本文提出的CO-KH算法的优化性能,实验选取了7个标准测试函数进行仿真测试,并与原始KH算法［6］以及最近的改进算法SKH［10］进行性能对比。

4.1 标准测试函数及算法参数设置

标准测试函数如表1所示,其中函数f1～f5是复杂的非线性多模态连续优化函数,存在大量局部极值,常用于测试算法的全局寻优能力、摆脱局部极值的能力及收敛性能,f6-f7是复杂的单模连续优化函数,极难收敛到全局最优点,常用于测试算法的收敛速度。

表1 标准测试函数

实验参数设置如下:对于CO-KH,KH和SKH算法,依据文献［11］的模型研究,设置最大移动步长Nmax为0.01,最大觅食速度Vf为0.02,最大扩散速度Dmax为0.005,惯性权重ωn和ωf的值随着迭代次数从0.9线性变化到0.1,时间常量Ct参照文献［6］的实验取值为0.5。另外,对于CO-KH算法,经反复实验比较,SEL算子中的参数比率a取10,采用单点交叉操作;局部搜索系数Cchaos取值为0.2。对于SKH算法,SSC算子同样采用单点交叉操作。

4.2 实验结果

所有算法在Matlab2011上编码实现,种群规模设置为50,个体采用实数编码,最大迭代次数固定设置为1 500次。每种算法在函数上独立运行30次,并统计平均最优适应度值(Mean)和标准差(Std)。表2给出了相应的实验统计结果。

表2 不同算法的实验结果比较

从表2的实验可以看出,固定迭代次数情况下, CO-KH算法的寻优精度在多模态函数和单多模态函数上均显著优于KH算法,其中,在3个测试函数上的寻优误差低于10-4。这表明本文采用的3种算子有助于增强算法的跳出局部极值的能力,具有非常强的全局寻优性能。原始的KH算法由于局部搜索能力不足,基本上在除f1外上的所有函数上的寻优结果均明显偏离最优值(例如,在Fletcher函数上的平均适应度值达0.624×104),表明KH算法在复杂多模态优化问题上存在容易陷入局部极值而发生收敛停滞的缺陷。相比较,SKH改进算法的寻优精度稍好于KH算法,在f6和f7上获得的寻优精度与CO-KH算法基本在同一个数量级,但在其他函数上的结果仍明显比后者差。此外,CO-KH算法在所有函数上的30次独立实验的统计标准差最小,表明该算法具有良好的鲁棒性。

为进一步比较各算法的收敛性能,实验度量了各算法在不同函数上的平均适应度值进化曲线。限于篇幅,图1～图4只给出了具有代表性的函数f1,f4,f5,f7上的测试结果。可以观察到以下主要现象: (1)CO-KH算法具有最快的收敛速度和最优的精度。例如,在Schwefel2.26函数上300次迭代时的寻优精度甚至优于KH和SKH算法在1 500次迭代时的结果。(2)CO-KH算法能够获得较好的初始值(见图中▼标记)。(3)SKH算法的收敛速度和精度强于原始的KH算法,但仍明显弱于本文算法。

图1 不同算法在函数f1上的适应度进化曲线

图2 不同算法在函数f4上的适应度进化曲线

图3 不同算法在函数f5上的适应度进化曲线

图4 不同算法在函数f7上的适应度进化曲线

实验现象(1)和现象(3)表明本文算法采用的混沌局部搜索算子显著增强了KH算法的局部寻优和避免陷入局部极值的能力,图中CO-KH算法的收敛曲线在中后期仍有明显的锯齿状下降趋势。同时,采用的精英交叉算子使得种群贪婪地向最优解集靠近,因而算法的收敛速度大幅加快。实验现象(2)表明本文采用的对立搜索算子明显提高了算法初始解的质量,有助于加快算法的收敛。

5 结束语

本文针对磷虾觅食算法在求解一些复杂连续函数优化问题时遇到的局部搜索能力差、收敛速度慢等不足,提出一种性能优异的改进算法——CO-KH。使用一种新颖精英交叉算子加快种群的全局寻优速度,并采用一种基于逻辑自映射的混沌局部搜索算子增强其局部寻优能力。此外,利用对立搜索算子提高初始种群的质量。基于7个标准测试函数的实验结果表明,在复杂函数优化问题中,本文算法在寻优精度、收敛速度及鲁棒性方面均优于原始的KH算法及最新的SKH算法,具有良好的应用前景。

［1]Yang Xinshe.Nature-inspiredMetaheuristicAlgorithms［M］.［S.1.］:Luniver Press,2008.

［2]Yang Xinshe.ANewMetaheuristicBat-inspired Algorithms［C］//ProceedingsofNatureInspired CooperativeStrategiesforOptimization.Berlin, Germany:Springer-Verlag,2010:65-74.

［3]Simon D.Biogeography-based Optimization［J］.IEEE Transactions on Evolutionary Computation,2008,12(6): 702-713.

［4]Geem Z W,Kim J H,Loganathan G V.A New Heuristic Optimization Algorithm:Harmony Search［J］.Simulation, 2001,76(2):60-68.

［5]Yang Xinshe,DebS.CuckooSearchViaLevy Flights［C］//Proceedings of World Congress on Nature &Biologically Inspired Computing.Washington D.C., USA:IEEE Press,2009:210-214.

［6]Gandomi A H,Alavi A H.Krill Herd:A New Bioinspired Optimization Algorithm［J］.Communications in Nonlinear Science and Numerical Simulation,2012, 17(12):4831-4845.

［7]Wang G G,Guo L H,Wang H Q,et al.Incorporating Mutation Scheme Into Krill Herd Algorithm for Global Numerical Optimization［J］.Neural Computing and Applications,2014,24(3-5):853-871.

［8]Mandal B,Roy P K,Mandal S.Economic Load Dispatch Using Krill Herd Algorithm［J］.International Journal of Electrical Power&Energy Systems,2014,57:1-10.

［9]Saremi S,Mirjalili S M,Mirjalili S.Chaotic Krill Herd Optimization Algorithm［J］.Procedia Technology,2014, 12(1):180-185.

［10]Wang G G,Gandomi AH,Alavi A H.Stud Krill Herd Algorithm［J］.Neurocomputing,2014,128(1):363-370.

［11]Hofmann E E,HaskellAG,KlinckGM,etal.Lagrangian Modelling Studies of Antarctic Krill Swarm Formation［J］.ICES Journal of Marine Science,2004, 61(4):617-631.

［12]Khatib W,Fleming P.The Stud GA:A Mini Revolution?［C］//Proceedings of the 5th International Conference on Parallel Problem Solving from Nature.Berlin, Gexmany:Springer,1998:683-691.

［13]刘长平,叶春明.具有混沌搜索策略的蝙蝠优化算法及性能仿真［J］.系统仿真学报,2013,25(6): 1183-1188.

［14]Rahnamayan S,Tizhoosh H R,Salama M M.Opposition Versus Randomness in Soft Computing Techniques［J］.Applied Soft Computing,2008,8(2):906-918.

［15]董明刚,牛秦洲,杨 祥.基于对立策略的螺栓遗传算法［J］.计算机工程,2009,35(20):239-241.

编辑 索书志

Krill Herd Foraging Algorithm Based on Chaotic Searching and Elitism Crossover Operator

WANG Leia,ZHANG Hanpengb
(a.School of Economics Information Engineering;b.School of Business Administration, Southwestern University of Finance&Economic,Chengdu 610074,China)

Krill Herd(KH)foraging optimization algorithm is one of the most recent achievements in the field of bionic swarm intelligence.Despite high performance of KH,weak local searching ability and slow convergence speed are two probable deficiencies for solving some high-dimension and multi-modal function optimization.This paper proposes a greedy elitism crossover operator for accelerating convergence,utilizes one chaotic searching operator to escape some local optima based on self-logical mapping function,and employs an opposition searching operator to improve quality of initial population.A new improved KH algorithm combining such three operators is given.Simulation results on 7 benchmark functions show that the new algorithm has remarkable global optimizing ability and fast convergence speed, and outperforms the original KH algorithm and its newest variant algorithm.

Krill Herd(KH)foraging algorithm;local searching ability;opposition strategy;elitism crossover operator;chaotic searching;convergence speed

王 磊,张汉鹏.基于混沌搜索与精英交叉算子的磷虾觅食算法［J］.计算机工程,2015,41(3):156-161.

英文引用格式:Wang Lei,Zhang Hanpeng.Krill Herd Foraging Algorithm Based on Chaotic Searching and Elitism Crossover Operator［J］.Computer Engineering,2015,41(3):156-161.

1000-3428(2015)03-0156-06

:A

:TP18

10.3969/j.issn.1000-3428.2015.03.030

中央高校基本科研业务费专项基金资助项目(JBK130503);四川省教育厅基金资助项目(14ZB0046);教育部人文社会科学研究基金资助项目(10YJCZH153)。

王 磊(1978-),男,副教授、博士,主研方向:机器学习,数据挖掘,计算智能;张汉鹏,副教授、博士。

2014-03-20

:2014-05-30E-mail:wanglei_t@swufe.edu.cn