一种量子行为磷虾算法及其仿真分析

刘 振， 刘文彪， 鲁华杰

(海军航空大学 岸防兵学院，山东 烟台 264001)

0 引言

磷虾算法作为一种低阶群智能进化算法[1]，具有进化机制简单、收敛速度快等特性，但同时也容易陷入局部极值的情况.因此磷虾算法的改进方式不断涌现，当前对其改进主要可以概括为以下几类：

(1)与局部进化方式进行有效融合.如文献[2]提出个体进化方式依据列维飞行，并利用精英个体更新磷虾个体位置；文献[3]引入反向学习方法初始化种群，用于提高进化效率；文献[4]将混沌算法的思想引入到磷虾算法中；文献[5]对当前种群进化获得的新位置，再次进行局部调整和二次开发，并采用贪婪选择方式.

(2)对磷虾算法中的进化参数进行调整，文献[6]将静态常数Δt进行了自适应推广；文献[7]不仅使Δt自适应变化，同时对惯性权重依据正弦方式进行调整.

(3)在磷虾个体的进化过程中引入传统进化规划的操作算子，如个体迁移、交叉、变异等操作.文献[8]引入了侧重于开采的磷虾迁移操作，能让磷虾个体在进化后期处于全局最优值附近搜索；文献[9]将交叉、变异引入到基本磷虾进化算法中，保证算法进化过程中的全局勘探和局部开采的有机统一.

(4)与其他进化算法的有机融合，文献[10]提出一种混合磷虾进化算法，将磷虾个体依据粒子群算法中的粒子进化操作方式执行.

当前各种群智能进化算法大量涌现，如头脑风暴优化算法[11]，通过聚类和变异等操作方式驱动进化过程，克服传统群智能进化算法存在的随机性和盲目性，但相比磷虾算法缺少生物学进化基础，种群进化中也没有考虑协同机制.量子计算以经典的量子力学为理论基础，充分利用量子的叠加性、相干性、纠缠性，因而使量子计算具有极好的并行计算能力.文献[12-14]将量子计算与人工智能演化算法相结合，使量子计算技术可以结合人工智能进化优势，从而使进化算法具备全局收敛能力强、鲁棒性好等特性.文献[12]较早将量子编码引入到免疫克隆算法中；文献[13]和[14]将量子力学思想分别与引力搜索算法和粒子群算法相融合，构成量子引力搜索算法和量子粒子群算法，有效提升了原有算法的收敛性能.根据量子理论，并利用协同进化思想，笔者提出一种协同进化量子磷虾算法(cooperative evolution quantum krill herd algorithm, CEQKHA).将磷虾进化种群分为主种群、辅种群，将磷虾个体的运动状态以量子态中的波函数表示，以一维delta势阱作为势场，在得到变量分离形式的波函数以后，适当选择势阱参数，使量子磷虾个体在更新位置过程中趋向于当前势阱中心最优个体的位置，从而提高个体局部开采能力.

1 基本磷虾算法及其特性分析

基本磷虾算法用于模拟磷虾群体受到食物源及群体影响的觅食行为，其觅食行为主要受食物吸引度、种群趋同性以及外部不确定因素影响.个体位置的进化过程可以利用拉格朗日模型表示为

(1)

式中：Xi(t)={xi,1,xi,2,…,xi,n}表示第i个磷虾个体在t时刻的位置，n为问题维数；Ni(t)表示t时刻第i个磷虾个体受群体影响的向量；Fi(t)表示第i个磷虾个体受到食物吸引而产生的运动向量；Di(t)表示外界不确定性因素对其运动位置影响的向量，则个体在下一时刻的位置更新可按照式(2)进行：

(2)

磷虾算法进化机制简便，所需控制参数少，由于编码机制设计过于简单，多样性不高，无法在进化过程中保持良好的全局勘探和局部开采性能.为提高基本磷虾算法的全局收敛性能，笔者提出一种协同进化量子磷虾算法.

