一种基于交叉选择的柯西反向鲸鱼优化算法

冯文涛,邓 兵

(盲信号处理国家级重点实验室， 成都 610041)

在现代社会中最优化的需求普遍存在，如资源调度、导航规划、任务分配以及结构优化等等。传统的优化算法如最速下降法、共轭梯度法、最小二乘法等[1]，对于优化问题的求解通常是利用梯度信息进行迭代计算，需要正确选取初始值且要求目标函数连续可导，对于解决大规模、不连续、非线性等复杂性较高的问题往往显得力不从心。针对传统优化算法存在的缺陷，基于概率搜索的随机优化算法成为了几十年来新的研究热点。随机优化算法中的模拟退火算法、遗传算法、禁忌搜索算法等[2]算法在解决NP完全或者NP难问题上显示出了良好的性能。模仿自然界生物群体行为的群体智能算法属于随机优化算法的一个分支，也受到了人们广泛的关注与研究，比如人工蜂群算法[3]模仿的是自然界中蜜蜂群的采蜜行为、蚁群算法[4]模仿的是自然界中蚁群的集体觅食行为。模仿大海中鲸群捕食行为的鲸鱼优化算法(Whale Optimization Algorithm，WOA)[5]在2016年提出，具有原理新颖、结构简单等优点，已成功的应用于瞬时混叠信号的盲源分离[6]、水资源的优化配置问题[7]等，WOA算法及其改进算法的性能也优于传统的群体智能算法[8-9]。同其他的群体智能算法一样，WOA算法有时也存在求解精度不高、易陷于局部最优的缺点，而且算法后期的开发能力较弱。

差分进化算法(Differential Evolution,DE)[10]是一种应用非常广泛的智能优化算法，其具有流程简单、容易实现等诸多优点，自提出以来获得了广泛的研究与应用。吴擎等[11]提出了一种基于混合交叉的差分进化算法，李袁等[12]提出了一种基于差分进化模型的多等级子群杂草优化算法，均取得了较好的效果。反向学习的概念由Tizhoosh在2005年提出[13]，并在其后成功的应用于机器学习、进化计算等诸多领域。Rahnamayan等[14-15]证明了基于反向学习的差分进化算法比普通差分进化算法有更快的收敛速度和更高的收敛精度，而且柯西反向点比普通反向点的寻优概率更高。

针对WOA算法存在的缺点，本文首先采用柯西反向学习生成算法的初始种群，然后利用WOA算法生成当前种群的变异向量，并对变异向量进行交叉和选择操作以生成新的子代个体，在更新完种群所有个体后再利用柯西反向跳转技术生成新的反向种群，最后选择当前种群和反向种群中较优的一半个体进入下一次迭代。试验结果证明，所提改进算法能显著提高WOA算法的性能。

1 鲸鱼优化算法

WOA算法模仿的是海洋中鲸鱼群的群体合作捕食行为，算法中的种群更新机制主要包含搜索觅食、收缩包围和螺旋更新位置3种，其选择方式由随机概率因子p和系数|A|的值共同决定。如图1所示。

图1 WOA算法的种群更新机制框图

随机概率因子p是在[0,1]之间生成的随机数，系数A的定义为：

A=2a·r-a

(1)

式(1)中：r为[0,1]之间的随机向量；a被称为控制参数。a定义为：

(2)

式(2)中：t为当前迭代次数；Max_iter为最大迭代次数。可以看出随迭代次数t的增加a从2线性减小到0，因此系数|A|的值也随之从2减小到0。

搜索觅食阶段是鲸鱼随机寻找食物的过程，当前鲸鱼个体随机选取另一鲸鱼个体作为目标并向其位置靠拢，对应着算法的全局开发阶段，其数学模型可表示为：

D=|C·Xrand(t)-X(t)|

(3)

X(t+1)=Xrand(t)-A·|C·Xrand(t)-X(t)|

(4)

式(3) ～(4)中：Xrand(t)是从当前鲸鱼群体中随机选取的鲸鱼个体；X(t)是当前的鲸鱼个体位置；系数A由式(1)决定；C是随机分布于[0,2]之间的系数向量。

鲸鱼群在捕食猎物时采用了泡泡网的攻击方法，包含了收缩包围和螺旋更新位置两种机制，对应着WOA算法的局部开采阶段。在鲸鱼优化算法中，当前获得最优解的种群个体被认为是目标猎物，其他所有个体均向其进行靠拢。

收缩包围阶段的数学模型如下：

D=|C·Xbest(t)-X(t)|

(5)

X(t+1)=Xbest(t)-A·|C·Xbest(t)-X(t)|

(6)

式(5)～(6)中：Xbest(t)是当前鲸鱼群体中位置最佳的鲸鱼个体；A·|C·Xbest(t)-X(t)|为包围步长；|A|越小时鲸鱼游走的步长越小。

在螺旋更新位置阶段，其他鲸鱼个体在接近最佳鲸鱼个体的同时，会以螺旋方式进行游走觅食，搜索其至最佳个体之间可能存在的最优解。螺旋更新的初始点为当前鲸鱼个体的位置，目标终点是当前最佳鲸鱼个体的位置。其数学模型可表示为：

