采用协同搜索策略的算术优化算法

付小朋,王 勇,2,冯爱武

1(广西民族大学 人工智能学院,南宁 530006)

2(广西混杂计算与集成电路设计分析重点实验室,南宁 530006)

1 引 言

元启发式算法是随机算法与局部搜索算法相结合的产物,是一个基于直观或经验构造的算法.其主要分为基于进化的算法,如遗传算法(GA)[1]、差分进化算法(DE)[2]等;基于群体的智能优化算法,如粒子群算法(PSO)[3]、鲸鱼优化算法(WOA)[4]等;基于物理规律的优化算法,如引力搜索算法(GSA)[5]、正余弦算法(SCA)[6]等;基于人的优化算法,如教学优化算法(TLBO)[7]和社会进化算法(SEA)[8]等.目前这些算法已经在图像分割[9]、电力调度[10]、环境污染物预测[11]等方面得到了应用.

算术优化算法(Arithmetic Optimization Algorithm,AOA)是Abualigah[12]等人受数学运算算子加、减、乘、除求解问题的启发,在2021年提出的一种新的元启发式算法.AOA利用算术中的乘除运算扩大算法全局搜索的分散性,利用加减运算提高算法局部搜索的精确性,具有一定的求解精度和较好的稳定性.然而,AOA也存在收敛速度慢、易陷入局部最优等问题.针对AOA存在的不足,郑婷婷[13]等人通过引入自适应分布变异策略来提高算法的收敛速度,引入余弦控制因子的动态边界来平衡全局勘探和局部开发;兰周新[14]等人通过Sobol初始化序列来增加种群的多样性,重构数学优化加速函数和混沌精英变异策略来改善算法的优化性能;杨文珍[15]等人利用激活因子来改善算法的全局优化性能,利用反向学习和灰狼信息反馈机制来提高算法寻优精度;Agushaka[16]等人利用beta分布初始化种群,使用自然对数和指数算子生成的高密度值来增强AOA的探索能力;Wang[17]等人利用自适应权重来增强算法的优化性能.尽管在优化精度方面,以上文献提出的改进版本AOA比标准AOA优,但这些改进版本AOA也还存在全局搜索能力不强、易陷入局部最优之不足,仍有进一步提升的空间.

针对以上存在的问题,本文提出一种新的采用协同搜索的算术优化算法(Arithmetic Optimization Algorithm Using Cooperative Search Strategy,CSSAOA):采用乘法搜索与除法搜索协同并行开展搜索策略,以增强算法的全局勘探能力;采用减法搜索与加法搜索协同执行,以增强算法的局部搜索能力;对MOA进一步完善,以加快了算法的全局收敛速度;利用外抛交叉变异对当前最优个体实施多样性变异,以增强算法搜索跳出局部最优的能力.通过数值实例仿真验证了本文算法的有效性和可行性.

2 标准AOA介绍

标准AOA利用乘法算子和除法算子进行全局勘探,利用加法算子和减法算子进行局部开发.具体实现如下:

1)数学优化加速函数(MOA).AOA在寻优之前,通过MOA选择搜索阶段(是执行全局勘探还是局部开发),选取随机数r1(0～1之间的随机数),若r1

(1)

其中:t为当前迭代次数,T为最大迭代次数,Max和Min分别是数学优化器加速函数的最小值和最大值,分别取值为0.2和1.

2)全局勘探.在这个阶段AOA主要采用两种搜索策略(除法搜索策略和乘法搜索策略)寻找更好的候选解.随机从[0,1]取一个随机数r2,若r2<0.5,则执行除法运算策略;否则执行乘法运算策略.其搜索数学表达式如式(2)所示:

(2)

MOP(t)=1-t1/α/T1/α

(3)

L=(UB-LB)×μ+LB

(4)

其中:x(t+1)表示t+1次迭代的位置,best(x)表示目前候选解中最优个体的位置,ε是一个很小的整数,防止分母为0,UB和LB分别表示搜索空间的上界和下界,u为调整搜索过程的控制参数,AOA中u=0.5,MOP(t)为数学优化率系数,α表示迭代开发精度的敏感度参数,AOA中α=5.