2 协同进化量子磷虾算法

2.1 多种群协同进化框架结构

传统磷虾进化算法通常都维持单一种群进化模式，无法实现种群之间个体交流和信息的交互.多种群的进化模式能够有效地保证个体进化过程中的多样性[15]，使个体能够以较大的概率接近最优值.因此笔者将磷虾群体划分为主种群和辅种群，经分析验证设置辅种群数目为4，其进化结构如图1所示.

图1 种群协同进化框架Fig.1 Framework for the cooperative evolution

在协同进化量子磷虾算法中，设置主种群为M，辅种群为Subi(i=1,2,3,4).每个辅种群在完成一次进化后，都会把当前寻找到的最优个体gbi(i=1,2,3,4)传递给主种群M，主种群M进行贪婪选择判断后，更新当前全局最优解集.

2.2 量子进化行为

一个微观粒子的量子态一般用波函数表示，因此波函数的演化状态确定以后，就足以描述整个系统的状态[16].薛定谔方程具有和经典牛顿力学等同的作用，在任何时刻粒子的状态都可以用波函数ψ(X,t)表示为:

(3)

式中：ħ为普朗克常数；H为与时间t无关的汉密尔顿操作符.

(4)

式(4)中，等式左边是关于t的函数，而等式右边是关于X的函数，两边相等并且都是能量E.因此，可以获得微分方程为：

(5)

假定在磷虾算法中，所有个体都具备量子行为，选择其中最优的Gbest个体构成吸引势场.不失一般性，假定用量子表示的个体都在一维空间中，因此所有向量X将变成标量x，设定y=x-gbest，其中gbest表示最优个体的位置.应用δ势阱，令其中心在零点处，假定一维势阱的数目和Gbest数目一致，则V(y)=-γδ(y)(γ>0)，其中γ为势阱深度.势阱深度在原点处为无穷，而在其他处为零，此时薛定谔方程为：

(6)

(7)

2.3 不同种群个体多样化位置更新方式

为了充分发挥优良个体引导作用，文献[17]以等概率方式使磷虾个体在最优值附近进行搜索；文献[18]在其基础上，引入了群体平均值，增加了个体位置选择的随机性.笔者借鉴上述思想，提出在主种群中进行全局勘探，采用式(8)更新当前磷虾个体的位置：

k|xi,d(t)-xmean(t)|·ln(1/u),

(8)

在辅种群中，为了进行局部精细开采操作，采用式(9)更新当前磷虾个体的位置：

(9)

通过以上的描述，笔者提出的协同进化量子磷虾算法(CEQKHA)整体流程可以表述如下:

步骤1设定算法进化参数信息，初始化种群P(t)，循环迭代次数t=1；

步骤2将种群P(t)划分为一个主种群和4个辅种群分别独立进化；

步骤4将辅种群Subi(i=1,2,3,4)中最优个体gbi(i=1,2,3,4)传递给主种群M，辅种群向主种群进行精英个体交流；

步骤5按照2.2节的方式对磷虾个体进行量子进化，并依据式(8)和式(9)进行更新；

步骤6判断是否迭代结束，没有结束，则t=t+1，返回步骤3，否则输出最优解，算法结束.

3 收敛性分析

由式(1)和式(2)，并结合式(8)和式(9)可以得到

X(t+1)=X(t)+G(t).

(10)

G(t+1)=μG(t)+αX(t)+β.

(11)

因此,根据式(10)和式(11),可以得到

X(t+2)-(1+μ)X(t+1)+(μ-α)=β.

(12)

由式(12)方程两边的构造可以看出，其为一个差分方程，因此给出定理1.

Δ=(1+μ)2-4(μ-α)≥0，

则可得到

定理1得证.

4 仿真分析

