基于动态压力控制算子的磷虾群算法

沈莹 黄樟灿 谈庆 刘宁

摘 要：针对基础磷虾群（KH）算法在求解复杂函数优化问题时局部搜索能力差、求解精度低、收敛速度慢、容易陷入局部最优等问题，提出一种基于动态压力控制算子的磷虾群算法（DPCKH）。该算法将一种新的动态压力控制算子加入了标准磷虾群算法，使其处理复杂函数优化问题更有效。动态压力控制算子通过欧氏距离量化了多个不同优秀个体对目标个体的诱导效应，进而在优秀个体附近加速产生新磷虾个体，提高了磷虾个体的局部探索能力。通过比较蚁群算法（ACO）、差分进化算法（DE）、磷虾群算法 （KH）、改进的磷虾群算法（KHLD）和粒子群算法（PSO），DPCKH算法在7个测试函数上的结果表明，DPCKH算法与ACO算法、DE算法、KH算法、KHLD算法和PSO算法相比有着更强的局部勘测能力，其开采能力更强。

关键词：磷虾群算法;动态压力控制算子;函数优化;开采能力;探索能力

中图分类号： TP18

文献标志码：A

文章编号：1001-9081（2019）03-0663-05

Abstract： Aiming at the problem that basic Krill Herd （KH） algorithm has poor local search ability and insufficient exploitation capacity on complex function optimization problems， a Krill Herd algorithm based on Dynamic Pressure Control operator （DPCKH） was proposed. A new dynamic pressure control operator was added to the basic krill herd algorithm， which made it more effective on complex function optimization problems. The dynamic pressure control operator quantified the induction effects of several different outstanding individuals on the target individual through Euclidean distance， accelerating the production of new krill individuals near the excellent individuals and improving the local exploration ability of krill individuals. Compared to ACO （Ant Colony Optimization） algorithm， DE algorithm， KH algorithm， KHLD （Krill Herd with Linear Decreasing step） algorithm and PSO （Particle Swarm Optimization） algorithm on 7 benchmark functions， DPCKH algorithm has stronger local exporatioin and exploitation ability.

Key words： Krill Herd （KH） algorithm; dynamic pressure control operator; function optimization; exploitation capacity; exploration capacity

0 引言

群智能优化算法[1-2]是求解复杂的实际优化问题的一种计算方法。该类算法从仿生学的角度，模拟自然界中生物生活习性在定义域中快速寻找目标问题的最优解，具有可扩展性、自适应性和并行性[3]等多种优点。目前，群智能优化算法被广泛地应用于求解复杂的优化问题中，包括有：蚁群优化（Ant Colony Optimization， ACO）算法[4]、粒子群優化（Particle Swarm Optimization， PSO）算法[5]、人工蜂群（Artificial Bee Colony， ABC）算法[6]、遗传算法（Genetic Algorithm， GA）[7]、差分进化（Differential Evolution， DE）算法[8]等。

Gandomi等[9]通过对南极磷虾群（Krill Herd， KH）的生活习性的观察和研究，并于2012年提出了磷虾群（KH）算法，该群智能优化算法[10]通过模仿磷虾的活动方式，能够在算法演化的初期快速收敛，找到表现优秀的可行解。该算法的缺点是磷虾个体随着演化的发展，缺乏全局搜索能力，算法容易陷入局部最优解。针对该问题，相关研究工作者通过优化算法参数和演化策略，改进算法的搜索能力。文献[11]引入差分演化算子，提出了改进的磷虾群算法 （hybrid Differential Evolution Krill Herd， DEKH）;文献[12]中提出的改进算法通过线性递减步长对因子进行缩放，设计完成改进的磷虾群算法（Krill Herd with Linear Decreasing step， KHLD）;文献[13]中设计了一种基于混沌映射的动态参数优化方法对当前种群中的最优值进行更新，从而实现对磷虾群算法的改进;文献[14]中的改进算法对粒子群与磷虾群两种不同类型的群智能优化算法进行了融合，对两种群智能算法规则下进行个体的演化，并分别保留其中的优秀个体。上述对于传统的KH算法的改进主要从参数优化和演化规则两个方面展开研究，均一定程度上改进了算法的性能。然而，已有的改进算法仅仅从适应度函数的角度出发，通过改进参数和适应度评价规则来实现对传统算法的改进，并没有考虑中其中优秀个体周围环境中优秀个体对种群演化的影响，有一定的局限性。

