自适应变异粒子群优化算法及在新冠肺炎疫情传播预测中的应用

季伟东,徐浩天,林 平

1(哈尔滨师范大学 计算机科学与信息工程学院,哈尔滨 150025) 2(哈尔滨医科大学,哈尔滨 150086)

1 引 言

群体智能算法通常是指模拟自然过程来解决复杂的工程问题的算法,这些算法具有群体搜索性、多进程并行性、自适应、自学习等特质,代替传统算法解决含有多个极值和高维复杂优化问题.经过多年的发展,在参数优化、神经网络训练等领域得到广泛运用.而其中的粒子群算法原理简明,参数少而受研究者们青睐.为了解决大规模高维复杂函数优化问题,出现很多改进粒子群优化算法,这些算法通常针对某一方面进行改进来强化全局搜索或者局部搜索能力.譬如对粒子群算法参数进行改进,Shi[1]等将惯性权重因子加入速度位移公式,得到线性递减权重的粒子群算法,算法的全局和局部搜索得到了较好的平衡.Yan[2]等引入收缩因子,该因子控制粒子的移动轨迹,提升算法全局开发能力,使得算法能够得到及时收敛.从算法的拓扑结构角度研究,Cheng[3]等设计的SLPSO将社会学习机制引入粒子群优化,每个粒子向种群中任何一个更优的粒子学习,将社会学习机制的能力即全局搜索能力最大化.梁静等[4]提出随机动态协同进化策略,将其应用到多种群粒子群优化算法中,加强算法局部搜索能力.邓先礼[5]通过赋予不同子种群不同的搜索特性,实现子种群间的协作和综合性能的提升.除参数和拓扑结构,重新设计速度位移更新的规则也可以对提升算法的搜索能力,如经典的CLPSO算法[6]中,粒子以不同维度从各个粒子学习经验来更新自身的速度.黄洋等[7]在算法的位移更新公式引入S型函数,利用粒子与种群之间的适应度比值关系自适应调整搜索步长,提高了算法的搜索效率.而当今较为流行的是将粒子群优化算法与智能方法结合,反向学习策略是其中的佼佼者,Tizhoosh H R[8]中提出了反向学习(Opposition-based learning,OBL).夏学文[9]提出一种具备方向学习和局部学习能力的粒子群算法,反向学习保证全局探测能力,利用差分策略提升局部探测能力,较好的实现全局和局部双重优化.周凌云[10]将邻域重心引入反向学习PSO中,保持种群多样性的同时充分利用种群搜索经验,增强全局搜索能力,有效提高了算法性能.

从中可以发现,目前的改进粒子群算法一般针对于局部搜索能力或全局搜索能力其中一方面进行强化.兼顾强化局部和全局搜索能力的算法也很容易会失去平衡搜索能力的控制力,最终导致算法本质上只强化部分能力,并未充分发挥粒子群算法的特点.针对该系列问题,受深度学习萤火虫算法[11]和二阶振荡粒子群算法[12]的启发.本文提出了一种自适应变异优化的学习策略,并将之应用到粒子群优化算法.利用算法优化神经网络参数,实现新冠肺炎疫情传播预测模型的构建.其创新点主要体现在4方面:

1.设计了柯西变异和高斯变异的方法.

2.设计了新的速度位移更新规则.

3.设计了基于算法进度的自适应变异优化策略.

4.算法应用到前馈神经网络完成新冠肺炎疫情预测模型.

最后通过实验结果验证了本文算法的性能优于其他改进算法,且具有较高的实用性.

2 相关工作

2.1 基于正态分布衰减的惯性权重

为使自适应变异优化策略性能最大化,针对传统粒子群算法的惯性权重因子,本文引入基于正态分布衰减的惯性权重[13],惯性权重公式为式(1),惯性权重变化曲线如图1所示.由图1可见,正态分布衰减惯性权重变化规律可分为前后两个时期.

(1)

其中ωmax,ωmin分别为最大和最小加权系数;tmax为最大迭代次数;t为当前迭代次数;θ描述了正态分布数据分布的离散程度,控制图形曲线,文献[13]提出满足最佳衰减权重曲线的θ等于0.4433．

这样的惯性权重衰减策略可以满足以下规律:前期惯性权重处于最大值,使得算法全局搜索能力最大化,提高算法收敛速度;中期快速过渡,惯性权重衰减迅速,全局搜索能力减弱,局部开发能力增强;后期局部开发能力最大化,提高算法收敛精度.达到全局寻优和局部寻优共同优化的效果.

2.2 自适应变异优化

对粒子进行变异操作可以拓展算法的搜索范围.若进行变异操作后,采用贪心选择策略,粒子的适应度值优于之前的粒子的适应度值,算法便将之前粒子取而代之,从而获得更优解.