利用基准函数f1～f18进行仿真分析，其中惯性权重ωn=ωf=0.9，Ct=2，最大引导速度为0.01，最大扩散速度为0.005，觅食速度为0.02，种群规模NP=100，循环迭代次数为100.所有仿真分析均在Intel(R) Core(TM) i3-3220处理器，内存2.00 GB，Windows 7系统的计算机上进行，仿真软件为Matlab R2009a.将笔者提出的协同进化量子磷虾算法(CEQKHA)，与基本磷虾算法(KHA)[1]、对立搜索磷虾算法[3](OKHA)以及改进磷虾算法[5](IKHA)进行仿真对比分析，变量取值范围均设定在[-100,100]内，分别利用单模函数、多模函数进行仿真分析，并分析进化框架结构和位置更新方式对算法影响.

4.1 单模函数对比分析

将笔者提出的CEQKHA，利用单模基准函数f1～f6进行仿真分析，其中f1～f3维数为5，f4～f6维数为10.并与基本磷虾算法(KHA)、对立搜索磷虾算法(OKHA)以及改进磷虾算法(IKHA)进行对比，其中基准函数的全局最优值均为0.4种算法分别独立运行30次，统计获得的最优值、平均值和标准差，对比分析结果如表1所示.

表1 单模函数仿真对比分析Tab.1 Comparison results for unimodal functions

从表1的统计结果能够看出，在设定的循环迭代次数范围内，几种磷虾改进算法(OKHA、IKHA、CEQKHA)，相比基本磷虾算法(KHA)收敛性能都有了一定程度的提高.另外,从表1还可以看出，笔者提出的CEQKHA在大部分函数上的进化性能都优于其他几种进化算法.这是由于笔者采用了协同进化框架结构，并应用量子势阱机制，提升了个体在整个搜索空间中勘探和开采能力，因而寻优效果整体优于其他几种改进算法.

为了充分进行算法对比，以f5函数为例进行进一步详细分析，取一次迭代进化收敛如图2所示. 从图2可以看出，OKHA和IKHA分别采用了对立搜索方式和局部搜索算子，提高了算法的基本进化性能;而本文算法不仅采用了协同进化框架，而且采用了量子编码提高了个体的全局和局部搜索能力.另外，基本磷虾算法由于搜索的盲目性，初始进化效果不佳，OKHA和IKHA由于采用了对立搜索方式及局部搜索设计，因而提高了进化能力；而本文的CEQKHA寻优迭代效果较好，能够利用较少的迭代次数就能锁定在最优值附近搜索，因而无论是方差和均值性能均优于其他对比算法.

图2 f5函数仿真对比结果Fig.2 Comparison results for function f5

4.2 多模函数对比分析

将本文算法CEQKHA以多峰基准函数f7～f9为例进行仿真对比分析，其中3个多峰函数的全局最优值均为0，函数维数均设置为20.对比算法也分别是基本磷虾算法(KHA)、对立搜索磷虾算法(OKHA)以及改进磷虾算法(IKHA).4种算法分别运行30次，对其最优值、平均值及标准差进行统计对比，同时进行单侧t检验，并构造检验统计量：

式中：n1和n2表示运行次数；S1和S2表示对比方差；M1和M2为对比均值.

检验假设为：H0：μ1≥μ2，H1：μ1<μ2，μ1和μ2理论最优均值，给定显著性水平0.05，拒绝域为：W={t>t0.05(n1+n2-2)}，经查表后t0.05(58)=1.672 ，统计结果如表2所示.

从表2的统计结果能够看出，当对多模函数进行优化时，本文的CEQKHA相比其他几种进化算法，在大部分函数上都能取得较好的收敛结果.从多模函数优化对比结果可以看到，算法的进化能力得到了考验，对算法的全局开采能力提出了更高的要求.同时表2还给出单侧t检验结果，当显著性水平为0.05时，t的计算结果均大于1.672，因此拒绝假设H0：μ1≥μ2，接受H1：μ1<μ2，说明本文算法平均值优于其他对比算法.

表2 多模函数仿真对比分析Tab.2 Comparison results for multimodal function

4.3 高维函数对比分析

