基于交叉算子的反向梯度优化算法

吴 芸，程冲华 ，江海新，刘俊峰，李 进

(1.九江学院 理学院，江西 九江 332005；2.浙江大学 控制科学与工程学院，工业控制技术国家重点实验室,杭州 310027)

梯度优化算法(Gradient-based optimizer，GBO)[1]是Iman Ahmadianfar、Omid Bozorg-Haddad 等人于2020年提出的一种群体智能优化算法.GBO的灵感来自于牛顿法，借助群智能优化算法的思想，利用一组向量并结合梯度搜索规则(GSR)、局部逃逸算子(LEO)来进行搜索.

GBO概念简单易实现，通过与灰狼优化算法(GWO)[2]，人工蜂群算法(ABC)[3]，鲸鱼优化算法(WOA)[4]的比较，验证了GBO具有较好的开发与探索能力，且在求解减速机、三杆桁架、工字钢设计和悬臂梁等工程问题时性能显著.GBO算法虽然性能表现卓越，但在解决某些复杂优化问题时仍存在求解精度低、收敛速度慢且易陷入局部最优等缺点，因此许多学者对GBO算法进行了不同的改进与应用.Zhou Wei[5]等提了基于梯度的光伏模型参数提取优化器，利用随机学习机制来提高梯度优化算法的性能；M H Hassan[6]等将曼塔射线觅食优化(MRFO)与基于梯度优化器(GBO)混合为MRFO-GBO，MRFO-GBO能有效求解单目标和多目标EED问题.

为改善GBO的性能表现，MGBO应用了交叉算子和反向学习两种策略进行改进.首先对每次迭代前的种群进行预处理，执行交叉算子来提高解的质量、增强种群多样性，加快收敛速度；然后对搜索后更新的种群进行反向学习，加强算法逃离局部最优的能力，提高算法求解精度.通过对9个测试函数进行仿真实验对比，结果表明改进算法效果显著，收敛速度和求解精度得到较大的提升.

1 基本梯度优化算法

梯度优化算法的主要思想是将梯度搜索规则(GSR)和局部逃逸算子(LEO)相结合进行全局和局部搜索.

1.1 梯度搜索规则 (GSR)

GBO算法从一组随机的初始解开始，并根据指定方向的梯度更新每个个体位置.为了保证算法的探索与开发能力之间的平衡，采用的ρ1如下：

ρ1=2×rand×α-α

(1)

(2)

(3)

rand是[0,1]中的一个随机数，βmin=0.2，βmax=1.2，m为当前迭代次数,M为总迭代次数，参数ρ1基于正弦函数α进行更新.因此，GSR可以确定如下：

(4)

Δx=rand(1：N)×|step|

(5)

(6)

(7)

DM=rand×ρ2×(xbest-xn)

(8)

ρ2=2×rand×α-α

(9)

(10)

(11)

ypn和yqn表达式如下：

(12)

(13)

(14)

(15)

(16)

其中

定义如下：

(17)

1.2 局部逃逸算子(LEO)

ifrand

End

(18)

f1是在[-1,1]范围内的均匀随机数，f2是来自均值为0、标准差为1的正态分布的随机数，pr是概率，u1、u2、u3是三个随机数，分别定义为：

u1=L1×2×rand+(1-L1)

(19)

u2=L1×rand+(1-L1)

(20)

u3=L1×rand+(1-L1)

(21)

(22)

其中L2是一个二进制参数，其值为0或1.如果μ2小于0.5，则L2的值为1，否则为0.

2 基于交叉算子和反向学习的GBO

针对基本梯度优化算法存在的求解精度低、收敛速慢、易陷入局部最优等缺陷，MGBO分别从两个方面进行改进：①利用交叉算子对当前种群进行处理，能丰富种群的多样性，提高收敛速度和收敛精度；②通过对当前所得解进行反向学习来扩大解的搜索范围以逃离局部最优，从而提高求解精度.

2.1 交叉算子

曹天问等[7]将两点交叉算子运用于细菌觅食算法中，受此启发，MGBO也采用两点交叉来进行改进，但又与他们不同，这处理的方式是将要淘汰的一半个体分别与当前种群最优个体两两进行交叉，交叉过后所得种群代替即将被淘汰的个体.与原始算法相比这有利于降低时间复杂度且该过程将优质基因带入到当前种群，优质基因的流入提高了种群多性，利于逃离局部最优，提高求解精度.交叉算子表达式如下：

(23)

2.2 反向学习

反向学习(Opposition-based learning,OBL)是Tizhoosh教授在2005年提出来的一种优化技术，根据概率定律，当前解有0.5的概率比它的反向解更接近最优解，目前反向学习已经成功运用于果蝇优化算法(FOA)[8]，粒子群算法(OPSO)[9]，差分算法(ODE)[10].

