融合单纯形法和个体记忆的鲸鱼算法及工程应用

赵筱斌，王未卿

(1.浙江建设职业技术学院 教育技术中心，浙江 杭州 311231；2.北京科技大学 东凌经济管理学院，北京 100083)

0 引 言

鲸鱼是自然界中最大的哺乳动物，拥有独特的捕食方法-气泡网螺旋捕食法。该方法分两个阶段：第一阶段，鲸鱼在水下较深位置围绕猎物螺旋游动生成大量气泡；第二阶段，通过循环方式完成捕食。受此启发，学者Mirjalili提出一种新型群体智能优化算法-鲸鱼优化算法(whale optimization algorithm，WOA)[1]，该算法通过鲸鱼群体搜索、包围、螺旋气泡围捕等过程，实现优化目标搜索。WOA算法执行原理简单易行，依赖关键参数少，拥有较强全局搜索性能，用于函数优化时，求解精度和收敛性能要优于粒子群、引力搜索及差分进化等算法。该算法已经在车间作业调度[2]、物流路径优化[3]、图像分割[4]、群智感知系统[5]、TSP问题[6]、特征选择[7]等诸多领域得到了应用。

然而，基本WOA算法依然存在搜索与开发间难以协调、复杂高维问题求解精度低、收敛速度慢等不足。为此，文献[8]利用Logistic混沌映射优化种群初始位置，并设计非线性自适应权重协调种群搜索能力，提升种群多样性。文献[9]通过非线性收敛因子提升种群多样性，利用局部扰动避免陷入局部最优，提升寻优精度。文献[10]同样利用混沌和非线性收敛因子的组合方式分别提升种群多样性和平衡搜索能力。文献[11]设计自适应随机策略的鲸鱼对猎物的包围方法，可以较好提升收敛速度和寻优精度。文献[12]提出莱维飞行的改进鲸鱼优化算法，通过不同步长飞行轨迹提升种群多样性。文献[13]引入粒子群的惯性权重思维对算法搜索能力进行改进，提升寻优精度。

然而，已有改进工作虽然可以从某些方面优化WOA的寻优性能，但在局部开发与全局搜索的自适应均衡、收敛速度、跳离局部最优上，仍有进一步研究空间。为此，本文将提出一种改进算法，分别引入非线性收敛因子调整、单纯形法及个体记忆融合机制对传统鲸鱼算法的寻优能力进行改进。通过国际公认的若干基准函数的寻优测试验证改进算法可以有效提升收敛速度和寻优精度，实现预期效果。并用一种典型工程设计问题对改进算法的可应用性进行了验证。

1 鲸鱼优化算法WOA的基本原理

WOA是一种新型的受自然界动物行为启发的元启式算法，其主要思想是模拟大海中座头鲸的捕食行为。座头鲸以螺旋形式逐步靠近猎物并生成气泡限制猎物的行动。同其它元启发式方法类似，WOA算法有两个阶段：开发阶段和搜索阶段。开发阶段根据座头鲸包围猎物(代表目前为止的最优解)并逐步向其靠近的机制模拟，可以表示为以下两式

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

(1)

X(t+1)=X*(t)-A·D

(2)

其中，X(t) 为当前鲸鱼个体的位置，X*(t) 为当前种群中最优解的位置(可理解为食物源的位置)，t为当前迭代，A、C为系数矢量，代表鲸鱼向猎物的包围步长，具体定义为

A=2a·r1-a

(3)

C=2·r2

(4)

其中，r1和r2是[0,1]间的随机量，a为收敛因子，取值迭代式从2线性递减至0(模拟向猎物的收缩包围行为)，表示为

a=2-2×t/max_iter

(5)

式中：max_iter为算法的最大迭代数。

下式用于模拟鲸鱼向猎物靠近的螺旋式路径

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

(6)

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

(7)

其中，D′为个体i与当前最优目标的距离，b为对数螺旋形状常量，l∈[-1,1]。 算法以50%概率选择位置更新方式

(8)

式中：p为[0,1]间的随机量。

为了模拟WOA算法的搜索行为，随机选取一个搜索个体更新当前个体位置，以替代根据目前最优解引领个体位置更新，此方法可以提升算法的随机性。该过程可表示为

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

(9)

X(t+1)=Xrand(t)-A·D

(10)

其中，Xrand(t) 为当前种群中随机选取的搜索个体。

WOA算法始于一个随机初始化的种群结构，然后通过目标函数计算每个解的适应度。紧接着选取最优解，并更新相关系数因子。接下来，种群内的解根据式(2)或式(6)进行更新，这取决于随机概率p。该过程重复直到满足预定义的终止条件为止。最终，算法将返回种群内的全局最优解。

