多策略金枪鱼群算法及其应用

吴荣生

(漳州职业技术学院,福建漳州 363000)

0 引言

最优化问题是工程实践中常遇到的一类问题,这些实际问题通常是非线性、多变量、具有复杂约束的[1],因此需要算法去求解.传统的优化方法,诸如梯度下降法、牛顿迭代法等,需要被求解问题的梯度信息,难以高效地求解这些复杂问题.为了解决这些复杂优化问题,受自然界动物群体行为的启发,研究人员提出了多种群智能优化算法.群智能优化算法不需要待解问题的梯度信息,能够很好地平衡计算成本和计算精度之间的关系,因此受到广大研究人员的关注并被用于各种优化模型求解.最常见的群智能优化算法是粒子群算法(Particle swarm optimization,PSO)[2],它模拟了鸟群捕食行为.随着群智能优化算法的不断发展,越来越多的研究人员不断提出并发展新的群智能优化算法,例如鲸鱼优化算法(Whale optimization algorithm,WOA)[3]、灰狼优化算法(Grey wolf optimization,GWO)[4]、旗鱼优化算法(The sailfish optimizer,SFO)[5]等,这些群智能算法被广泛用于各类工程问题的求解.

金枪鱼群算法(Tuna swarm optimization,TSO)是一种启发于金枪鱼合作觅食机制的群智能优化算法,由Xie等人于2021年提出[6].TSO在金枪鱼合作行为的基础上,模拟其两种不同觅食方式达到最优捕食的目的.TSO相比其他算法,结构简单,可调参数少,具有不错的性能.但TSO也存在一些不足,同其它群智能算法类似,TSO也会在优化后期种群多样性减弱,存在陷入局部最优的可能,以及种群个体间的信息交流程度不够.

为了解决金枪鱼群算法存在的不足,本工作提出一种多策略金枪鱼群算法(Multi-strategy tuna swarm optimization,MSTSO).首先,引入局部搜索策略,增强算法开发能力.将混沌算子和局部搜索策略结合,利用混沌算子的遍历性和随机性,进一步提升局部搜索策略的开发能力.其次,提出偏移分布估计策略,使个体能够和优势种群以及最优个体之间充分交流,引导个体进化方向,进一步提升算法搜索能力.为验证改进算法的性能,使用CEC2017测试集对其进行检验,并和多个优化算法进行比较,此外将改进算法应用于求解机器人路径规划问题,实验说明了改进算法MSTSO具有更好的寻优能力,能协调算法的开发和探索能力.

1 金枪鱼群算法

金枪鱼作为顶级的海洋捕食者,是一种群居动物.它们会根据觅食对象选择对应的捕食策略.第一个策略是螺旋式觅食,当金枪鱼进食时,它们会形成螺旋形游泳将猎物带到浅水中,进行攻击从而捕获猎物.第二种策略是抛物线型觅食,每条金枪鱼跟随前一个个体,形成抛物线形状来包围猎物.金枪鱼通过上述两种方法成功觅食.TSO是基于这些自然觅食行为进行建模,该算法遵循的基本规则流程如下:

(1)种群初始化,TSO通过在搜索空间中均匀地随机生成初始群来开始优化过程,进行位置更新.

(1)

(2)a.螺旋觅食,金枪鱼群通过形成紧密的螺旋来追逐猎物,除了追逐猎物,成群的金枪鱼还相互交换信息.每一条金枪鱼都跟在前一条鱼的后面,因此可以在相邻的金枪鱼之间共享信息.基于上述原理,螺旋觅食策略的数学公式如下:

(2)

(3)

特别地,元启发式算法通常在早期阶段进行广泛的全局探索,然后逐渐过渡到精确的局部开发.因此,随着迭代次数的增加,TSO将螺旋觅食的参考点从随机个体更改为最优个体.综上所述,螺旋觅食策略的最终数学模型如下:

(4)

(2)b.抛物线式觅食,除了通过螺旋形成进食,金枪鱼还可以形成抛物线合作进食.其中之一是金枪鱼以食物为参考点,形成抛物线形进行进食.另外一种是金枪鱼可以通过在自己周围寻找食物进行觅食.并假设两者的选择概率均为50%的情况下两种方式同时执行.金枪鱼通过以上两种觅食策略协同捕猎,然后找到它们的猎物.

(5)

(3)终止条件,该算法通过对金枪鱼的所有个体进行不断的更新和计算,直到达到最大迭代次数或者满足允许误差后,返回最优个体和相应的适应度值.

2 多策略金枪鱼群算法

2.1 混沌局部搜索策略

混沌局部搜索策略通过搜索每一个解决方案的附近区域,从而找到更好的解决方案.因此该策略能够有效提高算法的开发能力.混沌映射具有随机性和遍历性的特点,所以利用混沌映射可以进一步提高局部搜索策略的有效性.在MSTSO中,混沌局部搜索策略只应用于种群的优势种群.混沌局部搜索策略的公式具体如下:

(6)

(7)

2.2 偏移分布估计策略

分布估计策略通过概率模型表示个体之间的关系.该策略利用当前优势种群计算概率分布模型,并在概率分布模型抽样的基础上生成新的子代种群,通过不断迭代最终得到最优解.本工作选取表现较好的前一半个体进行采样,并对较差个体使用该策略.该策略的数学模型描述如下.

3 仿真实验与结果分析

3.1 算法性能验证

