马晓宁，李笑含

(中国民航大学计算机科学与技术学院，天津 300300)

1 引言

Mirjalili S[1]等人在2016年提出了一种仿生优化算法—鲸鱼优化算法(Whale Optimizat-ion Algorithm，WOA)。WOA所需参数少，算法结构及操作简单，然而，算法本身存在易陷入局部最优、收敛速度较慢、求解精度低等缺点，因此备受广大学者的关注，并衍生出很多改进的算法和应用。例如，凌颖[2]为了提高鲸鱼优化算法的全局搜索能力，在鲸鱼个体位置进行所有的位置更新后引入Lévy飞行轨迹策略。M. Huang[3]在传统鲸鱼算法中增加了自适应惯性权重和非线性收敛因子，引入了鲸鱼位置更新中的量子旋转门的概念。E.Emary[4]基于每个搜索代理的随机游动的自适应切换，提出了一种最新引入的鲸鱼优化算法的变体。黄辉先等人[5]提出基于混沌权重和精英引导的先进鲸鱼优化算法(AWOA)。褚鼎立等人[6]通过改进的自适应权重策略来调整算法的收敛速度，通过模拟退火增强鲸鱼优化算法的全局寻优能力。

混沌优化被众多学者应用于算法中，以提高算法的性能。目前文献中引用较多的混沌映射是Logistic映射，例如王涛[7]使用改进后的Logistic混沌映射来初始化种群，增加种群多样性。但单梁等人[8]研究了Tent映射的结构和混沌特性，指出该映射结构简单，且迭代过程适合计算机运行。并且相对一些问题而言，其运算效率要远远高于 Logistic 映射。赵欣[9]也对几种常见混沌映射进行了优化性能比较，指出Tent映射混沌序列的均匀分布性质，可以有效提高算法搜索效率。

本文为提升鲸鱼优化算法收敛性能和搜索能力，解决其易出现早熟现象、求解精度低等问题，提出了一种新的基于Tent混沌映射的可复制的鲸鱼优化算法(TRWOA)。首先，利用Tent混沌映射生成的随机混沌序列，提升初始解的质量。然后，为了加快算法的收敛速度，增强其全局搜索能力，引入细菌觅食优化算法的复制操作，协调全局搜索和局部搜索。与以往鲸鱼算法改进方法不同，本文首次引入细菌觅食算法的复制操作来提高鲸鱼算法的性能，结合Tent映射产生的随机初始化序列，使得改进后的鲸鱼算法性能更优。

2 鲸鱼算法

在鲸鱼算法中，每只鲸鱼的位置代表一个优化问题的可行解[10]。在鲸鱼群的捕猎过程中，鲸鱼有两种捕食行为：一种是包围猎物，所有的鲸鱼游向其它鲸鱼；另一种是气泡网捕食，鲸鱼螺旋形游动并喷出气泡来驱赶猎物。

2.1 包围猎物

首先获得鲸鱼个体位置与最佳鲸鱼位置之间的距离

(1)

2.2 气泡网捕食

气泡网捕食法可描述为如下两种行为：

1) 摇摆包围捕食

鲸鱼个体位置由式(2)更新

(2)

2) 螺旋气泡网捕食

鲸鱼螺旋上游，同时吐出气泡形成起泡网进行捕食。数学模型如下

(3)

设鲸鱼用式(2)或式(3)更新位置的概率各为50%。数学模型如下

式中，p是[0，1]范围内的随机数。

2.3 随机捕食猎物

(5)

3 基于Tent混沌映射的可复制的鲸鱼算法

为提升WOA的算法性能，有效增强其搜索能力和收敛性能，本文提出了基于Tent 混沌映射的可复制的鲸鱼优化算法(TRWOA)。该算法是利用Tent映射产生初始种群，保证初代鲸鱼群个体的随机性，提升其分布均匀性和多样性，从而提高初始解的质量和求解精度。并在每一次迭代后期，引入细菌觅食优化算法的复制操作，首先，对鲸鱼个体进行适应度值降序排序，然后淘汰掉适应度值差的二分之一鲸鱼，优秀的二分之一鲸鱼进行复制，来增强算法的全局搜索能力。

3.1 Tent混沌映射初始化种群

混沌映射特别适用于优化算法的初始化种群，用混沌映射代替随机参数使得算法能够在搜索空间中生成具有良好多样性的初始解。高质量的初始种群对算法的收敛速度和求解精度等性能有很大的帮助[11]。

基本的鲸鱼优化算法初始化种群采用的是随机产生的方法，该方法不仅随机性大，而且不能保证初始解的质量。为提升初始解的质量，利用Tent混沌映射生成的随机混沌序列产生初代鲸鱼群。

