具备反向学习和局部学习能力的磷虾群算法

肖素琼，罗 可

1.长沙理工大学 计算机与通信工程学院，长沙 410114

2.长沙理工大学 综合交通运输大数据智能处理省重点实验室，长沙 410114

1 引言

2012年，Gandomi和Alavi通过对磷虾群活动规律进行研究发现，磷虾群个体在运动过程中会受到周围磷虾和估算的食物位置的综合影响，并不断向最优位置（食物）移动。他们采用拉格朗日模型来解释该行为，并提出了一种新型仿生优化算法—磷虾群算法（Krill Herd，KH）[1]。

KH算法相比其他的智能优化算法具有控制参数少（仅有时间间隔参数Δt需要微调）、易于实现，且在连续空间的非线性优化性能强等优点，已被广泛应用于工程技术和科学研究等领域[2-4]。但其存在的易陷入局部最优以及收敛速度慢等问题严重制约它的发展。造成KH早熟的直接原因是由于代表全局最优值的食物位置实际是由所有磷虾当前位置所估计的，在进化末期，一旦磷虾群个体聚集在极值点附近，形成高密度虾群，优质个体的影响力趋于同质，便很难跳出局部最优解，这种现象在处理复杂多峰优化问题时显得尤为突出[5-8]。针对这些问题，文献[5]提出了一种模拟退火算法的磷虾群优化算法以解决全局优化任务。文献[6]将KH算法与整合增量学习算法相结合，解决KH算法多式联运时收敛速度慢的问题。文献[7]将布谷鸟搜索思想引入磷虾群算法，通过对磷虾个体的遗弃和更新来达到快速收敛的目的。文献[8]提出混合KH算法的量子粒子群优化算法，以增强算法的全局探索能力。文献[9]以反向学习为基础，结合柯西变异算子和定位夹紧算子，以提高种群多样性和逃离局部最优解的能力。类似的研究包括文献[10-12]，一定程度克服了KH算法的不足，但大都仅针对单方面的缺陷进行改进。

鉴于上述分析，本文提出具备反向学习和局部学习能力的磷虾群算法。首先利用混沌映射和反向学习的思想初始化种群，然后改进广义的精英反向学习策略，引入根据算法迭代次数自适应调整学习维度的思想，对精英个体进行反向学习，扩大搜索区域范围，提高种群的多样性，迅速逼近全局最优解，最后，选取精英群体，通过自适应的Lévy飞行分布和改进的差分变异算子，提高种群局部搜索能力和算法的收敛速度。

2 相关基础

2.1 KH算法

KH算法是对自然界磷虾群觅食活动的模拟。磷虾群个体在运动过程中通常形成一定的结构，磷虾群密度和食物吸引是影响该结构的两大主要因素。磷虾个体的移动位置可以用拉格朗日模型建模：

KH算法中，引导移动向量Ni()k不仅受到周围磷虾个体的局部吸引，也受到当前全局最优个体的吸引。因此，Ni(k)定义为：

其中，Nmax为最大引导速度，ωn∈[ ]0,1为惯性权重，表示受周围磷虾个体吸引的运动向量，表示受当前最优个体吸引的运动向量。

觅食移动向量Fi(k)由觅食经验及食物指引两部分构成，定义为：

其中，νf为觅食速度，ωf∈[0 ,1]为惯性权重，为食物的吸引程度，为个体历史最优的觅食位置的吸引值。

物理扩散向量Di()k被看作是一个随机搜索过程，定义为：

其中，最大扩散速度用Dmax表示，δ∈[-1,1]表示当前的随机方向向量。

基于以上定义的三种运动，磷虾个体位置更新公式为：

其中，Δt是与实际应用有关的时间间隔。更详细的KH算法参数取值方法及步骤参见文献[1]。

2.2 精英反向学习

反向学习（Opposition-Based Learning，OBL）策略是由Tizhoosh[13]提出的智能计算领域中的一种新技术，其基本思想是对于一个可行解，生成其反向解，同时评估当前解和反向解，选择较优的解作为下一代个体。并说明了反向解要比当前解有约50%的概率靠近全局最优。

定义1反向点[14]（Opposite Point），设X=(x1,x2,…,xD)是D维空间中的一个点（可视为可行解），xj∈[aj,bj]，其对应的反向点可定义为

