基于4VA信息素的蝗虫优化算法*

赵艳玲，王 勇,2,3**，袁 磊

(1.广西民族大学人工智能学院，广西南宁 530006；2.广西混杂计算与集成电路设计分析重点实验室，广西南宁 530006；3.广西高校复杂系统与智能计算重点实验室，广西南宁 530006)

群智能优化算法是人们通过对自然界中某些生物体的功能、特点和作用机理的观察和理解，或者对自然界中某些自然或物理现象的分析和研究，从中挖掘出其中蕴含的运行规律或机制，并基于对其运行规律或机制的模拟而构建的随机搜索算法。迄今，国内外学者先后提出了诸如遗传算法(GA)[1]、粒子群算法(PSO)[2]、蚁群算法(ACO)[3,4]、人工蜂群算法(ABC)[5]、蝗虫优化算法(Grasshopper Optimization Algorithm,GOA)[6]、正弦余弦算法(SCA)[7]、鲸鱼算法(WOA)[8]、蝴蝶优化算法(BOA)[9]等群智能优化算法。这些群智能优化算法的提出为解决工程等的优化问题提供了新的技术支持。

GOA是Saremi等[6]基于对蝗虫觅食行为的模拟而提出的一种新的群智能随机优化算法。GOA分为勘探和开发两个步骤，局部搜索能力较强，但全局搜索能力偏弱，故该算法规避陷入局部最优的能力不强。针对GOA的不足，Yildiz等[10]提出一种改进GOA，通过与精英对立学习机制杂交来提高算法的全局搜索能力，并利用工程中的具体优化实例来验证该算法的优化性能。Reddy等[11]利用遗传算子来改善勘探和开发之间的平衡，利用差分进化策略来指导算法搜索，以提高算法搜索效率。与标准GOA相比较，其改进的GOA在一定程度上提升了优化精度和收敛速度，然而提升的程度比较有限，仍有待进一步提高。尹德鑫等[12]利用Fuch初始化种群，通过引入正余弦因子和非线性惯性权重来提高算法的全局搜索能力，但在一定程度上增加了算法的时间复杂度。刘奇等[13]利用反向学习机制与混沌映射来加快算法的收敛速度，以增强算法的搜索能力，并利用红细胞供应预测实例来验证其改进算法的有效性。李洋州等[14]利用曲线自适应和模拟退火算法来提高算法的优化性能，其改进GOA的优化性能相较于标准GOA有一定的提高，但在收敛精度和优化精度方面仍有待进一步提升。何庆等[15]采用分段位置更新方式和利用柯西变异算子与反向学习策略对当前最优位置进行变异更新，提高算法跳出局部最优能力，将均匀分布函数引入非线性控制参数，平衡算法全局探索与局部开发，但对当前最优位置进行变异更新会增加算法的迭代次数，从而增加算法的时间复杂度。Luo等[16]通过引入高斯变异、列维飞行策略和反向学习策略来提高算法的收敛速度，但这样处理会增加算法的时间复杂度。林杰等[17]根据概率转换采用不同的位置更新方式，利用正弦余弦来平衡全局探索和局部开发，通过变异选择对最优解进行变异，提高算法的优化精度。然而采用变异选择对最优解进行变异会增加算法的迭代次数，从而增加算法的时间复杂度。杨文珍等[18]利用非线性曲线函数去平衡算法的局部开发和全局探索，引入扰动因子并利用高斯分布增加种群多样性，提高算法的收敛速度，但采用扰动因子和高斯分布增加种群多样性策略会增加算法的时间复杂度。上述文献[10-18]提出的各种版本的改进GOA相较于标准GOA，虽然在优化精度方面有一定的改善，但是仍存在早熟收敛问题，跳出局部极值的能力仍有待提高。本研究针对这些问题，提出一种基于4-乙烯基苯甲醚(4-vinylanisole,4VA)信息素的蝗虫优化算法(Grasshopper Optimization Algorithm Based on 4-vinylanisole Pheromone,VAGOA)。根据蝗虫生活习性和行为特征的最新研究发现[19,20]，结合标准GOA模型，基于4VA是蝗虫聚集信息素，设计4VA信息素表达式，对于不同蝗虫群体(群居型蝗虫和散居型蝗虫)分别采用不同的搜索策略，以平衡全局探索和局部开发，使算法的全局探索能力和局部开发能力均得到提升，并通过数值实例仿真验证本研究算法的优化性能。

1 蝗虫优化算法