2 融合个体记忆和单纯形法的非线性改进鲸鱼优化算法IMSWOA

2.1 非线性收敛因子调整机制

WOA算法的搜索过程始于随机解集合。每次迭代中，个体将根据随机选取的搜索代理或当前最优个体作位置更新。收敛因子a线性从2递减至0，提供全局搜索和局部开发的协调能力。 |A|>1时，选取随机个体为向导作位置更新，即：个体将扩大搜索范围，寻找更好的解，可视为全局搜索； |A|<1时，选取当前最优解为向导作位置更新，即：个体将在局部范围作精细搜索，可视为局部开发。概率p决定是进行螺旋靠近或向目标包围。可见，a决定算法的局部开发与全局搜索之间的协调。由式(5)可知，a值呈线性递减。即：整个过程中，全局搜索和局部开发的递减速率是相同的，这极大降低了鲸鱼搜索个体的灵活性，使迭代早期的搜索和迭代后期的寻优收敛失去平衡。

为此，IMSWOA引入非线性收敛因子递减调整策略，使a值在迭代中以不同的速率进行递减。具体改进公式为

(11)

式中：ainitial、afinal分别为收敛因子的初值和终值，max_iter为最大迭代数，μ为调整系数，μ>0。根据式(11)，收敛因子将随迭代次数呈非线性递减，其曲线为递减式的凸曲线形式。那么，迭代早期a较大，但递减速率较小，可以更大步长实现充分全局搜索。迭代后期a变小，但递减速率变大，这样个体可以以较小的步长以更快的速度在局部范围内进行精细的局部开发，可以加速算法收敛，得到最优解。这种以不同速率递减的收敛因子调整策略将有助于算法的局部开发与全局搜索间的协调进行。

2.2 基于单纯形法的局部搜索机制

单纯形法(simplex method)是一种原理简单、搜索速度较快、局部搜索能力较强的多面体搜索算法。IMSWOA算法进一步引入单纯形法增强局部搜索能力，提升算法收敛速度。单纯形法构建在由若干顶点组成的多面体多维空间上，通过评估各顶点(代表鲸鱼个体位置目标)适应度，寻找最优点、次优点和最差点；然后通过反射、扩展、收缩和压缩4种策略寻找较优点以替换较差点，以形成新多面体结构，通过若干次迭代接近全局最优点。点搜索模型如图1所示。

图1 单纯形法的点搜索模型

基于单纯形式法的局部搜索过程如下：

步骤1 根据选取的基准函数，计算所有顶点(对应种群中的鲸鱼个体)的适应度(由于基准函数是最小值寻优，故适应度值越小，位置越优)，找到适应度最优点Xg、次优点Xb、最差点Xw，并计算中心点Xc为

Xc=(Xg+Xb)/2

(12)

步骤2 根据最差点Xw和中心点Xc的位置，进行反射操作，反射点Xr为

Xr=Xc+α×(Xc-Xw)

(13)

式中：α为反射因子，取值1。

步骤3 若f(Xr)

Xe=Xc+γ×(Xr-Xc)

(14)

式中：γ为扩展因子，取值2。若f(Xe)

步骤4 若f(Xr)>f(Xg)， 说明反射方向不对，进一步作压缩操作，压缩点Xt为

Xt=Xc+β×(Xw-Xc)

(15)

式中：β为压缩因子，取值0.5。若f(Xt)

步骤5 若f(Xw)>f(Xr)>f(Xg)， 则进行收缩操作，收缩点Xs为

Xs=Xc-β×(Xw-Xc)

(16)

式中：β为收缩因子，取值同上。若f(Xs)

2.3 融入个体记忆的位置更新机制

由式(2)可知，鲸鱼对猎物进行包围时的位置迭代更新中仅考虑当前种群的历史最优位置和个体的当前位置的结合来得到最优解，而没有考虑与个体自身经验的交流，即缺乏考虑个体历史最优位置对其位置更新的影响，导致缺乏个体记忆性。为此，借用粒子群优化的思路，将个体的历史最优解考虑在位置更新中，使个体位置更新具备记忆保存功能，促进自身位置进一步寻优。那么，个体包围猎物时，融入个体记忆功能的位置更新方式为

X(t+1)=c1r3·(X*(t)-A·D)+c2r4·(Xibest-X(t))

(17)

式中：c1为社会学习因子，对应于当前种群最优解对个体搜索能力的影响，c2为认知学习因子，对应于个体本身所经历的最优解对个体搜索能力的影响，r3、r4为[0,1]区间的随机量，Xibest为个体经历的最优解。

相应地，鲸鱼的螺旋靠近也进一步添加记忆功能，则

X(t+1)=c1r5(D′·ebl·cos(2πl)+X*(t))+c2r6·(Xibest-X(t))

(18)