3)局部开发.在这个阶段AOA主要采用减法搜索策略和加法搜索策略进行开发计算,若r3<0.5(r3为0～1之间的随机数)采用减法搜索策略,否则采用加法搜索策略.其搜索数学表达式如式(5)所示:

(5)

3 本文算法

本文首先分析标准AOA更新公式(2)和公式(5)、及其设计的MOA存在的不足:

1)分析公式(2)、公式(5):公式(2)采用best(x)÷(MOP(t)+ε)×L除法搜索策略和best(x)×MOP(t)×L乘法搜索策略两种选择.由于这两种选择的执行是由随机数r2决定,故其在勘探期间这两种搜索策略分别以相同概率执行;公式(5)分别采用减法搜索策略best(x)-MOP(t)×L和加法搜索策略best(x)+MOP(t)×L,这两种搜索策略也是以相同的概率执行,由随机数r3确定.通过分析数学表达式(2)和公式(5)不难看出:①所有搜索个体都只关注群体当前最优位置,都是盲目地向群体当前最优位置的附近移动;②群体中的搜索个体在开展搜索活动中相互之间缺乏信息交流,“眼睛”只盯住“群体当前最优位置”而不管不顾其余搜索个体的搜索信息,使个体的搜索效率极其低下.这必然会造成搜索个体过度聚集到当前群体最优位置的附近,使种群的多样性得不到有效保持,致使算法搜索陷入局部最优;③ 公式(2)只允许从“乘法搜索”与“除法搜索”当中选择一种而不能并行执行两种搜索(由随机数r2决定),公式(5)也是只从“加法搜索”和“减法搜索”当中二选一,而不让两种搜索并行执行(由随机数r3决定).换言之,标准AOA算法不允许“乘法搜索”、“除法搜索”、“加法搜索”、“减法搜索”同时执行,这会造成其相互之间不能同时兼顾和协同开展搜索,从而降低了个体的搜索能力,导致算法的全局搜索能力不强、收敛精度不高.

2)标准AOA是通过如下规则来选择勘探和开发的:首先从[0,1]中取一个随机数r1,若r1

综合以上分析,针对标准AOA存在的问题,本文有针对性地采用以下改进策略:

3.1 协同搜索策略

基于以上针对标准AOA的公式(2)和公式(5)存在不足的分析:标准AOA算法的“乘法搜索”、“除法搜索”、“加法搜索”、“减法搜索”相互之间不能同时兼顾或协同开展搜索,在不同的搜索阶段均以相同的概率选择搜索策略.这种采用排他性的搜索切换策略,必然造成其相互之间不能同时兼顾和协同开展搜索,从而使个体的搜索效率低下,进而难以提升群体的全局搜索效率.因此,本文对标准AOA的公式(2)和公式(5)进一步完善,分别改为公式(6)和公式(7):

x(t+1)=w(t)×best(x)÷(MOP+ε)×L×sin(θ)
+w(t)×best(x)×MOP×L×cos(θ)

(6)

x(t+1)=w(t)×best(x)+sgn(f(best(x))-
f(x))×·MOP(t)×L

(7)

其中:θ为[0,π]中的随机角,公式(6)兼顾了“乘法搜索”与“除法搜索”,让两种搜索协同并行开展全局勘探,增强了个体的搜索能力,进而有效提升了算法的全局探索能力;利用两部分信息来指导个体开展协同搜索,提升了个体的搜索效率.公式(7)中sgn(·)为符号函数,f(best(x))-f(x)表示种群最优个体的适应度值减去当前个体的适应度值.公式(7)中,利用符号函数动态切换法则,让减法搜索与加法搜索协同执行,增强了个体的局部搜索能力;利用最优个体的适应度值进行信息引导,可使搜索个体对减法搜索与加法搜索的选择更具有指向性,增强了算法的局部寻优能力,进而提升了算法的优化精度.其中,w(t)=1.1-gbest/fitavg,gbest表示当前最优个体适应度值,fitavg表示当前种群的平均适应度值,w(t)表示为一个基于适应度值反馈的惯性权重.算法在前期整体的离散程度较高,最优个体的适应度值和种群适应度平均值有着较大差距,因此,gbest/fitavg的比值在算法前期较小,则惯性权重w(t)较大,较大的惯性权重有利于算法的勘探行为;随着迭代次数的增加,更多的个体向最优解附近靠近,因此gbest/fitavg比值逐渐增大,惯性权重w(t)减小,较小的惯性权重有利于算法的开发行为,加快算法对最优目标的获取.