表1 8个标准测试函数Table 1 Eight benchmark test functions

本文设计柯西变异和高斯变异用于自适应变异优化.其中柯西变异参考柯西分布函数是一种数学期望不存在的连续型概率分布函数.其分布图如图2中的柯西分布所示,柯西变异操作如式(2)所示:

x(i)*=x(i)+Cauchy*(pbest(i)-x(i))

(2)

其中,x(i)是第i个粒子的位置;x(i)*是更新后的第i个粒子的位置;pbest(i)是第i个粒子的个体最优;Cauchy是基于柯西分布产生的随机数.

图1 惯性权重曲线Fig.1 Inertial weight curve

高斯变异则参考高斯分布,高斯分布是一种连续随机型变量概率分布函数.其分布图如图2中的高斯分布所示,高斯变异操作如式(3)所示:

x(i)*=x(i)+Gaussian*(pbest(i)-x(i))

(3)

其中,x(i)是第i个粒子的位置;x(i)*是更新后的第i个粒子的位置;pbest(i)是第i个粒子的个体最优;Gaussian是基于柯西分布产生的随机数.

图2 柯西分布与高斯分布Fig.2 Cauchy distribution and Gaussian distribution

从图2中可以看出,柯西分布在x轴上具有更宽的取值范围,意味着对应的柯西变异能帮助扩大粒子搜索的解空间范围.经过柯西变异的粒子能够搜索到更多更优的可行解,由此可得知柯西变异适合前期的全局搜索.而高斯变异在y轴上具有更深的取值范围,经过高斯变异的粒子可以提升算法的收敛精度,可以得知高斯变异适合后期的局部搜索.

自适应变异优化则是将算法整个过程分为两个部分:前期与后期.前期对粒子更新完成的位置进行柯西变异,扩大全局搜索范围;后期对粒子的位置进行高斯变异,提升算法收敛精度.

3 自适应变异优化粒子群算法

3.1 速度公式的更新

为了避免改进的粒子群算法在搜索过程中陷入局部最优和收敛精度过低的问题.给出了一种自适应速度更新公式,用来控制个体最优和全局最优对粒子速度的影响度.前期个体最优影响度更大,后期全局最优影响度逐渐变大,以此达到全局搜索和局部开发共同优化的效果.给出粒子速度更新公式见公式(4).

(4)

其中vid(t+1)为更新后的粒子速度;ω为正态分布衰减惯性权重;pbest(t)是粒子在第t代所得的最优位置信息;gbest(t)是种群在第t代所得的最优位置信息;t/tmax为当前迭代次数与最大迭代次数的比值;xid(t)为第t代粒子的位置信息;r1、r2和rand为[0,1]之间均匀分布的随机数.

3.2 自适应变异优化策略

由于柯西变异适合前期全局搜索,高斯变异适合后期局部搜索[14].根据算法迭代次数进行自适应选择变异方式,前期选择柯西变异,后期选择高斯变异.如式(2)和式(3)中,粒子利用自身找到的最优信息完成相应的变异优化.这样的优化方式可以结合式(4)中的局部和全局最优的影响度,前期让全局最优的影响度最大化,使得算法前期能很好的拓展搜索范围,寻得更多更优的可行解;后期让局部最优的影响度最大化,大大提升算法的收敛速度与收敛精度.

3.3 算法流程

将新的速度更新公式和自适应变异优化应用于粒子群优化算法,得到本文的算法—自适应变异优化粒子群算法(ADVPSO).

算法流程如下:

Step 1.采用均匀分布随机初始化种群,生成由N个D维的粒子组成的种群P;

Step 2.计算评价种群P中各个粒子的适应度值.根据优劣更新个体历史最优解Pbest、全局历史最优解Gbest;

Step 3.计算算法迭代次数与最大迭代次数的比值结果,用式(1)更新惯性权重ω;

Step 4.按照式(4)更新每个粒子的速度vi;

Step 5.根据算法迭代次数与最大迭代次数的比值判断,比值如果小于或等于1/2,用式(2)优化更新粒子位置xi;否则用式(3)优化更新粒子的位置xi.

Step 6.计算评价种群P中各个粒子的适应度值.将其与个体历史最优Pbest和全局历史最优Gbest比较,更新最优解.

Step 7.判断算法是否满足终止条件,若满足,算法停止;否则返回执行Step 3.

4 实验对比与结果分析

4.1 参数设置与测试函数

