多策略改进的麻雀搜索算法及应用

薛 涛,张安杰

(西安工程大学 计算机科学学院,陕西 西安 710048)

0 引 言

随着算法的不断发展,学者们通过现实生活中的生物行为提出了一系列群体智能优化算法[1],如萤火虫算法(firefly algorithm,FA)[2]、灰狼优化(grey wolf optimizer,GWO)[3]算法、布谷鸟搜索(cuckoo search,CS)[4]算法、鲸鱼优化算法(whale optimization algorithm ,WOA)[5]等。麻雀搜索算法(sparrow search algorithm,SSA)[6]是近年来发展起来的一种新型元启发式算法,具有较高的局部搜索能力和收敛性能。在电力负荷预测[7-8]、无人机航迹规划[9-10]、图像处理[11-13]、神经网络参数优化[14-16]等方面的应用研究取得了较大进展,具有一定的研究意义。

与其他智能算法相比,SSA的优化效果更好,但在搜索过程中仍然存在全局搜索能力弱和容易陷入局部最优的问题。针对此问题,国内外学者做了相关的研究。文献[17]提出了一种自适应混沌麻雀搜索优化算法,采用改进的Tent混沌映射对种群进行初始化,以增加种群的多样性,进而提高算法的全局搜索能力。文献[18]在此Tent混沌映射的基础上引入了高斯变异方法,以避免麻雀搜索算法陷入局部最优解。文献[19]除了利用混沌对立学习策略初始化麻雀种群,还改进发现者位置更新公式,采用非线性权重因子和柯西算子来平衡该算法的全局探索和局部开发能力,最后,根据基于差分进化的GWO算法的思想,对种群个体进行分阶段干扰,进一步提高种群多样性,降低算法陷入局部极值的可能性。文献[20]提出一种融合柯西变异和反向学习的改进SSA,通过在最优解位置扰动变异,产生新解,提升算法避免陷入局部最优的能力。上述文献中虽然对于SSA的全局搜索能力和跳出局部最优的能力进行了改进和优化,但是同时也增加了种群的多样性,在收敛速度和精确度上并没有得到较大的改善,需要进一步研究。

为了改善SSA收敛速度慢和精确度不高的问题,本文基于原始SSA,提出了多策略改进的麻雀搜索算法(improved sparrow search algorithm based on multiple strategies,ISSAMS)。首先,采用改进的Circle混沌映射初始化种群,相对于Logistic映射和Tent映射种群分布更均匀、更稳定,避免陷入不动点;随后,在更新跟随者位置时使用正弦余弦搜索策略,可以避免陷入全局最优;最后,通过萤火虫扰动来提升算法的局部搜索能力,加快算法整体的收敛速度。本文选取8个基准函数对于改进后的SSA进行验证,其算法表现出的收敛速度和精确度上明显优于其他算法。通过将改进后的SSA应用到优化BP神经网络的权值和阈值中,与其他几种模型进行比较,来验证改进的有效性和可行性。

1 SSA理论

SSA主要模拟麻雀的觅食行为和反捕食行为,可以按照其行为将麻雀分为几种不同的角色。种群中适应度值高的个体称为发现者,其捕食能力强,自身能量高。剩余个体称为跟随者,同时从种群中选取一定比例的麻雀个体作为侦察者,来对种群进行侦察预警,如果发现危险则放弃食物向安全位置移动。

在种群中,发现者大多聚集在种群的中心,捕食能力强。同时,种群中大多数麻雀为了获取更多的食物会向能量高的麻雀中心靠拢,即称为跟随者。在种群边缘的个体容易受到其余捕食者的攻击,因此选取一定的麻雀作为侦察者,一旦发现捕食者时,便会发出鸣叫警示种群,并不断向种群中心靠拢,通过更新位置来确保安全。该具体算法流程步骤如下所示。

1) 初始化种群的位置。种群的初始位置可以用一个矩阵表示,总共有n只麻雀,矩阵的每一行是在d维空间内每只麻雀初始的位置:

(1)

