融合改进天牛须和正余弦的双重搜索优化算法

姚信威，王佐响，姚 远，黄 伟

(浙江工业大学 计算机科学与技术学院，杭州 310023)

E-mail：xwyao@zjut.edu.cn

1 引 言

随着科学技术的不断发展，生产力的迅猛提升使得优化问题逐渐成为现阶段研究的热点.近年来，不断有新的算法被提出和拓展，如遗传算法(Genetic Algorithm，GA)[1]，模拟退火算法(Simulated Annealing Algorithm)[2]，粒子群优化算法(Particle Swarm Optimization，PSO)[3]，蝙蝠算法(Bat Algorithm，BA)[4]，蚁群优化算法(Ant Colony Optimization，ACO)[5]，风驱动算法(Wind Driven Optimization，WDO))[6]等等，而这些算法也可以分为两类：基于个体和基于群体的.第1类只生成优化一种解决方案，而第2类会生成多个解决方案并优化.这种特点使得上述算法在科学和工业领域得到广泛关注，尽管现阶段在该领域已经有很多优化算法，但是没有一种算法是能够满足所有的优化问题的[7]，所以仍有大量优化算法不断在被提出和改进.

正余弦优化算法(Sine Cosine Algorithm，SCA)[8]是2016年由Seyedali、Mirjalili教授提出的一种群智能优化算法，该算法基于正余弦数学函数设计，算法始于一组随机解，通过目标函数反复评估此随机解，并通过作为优化技术核心的一组规则对其进行改进，位置的更替通过线性递减函数即转换参数完成，该算法被验证有效并已经应用到很多现实问题上，如天气多方位分析预测系统[9]、城市动力系统全局调度优化[10]、城市土地优化配置问题[11]、图像分割[12]、结构损伤检测[13]、数据挖掘等许多问题上，但是在其他高维或者更加复杂的情况中，往往会受到一些瓶颈，如陷入局部最优解、计算精度低等.

为了解决传统正余弦优化算法存在的问题，很多研究者把目光朝向了改变转换参数和加入动态调整等方向.转换参数对整个正余弦优化算法的搜索能力有很大的影响，对正余弦的进一步研究可以了解到，其先是进行全局范围内的搜索，再对局部进行进一步优化分析，所以转换参数应该随着搜索过程而改变，根据这个原理，刘勇等[14]针对转换参数的设置进行分析，提出将传统正余弦算法中的线性递减函数更改为非线性递减函数，采用抛物线函数来设置参数，称为(Parabolic Sine Cosine Algorithm，PSCA)；Li Ning等[15]提出了一种新的正余弦优化算法(Bare bones Sine Cosine Algorithm，BBSCA)，该算法结合了高斯搜索方程和指数递减策略来生成个体；Shubham Gupta等[16]针对SCA的停止和局部最优解的情况提出用扰动率产生相反种群并引入自适应权重从而使算法能充分搜索函数区域，其把该算法称为修正正余弦算法(Modified Sine Cosine Algorithm，MSCA)；Yetao Ji等[17]发现SCA在算法后期处理复杂问题容易陷入局部最优和惰性收敛，为了让SCA算法在全局搜索和局部探索之间的变换更加灵活，提出一种基于自适应参数和混沌开发策略的改进SCA来增强算法的局部搜索能力；Wen Long等[18]发现传统SCA以及变体并没有在高维全局优化问题中得到广泛应用，为了解决高维问题，提出了一种引入惯性权重的改进SCA(Improved Sine Cosine Algorithm，ISCA)，同时采用了一种基于高斯函数的非线性转换参数减少策略来平衡SCA的两个探索过程；Rizk M 等[19]考虑到SCA无法对解决方案的多样性进行保护以及没能采用强调策略引导搜索区域，提出了一种基于正交并行信息的SCA(Sine Cosine Algorithm via orthogonal parallel information，SCA-OPI)，引入多正交并行信息，采用一种基于经验的对立方向策略来保持搜索能力；Turgut[20]结合回溯算法的优点，提出了一种混合正余弦优化算法(Backtracking Search Algorithm & Sine Cosine Algorithm，BSA-SCA)并在此优化算法基础上实现了管壳式蒸发器的优化设计；Chegini等[21]将正余弦位置更新方程与粒子群优化算法以及Levy flight(LF)方法结合，提出了新的混合算法，LF方法是一个随机游动，通过Levy分布生成搜索步骤，随着跳转次数的增加，在搜索空间内能进行更加有效的搜索，提高基础正余弦的搜索能力，避免陷入局部极小值；Issa等[22]通过引入调优参数并结合粒子群优化来改进正余弦算法.