为进一步验证ADVPSO的性能和优势,实验选取了LDWPSO(1998)[1],RLPSO(2015)[9],MSMPSO(2018)[5],SAPSO(2019)[7]和NDPSO(2020)[13]对比.LDWPSO是原始粒子群算法,其中引入了线性衰减惯性权重参数;与RLPSO和MSMPSO对比,是为了验证自适应变异优化策略对比其他智能方法策略的优越性;SAPSO和NDPSO是近几年提出的新型改进PSO算法.为了比较的公平性,实验设置在同一硬件环境下,6个算法的参数设置如下:种群大小N为30;维数D为500维;迭代优化次数为2000次;运行算法次数为20次;c1=c2=2;ωmax为0.9,ωmin为0.4.

表2 各算法在8个标准测试函数上20次独立运行的结果Table 2 Comparison of convergence results of six algorithms

为了客观的对ADVPSO算法的性能做出评价,选用两组基准测试函数[15,16]进行测试.第1组是单峰测试函数:Sphere,Quartic,Rosenbrock和Step,分别记为f1-f4.第1组是复杂的多峰测试函数:Ackley,Rastrigin,Griewank,Schwefel,分别记为f5-f8.这些测试函数是群智能算法最常用的基准测试函数.8个典型标准测试函数定义如表1所示.其中测试函数的定义域为粒子的每一维度的数值取值范围,最优值为理论上对应测试函数的最优解,而算法的目的就是要求得此最优值.

4.2 实验结果与分析

将6个算法根据以上要求设定初始值,运行20次后取平均最优值进行比较,结果如表2所示.加粗值表示各算法中最优值.第1组测试函数f1-f4是较为简单的单峰测试函数.从表2结果来看,由于算法初始设定D=500维,而LDWPSO、RLPSO、MSMPSO、SAPSO 由于高维度的复杂性,几乎不能找到单峰函数的最优解,并且过早的陷入局部最优.ADVPSO在f1和f2上的收敛精度是最高的.除了f3和f4,ADVPSO解的平均最优值都远远小于其他算法.而f3是单峰测试函数中较为复杂的病态测试函数,故而大部分算法在此函数上性能表现较差,但ADVPSO的解的精度仍要高于其他算法.在f4函数中,由于其特殊的阶梯形状,使得算法容易陷入局部最优.ADVPSO是根据迭代次数分别在前后期进行柯西变异,高斯变异,虽然可以跳出部分阶梯,但仍会陷入局部最优,而其他算法几乎无法跳出局部最优,所以尽管精度都不高,但ADVPSO仍然有较强的性能.

第2组测试函数f5-f8是较为复杂的多峰测试函数.这些测试函数往往有多个局部极小值,且分布位置特殊,极其容易引导算法陷入局部极小值.ADVPSO算法在多峰测试函数中表现良好,在f6-f7中,ADVPSO都取得了最优解0.在f5和f8中,ADVPSO取得的解精度也远远高于其他算法,因为f8具有很深且距离最优解较远的局部极小值,相比其他算法,ADVPSO的正态分布衰减权重策略能扩大算法前期的全局搜索范围,后期也有较好的局部搜索能力,很好的平衡了局部与全局搜索.

图3 各算法在f1-f8上的收敛曲线Fig.3 Convergence curves of each algorithm on f1-f8

从图3中可以看出,ADVPSO的收敛性能远远优于LDWPSO、RLPSO、MSMPSO、SAPSO、NDPSO得益于ADVPSO算法的自适应变异优化策略.图3中(a,e,f,g,h)有一个明显的曲线转折点,当迭代次数为1000次时(即最大迭代次数的一半),解的精度大幅度提升.自适应变异优化策略依靠局部和全局寻优的影响度,图2中可知柯西分布使粒子拥有较宽的取值范围,意味着对应的柯西变异能帮助扩大粒子搜索的解空间范围. 经过柯西变异的粒子能够搜索到更多更优的可行解,由此可得知柯西变异适合前期的全局搜索.而高斯分布在y轴上具有更深的取值范围,经过高斯变异的粒子可以提升算法的收敛精度,可以得知高斯变异适合后期的局部搜索.当算法前期陷入局部最优时利用正态分布惯性权重衰减策略的前期粒子收敛步长较大的特性,结合柯西变异拓展解空间,让粒子有更多的可行解进行搜索,及时跳出局部最优,后期利用正态分布惯性权重衰减策略后期粒子步长较小的特性,结合高斯变异加强局部搜索能力,提高解的精度.

实验分析后,ADVPSO算法性能优于其他改进PSO算法,证明了自适应变异优化策略的有效性.

5 算法在新冠肺炎疫情传播预测中的应用