2.3 基于交叉算子的反向梯度优化算法(MGBO)

MGBO算法流程大致如下：

Step 1 初始化设置算法的基本参数.

Step 2 通过评估函数求出每个个体的适应值，并记下最优xbest和最差xworst位置.

Step 7 对当前解的位置信息进行越界处理，随后计算其适应度，判断是否优于当前记录中的全局最优值，若是，则更新全局最优值.

Step 8 判断算法是否满足迭代终止条件，若满足，则输出全局最优解，否则跳转至Step 3进行下次迭代寻优.

2.4 算法复杂度分析

时间复杂度是指算法执行所需要的计算工作量.在基本梯度优化算法中，时间复杂度主要受到种群规模nP、最大迭代次数MaxIt、及问题维度D的影响.由GBO算法寻优过程可知其时间复杂度为O(nP*MaxIt*D+nP).相比GBO算法，MGBO算法在迭代过程中，增加了将种群的一半个体与最优个体两两进行交叉、反向学习操作，因此MGBO比GBO多(MaxIt*(nP*3/2+D))次运算量.

3 实验仿真及分析

为了验证本文提出的MGBO算法的有效性，选取了9个经典基准函数进行数值实验，并与基本梯度优化算法、灰狼优化算法、粒子群算法[11]、哈里斯鹰优化算法[12]和鲸鱼优化算法进行比较.表1给出了测试函数的基本信息和相关参数设置，包含单峰、多峰等不同特征的测试函数.表2为每个算法主要参数设置.

表1 测试函数参数设置

表2 算法主要参数设置

为了降低算法的随机性对实验结果的影响，我们对独立运行30次的实验结果取平均，其中种群规模为50、最大迭代次数为1 100次.表3给出了改进算法(MGBO)、梯度优化算法(GBO)、灰狼优化算法(GWO)、粒子群算法(PSO)、哈里斯鹰优化算法(HHO)和鲸鱼优化算法(WOA)在30维、50 维、100 维三种的情况下搜索得到的平均值、标准差，其中结果最好的用粗体显示.

表3 不同算法在不同维度下的平均值及标准差

实验环境为：Windows10 系 统，8 GB 内 存，CPU 2.00 GHz，算法基于 MATLAB 2016b 用M语言编写.

从表3知，无论是30、50、100维MGBO对于5个单峰函数(f1-f5)都是最优，特别在求解f1和f3时获得了理论最优值0.对于4个多峰函数(f6-f9)，在30、50、100维上，MGBO在求解f6和f8时都获得了理论最优值0，MGBO虽在f7上无法取到理论最优值，但平均值都优于其对比算法的平均值，且求解f9函数时MGB0的结果都比对比算法要好.因此整体来说MGBO在求解单峰、多峰函数时都有更好的寻优效果与可扩展性.标准差可以反映算法的稳定性.由表3可知，MGBO独立运行30次计算的标准差始终不大于对比算法，这说明MGBO对单峰、多峰、低维、高维测试函数的稳定性好.

表4 MAE算法排名

可以看出，MGBO排名均为 1，与另外5种算法相比，MGBO提供了最小的MAE，进一步证明了MGBO的有效性.

为了更好地对比六种算法的寻优性能，图1给了它们在不同函数上50维的收敛曲线，其中横坐标为迭代次数，所有函数其适应度值都取以10为底的对数.

由图1(a)-(e)可知，随着迭代次数的增加，梯度优化算法、灰狼优化算法、粒子群算法、哈里斯鹰优化算法和鲸鱼优化算法在单峰函数上均收敛速度均较慢、无法搜索到理论最优值且MGBO的收敛曲线下降最快，速度得到了明显的提高，这说明引入交叉算子增加了种群多样性，使得算法加快收敛速度.图(f)-(i)是多峰函数平均收敛曲线，MGBO在f6-f9上迭代收敛速度很快，尤其对f6和f8两函数最明显，这说明反向学习有效改善算法性能及交叉算子引入优质基因的作用是突出的.

图1 函数收敛曲线

4 结语

本文对GBO算法中存在早熟性收敛以及陷入局部最优，提出了一种应用交叉算子和反向学习的梯度优化算法(MGBO).交叉算子的引入可以丰富种群的多样性，对单峰函数而言，寻优能力和收敛速度得到了明显的提高；反向学习策略是通过评价候选解和反向解的优劣来扩大搜索空间，对于多峰函数而言有利于逃离局部最优值转向全局最优值收敛，加快算法收敛速度.实验证明，本文的算法不但有效地加快搜寻速度，且提高了解的精度.