尽管已经有部分学者对SCA算法进行改进，如优化参数或结合粒子群等其它算法，但是该算法存在的易陷入局部极小值问题仍无法完全避免，算法收敛精度较低还是需要改善，针对上述问题，本文提出了融合改进天牛须搜索算法(Beetle Antennae Search，BAS)和正余弦的双重优化算法(BAS-SCA).天牛须搜索(Beetle Antennae Search，BAS)，也叫甲壳虫须搜索，是Jiang Xiang-yuan[23]在2017年提出的一种高效智能优化算法.与遗传算法、蚁群算法、风驱动等智能优化算法不同，天牛须搜索可以在忽略函数的具体信息如函数的梯度等情况下完成寻优目标，并且天牛须搜索只需要一个个体就能够进行寻优计算，因此天牛须算法的运算量远小于粒子群算法.但是基础的天牛须搜索步长是固定的，为了更好的改善性能，将天牛须搜索的固定步长改为变步长提升正余弦优化算法搜索性能.在正余弦中提出了一种新的自适应转换参数模型，改变了传统的线性递减参数设置，此外，引入了一个全新的自适应惯性权重机制来保证算法后期的收敛性，变步长天牛须搜索对改进正余弦算法进行二次寻优，增强了正余弦优化算法的局部搜索能力.通过14个标准测试函数上的仿真实验，与抛物线正余弦优化算法[14]和指数正余弦优化算法[15]进行对比，本文所提算法在寻优精度和寻优准确度上都有较大的性能优势，证明了算法的可行性.

2 正余弦优化算法

标准的正余弦算法的位置更新公式如式(1)所示，正余弦搜索过程可以分为两个过程[24]：探索和开发，探索过程中，算法以高概率将随机解组合，寻求在搜索空间内最有希望的区域.

Xt+1i=Xti+r1×sin(r2)×|r3Ptj-Xti|，r4<0.5
Xti+r1×cos(r2)×|r3Ptj-Xti|，r4≥0.5

(1)

其中，t为当前迭代次数，Xti为在第t次迭代下第i个粒子在第j维度下的最优位置，r2/r3/r4是3个参数，r2变化范围在[0，2π]，r3变化范围在[-2，2]，r4变化范围在[-1，1]，Ptj为在t次迭代下的目标点，r1称为转换参数并且为一个线性递减函数，它会随着迭代次数的增加从常数a线性递减至0，它的线性变化公式如式(2)所示：

r1=a-taT

(2)

其中，T为最大迭代次数，a>0.

正弦余弦算法的迭代过程如图1所示，图中的r1设为2，可以看出，当r1sin(r2)或者r1cos(r2)的值在区间(1，2]或[-2，-1)之内时，SCA对全局环境进行搜索；当r1sin(r2)或者r1cos(r2)的值在区间[-1，1]之内时，SCA对已探索空间进行局部寻优操作.可以看出，正余弦优化算法的性能好坏很大程度上取决于全局和局部搜索两者能否达到一种动态平衡，全局搜索用于快速定位最优解的范围，而局部解则在该范围内来寻找最优解，全局搜索过多会使得搜索效率低下，而局部搜索过多会使得算法陷入局部最优解的情况.