定义2精英反向解[15（]elite opposition solution）。设当前群体中的精英个体为Xi=(xi,1,xi,2,…,xi,D)，相应的精英反向解定义如下：

其中，Xi,j∈[aj,bj],k∈[ ]0,1为一般化系数。

3 改进后的KH算法

KH算法在优化过程中，种群的多样性和算法的收敛速度之间始终存在着矛盾。对标准KH算法的改进，无论是参数的选取还是其他算法与KH的融合，其目的都是希望在保持种群的多样性的同时，加强算法局部的搜索能力，防止算法在快速收敛的同时出现早熟。本文所提出算法也是基于这一思想，即利用混沌映射和反向学习的思想初始化种群，并通过改进的自适应维度的精英反向学习策略，保持种群的多样性，同时，选取精英群体，通过自适应的Lévy飞行分布和改进的差分变异算子，提高种群的局部搜索能力。具体采用的改进策略如下。

3.1 基于混沌反向学习的种群初始化

基本的KH算法随机确定初始磷虾群的位置，若随机生成的初始值不佳，则对算法的收敛速度以及最终的实验结果造成影响。最近有研究表明，利用混沌初始化和反向学习初始化均取得了较好的实验结果。混沌映射因具有随机性、灵敏性等特点，可以满足算法搜索的多样性[16]。同时，文献[17]已经从理论上证明了基于反向学习的种群初始化可以得到较好的初始解，进而加快收敛速度。因此，本文利用这两种初始化方法的优点，提出了基于混沌映射和反向学习的思想生成初始化种群。混沌映射表达式为：

其中，k为迭代次数，Max_k是混沌迭代设定的最大次数。

算法1初始化种群算法

步骤2 生成反向种群

步骤3比较初始种群和反向种群，选择N个适应度最优的个体组成初始种群。

3.2 基于自适应维度的精英反向学习

文献[15]提出了精英反向解的概念，并从理论上证明了大多数精英粒子的反向解比普通粒子的反向解更靠近最优解。因而，在搜索过程中引入精英粒子的反向解，可拓宽群体的活动区域，提高种群多样性，有利于避免算法陷入局部最优。但在KH改进算法中，若每次迭代都对精英个体位置所有维度进行反向学习，则有一定的盲目性。受文献[18]采用的基于部分维度反向学习策略启发，提出了根据算法迭代次数自适应调整学习维度的精英反向学习策略。一般而言，在进化初期，对精英个体位置选择较大维度进行学习，能有效提高种群的多样性，有更多向全局最优解逼近的机会。在末期，磷虾群已基本接近最优解，可以保留精英个体位置大部分维度优势信息，而仅进行较小维度学习，开发更高精度解。维度更新公式如下：

其中，dim_size表示反向学习维度大小，iter为当前迭代次数，max_iter为最大迭代次数，D为维度表示不大于⋅的整数。

本文采用群体选择机制，设p()g为当前群体，选择适应值最优的个体作为精英个体，根据公式（8）计算当前迭代下进行精英反向学习的维度数，再随机选择相应数量维度根据公式（6）进行精英反向学习产生精英个体所对应的反向群体Eop(g )，从中选择NP个最好的个体组成下一代个体p(g +1)。其中，NP为种群大小，精英个体由适应度最低的a%磷虾个体向量组成，取值为a=10。

显然，与KH改进算法采用单纯的精英反向学习策略相比，自适应调整学习维度的精英反向学习策略能在相同迭代次数下，节省算法运行的时间。同时，精英反向学习策略的采用有利于保持种群的多样性，一定程度地避免算法陷入局部极值。

3.3 精英磷虾群局部学习

基本的KH算法，搜索完全取决于随机游走，因此不能保证算法快速收敛。针对这一问题，用改进的精英磷虾群局部学习代替基本KH算法的随机扩散，主要进行了三方面的改进。（1）改进差分变异搜索算子。以差分进化算法思想为基础，选取了变异选择操作，并对其进行了优化设计，以加强种群的局部搜索能力。（2）基于Lévy飞行引入自适应步长α。α在迭代的过程中自适应减少，这是类似基本KH[1]中惯性常数递减的原因，目的是为了更好的进行搜索，以接近全局最优解。（3）考虑到精英群体比普通群体具有更优的搜索信息空间，所以，在改进算法中，仅添加精英群体之间的局部搜索以达到更快收敛的目的。通过测试基准函数，选取的精英群体占35%能取得最好的结果。