D′=|Xbest(t)-X(t)|

(7)

X(t+1)=D′·ebl·cos(2πl)+Xbest(t)

(8)

式(7)～(8)中：D′表示当前鲸鱼个体与最佳位置鲸鱼之间的距离；b是常量系数；l是[-1,1]之间的随机数。

2 差分进化算法

DE算法主要包含变异、交叉和选择3个过程，其控制参数有种群规模大小、差分变异参数F和交叉概率CR三个。DE算法首先通过差分变异参数F控制生成新一代变异向量，然后将变异向量与目标向量之间进行交叉操作并生成新的试验向量，最后对试验向量和目标向量进行贪婪选择，适应度更好的个体被选择进入下一代迭代过程。

DE算法中的变异操作一般定义如下：

(9)

式(9)中：Xr1(t)、Xr2(t)和Xr3(t)是从当前种群中任意选出的3个不重复的个体向量；变异尺度因子F∈[0,1]。式(9)也被称为DE/rand/1策略，其他变异策略还有DE/rand/2、DE/best/1、DE/best/2等。

在变异操作生成变异向量后，即将变异向量与原目标向量进行交叉操作生成试验向量，常见的交叉方式有二项式交叉和指数交叉两种。其中二项式交叉的应用较为普遍，其定义如下：

(10)

式(10)中：randi, j[0,1]是定义在[0,1]之间的随机数；交叉概率CR∈[0,1]。

试验向量生成后，比较其与目标向量的适应度值，适应度值较优的个体被选择进入下一代。选择操作的数学模型定义如下：

(11)

式(11)中，f(*)表示适应度函数。

选择过程也可分为同步选择和非同步选择两种，其中非同步选择的方式比同步选择的方式性能更优。在非同步选择方式中，每一个新生成的试验向量在与目标向量进行比较后，较优的试验向量立刻替换种群中对应的目标向量并参与剩余种群个体的更新操作，因此算法的收敛速度更快。

3 改进鲸鱼优化算法

根据第1节对鲸鱼优化算法的描述可知，WOA算法将探索过程和开发过程分离开来，且其局部开采能力显著强于全局开发能力，导致算法在迭代后期的全局探索能力不足，易于陷入局部最优。针对WOA算法的上述特点，本文采用了柯西反向学习技术和DE算法的交叉与选择策略以提高WOA算法求解的速度与精度。

3.1 柯西反向学习

k维空间中一个点的反向点定义如下：

定义1假定P=x(x1,x2,…,xk)是k维空间中的一个点，其中xi∈[ai,bi],i=1,2,…,k，ai和bi为P点在第i维的最小值和最大值。则P点的反向点为：

(12)

在一般反向点概念的基础上，很多新颖的反向学习概念也随之产生。柯西反向点定义如下：

定义2假定P=x(x1,x2,…,xk)是k维空间中的一个点，其中xi∈[ai,bi],i=1,2,…,k，ai和bi为P点在第i维的最小值和最大值。则P点的柯西反向点为：

(13)

与普通反向点相比，柯西反向点是在中点和普通反向点之间随机产生的一个点。

本文除了利用柯西反向学习生成初始种群外，在迭代过程中还采用了柯西反向跳转的方式生成当前种群的反向种群，从而加快算法的收敛速度。柯西反向跳转的定义如下:

定义3假如rand[0,1]≤Jr条件满足，则为当前种群生成对应的柯西反向种群，其中Jr为跳转率。

3.2 引入交叉与选择策略的鲸鱼优化算法

在DE算法中，交叉是影响算法性能的关键步骤之一。本文将DE算法的二项式交叉与非同步选择过程引入到WOA算法中，提高了WOA算法的种群多样性和求解精度。

引入交叉和选择策略后的柯西反向鲸鱼优化算法(quasi-oppositional whale optimization algorithm based on crossover and selection strategy，QOWOA-CS)的伪代码如算法1所示。

算法1 QOWOA-CS算法伪代码

1: 设置算法初始参数

2: 生成初始种群P0

3: 生成初始种群P0的柯西反向种群OP0

4: 选择{P0,OP0}中适应度较优的一半个体作为初始种群

5: 选择{P0,OP0}中适应度值最小的个体作为当前最优解