蝗虫优化算法(GOA)[6]的基本思想：将蝗虫的生命周期分为幼虫和成虫两个阶段。在幼虫阶段，蝗虫具有跳跃步幅小、移动缓慢、小范围觅食活动的特征，倾向于局部搜索；在成虫阶段，蝗虫具有跳跃步幅大、移动快速、大范围觅食活动的特征，倾向于全局搜索。

GOA模型及步骤如下。

Input：蝗虫种群规模N，搜索空间维数dim，最大迭代次数Tmax，参数cmax和cmin。

①初始化种群Xi，i=1，…，N。

③依公式(1)更新参数c：

c=cmax-t(cmax-cmin)/Tmax，

(1)

其中，cmax和cmin分别表示参数c的最大值和最小值，t为当前迭代次数。

④蝗虫个体依公式(4)更新位置：

(2)

(3)

(4)

其中：s(r)表示种群社交影响强度，f为吸引力强度，l为吸引力范围(GOA在仿真实验中取f=0.5，l=1.5)；ubd和lbd分别表示第d维度的上下界，dij=

⑥判断是否满足终止条件，如果是，则转步骤⑦；否则,重复步骤③-⑤。

2 采用4VA信息素的蝗虫优化算法

2.1 构建算法模型的主要依据

根据Guo等[19]和Chen等[20]的最新研究，蝗虫除具有前面已提及的特征外，还具有以下活动习性和生物行为特征：①4VA是蝗虫的聚集信息素。②3′-磷酸腺苷-5′-磷酰硫酸(PAPS)生物合成过程能有效诱导蝗虫的行为转变。抑制PAPS的合成可以促使蝗虫行为从群居状态转变为独居状态。③根据活动行为状态，蝗虫分为群居型蝗虫和散居型蝗虫两种。④群居型蝗虫行为的亢奋是源于4VA信息素的分泌，4VA信息素专门由群居蝗虫释放，4-5只孤立蝗虫的聚集就会触发4VA信息素的产生，而且4VA信息素对蝗虫的吸引力极强。⑤释放4VA信息素的浓度与群居蝗虫发育密度有关，4VA信息素生物合成对于调节迁徙蝗虫的嗅觉吸引力和移动性至关重要。⑥4VA信息素对群居型蝗虫和散居型蝗虫的不同发育阶段都有很强的吸引力，能够响应蝗虫种群密度的变化，随着种群密度增加而增加。⑦根据种群密度显示出两个不同的行为阶段，即独居阶段和蜂拥而至的群居阶段，低密度发育的独居期蝗虫(散居型蝗虫)具有嗜睡和同种排斥的特征，而高密度发育的群居期蝗虫(群居型蝗虫)具有高流动性和同种吸引的特征。⑧散居蝗虫背部是绿色的，蝗虫从散居变成群居一段时间后，背部就会从绿色转换为黑色，行为也会变得亢奋起来。此时的蝗虫胃口很大，所过之处食物全被一扫而空。

本研究基于以上蝗虫活动习性和生物行为特征，设计一种新的采用4VA信息素的蝗虫优化算法。

2.2 构建算法模型

2.2.1 4VA信息素表达式的设计

4VA是蝗虫聚集信息素，能够响应蝗虫种群密度的变化，其浓度随着种群密度的增加而增加。因此，某处(蝗虫爱吃的)食物越丰富，该处引来的蝗虫就越多，从而该处蝗虫释放出的4VA信息素浓度也就越高。即哪里的食物越丰富，哪里的4VA信息素浓度就越高。基于此，设群体于t时刻找到最优位置，即食物最丰富、4VA信息素浓度最大位置是xbest(t)，i个体于t时刻位于xi(t)。由于i个体嗅觉受体在t时刻闻到4VA信息素的强弱与位置xbest(t)的4VA信息素浓度、距离有关，也与其嗅觉受体感应能力有关，故设计4VA信息素表达式如下：

(5)

其中，β0=2，qi=|f(xbest(t))-f(xi(t))|，

f(xbest(t))表示位置xbest(t)的适应度值(即此处4VA信息素浓度)，f(xi(t))表示i个体的嗅觉受体感应能力(以适应度值表示)；hi=‖xbest(t)-xi(t)‖为xbest(t)与xi(t)的距离，Tmax为最大迭代次数，t为当前迭代次数。

公式(5)说明i个体嗅觉感应到4VA信息素的强弱，不仅跟其与xbest(t)的距离、与其嗅觉受体感应能力和位置xbest(t)的4VA信息素浓度有关，还跟时间有关，4VA信息素随时间的增加而逐渐变弱。

