基于互利共生和优胜劣汰的改进磷虾群算法

王 滔，高岳林，曹 凯

(北方民族大学 信息与系统科学研究所，宁夏 银川 750021)

磷虾群(KH)算法[1]是一种用于优化全局非线性问题的群智能优化算法。该算法是基于对南极磷虾的生存环境以及生活规律的仿真模拟[2]。磷虾群为了更好地存活下来，既要躲避捕食者的袭击，又要时刻搜寻食物的位置；同时，磷虾种群会不断淘汰生存能力较差的个体，使得种群在恶劣的环境中得以繁衍。磷虾群算法前期收敛速度快，但后期无法跳出局部最优，求解精度较差。对此，研究人员对磷虾群算法从不同方面进行了改进，文献[3-5]主要是对算法的部分参数进行了调整，文献[6-7]则是对算法采用不同的改进优化策略，提升了算法的搜索能力。本文提出了一种基于互利共生和优胜劣汰的改进磷虾群算法(MASFKH).在磷虾群每一次迭代过程中，磷虾群中的个体在感知捕食者存在的情况下，会向其他磷虾个体传递危险信号，磷虾个体会不断与其他位置的磷虾进行比较，朝着更安全的位置游去；即适应度值较差的个体会向适应度较好的方向移动，从而达到躲避捕食者袭击的目的，有效地增加了每次迭代过程中的信息交流。然后，通过优胜劣汰的进化策略，用目标函数适应度值好的磷虾个体位置替换目标函数适应度值较差的磷虾个体位置，提升了下一轮迭代的磷虾个体的质量，以此提升算法的求解精度和局部的搜索能力。最后，用仿真实验说明了算法的有效性。

1 KH算法

KH算法是一种新的启发式智能优化算法，该算法主要是基于对南极磷虾群在海洋环境中的生存运动过程的仿真研究。对于每个磷虾粒子，它的位置更新主要受到3个因素的影响：

1) 诱导运动(周围磷虾的诱导)；

2) 觅食活动；

3) 随即扩散。

磷虾个体的速度更新公式采用了下面的拉格朗日模型：

(1)

其中，Ni，Fi，Di分别代表诱导运动、觅食运动和随机扩散。

3个因素的公式构造如下：

Ni=Nmaxαi+wnNold,i.

(2)

Fi=vfβi+wfFold,i.

(3)

(4)

式中：Nmax，vf，Dmax分别代表最大诱导速度、最大觅食速度和最大扩散速度；αi，βi，δ分别代表诱导方向、觅食方向和扩散方向；wn，wf分别代表诱导权重和觅食权重；t，tmax分别为当前迭代次数和最大迭代次数。其中Nmax=0.01，vf=0.02，Dmax=0.005[1].

磷虾个体在t到(t+Δt)区间的位置更新如下：

(5)

(6)

式中：Δt为速度向量的缩放因子；Ct为步长缩放因子，取介于[0,2]的常数；Nv代表变量数；Bu,j，BL,j分别为第j个变量的上界和下界。

为了进一步提升算法的性能，在算法中执行遗传算子(交叉或变异)，经测试，交叉算子更为有效[1]。

(7)

(8)

式中：Cr为交叉算子；Mu为遗传算子；a为[0,1]上均匀分布的随机数；μ为[0,1]内的常数。

2 MASFKH算法

由标准KH算法知,由于算法在迭代过程中粒子运动具有随机性，所以算法运动到较差位置时，即磷虾群运动到捕食者存在的恶劣环境时，磷虾个体之间若不能及时地进行信息传递做出危险预警，磷虾群很容易被捕食掉，也就出现了大量的无效迭代，使得算法不能很好的完成局部搜索；特别是处理多峰优化问题时，算法的解更易陷入局部最优，出现“早熟”现象。基于此，提出了一种基于互利共生和优胜劣汰的改进磷虾群算法。

2.1 磷虾群互利共生策略

自然界中的生物生活在一起，构成了一个稳定的生态系统，不同物种之间不断地发生直接或间接的某种关系。这种关系大致可以分成3类：互利共生，即对双方都相互有利；共栖，只对其中一方有利，但对另一方无害；寄生，对其中一方有利，但对另一方有害。互利共生归纳总结为：不同物种的个体生活在一起，双方都收益的相互关系，也可指即使相互离开但仍可正常生存的生物，它们既相互依存又相互独立，构成了物种间的合作关系。