在d维空间内,其所有麻雀的初始适应度值为

(2)

2) 更新发现者位置。在种群中适应度值高的麻雀作为发现者,且发现者通过不断地移动来寻找更多的食物,而其他跟随者也随之移动位置。如果有麻雀发现了捕食者,就会向种群发出鸣叫表示预警,如果预警信号值大于阈值时,发现者就会向安全的位置移动,跟随者也随之移动,整个种群会更新到新的位置,其中,发现者更新公式可表示为

(3)

3) 更新跟随者位置。在种群中选取70%～80%作为发现者,其余均为跟随者,跟随者随着发现者向食物更多的地方移动,所获取的食物量越来越多,也可能会变为发现者。跟随者位置更新公式可表示为

(4)

4) 更新侦察者位置。种群中随机选取10%～20%的麻雀作为侦察者,其他麻雀在觅食时,它们负责警戒,如有危险靠近会立即放弃当前食物移动到下一个位置。侦察者位置更新公式可表示为

(5)

2 SSA的改进

针对SSA随着种群迭代次数的增加容易陷入局部最优解问题,并且收敛速度慢等问题。本文提出了ISSAMS,使用Circle混沌映射初始化种群,提升种群的多样性和稳定性;同时修改种群中发现者的位置更新公式,改变原始算法中繁琐的计算,去除向原点收敛的操作,提升全局搜索能力;采用正弦余弦搜索策略更新跟随者位置和利用萤火虫扰动进行寻优,提升算法跳出局部最优的能力,避免陷入局部最优。

2.1 Circle混沌映射

目前初始化种群常用的是Tent混沌映射[21]、Logistic混沌映射[22],本文选用Circle混沌映射来初始化种群。传统的Logistic混沌映射分布不均匀对算法的收敛速度和精度有影响。虽然Tent映射的分布更加均匀,但存在不稳定周期,容易陷入不动点。Circle映射比较稳定且分布的均匀性和Tent相当。其具体公式如下:

(6)

式中:Xi+1代表第i+1个位置,已知Xi位置,通过对其运算求余得到第i+1位置,其中mod为取余函数,以此类推,生成每个位置成功初始化种群。其Circle混沌映射如图1所示。

图1 Circle混沌映射分布

从图1可以看出,原始的Circle混沌映射,混沌值集中在0.2～0.4之间,仍存在种群分布不均匀问题,针对于此,改进Circle混沌映射公式,改进后的具体公式为

(7)

改进后的Circle混沌映射如图2所示。

图2 改进后的Circle混沌映射分布

从图2可以看出,改进后的Circle混沌映射分布共更均匀,在初始化种群时,增强种群的多样性,提升算法的寻优能力。

改进更新发现者的位置公式:

(8)

去除向原点靠近的操作,当R2

2.2 正弦余弦搜索策略

在原始SSA中,当更新跟随者位置时使用正弦余弦搜索策略,利用正弦余弦函数使解震荡性地趋于全局最优解,避免陷入全局最优。

(9)

2.3 萤火虫扰动

为了提升算法的局部搜索能力,在麻雀每代个体位置更新后用萤火虫扰动进行寻优,不仅可以对单峰函数表现出很好的性能,在优化多峰函数上也有不错的表现,可以在一个较小的区域内快速找到该区域的最优解。

Xi=Xi+β0exp(-γr2)(Xj-Xi)+

α·k

(10)

式中:Xi为萤火虫i所处的空间位置;Xj为萤火虫j所处的空间位置;β0为最大吸引度;γ∈[0,1]为吸光系数;α∈[0,1]为步长因子;k为[-0.5,0.5]上服从均匀分布的随机数。改进后的具体算法流程如图3所示。

图3 算法流程

3 仿真实验

本文将ISSAMS与其他算法做对比试验。选取5个基准测试函数:

其维度均为30,最优值均为0;f1～f3为单峰函数,f4～f5为多峰函数。