为了进一步提升KH算法的搜索能力和收敛性能，本文设计了一种动态压力控制算子对演化规则进行控制，实现对磷虾群算法的改进。本文提出的基于动态压力控制算子的磷虾群算法（Krill Herd algorithm based on Dynamic Pressure Control operator， DPCKH），首先利用传统KH算法进行全局搜索，评价并保留潜在的优秀个体;然后，通过本文设计的动态压力控制算子在种群中产生的新个体与旧个体之间进行评价选择，保留优秀的磷虾个体。其中，动态压力控制算子通过在当前种群优秀个体的邻域内寻找相似个体，来形成潜在优秀个体种群，从而增强算法的搜索能力，提高算法的收敛速度。最后，本文中通过7个测试函数对提出的改进算法进行了验证，并选取了2种算法进行了对比。实验结果充分证明了本文设计的改进算法的有效性和高精度。

1 KH算法

磷虾群（KH）算法是由Gandomi和Alavi在2012年提出的一种模仿南极磷虾群生存活动的新型群智能算法。磷虾个体的位置移动主要受到三个因素影响：1）其他磷虾个体的诱导运动;2）觅食活动;3）随机扩散活动。

磷虾个体的移动方向用拉格朗日模型建模：

2 基于动态压力控制算子的磷虾算法（DPCKH）本文算法

在通常的KH算法中，由式（5）可知，磷虾个体诱导方向αi由附近磷虾的诱导方向αlocali和最优个体的诱导方向αtargeti组合构成。这里的αtargeti指代种群中最优秀的一个磷虾个体对当前研究的目标磷虾个体产生的诱导方向。对于当前研究的目标磷虾个体而言，比自身优秀的磷虾个体可能有多个，由于没有考虑全局优秀方向的多样性，所以仅由一个优秀个体全局感知方向是存在缺陷的。为了改善克服多样性的不足，提高标准KH算法的开采能力，动态压力控制算子被加入了KH算法。动态压力控制算子从多个优秀个体与目标个体之间的距离入手，更加侧重于全局搜索，这使算法可以避免早熟。

DPCKH算法中，动态压力控制算子主要分为筛选操作和动态压力控制操作两部分。首先对磷虾群体中所有个体进行编号，磷虾种群S定义如下：

动态压力控制算子在DPCKH算法演化初期主要起到局部搜索的作用，此时距离较近的优秀个体权值较大，其诱导作用较强，对算法本身起到加速作用。当DPCKH算法演化到中后期时，距离较远的优秀个体权值较大，其诱导作用更强，由于新个体产生的搜索区域更大，因此跳出局部最优的能力更强，所以增强了算法的全局寻优能力。

动态压力控制算子的详细计算方法见算法1。

其中：popsize指的是种群里磷虾个体的数目，rand表示[0，1]中的伪随机数，X是原始种群中的磷虾个体，K是通过近邻套索算子新产生的磷虾个体。

在动态压力控制算子中，对于函数值最小化问题，如果新产生的磷虾个体适应度值比较差，旧的个体将被保留;如果新产生的个体适应度值比较好，则新的个体将被保留下来。然后DPCKH算法进入下一次演化。

在DPCKH算法中，标准的KH算法被用于全局搜索，其目的在于提供优秀个体的目标区域。在对可行域进行初步筛选之后，动态压力控制算子作为一个局部算子被引入。在算法演化初期，动态压力控制算子主要体现了目标个体近距离优秀个体的诱导作用，这种性质能够提高算法初期的收敛速度。进一步的，在算法演化的中后期，动态压力控制算子主要体现了目标个体远距离优秀个体的诱导作用，这种性质能够提高算法跳出局部最优的能力，使得算法具备更强的全局寻优能力。简而言之，DPCKH算法平衡了磷虾个体在演化过程中开采与探索的矛盾。

将动态压力控制算子加入KH算法之中，得到DPCKH算法。该算法的流程如图1所示。

3 仿真实验与结果分析

3.1 测试函数与实验参数