在全世界抗击新冠肺炎的过程中,涌现出大量对新冠肺炎疫情传播的研究.国内高校及科研院所利用模型对新冠肺炎疫情传播进行预测分析,其中张琳[17]采用了次指数增长方式拟合了早期国内新冠肺炎疫情爆发的情况,并在拟合好的次指数增长模型基础上,预测疫情当前阶段的发展情况.盛华雄[18]对武汉封城前后的新冠肺炎疫情传播进行建模分析,采用经典的SIR模型和差分递推方法预测疫情.以此为例,本文爬取中华人民共和国国家卫生健康委员会疫情通报中的每日新确诊人数数据(1)http://www.nhc.gov.cn/xcs/yqtb/list_gzbd.shtml,使用神经网络进行预测分析.其中神经网络中的各个权重参数(初始权值和阈值)由本文提出的ADVPSO算法进行优化.

将2020年3月14日-6月21日共100天的每日新确诊人数进行数据与处理,处理结果如图4所示.从图中可以看出疫情爆发前期,每日新确诊人数居高不下,后期即使减少也偶尔有人数爆发,由于政府的有效控制以及人口流动等诸多未知因素,新确诊人数呈现非线性、非平稳和非高斯分布特性,因此数据的拟合存在困难且预测每日确诊人数准确率较低.如果采用普通的神经网络,则需要前期不断调试网络节点中的初始权值及阈值,这会花费大量的人力时间成本.本文因此采用改进的粒子群算法对神经网络中的权重参数及隐含层节点数进行迭代优化,使模型能更准确的预测,提高模型准确率.

实验参数设置为:模型独立预测次数为20次,分析所得数据后,将训练集与测试集按2:1的比例进行数据分割.训练集为2020年3月14日-5月16日,共64天的新确诊人数数据,测试集为2020年5月17日-6月14日,共36天的新确诊人数数据,模型输入层节点数为3,隐含层节点数为4,输出层节点数为1,其中粒子群优化权重参数的参数为:迭代次数为500次c1=c2=2;ωmax为0.9,ωmin为0.4.

图4 预处理后的新确诊人数Fig.4 Number of newly diagnosed patients after pretreatment

实验结果如图5所示,在进化初期,曲线上升速度快,说明神经网络具有较快的收敛速度,能有效的减弱常规进化算法的早熟收敛、易陷入局部最优解的现象.算法适应度值随着次数的增加而逼近最优解,平均适应度值最佳为0.9546.

图5 适应度值变化曲线Fig.5 Fitness curve

图6 用ADVPSO预测新确诊人数曲线与实际新确诊 人数曲线比较图Fig.6 Comparison between predicted and actual newly diagnosed cases

使用ADVPSO算法优化的神经网络预测模型在训练后,预测2020年5月17日-2020年6月21日总计36天的新确诊人数,其中实际新确诊人数为实线,预测新确诊人数为虚线,如图6所示.

从图6中可以看出,使用ADVPSO算法优化的神经网络预测模型在训练后,预测新确诊人数与实际新确诊人数基本相同,由此可见本文使用的ADVPSO优化神经网络具有良好的预测新冠肺炎新确诊人数的能力,通过对神经网络的权值和阈值进行调整优化,使得算法适应度值不断逼近最优解,与此同时,神经网络预测模型的预测性能随着适应度值的逼近也得到提升.

为了方便描述ADVPSO算法优化神经网络的优势,采用传统粒子群算法与ADVPSO进行实验比较,通过比较适应度值、误差(训练误差即训练集结果与元数据集的误差,预测误差为模型训练完毕后新预测的结果与元数据集的误差) 和所获得的节点连接数,完成性能比较,实验结果如表3所示,加粗值为比较后的最优值.

表3 两种算法实验结果比较Table 3 Comparison of experimental results of two algorithms

6 结 语

本文提出了一种自适应变异优化粒子群算法,以算法运行进度作为参考,将整个寻优过程分为两个阶段.在此基础上,采用高斯分布惯性权重衰减策略动态更新ω,在不同阶段引导粒子的搜索行为.当粒子寻找到自身的最优解,便利用个体最优信息以及自适应变异机制优化粒子,实现了算法的高效搜索及计算资源的合理利用.实验结果表明ADVPSO具有良好的综合性能,在单峰及高峰函数中都表现出较好的鲁棒性.结合2020年新冠疫情爆发情况,本文将该算法应用至神经网络来建立预测模型,用ADVPSO算法优化神经网络权重参数,提高预测模型准确率.为验证ADVPSO算法的优势,将其与传统PSO算法优化的模型进行比较,ADVPSO仍具有较好的鲁棒性和实用性.

其中,ADVPSO对寻优过程的自适应划分并非最优划分方式.前期的全局搜索和后期的局部搜索对整个寻优过程的影响度还有待分析.这些研究将在后续工作中进一步解决.