本文利用的互利共生策略就是使得磷虾之间具有上述的合作关系。磷虾之间通过信息交换、信息传递的方式为其他磷虾个体提高生存能力。磷虾在感知有捕食者存在的危险情况下会四处逃窜，导致整个磷虾群会往不同的方向移动，在此过程中引入互利共生策略，使得磷虾个体之间能够相互交流，传递危险信号，为其他磷虾预警。磷虾个体会通过比较各自的位置优劣，即当前位置的适应度值差的磷虾个体，会朝着适应度值好的磷虾方向移动，从而达到躲避捕食者的目的。记当前位置安全系数水平Xk，全局最安全系数水平Xbest，全局磷虾平均安全系数水平Xmean，用如下公式表示全局最安全的磷虾向所有磷虾发出的危险警告后，各磷虾的移动方式：

X'k=Xk+ri×(Xbest-λXmean) .

(9)

λ=round[1+a(0,1)] .

(10)

其中，ri是[0,1]之间的随机数，λ是预警因子，λ的值是1或2.如果X'k优于Xk，那么就更新Xk；如果X'k优于Xbest，则更新Xbest.

此时，收到全局预警危险信号后，磷虾群之间会相互传递危险信号，所以随机地选择两个磷虾p和q，且Xp≠Xq.这一策略的互利共生现象由下式表示：

(11)

式中：ri是[0,1]之间的随机数；X'p和X'q分别表示磷虾p和q磷虾在交流前的安全系数水平；X"p表示磷虾p向磷虾q交流后的安全系数水平。如果X"p优于X'p，则更新X'p；如果X"p优于X'q，则更新X'q.

2.2 优胜劣汰策略

在上述改进的基础上，本文还加入了优胜劣汰的思想，最终得到了基于互利共生和优胜劣汰的改进磷虾群算法(MASFKH).

优胜劣汰的基本思想是为了维护种群中粒子的多样性。“优胜劣汰”策略具体操作办法为：在对新一代种群生成过后，将对新生成的种群进行适应度值的评估，即按照适应度值进行排序，在算法中将最差的R个粒子舍去，同时在搜索空间随机产生R个新粒子。若R取值越大，则产生的新粒子越多，有利于保持种群的多样性，避免算法陷入局部最优。但如果R的取值很大，则会使算法趋于随机搜索；若R取值越小，则不利于算法维持粒子的个体多样性，算法的全部搜索能力变弱。因此，这里的R取NP/10，其中NP为种群规模。

3 MASFKH算法具体流程

Step 1：确定种群规模并初始化种群及相关参数的设置；

Step 2：将目标函数值作为适应度值，评价种群中每个粒子的适应度，并将当前的磷虾群个体的位置和适应度值存储在各个体的Pbest，将所有的Pbest中最优的存储在Gbest中；

Step 3：采用式(2)—(4)计算磷虾个体的运动速度分量；

Step 4：采用式(9)—(11)对磷虾群实行“互利共生”策略；

Step 5：对于各个体，将其所经历的位置和目标函数进行比较，更新Pbest和Gbest；

Step 6：将新的种群按适应度值排序，进行“优胜劣汰”策略；并保持Pbest和Gbest不变；

Step 7：判断算法是否满足终止条件，若满足，输出Pbest和Gbest；否则，返回Step 3继续搜索。

4 实验及结果分析

4.1 数值实验

为了验证MASFKH算法的性能，本文将MASFKH算法、KH算法和KHLD算法[5]进行比较。分别对10个典型的标准测试函数进行测试，每个测试函数独立进行30次的数值实验。其中f1—f3是典型的单峰函数，在整个搜索空间中仅有一个极值点；f4为病态函数，是一个经典复杂优化问题，它的全局最优点位于一个平滑、狭长的抛物型山谷内；f5—f10是典型的非线性多峰函数，在探索空间中存在大量的局部极值点，若算法的设计存在问题则很难跳出局部极值去全局最优。测试内容包括3种算法在10个测试函数[8-9]上最小值(Min)，最大值(Max)，平均值(Mean)，标准方差(Std)的表现，结果见表1.

4.2 结果分析

对实验数据进行分析时，主要对最小值(Min)、最大值(Max)、平均值(Mean)和方差(Std)等4方面进行比较。从表2可以直观看出，除了f4之外的9个函数，MASFKH算法在Min、Max和Mean方面的数值结果比KH和KHLD算法都有显著提高；Min和Max值分别代表不同算法独立运行30次相同测试函数所得最优值的最小值和最大值，Min值越小说明算法所能达到的最大精度越高；Std代表不同算法独立运行30次所得最优解的方差，方差越小表明算法越稳定。在10个测试函数里MASFKH的Std均是表现最优的。由此可知：Min，Max，Mean方面的表现说明MASFKH算法相较于KH和KHLD算法来说，在绝大多数测试条件下，MASFKH算法具有很强的全局和局部搜索能力，因而在求解精度上表现优异。Std方面的表现说明了MASFKH算法每次独立测试的结果都相差无异，具有较强的稳定性，是一种可靠的智能算法。