为分析算法改进的有效性,本文将SSA、遗传算法(genetic algorithm,GA)、GWO算法、粒子群优化(particle swarm optimization,PSO)算法和本文算法对表1中的基准函数进行寻优测试,针对这5种算法,每个算法独立运行30次,取每次的最优值。其中,每运行一次的算法迭代次数为1 000,种群数量为30。如表1给出了SSA、GA、GWO、PSO、ISSAMS对于5种基准函数的仿真实验结果。

表1 SSA与GA、GWO、PSO、ISSAMS仿真结果

从表1可以看出,在单峰函数中,GA均值最大,同时标准差也最大,说明稳定性最差,GWO、PSO算法次之。SSA、ISSAMS虽然都能找到理论最优解0,但是通过标准差来看,ISSAMS标准差为0,算法更稳定,由于ISSAMS融合了多种策略,并且在局部搜索能力和寻优速度上都有所提升,因此ISSAMS在稳定性和精确度上都优于SSA,而且是实验中5种算法整体性能最好的。在多峰函数函数中,每个函数都具有多个局部最优解,容易陷入局部最优。本文的ISSAMS引入正余弦搜索策略,增强局部搜索能力,避免陷入全局最优使其具备跳出局部最优解的能力。因此,不管是在最优值还是标准差上都较优于其他4种算法,特别是函数中ISSAMS相较于另外4种算法在平均值和标准差有着很大的提升。因此,结合上述分析,对于融合多策略改进的ISSAMS在收敛速度、稳定性和精确度上都表现出很好的性能。

为了更进一步分析改进后算法的收敛速度,对于5种算法依次进行了仿真实验,图4和图5为本文中的5种算法分别迭代了1 000次以后得到的收敛曲线。

(a) f1收敛曲线

从图4可以看出,对于单峰函数 ,ISSAMS收敛速度更快,明显优于其他,4种算法,而且表现出更强的局部搜索能力和更高的精确度,其次是SSA。

从图5可以看出,对于多峰函数,除了GA和PSO算法,SSA、GWO算法、ISSAMS收敛速度相差不大,但是总体ISSAMS收敛速度还是较优于其他算法,而在精确度上ISSAMS明显优于其他4种算法,说明基于多策略改进的麻雀搜索算法具备更强的跳出局部最优解的能力。

上述结果说明,利用改进后的Circle混沌映射初始化种群,增加了种群均匀性,提升了算法的收敛速度;引入正弦余弦搜索策略和萤火虫扰动,增加了全局搜索范围,趋于全局最优解,加速寻优过程,提升了算法的逃离局部最优能力。因此,本文提出的ISSAMS对比其他算法,在收敛速度、精确度和跳出局部最优的能力都得到了较大的提高。

4 改进的SSA优化BP神经网络

BP神经网络是一种按照误差逆向传播算法训练的多层前馈神经网络,是应用最广泛的神经网络模型之一[23]。但是传统的BP神经网络在实际应用中,可能经常陷入到局部极小值中,此时可以通过选取智能优化算法对每一轮的权值和阈值进行优化,来获得全局最优值。其中,文献[24]提出一种基于正弦混沌映射的改进SSA改进BP神经网络对风速进行预测。文献[25]将Logistic混沌映射和Lévy飞行策略整合到传统的SSA,优化BP神经网络的初始权重和阈值来预测风电功率。上述基于SSA的改进结合BP神经网络进行预测,由于改进的有限性,仍存在收敛速度慢,权值阈值精确度低等问题。针对此问题,本文选取ISSAMS和SSA、CSSA、PSO算法、GWO算法来分别对BP分别进行优化;对于同一样本数据,比较其相关指标,如平均绝对误差(mean absolute error,MAE)、均方误差(mean-square error,MSE)、均方根误差(root mean squared error,RMSE)、平均绝对百分比误差(mean absolute percentage error,MAPE)、收敛速度等,验证本文算法的改进在优化BP神经网络上的有效性。

4.1 BP神经网络模型设计

首先针对现有的BP神经网络模型进行改进,优化BP神经网络的权值和阈值,其具体步骤如下:

1) 数据归一化处理,初始化参数;