图1 正余弦算法原理图Fig.1 Schematic diagram of sine and cosine algorithm

3 天牛须搜索算法

天牛须算法是一种有效的元启发式算法，其灵感来自于天牛的觅食行为[25]，如图2所示，将天牛简化模型分为天牛左须和右须，两须之间的距离为d0，两须到天牛质心的距离是相等的，天牛须搜索分为两个步骤：搜索行为和检测更新行为.天牛在每次迭代中都会根据随机方向进行移动，该算法的实现需要先对搜索方向进行矢量归一化处理，如式(3)所示：

b→=rand(j，1))‖rand(j，1)‖

(3)

其中，rand函数表示一个随机函数，j代表当前位置的维度.

图2 天牛须搜索原理图Fig.2 Schematic diagram of beetle antennae search

用式(4)初始化天牛须的双向搜索行为：

xr=xt+dtb→

xl=xt-dtb→

(4)

其中，xr代表的是右向的搜索空间，xl代表的是左向的搜索空间，dt是天牛须到天牛质心之间的距离，更准确的说，dt是某个特定时刻对应的天牛的搜索区域.

天牛须当前位置根据式(5)的规则进行更新移动：

xt+1=xt+δtb→sign(f(xr)-f(xl))

(5)

其中，δt是搜索步长，f(x)用来计算对应函数的适应度值，sign函数是用来确定天牛之后的搜索方向，如果右向适应度较大，则sign函数取1，天牛就朝着该方向继续前进，反之，朝相反方向移动，移动步长为δt，在传统算法中，dt和δt一般取0.95随迭代次数做线性缩减.据上，一次迭代过程中只探索了随机方向上的某一个位置.同时，根据公式(5)可知，每一次迭代的目标函数无论是较大还是较小，天牛的位置和步长都会进行更新，固定步长就会使得天牛容易陷入局部最优位置无法跳出.

4 融合改进天牛须和正余弦的优化算法

分析发现，标准的正余弦优化算法在维度较高时容易陷入局部最优解并且收敛精度较低，针对这一问题，引入了全新的自适应惯性权重w，w能够随着迭代次数的改变而动态影响算法所寻找的最优位置，最大限度保证算法的收敛性；另外，考虑到标准正余弦优化算法中线性递减函数的固定递减对算法性能的影响，提出了一种新的自适应转换参数模型，引入指数型函数和余弦函数对正余弦算法进行改进，提高搜索精度；为了尽可能的降低正余弦算法陷入局部最优解的可能性，创新地将高运算效率的标准天牛须算法进行改进，将标准的固定步长改进为变步长并将其融入改进的正余弦算法中，通过改进天牛须算法的二次搜索寻优来帮助正余弦跳出局部最优解.

4.1 引入自适应权重

受蚁群优化算法[5]的启发，在正余弦优化算法的位置更新公式中引入动态自适应权重w.在算法进行探索阶段时，自适应权重能有效减小当前最优个体位置对全局搜索的影响，而随着正余弦算法逐渐进入到开发局部搜索阶段时，自适应权重能随着迭代次数逐步提升最优个体位置的影响力，同时帮助其余个体尽快收敛到最优个体位置.随着正余弦优化算法迭代次数t改变的自适应惯性权重如式(6)所示：

w(t)=0.2cosπ2 ·1-tT

(6)

其中，T为最大迭代次数，t为当前迭代次数.在正余弦中引入自适应惯性权重之后，随着迭代次数的改变，每个位置上对下个寻优位置的影响将不再是固定的，而是由一种非线性的规律变化，对该函数分析可以看出，前期在寻找最优值中，权重较低，对下次更新位置影响较小，但是随着迭代次数的增加，权重会逐渐变大，这样之后的迭代位置变化范围就会逐渐变小，能够最大限度保证算法的收敛性.

4.2 递减参数r1的改变