Tent映射初始化鲸鱼群步骤如下：

步骤1：确定参数α的值；

步骤2：根据优化问题的目标函数设置初值x0序列的取值范围，随机生成此范围内的X个值；

步骤3：令X0=x0(n)，n=1，2，…，X；

步骤4：令x(1)=X0，x(n+1)由式(6)计算获得

0<α<1

(6)

为保证Tent混沌映射生成的序列有效，α≠0.5，且初值x0和参数α不能相等。

步骤5：保存x序列，进入TRWOA算法主循环。

3.2 复制操作阶段

细菌觅食优化算法主要包括三层循环，最外层的迁徙操作，中间层的复制操作，最内层的趋向性操作[12]。复制操作遵循的是优胜劣汰的规则。在细菌觅食优化算法中，复制操作后种群规模不变。觅食一段时间后，对细菌种群的适应度进行降序排列，把排在后50%细菌淘汰掉，剩余的一半细菌进行自我复制，各自生成一个与自己完全相同的新个体，即生成的新个体与原个体有相同的位置，也就说具有相同的觅食能力[13]。

在本文的算法中，鲸鱼经过一次捕食迭代后，每只鲸鱼均在自己相应的位置上，此时鲸鱼个体位置对应细菌个体位置。鲸鱼复制阶段步骤如下：

步骤1：计算得出上一次迭代完成后第i只鲸鱼个体位置的适应度值之和，即为该鲸鱼的捕食能力值。对于每只鲸鱼i=1，2，..，X，捕食能力值如下

WSkilli=∑fitnessi

(7)

步骤2：对鲸鱼个体捕食能力值(适应度值)进行降序排序

步骤3：令Xr=X/2表示被淘汰鲸鱼数。淘汰掉排在后50%的Xr只鲸鱼，剩下的鲸鱼进行自我复制。

步骤4：计算得出复制生成的Xr只鲸鱼的位置。复制生成的Xr只新鲸鱼与原鲸鱼个体有同等位置，且具有相同的捕食能力。第t次迭代复制生成的Xr只鲸鱼位置如下：

(8)

步骤5：保存各鲸鱼位置，进入TRWOA算法循环。

3.3 TRWOA算法步骤流程

算法主要步骤如下：

1)鲸鱼群规模为X。初始化a，A，C，l，p等参数以及迭代次数Iteration。

2)Tent映射生成分布均匀的初始鲸鱼个体，执行3.1节中步骤1到步骤5。

3)算法主循环，计算并比较每只鲸鱼的适应度值，比较得出当前适应度值最佳的鲸鱼位置，记为X*。

4)如果p<0.5且|A|<1，每只鲸鱼个体按照式(2)更新当前位置，|A|≥1则按照式(5)更新鲸鱼个体位置。如果p≥0.5，则每只鲸鱼个体依据式(3)更新位置。

5)复制操作阶段：执行3.2节中步骤1到步骤5；

6)判断是否满足算法的终止条件，满足则结束循环；否则转到步骤2)。

7)输出全局最优解X*。

算法流程如图1所示。

图1 TRWOA流程图

4 实验结果与分析

4.1 实验设计

为了验证TRWOA算法的性能，选取9个基准测试函数进行测试。这9个函数可以有效地评测算法的寻优能力。基准测试函数详情如表1所示。函数F1、F2、F3、F4、F5是单峰函数，可用于检测算法的收敛速度和搜索精度，其中函数F3是一种病态凹函数，具有局部极值点，主要用以检测算法的收敛速度和全局寻优能力。函数F6是具有许多局部极值点的、复杂的、非线性多模态函数，主要用于评价算法的跳出局部最优的能力。

实验在主频 2.2 G，内存12 G，Windows 10操作系统，Matlab2014b的计算机上实现。实验中算法最大迭代是500次，鲸鱼种群规模是30，各算法独立运行30次。

表1 标准测试函数表

4.2 性能分析

为了验证TRWOA算法的性能，将其分别与基本WOA、Tent混沌鲸鱼算法(Tent Chaotic Mapping-BasedWhale Optimization Algorithm，TWOA)以及可复制的鲸鱼算法(ReproducibleWhale Optimization Algorithm，RWOA)进行寻优测试。每种算法对每个函数单独运行30次，通过比较实验结果的均值和标准差来评价算法的性能。实验结果如表2所示。

表2 实验结果对比表