3.2 设计新的MOA

根据前面的分析知道:标准AOA利用MOA来切换“全局勘探”与“局部开发”时,造成算法在搜索后期进行局部开发的概率反而比进行全局勘探的小,这与一般智能优化算法普遍采用“算法在搜索前期侧重进行全局勘探、在后期侧重开展局部开发”搜索策略不一致,削弱了在算法后期的局部开发能力,这不利于算法的寻优速度和精度.因此本文设计新的MOA(t),如式(8)所示:

MOA(t)=a×(1-exp(-(T-t)/T))+b

(8)

其中a=0.8,b=0.2,新的MOA(t)是一个关于t的非线性单调递减函数.本文利用MOA(t)来控制执行全局探索与执行局部开发的个体数,来实现“在算法搜索的前期以较大概率进行全局探索、在算法搜索后期以较大概率进行局部开发”目标.这使得算法在搜索前期投入更多的个体进行全局勘探,在算法搜索后期则投入更多个体进行局部开发,以提升算法的收敛速度.

3.3 采用外抛交叉变异策略

标准AOA中的个体位置更新过于依赖群体当前最优个体位置,一旦群体当前最优个体位置持续不发生改变或只出现在一个比较小的区域内,则会吸引群体中过多个体过早聚集到当前最优位置的较小范围开展搜索,导致算法陷入局部最优.针对这一问题,本文利用个体信息相互交流方法,对当前最优个体实施交叉变异,使种群的多样性得到有效保持.对于种群过度聚集容易造成算法陷入局部最优,本文设计一种新的判别系数以此判断种群是否陷入局部最优,从而实施变异操作.

(9)

(10)

其中:N为种群规模,Hi(t)表示判别第t次迭代第i个体是否陷入局部最优,而P(t)则表示第t次迭代,种群总体陷入局部最优的程度,从式(10)可以看出,P(t)的值越大,则算法陷入局部最优的可能性越大.因此,在本文当中,若P(t)>rand,则对最优个体进行交叉变异.从P(t)的大小可知,P(t)越大则变异概率越大,算法摆脱局部最优的概率越大.其中交叉变异的步骤如下:

1)设群体当前最优个体为Xbest,随机选择的个体为Prand,其分别如式(11)所示表示,dim表示个体的维度.

Xbest={x1,x2,…,xdim}
Prand={p1,p2,…,pdim}

(11)

2)产生一个dim维度的交叉模板N={n1,n2,…,ndim},其中nj=0,1,j=1,2,…,dim,0表示交叉,1表示不交叉;产生一个在[0,1]范围内dim维度的数T={t1,t2,…,tdim};在[-1,1]中生成一个外抛系数A={a1,a2,…,adim},即aj∈[-1,1].最优个体Xbest与随机个体Prand进行交叉操作后,得到的个体位置如式(12)所示:

Xnewbest={x1+a1n1(1-t1p1),x2+a2n2(1-t2p2),…,
xdim+adimndim(1-tdimpdim)}
Prand={p1+a1n1(1-t1x1),p2+a2n2(1-t2x2),…,
pdim+adimndim(1-tdimxdim)}

(12)

其中:系数T={t1,t2,…,tdim}表示交叉系数,最优个体通过与随机个体进行交叉信息交流,调整最优个体的搜索步长;利用N={n1,n2,…,ndim}来控制是否要进行维度交叉、以及哪个维度需要进行交叉操作;A={a1,a2,…,adim}表示外抛系数,从A的取值范围可以看出,其使得最优个体的每个维度的朝向有所区别,以此来增加最优个体搜索方向的多样性和跳出当前局部最优位置的能力,从而保证了在算法搜索前期不至于吸引过多个体过早聚集到群体当前最优位置的较小范围内开展搜索,增强了算法搜索跳出局部最优的能力.经式(12)变异操作后得到Xnewbest,并将Xnewbest与原群体当前最优个体Xbest进行适应度值比较,若Xnewbest优于Xbest,则更新Xbest;否则不更新.