r1参数对整个正余弦优化算法的移动方向起着关键作用[26]，但是传统的线性递减函数使得正余弦的搜索方式显得很单一，每一次寻找都是按着固定的变值接近最优值，这样很大程度会陷入局部最优解.为了进一步加强迭代后期局部搜索能力，用更加灵活的搜索方式寻找，引入动态变化的思想，将线性递减函数r1变成指数型递减函数[27]，同时引入余弦函数，提出了一种新的转换参数模型，指数型函数由于其自身的单调性，能够保证变化是单向的，余弦函数随着迭代次数的增加，会非线性逐渐减小，反应在指数函数上，r1参数就会随着迭代次数的增加非线性减小，从而逐渐逼近最优值，增强正余弦对未知区域的搜索能力，如式(7)所示：

r1=αecosπ ·tT+t

(7)

其中，α为一个常数，本文中取0.05.

引入自适应权重和指数型递减函数之后，正余弦算法位置更新公式如式(8)所示：

Xt+1i=w(t)·Xti+r1×sin(r2)×|r3Ptj-Xti|，r4<0.5
w(t)·Xti+r1×cos(r2)×|r3Ptj-Xti|，r4≥0.5

(8)

4.3 变步长搜索机制

为了增强正余弦的搜索能力和效率，改善SCA算法易陷入局部最优、迭代效率低、搜索精度低等缺点，在改进正余弦算法中引入了具有高运行效率的天牛须搜索，同时为了规避标准天牛须算法自身参数简单易找不到最优解等情况，对天牛须搜索进行参数优化.为了使天牛须搜索能够更好的在正余弦上寻优，结合动态变化思想，将其搜索的固定步长改为变步长搜索[28]，变化步长为公式(9)：

δt=s1×s0s1TT+10t

(9)

其中，T为最大迭代次数，s0和s1为常数，本文取0.9和0.4，t为当前迭代次数.经过天牛须的二次搜索得到的值为Xt+1*.

改进的天牛须算法对改进正余弦优化算法搜索出的最佳位置进行二次寻优，再在计算适应度值的基础上用贪婪策略判断两次位置最优情况，得到更新的位置.

根据贪婪策略[29]来对搜索的值进行判断，具体公式如式(10)所示：

Xt+1=Xt+1i，f(Xt+1i)≤f(Xt+1*)
Xt+1*，f(Xt+1*)

(10)

其中，f(X)为在位置x处求得的适应度函数，比较原正余弦位置和天牛须二次搜索位置的适应度值，若二次搜索更优则替换原位置[30]，反之则不替换.

4.4 算法流程

融合改进天牛须和正余弦的双重搜索优化算法的具体流程如图3所示.

图3 算法流程图Fig.3 Algorithm flow chart

BAS-SCA算法的实现步骤如下：

步骤1.初始化算法参数，包含迭代次数，搜索维度，以及种群规模；

步骤2.根据参数的限定范围，随机初始化种群，根据目标函数计算找出全局最优值；

步骤3.计算自适应权值和递减参数，通过公式(8)更新最优个体位置及对应的适应度值；

步骤4.通过公式(5)和公式(9)对步骤3得到的最优个体位置进行二次搜索寻优更新，并计算适应度值；

步骤5.判断得到的位置是否超过步骤2设定的参数范围，如果超过则输出上一次未超过边界的最优解，；反之，则继续向下进行；

步骤6.运用贪婪策略，通过公式(10)判断最终的最优个体位置，如果二次搜索后更优，则替换当前个体，反之不替换；

步骤7.判断是否达到BAS-SCA的最大迭代次数，若达到，则输出最优个体位置及最优解；反之，继续进入步骤3进行.

5 算法性能测试

5.1 测试函数及性能指标