2.2.2 不同蝗虫群体搜索方法的设计

①群居型蝗虫搜索方法设计。由于4VA信息素由群居型蝗虫释放，群居型蝗虫具有同种吸引特征，故群居型蝗虫释放的4VA信息素会诱惑其他蝗虫前来聚集(图1)。因此，本研究结合GOA的公式(4)，将4VA信息素与高斯分布相结合，设计群居型蝗虫搜索方法如下。

首先利用正态分布选取数a：

a～N(0,σ2)。

(6)

在仿真实验中，取σ=t/Tmax。然后按公式(7)更新位置。

(7)

设xbest(t)=[xbest,1(t),…，xbest,D(t)]为群体于t时刻找到的最优位置，此时xbest(t)的4VA信息素浓度最大，故有一部分群居型蝗虫被诱惑到xbest(t)的周围觅食。针对这部分蝗虫，本研究设计其位置更新公式如下：

图1 4VA信息素诱惑蝗虫聚集[19]Fig.1 Locusts being lured by 4VA pheromone to gather

xi,j(t+1)=ξi,j，

(8)

其中，ξi,j为[xbest,j(t)-ε,xbest,j(t)+ε]中的随机数，0<ε≪1，j=1,…,D。在仿真实验中，取ε=

1/t2。

②散居型蝗虫搜索方法设计。尽管处于独居状态的蝗虫的觅食活动具有随意性，但4VA信息素对散居型蝗虫的不同发育阶段都有很强的吸引力。因此，当散居型蝗虫闻到其他蝗虫释放的4VA气味时，就会朝4VA散发地进发。针对散居型蝗虫，本研究设计其位置更新公式如下：

(9)

2.3 群居型蝗虫与散居型蝗虫的区分方法

由于“群居型蝗虫胃口大，所过之处食物全被一扫而空”，故认为群居型蝗虫的搜索(觅食)能力相对较强；“散居型蝗虫具有嗜睡和同种排斥特征”，故认为散居型蝗虫的搜索(觅食)能力相对较弱。因此，本研究根据蝗虫个体觅食能力强弱来区分其是群居型蝗虫还是散居型蝗虫。

区分方法如下：设至t时刻群体找到的最优位置为xbest(t)，相应的适应度值为f(xbest(t))。首先给定阈值ρ>1(本研究在实验中取ρ=1.4)。

Rule 1：若f(xi(t))≤2f(xbest(t))，则认为i蝗虫为群居蝗虫。此时，若ρ·f(xbest(t))

Rule 2：若2f(xbest(t))≤f(xi(t))，则认为i蝗虫为散居蝗虫，并按公式(9)更新位置。

2.4 算法实现步骤

本研究算法步骤和流程如下。

输入：种群规模N，搜索空间维数D，最大迭代次数Tmax。

步骤 1：初始化种群Xi，i=1，…，N。

步骤 3：按群居蝗虫与散居蝗虫的区分方法将种群分为群居蝗虫与散居蝗虫两个子群。

步骤 4：群居蝗虫按“Rule 1”选择公式(6)、(7)或公式(8)更新位置；散居蝗虫按公式(9)更新位置。

步骤 6：判断是否满足停止条件，若满足，则转Step 7；否则重复Step 3-Step 5。

3 实验仿真与结果分析

3.1 测试函数

为了测试本研究算法(VAGOA)的优化性能，将VAGOA与标准GOA[6]、PSO[2]，以及从各种改进版本GOA当中选择的比较有代表性的SA_CAGOA[14]和HCUGOA[15]进行算法数值实验对比分析。选取12个典型的基准测试函数(表1)作为本次算法性能测试分析(均为求最小值问题)。

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

续表

Continued table

3.2 结果与分析

为保证实验结果的对照与比较的客观和公平，5种算法统一设置群体规模为30，最大迭代次数为200。对于GOA、HCUGOA、SA_CAGOA 3种算法，其参数设置与相应的文献保持一致，即cmax=0.1，cmin=0.000 04。对于SA_CAGOA，设置初始温度T0=100，结束温度T=1，退火系数r=0.95。