3.4 本文算法执行步骤

步骤1.初始化种群规模N,搜索空间维度Dim,最大迭代次数T,搜索范围上界UB和下界LB.

步骤2.使用公式(8)计算MOA(t),使用公式(3)计算MOP(t),使用公式(4)计算出L,产生随机数r1,找出当前最优个体best(x).

步骤3.如果r1

步骤4.利用式(10)、式(12)进行变异操作,并保留优秀变异个体.

步骤5.判断算法是否达到最大迭代次数,满足算法结束条件,否则执行步骤2.

步骤6.算法结束,输出最优个体为寻优结果.

4 数值实验仿真分析

4.1 测试函数

为了检验本文算法(CSSAOA)的性能,将CSSAOA与标准AOA、海鸥优化算法(SOA)[18]、纵横交叉优化算法(CSO)[19],哈里斯鹰优化算法(HHO)[20]进行数值仿真实验对比,通过实验数据和仿真收敛图对算法的稳定性和寻优性能进行分析,以此验证本文算法的性能.通过选取8个基准测试函数对算法进行测试分析,来验证本文算法在不同类型的测试函数模型下依然有着可靠的优化性能,其中4个测试函数(f1～f4)为单峰函数,4个测试函数(f5～f8)多峰函数.8个基准测试函数如表1所示.

表1 基准测试函数Table 1 Benchmark function

4.2 数值实验比较和收敛图分析

为了保证测试结果的公平性,所有算法的迭代次数都设置为500,种群规模为30.为了避免随机性对测试结果造成影响,本文在测试数据时,每一种算法针对每一测试函数都独立运行30次,并将每次算法的最优值、平均值、标准差记录下来.这些数据指标总体上反应了算法优化能力的强弱.其中最优值能反映算法的寻优精度,平均值和标准差能够体现算法的稳定性能.表2为5种算法的测试数据.图1为5种对比算法求解f1～f8的收敛曲线图.

图1 函数收敛曲线图Fig.1 Function convergence curve

表2 测试数据Table 2 Test data

分析表2实验数据.首先从最优值指标上分析算法的寻优能力:CSSAOA在单峰函数f1～f3和多峰函数f5～f6均能找到理论最优值,找到f4、f7、f8的最优值的精度也均好于其他对比算法,特别在f7上,CSSAOA的寻优精度比AOA提升了19个数量级,提升程度非常明显;AOA仅找到f2和f5的理论最优值;SOA在所有测试函数均未找到理论最优值;CSO只找到f6的理论最优值;HHO仅找到f5的理论最优值.综合以上分析,针对不同类型的基准测试函数,本文算法(CSSAOA)的表现均优于其他4种比较算法.CSSAOA寻优能力的提升,得益于采用了外抛交叉变异策略,增强了个体之间的信息交流,保持了种群的多样性,增强了算法跳出局部最优的能力,提升了算法收敛精度.其次,从平均值和标准差指标上分析算法的稳定性:CSSAOA在f1～f3、f5～f6上的平均值均为理论最优值,且标准差均为0;对比算法当中,只有AOA在f2上、HHO在f6上的平均值达到理论最优值,且标准差为0.CSSAOA在f4、f7～f8上的平均值和标准差尽管未达到理论最优值,但其平均值和标准差精度均高于其他4种对比算法.因此,CSSAOA算法的稳定性在5种对比算法当中是最优的,并且优势十分明显.

分析图1(a～h)的收敛曲线图:CSSAOA相较于其他4种算法,其收敛曲线均位于其他4种算法的收敛曲线下面,这说明CSSAOA的收敛速度最快、优化精度最高.从图1(a～c)和图1(e～f)上看,CSSAOA在50代内找到理论最优值;从图1(d)和图1(g～h)上看,CSSAOA收敛曲线虽然没有达到理论最优,但相较其他4种算法,CSSAOA的下降速度最快,且更接近理论最优.进一步说明了CSSAOA的收敛速度和收敛精度均优于其他4种算法.