6:while(t

7:for(i=0;i

8: 更新a,A,C

9:if1 (p<0.5)

10:if2 (|A|≥1)

11: 按照公式(4)生成变异向量Vi(t)

12:elseif2 (|A|<1)

13: 按照公式(6)生成变异向量Vi(t)

14:endif2

15:elseif1 (p≥0.5)

16: 按照公式(8)生成变异向量Vi(t)

17:endif1

18: 检查变异向量Vi(t)的有效性

19: 按照公式(10)生成试验向量Ui(t)

20:if3f(Ui(t))

21: 选择用Ui(t)替换Xi(t)

22:endif3

23:endfor

24:if4 rand[0,1]≤Jr

25: 生成当前种群P的反向种群OP

26:endif4

27: 选择{P,OP}中适应度较优的一半个体进入下一次迭代循环

28: 选择{P,OP}中适应度值最小的个体作为当前最优解

29:t=t+1

30:endwhile

31: 算法结束，返回当前所获得的最优解

4 数值试验及分析

为了验证本文所提QOWOA-CS算法的有效性，采用文献[5]中表2及表3所示的f1(x)～f13(x)共13组可变维度的标准测试函数来对算法进行仿真测试，其中f1(x)～f7(x)为高维的单峰函数，f8(x)～f13(x)为高维的多峰函数，所有测试函数的维度均为30维。标准函数f8(x)的理论最小值为-418.982 9×30，其余标准函数的理论最小值均为0。WOA算法的种群大小设置为30，迭代次数为500，算法的独立运行次数为30。算法所在的实验平台参数为Windows 7操作系统、CPU主频2.4 GHz、内存8 GB，实现程序为Mlatlab 2015b。

本节将对柯西反向鲸鱼优化算法(quasi-oppositional whale optimization algorithm,QOWOA)、引入交叉和选择策略的鲸鱼优化算法(whale optimization algorithm based on crossover and selection strategy,WOA-CS)、引入交叉和选择策略的柯西反向鲸鱼优化算法(QOWOA-CS)三种算法与WOA算法分别进行比较，分析柯西反向学习方法和交叉选择策略对WOA算法的影响。

从算法1的描述可以看出，柯西反向跳转步骤生成了当前种群的柯西反向种群，增加了算法的计算复杂度。为了保证算法间比较的公平性，对QOWOA和QOWOA-CS算法的参数设置如下：柯西反向跳转概率Jr=1，交叉概率CR=0.95，迭代次数为250次；WOA-CS算法的CR=0.95，迭代次数为500次，其余参数设置与WOA算法相同。

4.1 柯西反向学习对算法的影响

对QOWOA和WOA算法进行仿真所得的结果如表1所示，平均值较优的值以粗体显示。从表1的结果可以看出，与WOA算法相比，QOWOA算法在f1～f4、f9和f11函数上的寻优能力明显提升，在函数f7和f10上的收敛精度则略有改善，其他标准函数上WOA算法较优。图2示出了函数f7和f13的典型收敛曲线，可以看出柯西反向学习有助于算法在早期的迅速收敛，但是总体而言在算法的迭代后期柯西反向学习对收敛速度及精度的影响较小。

4.2 交叉和选择策略对算法的影响

对WOA-CS和WOA算法进行仿真所得结果如表2所示，平均值较优的值以粗体显示。

从表2的结果可以看出，与WOA算法相比，WOA-CS算法在f1～f7和f10～f13共11个标准函数上的收敛能力更强，仅在f8和f9函数上处于劣势，表明引入的交叉和选择策略能有效提升WOA算法的求解精度。图3示出了两种算法在函数f6和f12上的收敛曲线。

从图3可以看出，WOA算法在后半段迭代过程中已经陷入局部最优，但是WOA-CS算法能持续寻求精度更高的最优解。这也表明交叉和选择策略有效保持了WOA-CS算法种群的多样性，有助于算法及时跳出局部极值，提高了算法的收敛精度。

图2 函数f7(左)和函数f13(右)的收敛曲线

图3 函数f6(左)和函数f12(右)的收敛曲线

表1 QOWOA算法和WOA算法的计算结果比较

表2 WOA-CS算法和WOA算法的计算结果比较

表3 QOWOA-CS算法和WOA算法的计算结果比较

4.3 基于交叉选择的柯西反向鲸鱼优化算法

对QOWOA-CS和WOA算法进行仿真所得的结果如表3所示，平均值较优的值以粗体显示。图4至图10示出了两种算法在13个标准测试函数上的收敛曲线。从表3、图4至图10的结果可以看出，QOWOA-CS算法在最优值、平均值等指标上均明显优于WOA算法，而且在f9和f11上均能收敛到理论最优值0，WOA算法只在f8上胜出。QOWOA-CS算法在收敛速度和收敛精度上均明显优于WOA算法，表明了本文针对WOA算法所提的改进策略切实有效。

图4 函数f1(左)和函数f2(右)的收敛曲线

图5 函数f3(左)和函数f4(右)的收敛曲线

图6 函数f5(左)和函数f6(右)的收敛曲线

图7 函数f7(左)和函数f8(右)的收敛曲线

图8 函数f9(左)和函数f10(右)的收敛曲线

图9 函数f11(左)和函数f12(右)的收敛曲线

图10 函数f13的收敛曲线

5 结论

提出了一种基于交叉选择策略的柯西反向鲸鱼优化算法QOWOA-CS。该算法使用柯西反向学习生成初始种群以及算法进化时当前种群的反向种群，并将DE算法的交叉和选择策略引入WOA算法以提高种群进化时的多样性。实验结果表明，所提的QOWOA-CS算法在收敛速度和收敛精度上相比WOA算法有较大提升。

本文提出的QOWOA-CS算法能够在海量的传感器集合中快速、准确的给出最优的解决方案，具有非常广阔的应用前景。