表1 测试函数Table 1 Test functions

表2 MASFKH、KH和KHLD等3种算法的数值实验结果Table 2 Numerical results of MASFKH、KH and KHLD algorithm

图1(a)—(f)为各种算法测试函数f1—f10的部分收敛图。图1(a)，(b)为经典单峰函数的收敛实验图，MASFKH算法与另外两种算法相比，前期迅速收敛到极值点附近，在前300代都出现频繁跳出局部最优的趋势，且在精度上提高了4个数量级以上。由图1(c)可以看出，MASFKH算法的最终求解精度虽与KH和KHLD算法相差无异，但MASFKH算法在前期就收敛到了稳定解。图1(d)—(f)为3个经典多峰测试函数对比图，MASFKH算法的收敛速度和求解精度均远优于KH和KHLD算法，说明MASFKH算法更够更准确地找到全局最优值。由表2函数f2、f8、f10实验结果可以看出，在算法迭代的后期，MASFKH相较于KH和KHLD仍具有很强的局部搜索能力，使得算法避免陷入局部最优；由表2函数f2、f5、f8、f10可以看出，MASFKH的最终求解精度即寻优能力远远优于KH和KHLD，均提高了5个数量级以上，在其他测试函数上求解精度也有显著提升；总之，对于大多数的单峰函数和多峰函数，MASFKH算法都能较快地找到函数的最优近似解并达到稳定，说明该算法有着稳定的全局和局部搜索能力。

图1 部分函数的运行结果Fig.1 Results of function

5 结论

针对磷虾群算法搜索能力较差的缺点，提出了一种基于互利共生和优胜劣汰的改进磷虾群算法(MASFKH).通过数值实验可知，MASFKH算法、KH算法和KHLD算法相比较，MASFKH算法增强了每次迭代粒子间的信息交流，有效地利用了局部最优解信息，避免所有磷虾陷入较差的局部最优区域。总的来说，在解决单峰和多峰优化问题上，MASFKH算法在探索能力和求解精度上都有着显著的优势。

[1] GANDOMI A H,ALAVI A H.Krill herd:a new bio-inspired optimization algorithm[J].Communications in Nonlinear Science & Numerical Simulation,2012,17(12):4831-4845.

[2] HOFMANN E E,HASKELL AG E,KLINCK J M,et al.Lagrangian modelling studies of antarctic krill (Euphasia superba) swarm formation[J].ICES Journal of Marine Science,2004,61:617-631.

[3] WANG G G,GUO L,GANDOMI A H,et al.Chaotic krill herd algorithm[J].Information Sciences,2014,274(274):17-34.

[4] SAREMI S,MIRJALILI S M,MIRJALILI S.Chaotic krill herd optimization algorithm[J].Procedia Technology,2014,12(1):180-185.

[5] LI J,TANG Y,HUA C,et al.An improved krill herd algorithm:krill herd with linear decreasing step[J].Applied Mathematics & Computation,2014,234(10):356-367.

[6] 郭伟,高岳林,刘沛.一种自适应惯性权重的改进磷虾群算法[J].太原理工大学学报,2016,47(5):651-657.

GUO W,GAO Y L,LIU P.An improved krill herd algorithm with adaptive inertia weight[J].Journal of Taiyuan University of Technology,2016,47(5):651-657.

[7] 刘沛，高岳林，郭伟.基于自然选择和随机扰动的改进磷虾群算法[J].小型微型计算机系统,2017,38(8):1845-1849.

LIU P,GAO Y L,GUO W.Improved krill herd algorithm based on natural selection and random disturbance[J].Journal of Chinese Computer Systems,2017,38(8):1845-1849.

[8] JAMIL M,YANG X S.A literature survey of benchmark functions for global optimization problems[J].International Journal of Mathematical Modelling & Numerical Optimisation,2013,4(2):150-194.

[9] VANARET C,GOTTELAND J B,DURAND N,et al.Certified global minima for a benchmark of difficult optimization problems[J].Applied Mathematics Computer Science & Automatics for Air Transport,2014.