综合以上分析,本文算法的优化能力相较于其他4种算法均具有比较明显优势.CSSAOA具有较强的全局搜索能力,得益于本文重新设计了MOA,更好地平衡了算法的全局勘探与局部开发,使算法在搜索前期能以较大概率执行全局勘探,在后期则以较大概率执行局部开发,加快了算法的全局收敛速度;搜索个体采用协同搜索策略,增强了个体的搜索能力,从而进一步增强了算法的全局搜索效率.

4.3 改进策略的有效性分析

为分析不同改进策略对算法的影响,将CSSAOA与仅采用协同搜索策略的算术优化算法(AOA1)、仅采用新的MOA的算法优化算法(AOA2)、仅采用外抛交叉变异的算术优化算法(AOA3)进行数值实验对比,并记录平均值和标准差.算法的实验条件与4.2节保持一致,其中实验结果如表3所示.

表3 不同策略寻优结果Table 3 Optimization results of different strategies

基于表3的实验结果可知,在函数f1～f3、f5、f6上,AOA1、AOA2、AOA3的平均值和标准差均达到理论最优,因此这3种改进策略是有效的.在函数f4、f7、f8上,AOA1和AOA2对算法寻优性能提升不明显,但AOA3对算法寻优性能提升具有明显地促进作用;融合3种策略的CSSAOA算法的寻优性能均好于单一策略的寻优性能.因此,本文提出的改进策略是有效的,并且明显改善了算法的寻优性能.

4.4 与其他改进版本AOA对比与分析

为了测试本文算法(CSSAOA)的性能,本文将CSSAOA与最新提出的各种改进版本AOA进行数值实验对比,以检验CSSAOA与各种改进版本AOA相比是否具有更好的优化性能.为此,将CSSAOA与文献[13]提出的t-CAOA、文献[16]提出的nAOA、文献[17]提出的APAAOA进行数值实验对比,以验证改进算法之间的差异,选取测试函数与表1中所列的8个基准测试函数相同,算法的实验条件均与4.2节保持一致.实验结果列在表4中,其中:t-CAOA、nAOA、APAAOA的数据均取自相应原文献中的数据,而“--”表示该算法缺相关数据.

表4 改进算法对比Table 4 Comparison of improved algorithms

基于表4的实验数据来分析各种算法的优劣:本文算法(CSSAOA)求解函数f4时得到的平均值精度比t-CAOA高11个量级、得到的标准差精度比t-CAOA高10个量级,求解单峰函数f1～f3时得到的“平均值”和“标准差”与t-CAOA的相同;求解多峰测试函数f7、f8时,本文算法(CSSAOA)相较于nAOA和APAAOA,在平均值精度和标准差精度上至少高出10个量级.因此,本文算法(CSSAOA)求解这8 个基准函数得到的“平均值”和“标准差”总体上都比其他3种对比改进算法的优,说明了CSSAOA的寻优能力和算法稳定性都比其他3种改进算法的好.

4.5 CEC2019测试函数验证

为进一步验证CSSAOA算法的寻优性能,选取CEC2019的10个测试函数进行数值仿真实验测试,CEC2019测试函数具有问题规模大,寻优较为复杂的特点,可以更加有效验证算法的寻优能力,有效区分算法寻优性能的差异性.其中为确保实验的公平性,所有对比算法的实验条件与4.2节保持一致.将CSSAOA算法与AOA算法在CEC2019测试函数上进行实验测试,并记录测试的平均值与标准差.其中CEC2019函数如表5所示.实验测试数据如表6所示.

表5 CEC2019测试函数Table 5 CEC2019 test function

表6 CEC2019测试数据Table 6 CEC2019 test data

基于表6的数据可知,CSSAOA在CEC01、CEC02、CEC04-CEC09上,其平均值寻优精度和标准差寻优精度均优过AOA,特别在CEC01上其平均值精度精度相较AOA提升了5个量级,标准差精度提升了6个量级;在CEC03上虽然算法的平均值寻优精度是一致的,但是CSSAOA的标准差精度相比AOA具有明显的提升,CSSAOA的稳定性更高;在CEC10上虽然AOA的标准差小于CSSAOA标准差,但是CSSAOA的平均值精度相比AOA更高.因此,从总体上看,CSSAOA算法寻优性能与AOA具有明显差异性,其寻优性能更加优异,本文算法的改进对算法寻优能力的提升具有明显的积极作用.