实现思路如下：

（1）在精英群体中，对每个个体xi，在搜索半径内随机选择第二个精英个体xj，并利用两者之间的差分结果指导xi进行局部搜索，增强xi邻域内的搜索能力，如式（9）所示：

在式（9）中，r∈[-1,1]是服从均匀分布的随机数，用于控制搜索方向；dt为第t代时的缩放因子，搜索前期，进行全局大范围的搜索，加快收敛速度；而进化末期，通过较小的步长逐步求得更高精度的解。因此，dt采用线性递减策略控制搜索半径，表示为：

（2）考虑选择的随机性，以及到进化后期，磷虾群形成高密集型种群，可能导致同时选中同一位置的磷虾。在这种情况下，采用自适应Lévy飞行方程进行局部搜索，则xi位置更新为：

其中levy(λ)表示随机游走路径，服从概率分布levy～u=为点乘积，步长，A为最大Lévy飞行步长，G为当前迭代次数，用于控制搜索范围。

（3）对局部搜索的结果x′i采用贪婪保留策略，即：

上式中，fit()

x为x的适应值。

3.4 改进算法—RLKH算法

（1）初始化参数：种群规模NP，设置觅食速度Vf，最大扩散速度Dmax，最大诱导速度Nmax，最大Lévy飞行步长A，精英磷虾占总磷虾群的比例Pa，精英磷虾的数量，迭代次数G=1。

（2）执行算法1，初始化种群 p(g)。

（3）从 p(g)中选择适应度最优的前10%的个体作为精英群，根据公式（6）、（8）产生精英个体的反向解，加入反向种群Eop(g)，从中选择NP个适应值最好的个体组成下一代种群p(g+1)。

根据公式（1）进行诱导运动；

根据公式（2）进行觅食运动；

选取当前磷虾所处位置xi，随机从精英磷虾群中选择磷虾xj；ifxi=xjthen

计算Lévy飞行步长，生成新的磷虾 x′i，并计算适应值 fx′i；

else

x′i=xi+r⋅dt(xi-xj)并计算适应值 fx′i；

比较 fx′i与 fxi，保留适应值较优的磷虾个体；

重新评价种群适应值及当前最优个体；

（5）若G

4 实验与结果分析

为了检验本文所改进算法的性能，将RLKH算法与基本的KH算法以及最近提出的KH-QPSO算法[8]和OKH算法[9]进行性能对比。

4.1 测试函数与参数设置

本文选用8个经典测试函数进行测试，其中，f1～f3为单峰连续优化函数，常用于考察算法的执行效率。f4～f8为多峰连续优化函数，存在多个局部极值，且数量随维度增加，常用于测试算法摆脱局部极值和全局寻优能力。实验基准函数见表1。

实验参数设置为：（1）对于四种算法的共同参数，依据文献[19]的模型进行如下设置：种群规模NP=50，最大诱导速度Nmax=0.01，最大觅食速度Vf=0.02，最大扩散速度Dmax=0.005，惯性权重ωf和ωn的值随着迭代次数从0.9线性变换为0.1。（2）KH-QPSO算法和OKH算法除共同参数外，均按照其参考文献提供的最优参数进行设置。（3）对于本文的RLKH算法，设置最大Lévy飞行步长A=1，经过反复的实验对比，精英磷虾比率Pa设置为0.35。

此外，所有实验均在操作系统为Windows 10，双核Intel处理器和4 GB内存，Matlab2014的平台上完成。

4.2 时间复杂度