为了验证本研究算法(VAGOA)的性能，对表1中的12个基准测试函数进行求解。表1中既有单峰函数，也有多峰函数。单峰函数主要用来测试算法的收敛速度，多峰函数主要用来测试算法的全局搜索能力(探索和开发能力)和规避陷入局部最优的能力。本研究以最优值、最差值、平均值和标准差作为算法性能评价指标，这些评价指标总体上反映了算法优化能力的强弱和算法稳定性的优劣。为了避免随机性对实验结果的影响，本研究在数值实验中将5种算法对每个测试函数均独立进行30次实验，并记录最优值、最差值、平均值、标准差等实验数据。高维测试函数(F1-F10)实验结果比较数据见表2，低维测试函数(F11-F12)实验结果比较数据见表3。

表2 高维测试函数(F1-F10)实验结果比较Table 2 Comparison of experimental results of high dimensional test function (F1-F10)

续表

Continued table

续表

Continued table

表3 低维测试函数(F11-F12)实验结果比较Table 3 Comparison of experimental results of low dimensional test function (F11-F12)

针对30，100和200维，本研究算法(VAGOA)找到F1-F9的最优值、最差值、平均值、标准差均与理论最优值相同，HCUGOA找到F1-F8的最优值、最差值、平均值、标准差也与理论最优值相同。VAGOA与HCUGOA找到F10的最优值、最差值、平均值、标准差相同，其他3种算法均没有找到这10个测试函数的理论最优值(表2)。基于以上分析，不论是求解单峰还是多峰优化问题，相较于其他4种算法，VAGOA全局寻优能力和规避陷入局部最优能力最强、优化精度最高、稳定性更好。

本研究算法(VAGOA)与HCUGOA找到F11和F12的最优值、最差值、平均值、标准差均与理论最优值相等，但VAGOA至41次迭代就已经找到理论最优解，而HCUGOA至175次迭代才找到理论最优解，其他3种算法均没有找到理论最优解(表3)。基于此，针对低维度优化问题，说明VAGOA相较于4种对比算法具有更快的全局收敛速度，收敛精度更高，稳定性更好。

为了更直观地对比本研究算法(VAGOA)、GOA、PSO、HCUGOA和SA_CAGOA 5种算法各自的全局收敛速度和全局搜索能力，给出5种算法求解以上12个基准测试函数的适应度进化曲线对比图(图2)。相较于GOA、PSO、HCUGOA、SA_CAGOA 4种算法，VAGOA的进化曲线均位于最下方位置，且下降趋势为5种算法中最快，没有出现停滞状态；VAGOA的F1-F9收敛曲线均到达理论最优位置，F10收敛曲线非常接近理论最优位置(图2)。说明本研究算法(VAGOA)在搜索后期没有陷入局部最优。基于以上分析，相较于GOA、PSO、HCUGOA、SA_CAGOA 4种算法，VAGOA的全局收敛速度明显更快，规避陷入局部最优的能力更强。

图2 5种算法进化曲线对比Fig.2 Comparison of evolution curves of five algorithms

4 结论

本研究从以下方面对GOA进行了优化：①根据确定的搜索方法规则，群体中位置较优者采用聚集搜索方法，而位置较劣者则采用分散搜索方法。②从确定的搜索方法规则上看，蝗虫个体可根据自身当前位置的优劣来确定下一步的搜索方法，使其能更快地搜寻到食物源，以增强个体的搜索能力。③对群居型蝗虫和散居型蝗虫分别采用不同的搜索方法，使得算法能基于群体信息反馈，及时分配群居型蝗虫个体数和散居型蝗虫个体数，使群体中从事探索活动的个体数与从事开发活动的个体数得到适当分配，也使种群的多样性得到有效保持，从而提升算法的全局搜索能力。④利用4VA信息素随时间增加而逐渐变弱这一特征，确保群体中时刻都有部分个体开展随机游走(搜索)活动，在保持种群多样性的同时，又增强算法规避陷入局部最优的能力。

本研究针对GOA存在的不足，基于蝗虫活动习性和生物行为特征，提出基于4VA信息素的蝗虫优化算法(VAGOA)。对不同蝗虫群体(群居型蝗虫和散居型蝗虫)分别采用不同的搜索策略，以平衡全局探索和局部开发，使算法全局探索能力和局部开发能力均得到有效提升,增强了算法的全局寻优能力和规避陷入局部最优的能力。通过求解12个基准测试函数，验证了VAGOA明显比GOA、PSO、HCUGOA、SA_CAGOA 4种算法具有更快的全局收敛速度、更强的规避陷入局部最优的能力、更好的全局搜索能力和稳定性。在后续研究中，将考虑把VAGOA应用于求解TSP优化问题,进一步验证VAGOA的性能。