式中：r5、r6为[0,1]内的随机量。融入个体记忆后，通过调整社会学习因子和认知学习因子，即可协调个体与种群间的信息交流和个体记忆对整体算法的搜索和寻优能力的影响。

2.4 IMSWOA算法具体过程

输入：初始种群结构X={X1,X2,…,XN}， 收敛因子初值ainitial、终值afinal，算法最大迭代数max_iter，收敛因子调整系数μ，反射因子α，扩展因子γ，压缩因子β，社会学习因子c1，认知学习因子c2，对数螺旋形状常量b

输出：全局最优解X*

(1) 初始化鲸鱼种群，规模为N，表示为Xi,i=1,2,…,N

(2) 计算N个个体的适应度f(Xi)

(3) 选择适应度最小(最优)的个体X*

(4)whilet

(5)foreachXi,i=1,2,…,N

(6) 根据式(11)更新收敛因子a

(7) 根据式(3)、式(4)更新参数A、C，并更新l、p

(8)if(p<0.5)

(9)if(|A|<1)

(10) 根据式(17)更新个体位置//位置包围

(11)if(|A|≥1)

(12) 随机选择个体Xrand

(13) 根据式(10)更新个体位置//猎物搜索

(14)endif

(15)elseif(p≥0.5)

(16) 根据式(18)更新个体位置//螺旋位置更新

(17)endif

(18)endfor

(19) 调用2.2节执行单纯形法优化种群中的较差解

(20) 越界检查，并修正越界个体

(21) 计算种群个体适应度{f(Xi),i=1,2,…,N}

(22) 更新全局最优个体X*

(23)t=t+1

(24)endwhile

(25) 返回全局最优解X*

3 实验分析

3.1 实验环境

为了验证IMSWOA算法在解决高维复杂函数优化问题的有效性，利用表1中比较常用的8种基准函数测试算法的寻优性能(基准函数很多，在此无法列举太多作数值测试分析，但表1中已经涵盖常用单峰函数和多峰函数)。表中包括函数表达式、搜索区间、理论最优值和收敛精度。仿真实验中，改进鲸鱼优化算法的相关参数：最大迭代次数max_iter=400，种群规模为N=30，收敛因子初值ainitial=2，终值afinal=0，收敛因子调整系数μ=10，社会学习因子c1=0.5，认知学习因子c2=0.5。对于每个基准函数，实验均独立运行30次。实验硬件环境为Intel Core CPU 2.5 GHz主频，4 G内存。软件环境为Windows 10操作系统和Matlab 2017a。

表1 基准函数

3.2 IMSWOA算法与同类改进WOA算法的对比

对比算法选择Logistic混沌映射和非线性自适应权重策略的改进鲸鱼优化算法MWOA[8]、非线性收敛因子和局部扰动的改进鲸鱼进化算法NPWOA[9]、惯性权重思维的改进鲸鱼优化算法IWWOA[13]进行性能比较。公有参数中，种群规模和最大迭代次数配置相同。表2是与同类改进WOA算法的对比结果，利用目标函数的平均精度和标准差进行性能对比。依据表2所示结果，IMSWOA算法在所有测试的8个基准函数上基本可以得到最优解，同时标准差也基本为0，表明本文的改进算法不仅拥有较强的寻优能力，而且在不同类型的基准函数上(单峰或多峰)具有较好的稳定性和鲁棒性。NPWOA算法引入非收敛因子和局部扰动机制，确保了WOA具有较强的搜索能力，但其复杂的过程会导致收敛速度变慢。但该算法在部分函数上还是取得了很好的寻优效果。IWWOA算法仅引入惯性权重思维，种群多样性缺乏，寻优精度性能依然不足，改进比较片面。MWOA算法同步在初始种群和收敛系数做了改进，提升了种群多样性，也增强了算法的搜索与开采能力的均衡，性能有所提升。总体上本文的IMSWOA算法的综合性能是4种算法中最佳的。

表2 与同类改进WOA算法的对比结果

图2是4种算法的收敛曲线。篇幅原因，仅罗列5个基准函数。总体观察400次迭代过程中算法的收敛情况，曲线的坠落程度可以反映算法的寻优速度和收敛速度，而曲线的端点值则对应于算法的寻优精度。可以看到，IMSWOA算法的收敛速度是最快的，其下降趋势是所有算法中最明显的，同时具有更高的寻优精度，最为接近理论最优值。IWWOA算法和MWOA算法所表现出的较为平缓的曲线说明算法的寻优速度较慢、收敛速度较慢、寻优精度也较低。

图2 收敛曲线

3.3 IMSWOA算法中不同改进策略的影响