为了详细检验分析DPCKH算法在函数优化问题下的性能，本文选取标准KH算法、DPCKH算法、KHLD算法以及文献[5]中提到的PSO算法进行比较。实验选取了7个典型的标准测试函数（见表1），其中： f1、 f2是高維单峰函数， f3是高维多峰函数， f4～f7是低维函数并且仅有少数几个局部极小值。

实验参数设置：KH算法与DPCKH算法采用文献[14]中的参数进行设置，其中最大诱导速度Nmax=0.01，最大觅食速度Vf=0.02，最大随机扩散速度Dmax=0.005，KH和DPCKH算法中Ct=1，DPCKH算法中k=10， C=0.2。对于PSO算法，所有的参数设置按照文献[5]中设置，对于KHLD算法，其参数按照文献[12]中进行设置。

3.2 实验结果

所有的算法均在Matlab 2016a软件上进行实现。其中种群规模设置为50，最大迭代次数设置为1000，每种算法在对应的测试函数上运行独立重复运行10次，计算其平均最优适应度（Mean）、标准差（Std）以及最差的最优适应度（Worst）。关于测试函数的维度详见表1，对应各种算法的运行结果如表2所示。

从表2中不难发现，DPCKH算法相比标准KH算法、标准PSO算法、ACO算法和DE算法而言在最大迭代次数内拥有更高的精度，其跳出局部最优的能力更强。对比Mean、Std、Worst三个指标发现，DPCKH算法在这三个方面均领先于其他三个算法，说明DPCKH算法不仅在优化精度上领先其他算法，而且在算法的鲁棒性上也具备一定优势。Mean和Std的优秀表现说明了在有限迭代次数内，DPCKH算法的全局寻优能力优于其他算法，而Std的优秀表现则说明了DPCKH算法更加稳定。

为进一步探讨DPCKH算法的全局搜索能力与局部开采能力，针对高维单峰函数、高维多峰、低维少局部极值三类测试函数，分别提取DPCKH算法、KH算法、KHLD算法、PSO算法的平均误差演化对比结果如图2所示。

高维度单峰函数Generalized Rosenbrock's Function和Generalized Schwefel's Problem 2.26测试结果如图2（a）和（b）所示。PSO算法的收敛速度最快，但是也容易陷入局部最优，导致其寻优精度有限。DPCKH算法不仅收敛速度优于标准KH算法和KHLD算法，而且尋优精度也高于后两者。说明DPCKH算法具有较强的全局探索能力，能够有效地跳出局部最优。高维多峰函数Kowalik's Function的测试结果如图2（c）所示，PSO算法依旧是很快陷入了局部最优，标准KH算法与KHLD算法则一定程度上改善了PSO算法容易陷入局部最优的问题，但是两者无论是收敛速度还是优化精度都劣于DPCKH算法。低维少极值函数Six-Hump Camel-Back Function、Branin Function和Hartman's Function 2的测试结果如图2（d）～图2（f）所示。PSO算法很快地陷入了局部最优，而DPCKH算法无论是在收敛速度还是收敛精度上都优于标准KH算法和KHLD算法。仔细对比（a）、（d）与（e），可以发现DPCKH算法的演化过程中，前期由于较近优秀个体的诱导作用主导，存在一个较快的收敛速度，能够高效地找到潜在优秀个体所在的区域，而中后期由于较远优秀个体的诱导作用主导，提高了算法跳出局部最优的能力，加强了算法全局探索的作用。总的来说，基于动态压力控制算子的DPCKH算法在整个演化过程中，跳出局部最优的能力强于PSO算法、KH算法与KHLD算法。动态压力控制算子改善克服了标准KH算法局部寻优能力不足的缺点，提高了算法的开采能力。

4 结语

本文针对KH算法在处理复杂函数优化问题上局部搜索能力差、开采能力不足导致的收敛速度慢、收敛精度有限的现象，提出了基于动态压力控制算子的磷虾群算法（DPCKH）。DPCKH算法从优秀磷虾个体的诱导效应入手，通过不同距离下的动态压力权重控制，在优秀个体附近加速产生新的优秀个体，充分考察了优秀磷虾个体对目标磷虾个体的影响。进而改善克服了标准KH算法中局部搜索能力不足、开采能力弱的问题。基于7个测试函数在多个维度的测试结果表明，DPCKH算法相比标准KH算法、KHLD算法、PSO算法不仅有着更强的全局搜索能力，寻优精度更高，而且收敛速度更快，稳定性更好。动态压力控制算子让DPCKH算法相较与普通KH算法有着更强的局部勘测能力。下一步的研究目标是继续探讨磷虾群算法在不同参数、不同压力控制下优化效果。