为了测试BAS-SCA算法的寻优能力，参考标准正余弦优化算法(Sine Cosine Algorithm，SCA)[8]、粒子群算法(Particle Swarm Optimization，PSO)[3]、基于变换函数与填充函数的模糊粒子群优化算法[31]、基于自适应搜索中心的骨干粒子群算法[32]中所选的测试函数，选择了14个选用率较高的基准函数进行测试，函数特性如表1所示，基准函数中包含单峰函数和多峰函数，其中，f1-f6以及f11为单峰函数，f7-f10以及f12-f14为多峰函数，单峰函数可以评测算法的收敛精度和寻优能力，多峰函数可以评测算法解决多维环境等复杂优化问题下的寻优能力.本文选取改进算法与标准SCA、粒子群算法(Particle Swarm Optimization，PSO)，改进的抛物线函数正余弦算法(Parabolic Sine Cosine Algorithm，PSCA)[14]和改进的指数正余弦算法(Exponential Sine Cosine Algorithm，ESCA)[15]作为比较对象进行实验.本文在正余弦算法的改进思路上，引入了指数函数和余弦函数，为了证明是两个函数的有效结合带来了算法的提升，与改进的抛物线函数正余弦算法和改进的指数正余弦算法进行比对.另为了对比该算法与其他自然算法的性能，选择了具有代表性的粒子群优化算法作为对比，粒子群优化算法自提出以来，便因其简单易用以及高效性被广泛研究改进，故本文选取了经典粒子群优化算法作为对比算法.

算法寻优精度为实际寻得最优解与理论最优解之间的误差绝对值，本文采用两个评价指标[33]：寻优精度的平均值(Ave)和标准差(Std)，两者的计算公式如式(11)和式(12)：

Ave=∑ti=1|f(X*)-f(Xopt)|T

(11)

Std=∑ti=1(f(X*)-Ave)2T

(12)

式中，Xopt为理论最优解，X*为每次算法得到的最优个体位置，T为最大迭代次数.寻优精度的平均值是在指定循环次数下算法得到的值和理论最优值差的绝对值的平均值，平均值越小，说明寻优结果越好；寻优精度标准差是实际最优值与平均值之间的标准差，标准差越小，则说明算法整体的稳定性越好.

在选取的14个基准测试函数中，函数的搜索区间及全局最优值已在表1中列出.几种算法的参数设置相同：个体规模设置Agents为30，最大迭代次数为500，每种算法都独立运行50次，并且考虑到高维的测试环境，这里设置了Dimension=30和200两种情况分别测试，所有的测试在Windows10操作系统，Intel i5-10400，16GB内存，MATLAB2020a仿真平台上运行，通过统计得出优化结果的平均值和标准差如表2所示.

5.2 优化算法的性能分析

表2给出了5种算法在14个标准测试函数下的寻优指标对比，分析单峰函数可以看出，在维度为30的情况下，算法寻优精度平均值和标准差上，标准正余弦算法都陷入了局部最优解的情况，PSCA和ESCA虽然在结果上比SCA有一定程度的改善，但是两者精度还是不高，对比之下，BAS-SCA算法在单峰函数寻优上都好于实验的其它算法.BAS-SCA算法在f1-f4函数中直接找到了全局最优解0，精度达到100%；在函数f5和f11中，虽然没能找到全局最优解，但是其寻优精度也是对比算法中最高的；在函数f6中，BAS-SCA算法虽然没能比PSO算法好，但是相较于其他改进的SCA算法，其仍具有优势.

表1 标准测试函数Table 1 Benchmark test function

表2 算法寻优指标对比Table 2 Comparison of optimization indexes

通过对比观察测试函数f7-f10在表格中的结果，在多峰函数中，在寻优精度和寻优稳定性上，BAS-SCA算法都远远好于其他算法，并且在f8-f10中直接找到了全局最优解，这是其他对比算法都没有达到的，他们都不同程度的陷入局部最优解而得到较差的收敛精度，虽然BAS-SCA算法在多峰函数f7中没有找到全局最优解，但是其收敛精度也远远高于其他算法.在测试函数f12和f13中，PSO算法和BAS-SCA算法都能够找到全局最优解，并且有较好的稳定性；在测试函数f14中，BAS-SCA也能实现较高的寻优精度及稳定性.