本节测试分析利用IMSWOA算法中的3种改进策略对传统WOA算法进行单独改进时算法的性能表现。将仅利用非线性收敛因子调整机制的改进鲸鱼优化算法命名为NC-WOA算法，将仅利用单纯形法的改进鲸鱼优化算法命名为SM-WOA算法，将仅融合个体记忆的改进鲸鱼优化算法命名为IM-WOA算法。相关参数配置和实验环境配置同上。实验结果见表3。从比较结果可以看出，仅融合个体记忆的改进鲸鱼优化算法IM-WOA对于传统WOA的寻优性能的改进还是比较有限的，而非线性收敛因子调整的NC-WOA算法和单纯形法的SM-WOA算法可以更好提升算法的寻优精度，稳定性也较好，在部分基准函数中甚至可以求解得到最优解。由此可见，对于WOA算法的改进问题而言，均衡个体的搜索与开采能力，提升整体种群质量，避免局部最优显得尤为重要。

3.4 收敛因子不同变化下的性能表现

本节测试收敛因子的变化对IMSWOA算法的性能影响。由收敛因子定义式(11)可知，收敛因子a随迭代次数的递增，主要受其初值ainitial、终值afinal、调整系数μ的影响。收敛因子决定搜索与开采能力的平衡。表4是4组收敛因子初值和终值对得到的实验结果，其它参数配置同上，调整系数为10。表5是4组调整系数取值的实验结果，收敛因子初/终值为2/0。根据表4的结果可以看到，不同的初/终值对寻优效果有一些影响，但影响很有限，在大多数基准函数上，改进算法的寻优精度表现比较稳定，寻优成功率未受到较大影响，说明算法对该因素的依赖性较小。同时，4组取值中，2/0这组取值相对寻优成功率是最高的(其它实验中应用该组取值)。表5的结果表明，调整系数对IMSWOA算法的寻优性能具有一定影响，但不是单纯的提升或者降低算法的性能。初期会随调整系数的增加而提升，到达一定高度后，又会出现下降。总体来看，4组取值中，μ=10得到平均精度和标准差是最好的(在5组基准函数上得到了理论最优解，其它实验中应用该取值)。

表3 不同改进策略下的WOA算法性能对比

表4 收敛因子初/终值的影响(维度=50维)

表5 调整系数取值的影响(维度=50维)

4 基于IMSWOA算法的工程设计优化应用

为了验证IMSWOA算法解决实际问题的可行性，本节进一步将IMSWOA算法用于求解一种标准的工程设计优化问题。因为篇幅原因，仅利用在求解拉伸弹簧设计问题上。拉伸弹簧设计问题的目标是最小化拉伸弹簧的设计重量，该最小化过程同时受到以下4个因素的约束：切变压力、波动频率、外径和绕度。问题的3个变量为：线材直径d、平均绕线直径D、活性线圈数量P。拉伸弹簧设计如图3所示。

图3 拉伸弹簧设计

具体的数学模型如下：

问题变量

x={x1,x2,x3}=[d,D,P]

最小化目标

f(x)=(x3+2)x2x12

约束条件

变量范围

0.05≤x1≤2.00, 0.25≤x2≤1.30, 2.00≤x3≤15.0

表6是20次算法运行中IMSWOA算法与其它已经应用在拉伸弹簧设计问题上的几种智能算法的寻优对比结果，表中同时给出了问题中的3个因变量和最优重量的取值，即优化变量的最优设计值。可以看到，前4种算法的最优解已经非常接近，其最优重量值的差别仅在10-7数量级上，但依然可以看到，IMSWOA算法得到了最小的拉伸弹簧重量。图4中4种算法对于拉伸弹簧设计问题求解的收敛曲线也验证IMSWOA算法可以更快的收敛，这说明算法在处理拉伸弹簧设计优化这类实际工程优化问题上是有效可行的。进一步可以将IMSWOA算法求解焊接梁设计、压力容器设计、三杆桁架设计等不同规模和复杂程度的工程设计问题上，因篇幅受限，在此不作数据列举。

表6 拉伸弹簧设计问题的求解

图4 拉伸弹簧设计求解结果

5 结束语

提出了一种基于单纯形法和融入个体记忆的改进非线性鲸鱼优化算法IMSWOA。算法通过非线性调整使收敛因子在迭代过程中呈现不同递减速率，以此协调搜索与开发间的平滑转换；通过单纯形法增强了算法的局部搜索能力，并利用融合个体记忆和种群最优改善位置更新机制，协调个体与种群间的交流和个体记忆对整体算法的搜索和寻优能力。基准函数测试验证算法可以有效提升收敛速度和寻优精度，避免局部最优解。求解拉伸弹簧设计问题也验证了算法的可行性。进一步研究可尝试将改进算法在其它工程设计或神经网络训练领域的应用验证，以此发现算法存在的可改进点。