设种群规模为NP，算法最大迭代次数为Imax，评价磷虾个体适应值1次的时间复杂度为O(f)。对于基本的KH算法，时间复杂度为O(Imax⋅(f⋅NP))。KH-QPSO算法每次迭代操作时都要计算每个粒子的局部最优位置，以此达到函数的最优解决方案，而平均最优位置计算消耗了较多的时间。例如，若测试函数维数为D，则每次迭代更新该种群最少需要进行NP(D+1)次计算。算法时间复杂度为O(Imax⋅f⋅NP(D+1))。OKH利用反向学习初始化种群，引入了柯西变异算子和定位加紧算子，其中每个磷虾个体位置更新都需要计算权重w(j)，则算法时间复杂度为 O(Imax⋅f⋅(NP+1))。本文RLKH算法采用混沌反向学习初始化方法，虽然增加了NP次计算，但仅在种群初始化时构建一次。利用精英反向学习策略也仅是选择种群10%的个体。采用改进的精英磷虾群局部搜索代替标准KH算法的随机扩散，只是改变了学习方式，并未增加额外的时间消耗。同时，本文选取35%的精英磷虾个体执行主体改进算法，大大节省了整个算法收敛时间。RLKH算法整体的时间复杂度为O(0.35⋅Imax⋅f⋅NP)。因此本文改进算法比其他三种算法耗时要少。

表1 基准测试函数

4.3 实验结果及分析

为了消除算法的随机性影响，每种算法在函数上独立执行30次，最大迭代次数设置为2 000次，并统计优化结果均值（Mean）和标准差（Std）。优化结果均值反映了给定最大迭代次数下算法的寻优精度，标准差反映了算法的鲁棒性。具体统计数据见表2。

从表2可以看出，固定函数迭代次数下，RLKH算法在单模态函数和多模态函数上均取得了最优的表现。对于形式简单的单峰函数 f1，RLKH算法能快速收敛到全局最优解0。对于最优解附近陡峭而极其难以极小化的病态二次函数 f2，RLKH在迭代后的最终收敛精度为2.59×10-2，比其他算法至少提高3个数量级。对于相对容易收敛的多峰函数 f4，RLKH的收敛精度在10-11以上。对于存在大量局部极值的复杂多峰函数 f5～f8，RLKH仍能收敛到最优值附近，收敛精度显著优于其他三种算法。此外，KH算法的收敛精度在所有函数上最差，OKH算法的收敛精度优于KH-QPSO算法，但在8个基准测试函数上明显劣于本文算法。

为了更加直观地比较各算法的收敛速度和寻优性能，图1给出了各算法在不同测试函数上的收敛曲线。限于篇幅，只给出了6个函数上的实验结果。可以观察到以下主要现象：（1）RLKH算法能够获得较好的初始值。（2）RLKH算法具有最优的精度和最快的收敛速度。例如，在Rosenbrock函数上迭代次数约为250次的寻优精度甚至优于其他三种算法在迭代次数2 000次的结果。（3）RLKH算法的收敛曲线在中后期仍有减缓的下降趋势。实验现象（1）表明本文采用的混沌反向学习的种群初始化可以得到较好的初始解，进而加快收敛速度。实验现象（2）和现象（3）表明本文算法采用的精英局部搜索策略具有优异的寻优效率，采用的自适应的Lévy飞行分布和改进的差分变异算子使得算法能迅速向最优解靠近，具有很强的局部寻优和跳出局部最优解的能力。

表2 四种算法的实验结果比较

图1 测试函数的进化曲线

与本文RLKH算法相比，KH算法的收敛曲线下降缓慢，除函数 f1和 f4外，基本上陷入了局部极值且收敛精度最低。KH-QPSO算法混合了量子粒子群算法，一定程度增加了种群的多样性，但寻优机制未发生变化，因而其收敛速度和精度并没有得到明显的改善。OKH算法利用柯西变异算子能提高算法的探索能力，使种群能快速靠近最优解，因此算法前期的收敛速度较快，但后期缺乏有效的摆脱局部极值的机制，收敛速度趋缓，未能达到较高的收敛精度。

综上所述，相比其他三种算法，RLKH算法在收敛速度和精度方面具有明显的优势，是一种有效的全局优化算法。

5 结论

为了改善基本KH算法在处理复杂多峰优化问题时容易早熟、收敛速度慢等不足，提出具备反向学习和局部学习能力的磷虾群算法。利用混沌映射和反向学习的思想初始化种群，可以得到较好的初始解。通过改进的自适应维度的精英反向学习策略，提高种群的多样性，并迅速逼近全局最优解。最后选取精英群体，通过自适应的Lévy飞行分布和改进的差分变异算子，加强种群局部搜索能力的同时使算法能更快的收敛。实验结果表明，本文提出的RLKH算法相对于标准的KH算法及最近的KH-QPSO算法和OKH算法具有更高的收敛速度和较高的求解精度，具有良好的应用前景。