利用高维基准函数f10～f12为例进行仿真分析，其中函数维数均设置为100，3个高维函数的全局最优值均为0.对比算法也仍然是基本磷虾算法(KHA)、对立搜索磷虾算法(OKHA)以及改进磷虾算法(IKHA).4种算法分别运行30次，对平均值、标准差和平均运行时间进行统计,结果如表3所示.

表3 高维函数仿真对比分析Tab.3 Comparison results for high-dimension functions

当函数的维数达到100维时，对于几种进化算法来说，寻找到最优值都会变得较为困难.从表3的统计结果能够看出，整体寻优精度都会有所下降，特别是基本磷虾算法(KHA)，函数寻优性能下降明显，性能指标相比其他几种改进的磷虾算法差距较大，甚至有时无法收敛到全局最优值附近.从所有性能指标的对比可以看出，本文算法仍然能够取得较为优越的寻优效果，显示出算法具有较好的鲁棒性.笔者采用的协同进化搜索框架和量子进化行为增强了算法的全局勘探和局部开采能力，使得CEQKHA相比其他改进的磷虾算法，如OKHA和IKHA，能够获得更优解.

4.4 算法进化行为影响分析

4.4.1 进化结构影响分析

对笔者提出的CEQKHA，当不采用协同进化机制时，将算法标记为CEQKHAwce(CEQKHA without cooperative evolution)，将KHA、CEQKHAwce和CEQKHA，利用f13～f15函数进行对比分析，以验证协同进化框架对算法运行结果的影响，各种算法分别独立运行30次，函数维数均为20，对平均值、标准差和平均运行时间进行统计，如表4所示.

表4 协同进化对算法影响对比分析Tab.4 Comparison results of cooperative evolution

从表4的进化结果可以看到，CEQKHA由于采用了协同进化框架结构和量子进化机制，因此其寻优迭代效果优于CEQKHAwce和KHA，虽然CEQKHAwce没有采用协同进化框架结构，但由于量子进化机制优良的进化性能，其寻优效果还是优于KHA，显示出本文算法良好的进化性能.从表4也可以看到，协同进化框架在提高了算法进化性能的同时，也相应地增加了算法的运行时间，因此适用于对时间要求不高而对精度要求较高的场合.

4.4.2 位置更新方式影响分析

文献[13]提出建立最优粒子集合，并采用轮盘赌方式选择粒子作为势阱中心，用于产生下一代个体，笔者没有采用这种方式，而是采用式(26)和式(27)进行个体更新.将笔者采用的磷虾个体更新方式，以f16～f18函数为仿真对象，函数维数均为20，与文献[13]采用的更新方式进行仿真对比.各种算法独立运行30次，其统计结果如表5所示，其中采用文献[13]更新方式的算法标记为CEQKHAwrw(CEQKHA with roulette wheel).

表5 位置更新方式对算法影响分析Tab.5 Comparison results of position refresh

从表5的统计数据可以看到，笔者提出的CEQKHA在大部分函数上的平均值和标准差都略优于CEQKHAwrw，只是在时间性能上处于劣势;KHA的进化性能相对较差，但其运行时间最短.可以看出,本文算法的进化性能得到了提高，但同时也注意到，为了单纯追求算法的寻优效果，运行时间呈现倍数级增长，对应用时机和场合提出了一定的要求.

5 结论

笔者提出了一种协同进化量子磷虾算法(CEQKHA)，将进化种群划分为主种群和辅种群，采用具有量子进化的行为模式，将当前最优个体设置为量子势阱中心，并在主种群和辅种群内采用不同的个体更新方式.对所提出的CEQKHA进行了收敛性分析和函数仿真分析，显示出所提出算法的优良性能和应用前景.但同时也注意到，受制于进化算法的特性和基本规律，寻找一种既能保证收敛精度又能保证收敛速度的“全优”算法是很困难的.因此，提高算法的运行速度，降低算法的系统开销，将是以后发展方向.