表2中实验结果的均值反映的是算法的收敛特性，均值小说明算法性能好，从表中可以看出TRWOA的收敛性更好、收敛精度更高。这里的标准差则反映的是算法进行30次实验所得实验结果相对于均值的偏离程度，小的标准差说明实验结果都集中在更小范围之内，算法的稳定性更好。从表中可以看出，基于Tent混沌映射的可复制的鲸鱼算法(TRWOA)与基本的鲸鱼算法(WOA)相比，算法性能得到了很大的提升。对于函数F6、F7、F8，RWOA和TRWOA的实验结果均值和标准差相同，且较WOA更小，对复杂的、非线性多峰函数F6寻优，TWOA也达到了与RWOA和TRWOA相同的结果。实验数据表明，Tent混沌映射和复制操作均可以在一定程度上提高算法的收敛性、收敛精度以及稳定性，将两者相结合的TRWOA性能更优。

为了更好地验证TRWOA的有效性和收敛性，将其与引入Lévy飞行轨迹策略的鲸鱼算法[2](Lévy Flight Trajectory-Based Whale Opt-imizationAlgorithm，LWOA)以及自适应权重改进的鲸鱼算法[6](Improved Whale Optimizat-ion Algorithm，IWOA)进行对比，通过观察收敛曲线来比较各算法的性能。各算法对每个测试函数寻优的优化收敛曲线如图2所示。

图2 算法收敛曲线图

观察图2中的图(g)和(h)发现，迭代初期IWOA收敛速度较WOA和TWOA快，但迭代后期较TWOA慢，且RWOA和TRWOA收敛性均明显优于IWOA。观察图(a)、(f)、(g)和(h)发现，算法LWOA和TRWOA收敛性能难分伯仲，图(b)和(g)显示，在迭代初期算法LWOA的收敛性能优于TRWOA，但观察图(c)、(d)、(e)和(i)发现，TRWOA收敛速度明显优于LWOA，而且LWOA在对函数F3、F4、F5、F9寻优过程中出现了明显的早熟现象，其中函数F3作为病态、单峰、凹函数，其对于全局搜索能力要求更高，说明TRWOA的全局搜索能力较LWOA更强，所以TRWOA算法优化性能比LWOA算法性能更好。综上所述，TRWOA算法稳定性更好，搜索能力更强，收敛性更优。

4.3 TRWOA在TSP问题上的应用

在有n个城市的 TSP 问题中，每只鲸鱼的搜索路线对应一条路径，以求得最短路径为目标，即以式 (9) 作为目标函数，求得f(x)的最小值为最优路径长度。

(9)

其中，d(i，j)为任意两城市间的距离，n为城市数。

为了验证TRWOA算法解决实际优化问题的能力，从TSPLIB 标准库中选取6个不同类型的TSP实例进行实验，并对比不同算法的求解结果。分别以burma14、att48、eil50、st70、pr226、gil262为实验对象对TRWOA以及遗传算法(GA)、蚂蚁群算法(ACO)、模拟退火算法(SA)进行实验，每个算法独立运行10次，每次实验迭代1000次。TRWOA对不同的TSP实例优化所得实验结果如表3所示。不同算法实验结果对比如表4所示，其中偏差率计算公式如下

(10)

表3 TRWOA对各TSP问题10次实验优化结果

表4 不同算法结果对比表

从表3可以发现，TRWOA在城市数量较少的小规模TSP问题中能够收敛到已知最优解，在城市数量较多的TSP问题中该算法也取得了较好的结果。对于burma14问题，每次实验都可以收敛到已知最优解；对于att48问题，每一次实验结果都接近最优解，没有陷入局部最优，能够随迭代次数增多而越接近最优解；对于eil51问题和st70问题，每次实验都尽可能收敛于已知最优解；对于pr226问题和gil262问题，随着TSP问题城市规模的增大，TRWOA也取得了较好的结果。从表4数据可以看出，与GA、ACO和SA相比，TRWOA的搜索能力更有优势。

5 结论

针对WOA的优缺点，本文提出了基于Tent 混沌映射的可复制的鲸鱼算法(TRWOA)，该算法具有如下主要特点：1)利用Tent混沌映射生成的随机混沌序列，提升初始解的质量，从而提高算法的求解精度。2)引入细菌觅食优化算法的复制操作，不但能有效避免其收敛于局部极值点，而且能加快其收敛速度。

本文对具有不同特性的测试函数分别进行了实验。测验结果表明TRWOA较WOA算法性能得到了明显增强，并且TRWOA对优化的函数类型要求不严格，对于有较多局部极值点的、非线性的、多模态的函数仍然具有良好的优化效果，在寻优过程中，能保证整个鲸鱼群的全局搜索能力。最后将改进的鲸鱼算法应用于TSP问题中，与其它各算法对比后更加验证了TRWOA的寻优能力。下一步工作将继续完善TRWOA算法并将其应用到更多的实际组合优化问题中。