4.6 工程应用

为验证本文算法(CSSAOA)的实用性,通过两个经典的工程应用优化案例对CSSAOA进行实用性测试,并将测试结果与其他算法进行对比.两个工程应用案例具有约束条件多,约束条件复杂等特点,对算法需要较强的寻优能力.因此,通过这两个工程应用测试可以验证CSSAOA的实用性与寻优效果.具体优化测试案例如下:

4.6.1 减速器优化问题

该问题是优化机械系统中变速箱的减速器,使得其重量最小,其减速器结构模型如图2所示,其包含7个决策变量分别为:端面宽度x1、齿模x2、小齿轮齿数x3、第1轴长度x4、第2轴长度x5、第1轴的直径x6、第2轴的直径x7,其数学模型如式(13)所示.

图2 减速器结构模型图Fig.2 Structural model diagram of reduction die

g7(x)=x2x3/40-1≤0

g8(x)=5x2/x1-1≤0

g9(x)=x1/12x2-1≤0

g10(x)=(1.5x6+1.9)/x4-1≤0

g11(x)=(1.1x7+1.9)/x5-1≤0

2.6≤x1≤3.6,0.7≤x2≤0.8,x3∈{17,18,…,28};

7.3≤x4,x5≤8.3,2.9≤x6≤3.9,5≤x7≤5.5,

(13)

分别利用CSSAOA和标准AOA对减速其优化问题进行求解,并与算法ABC[21]、APSO[22]、SHO[23]的最优结果进行比较.为确保数据的准确性,相关算法数据均来自原文献.其中对比结果如表7所示.

从表7的数据中可知,在减速器问题寻优结果中,CSSAOA的寻优结果最优,且优势较为明显.

4.6.2 拉力/压缩弹簧设计问题

该问题优化的目标是使拉力/压缩弹簧的重量最小,其模型图如图3所示.在优化设计中,该问题受到最小挠度、剪应力、波动频率、外径限制和设计变量的约束,其包含3个决策变量分别为:线圈直径D(x1)、导线直径d(x2)和有源线圈个数P(x3),该问题数学模型如式(14)所示:

图3 拉力/压缩弹簧模型图Fig.3 Tension/compression spring model

(14)

用CSSAOA和标准AOA求解拉力/压缩弹簧优化问题,并将求解结果与CPSO[24]、SSA[25]、WOA[4]求解结果进行比较.其对比结果如表8所示.

表8 拉力/压缩弹簧问题寻优结果Table 8 Optimization results of tension/compression spring

从表8中可以看出,CSSAOA求得的结果是0.01266,均优于其他4种对比算法.因此,在求解拉力/压缩弹簧优化问题时,CSSAOA的寻优能力强于其他4种对比算法.

综上所述,CSSAOA算法在用于解决实际工程问题时具有较好的实用性和较强的寻优能力.

5 结 论

本文针对标准AOA存在的不足,提出一种采用协同搜索策略的算术优化算法(CSSAOA).首先引入协同搜索策略,让个体搜索可同时兼顾乘法搜索与除法搜索、两种搜索协同并行开展全局勘探,增强了群体的全局搜索能力,进而提升了算法的全局探索能力;让减法搜索与加法搜索协同执行,增强了算法的局部开发能力.其次,重新设计了MOA,通过MOA来控制执行全局探索与执行局部开发的个体数,使算法在搜索前期投入更多的个体进行全局勘探,在搜索后期投入更多个体进行局部开发,加快了算法的全局收敛速度.再次,采用外抛交叉变异策略对当前最优个体实施多样性变异,以保证在算法搜索前期不至于吸引过多个体过早聚集到群体当前最优个体的周围,增强算法搜索跳出局部最优的能力.通过8个基准测试函数,2个工程应用实例及CEC2019函数测试,验证了本文算法的全局收敛速度和优化精度均得到了提升,算法跳出局部最优的能力得到了加强.在后续研究中,考虑将本文算法应用于特征选择、无线传感器网络节点定位和图像分割等应用中.