为了进一步测试BAS-SCA算法的高维寻优性能，将搜索维度改为200，其他参数没有改变，对算法重新进行实验分析，从表2中可以看出，在维度增加的情况下，BAS-SCA仍能保持很好的搜索性能，单峰函数f1-f4，多峰函数f7-f10、f12和f13中，都能找到全局最优解.在函数f6中，增加维度情况下，BAS-SCA算法超过了在30维度下性能优于自己的PSO算法，得到了较高的收敛精度.对于函数f12和f13，虽然增加维度的情况下指数型正余弦优化算法和抛物线型正余弦优化算法都能够在不同程度上找到全局最优解，但是根据表2数据，BAS-SCA的结果还是优于两者的.

为了能够更好的反应不同算法在不同测试函数下的收敛速度，在图4中给出了函数f1-f14在指定维度为30下的收敛对比图，从整体上看，BAS-SCA算法无论在收敛精度和收敛稳定性上都能大大超过本次比较的现有算法，尤其是图4(e)、图4(h)、图4(i)、图4(j)，BAS-SCA算法在一开始就以很快的收敛速度找到最优解，如图4(b)、图4(g)、图4(f)所示，可以发现，虽然开始标准SCA也有很快的收敛速度，但是其很快陷入了局部最优解并无法跳出，其余算法已经陷入了局部最优解，而得益于BAS-SCA算法的二次搜索，BAS-SCA在这几个函数中表现很好，直接跳出了局部最优，找到了全局最优解，图4(a)、图4(c)、图4(d)、图4(e)所示，虽然其余算法并没有陷入局部最优，但是其收敛速度和收敛精度是完全比不上BAS-SCA的，BAS-SCA算法在运行一开始就展示出极好的收敛性能，在很短的迭代次数中就找到了全局最优解.观察图4(l)，虽然BAS-SCA在收敛精度上略差于PSO算法，但是根据表2的实验结果，BAS-SCA仍可以找到最优解，图4(m)、图4(n)也可看出BAS-SCA能得到优于其他算法的结果.

图4 具体的测试函数收敛对比图Fig.4 Comparison chart of convergence of test function

为了更好的验证改进算法的有效性，增加改进变步长搜索的天牛须优化算法以及引入自适应转换参数正余弦优化算法自比实验，维度选取为30，最大迭代次数为500次，其它参数与原实验设置相同，实验结果如表3所示.

根据表3可知，改进的变步长搜索天牛须优化算法在给定的测试函数中效果表现较差，BAS-SCA优化算法在寻优精度及寻优稳定性上都比引入自适应转换参数的正余弦优化算法和改进的变步长搜索天牛须优化算法好.

表3 改进优化算法自比实验Table 3 Self comparison experiment of improved optimization algorithm

6 总 结

针对标准正余弦优化算法的搜索性能问题，本文创新性的将改进的天牛须搜索算法融合进改进的正余弦算法，提出了双重搜索优化算法BAS-SCA.该算法在正余弦中提出了一种新的自适应转换参数，改变了传统的线性递减参数设置，此外在正余弦中引入了一个全新的自适应惯性权重来保证算法后期的收敛性，此外，引入动态变化思想，将标准天牛须的固定步长改进为变步长搜索，改进的天牛须搜索再对改进正余弦进行二次搜索寻优，运用贪婪策略判断最终位置信息，测试函数实验以及对改进算法的自比实验证明，BAS-SCA算法能够很好的解决正余弦和天牛须两者后期易陷入局部最优解以及收敛精度较低等缺点，拥有很强的处理单峰以及多峰函数的能力，同时具备很好的寻优稳定性.