2) 使用Circle混沌映射初始化适应度值,然后找出当前最优适应度值和最差适应度值,以及相对应的位置;

3) 根据式(3)、(4)、(5)依次更新发现者、跟随者、侦察者位置;

4) 输出最优麻雀位置,即得到BP神经网络的相关最优参数;

5) 优化后的BP神经网络训练与测试,与优化前的BP神经网络进行误差分析和精度对比。ISSAMS-BP模型的流程如图6所示。

图6 ISSAMS优化的BP神经网络流程

4.2 改进算法优化BP神经网络性能分析

4.2.1 实验数据集

本文中选取的数据集为工业互联网数据湖[26]平台中的电力负荷数据,包含从发电厂收集的201个数据点。数据的特征包括每小时平均环境变量温度、环境压力、相对湿度和排气真空,以预测电厂每小时净电能输出。选取15组数据作为测试集对预测结果进行验证。其中初始种群规模为30,最大进化代数50。

4.2.2 实验环境

本文实验采用的PC设备参数为:AMDR7-5800H CPU,2.90 Hz,运行内存为16 GiB,Windows10系统。仿真实验使用Matlab2016b软件进行编程并作图。

4.2.3 实验结果分析

为了验证改进策略的有效性,通过将ISSAMS、SSA、基于Circle混沌映射初始化改进后的SSA(简称CSSA)、PSO算法、GWO算法分别对BP神经网络模型进行优化,优化后的模型对数据进行预测,其中将数据集中电厂每小时净电能输出的预测结果的均方误差作为衡量标准,进化代数表示算法的收敛速度,通过这2个指标来说明不同的算法在优化BP神经网络的好坏。具体实验结果如图7所示。

图7 进化收敛曲线

从图7可以看出,5种不同的算法对于BP的优化效果,其中使用SSA、PSO和GWO算法优化的BP模型,其误差区别不大,但SSA的收敛速度稍快于PSO和GWO算法,而CSSA和ISSAMS在其收敛速度上保持一致,由于都引入了Circle混沌映射进行种群初始化,增加种群的多样性,提高全局搜索能力,但是ISSAMS的MSE值更小,表示其模型预测的精度更精确。

为了更能说明改进算法优化BP的性能,通过比较MAE、MSE、RMSE和MAPE,具体对比如表2所示。

表2 性能指标

从表2和图7可以看出,在使用了本文提出的ISSAMS优化的BP神经网络模型预测,在收敛速度上,本文提出的算法从第2代开始逼近了最优值,收敛速度最快,明显优于其他4种模型,而且精确度也最高。在其MAPE值上,ISSAMS-BP模型误差达到了0.594 2%,比BP、SSA-BP、CSSA-BP、PSO-BP和GWO-BP的MAPE值分别降低了28.05%、12.84%、7.69%、18.59%、19.35%。总体来看ISSAMS在优化BP神经网络上具备一定的优势,通过实验得到了验证。

5 结 语

1) 采用改进的Circle混沌映射初始化种群,增加了种群的多样性和稳定性,扩大了麻雀在空间中的搜索范围,从而提高了算法的寻优效率。同时改进发现者位置更新公式,加快收敛速度;采用正弦余弦搜索策略和萤火虫扰动来提升算法跳出局部最优的能力和增强局部搜索能力。

2) 将融合多策略改进的算法与其他几种算法做对比实验,在加入了Circle混沌映射、正弦余弦搜索策略和萤火虫扰动后,实验结果表明ISSAMS有效地改善了SSA的寻优能力,同时具备更高的收敛能力、精确度和稳定性,大大提升了算法整体性能。

3) SSA可以优化BP神经网络的权值和阈值,提升神经网络的模型准确度。通过将融合多策略改进的ISSAMS应用到权值和阈值的优化中,得出ISSAMS-BP明显优于原始BP和另外4种预测模型,同时,进一步验证了ISSAMS改进的有效性。后续研究可将ISSAMS应用于更多的神经网络模型中,提升预测模型的准确度。