为说明提出的MSTSO算法性能,选取CEC2017测试集进行验证,包括1个单峰函数、7个多峰函数、10个混合函数和10个组合函数.所有仿真在MATLAB R2016b软件上运行,实验环境为Inter(R)Core(TM)i7-8700 CPU,16 GB内存的电脑.通过选取蝴蝶优化算法(Butterfly optimization algorithm,BOA)[7]、爬行者搜索算法(Reptile search algorithm,RSA)[8]、算术优化算法(Arithmetic optimization algorithm,AOA)[9]、被囊群优化算法(Tunicate swarm algorithm,TSA)[10]和麻雀搜索算法(Sparrow search algorithm,SSA)[11]同改进算法MSTSO比较来说明其性能,为确保实验的公平性,所有算法的种群数为300,最大迭代次数为1 000,其余算法的参数设置均采用原论文参数值,每种算法独立运行51次,统计平均值如表1所示.

表1 七种算法在CEC2017上的测试结果Tab.1 Test results of seven algorithms on CEC2017

分析表1的结果可知,MSTSO在大多数测试函数上表现优异.具体来说,对于单峰测试函数F1,MSTSO虽未能稳定取得最优解,但相比其他算法,MSTSO寻优精度明显优于其他算法,达到9个数量级,这说明MSTSO具有优异的局部搜索能力.多峰函数F2～F8常用于检验算法的全局搜索能力,这类函数通常有多个局部最小值,因此优秀的算法能够跳出局部最小值,得到全局最优值.MSTSO在其中7个函数上均表现最好,仅在F8上排在RSA的后面,对于TSO来说,MSTSO在所有多峰函数上都表现好于TSO,这说明MSTSO的改进策略显著改善了TSO的全局搜索能力.F9～F18和F19～F28分别是混合函数和组合函数,这两类函数结构复杂,能够更好地测试算法解决复杂优化问题的能力,由表1可知,MSTSO仅在F19上排名第二,在剩下的混合函数和组合函数中,MSTSO均表现最优,取得了较好的结果,明显优于TSO,这说明本文提出的改进策略很好地提升了算法解决复杂结构问题的能力,具有较好地解决现实世界复杂优化问题的潜力.综上所述,MSTSO能够很好地平衡算法的开发和探索能力,具有较好的局部最优规避能力,能够有效避免算法早熟收敛.

3.2 机器人路径规划

为了进一步说明改进策略的有效性,检验算法解决具体问题的性能,应用MSTSO来解决机器人路径规划问题.机器人路径规划可被用于多个领域,比如果园喷雾[12]、煤矿救援[13]、物流仓储[14]等.对于该问题,每只金枪鱼代表一条可能的路径.假设有N条可能的路径,维度D由起点到目的点的连接数决定.环境是用栅格法建模的,栅格值用来等同位置上的障碍物.机器人的工作环境被等效为一个平面,类似于栅格效应,然后根据栅格值来确定可行区和障碍物区.网格编号0被定义为可行区,1被定义为障碍区.机器人可以在指定为0的网格上行走.第i只金枪鱼的适应度函数如下所示.

(8)

其中,j表示每只金枪鱼的第j维.在机器人路径规划中,种群大小为300,迭代数为50.选择在测试函数中表现较好的RSA、TSA以及TSO作为对比算法.每个算法都在10×10的模型中工作,最佳路线如图1所示.为了避免偶然性,每种算法都运行了10次,并记录了每种算法的平均值、最优值和最差值.每种算法的统计结果显示在表2中.

图1 四种算法路径规划示意图Fig.1 Diagram of four algorithms for path planning

如图1所示,MSTSO的路线最短,其次是RSA和TSO,而TSA显然陷入了局部最优.从表2可以看出,MSTSO在最优成本、平均成本和最大成本方面是所有算法中最好的.这表明MSTSO相比TSO,能够稳定持续地给出更好的解决方案.图2显示了四种算法的收敛曲线,MSTSO虽然在前期收敛速度较慢,但在后期收敛速度提升,且收敛精度更高.图3是四种算法多次求解路径规划问题的箱式图,再次说明了MSTSO具有更稳定取得更好解的能力.因此,多种策略的引入使算法的搜索更加全面,这大大提高了MSTSO的搜索能力,规划出成本更低的路线.

图2 四种算法收敛曲线图Fig.2 Four algorithms convergence curve 图3 四种算法箱式图Fig.3 Four algorithms box diagram

4 结论

为了解决金枪鱼群算法存在的开发和探索不平衡、易于陷入局部最优等问题,提出融合了混沌局部搜索策略和偏移分布估计策略的多策略金枪鱼群算法.混沌局部搜索策略将局部搜索策略和混沌算子进行结合,有效提升了算法的开发能力;偏移分布估计策略考虑最优个体和优势种群的有效信息,成功引导种群更新,增强种群多样性,提升了算法的寻优性能.仿真实验部分使用五种优化算法在CEC2017测试集上对改进算法性能进行了验证,结果表明本工作提出的MSTSO具有更高的精度和更好的稳定性,性能相比TSO具有显著提升.

此外,使用机器人路径规划问题对MSTSO解决实际问题的潜力进行了测试,仿真结果表明MSTSO能够较好地解决具体问题,具有很好地解决现实世界优化问题的潜力.在接下来的研究中,计划将MSTSO扩展为二进制版本解决特征选择问题,以及修改为多目标版本解决多目标工程优化问题.