参考文献 （References）

[1] 林诗洁，董晨，陈明志，等.新型群智能优化算法综述[J].计算机工程与应用，2018，54（12）：1-9.（LIN S J， DONG C， CHEN M Z， et al. Summary of new group intelligent optimization algorithms [J]. Computer Engineering and Applications， 2018， 54（12）： 1-9.）

[2] 程述立，汪烈军，秦继伟，等.群智能算法优化的结合熵的最大类间方差法与脉冲耦合神经网络融合的图像分割算法[J].计算机应用，2017，37（12）：3528-3535.（CHENG S L， WANG L J， QIN J W， et al. Image segmentation algorithm based on fusion of group intelligent algorithm optimized OTSU-entropy and pulse coupled neural network [J]. Journal of Computer Applications， 2017， 37（12）： 3528-3535.）

[3] SALEEM M， di CARO G A， FAROOQ M. Swarm intelligence based routing protocol for wireless sensor networks： survey and future directions [J]. Information Sciences， 2010， 181（20）： 4597-4624.

[4] QU M. Lunar soft-landing trajectory of mechanics optimization based on the improved ant colony algorithm [J]. Applied Mechanics and Materials， 2015， 3748（721）： 446-449.

[5] FAYCAL H， ANIS L， ANIS S， et al. A new images segmentation method based on modified particle swarm optimization algorithm [J]. International Journal of Imaging Systems and Technology， 2013， 23（3）： 265-271.

[6] PAN Q-K. An effective co-evolutionary artificial bee colony algorithm for steelmaking-continuous casting scheduling [J]. European Journal of Operational Research， 2016， 250（3）： 702-714.

[7] 肖振久，孙健，王永滨，等.基于果蝇优化算法的小波域数字水印算法[J].计算机应用，2015，35（9）：2527-2530.（XIAO Z J， SUN J， WANG Y B， et al. Wavelet domain digital watermarking method based on fruit fly optimization algorithm [J]. Journal of Computer Applications， 2015， 35（9）： 2527-2530.）

[8] 刘宝，董明刚，敬超.改进的排序变异多目标差分进化算法[J].计算机应用，2018，38（8）：2157-2163.（LIU B， DONG M G， JING C. Multi-objective differential evolution algorithm with improved ranking-based mutation [J]. Journal of Computer Applications， 2018， 38（8）： 2157-2163.）

[9] GANDOMI A H， ALAVI A H. Krill herd： a new bio-inspired optimization algorithm [J]. Communications in Nonlinear Science and Numerical Simulation， 2012， 17（12）： 4831-4845.

[10] HOFMANN E E， HASKELL A G E， KLINCK J M， et al. Lagrangian modelling studies of Antarctic krill （euphausia superba） swarm formation [J]. ICES Journal of Marine Science， 2004， 61（4）： 617-631.

[11] WANG G-G， GANDOMI A H， ALAVI A H， et al. Hybrid krill herd algorithm with differential evolution for global numerical optimization [J]. Neural Computing and Applications， 2014， 25（2）： 297-308.

[12] LI J， TANG Y， HUA C， et al. An improved krill herd algorithm： krill herd with linear decreasing step [J]. Applied Mathematics and Computation， 2014， 234（10）： 356-367.

[13] WANG G-G， GUO L， GANDOMI A H， et al. Chaotic krill herd algorithm [J]. Information Sciences， 2014， 274： 17-34.

[14] WANG G-G， GANDOMI A H， ALAVI A H， et al. A hybrid method based on krill herd and quantum-behaved particle swarm optimization [J]. Neural Computing and Applications， 2016， 27（4）： 989-1006.

[15] 劉沛，高岳林，郭伟.基于自然选择和随机扰动的改进磷虾群算法[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.）