自適應變異粒子群優(yōu)化算法及在新冠肺炎疫情傳播預測中的應用

季偉東,徐浩天,林 平

1(哈爾濱師范大學 計算機科學與信息工程學院,哈爾濱 150025) 2(哈爾濱醫(yī)科大學,哈爾濱 150086)

1 引 言

群體智能算法通常是指模擬自然過程來解決復雜的工程問題的算法,這些算法具有群體搜索性、多進程并行性、自適應、自學習等特質,代替?zhèn)鹘y(tǒng)算法解決含有多個極值和高維復雜優(yōu)化問題.經過多年的發(fā)展,在參數優(yōu)化、神經網絡訓練等領域得到廣泛運用.而其中的粒子群算法原理簡明,參數少而受研究者們青睞.為了解決大規(guī)模高維復雜函數優(yōu)化問題,出現很多改進粒子群優(yōu)化算法,這些算法通常針對某一方面進行改進來強化全局搜索或者局部搜索能力.譬如對粒子群算法參數進行改進,Shi[1]等將慣性權重因子加入速度位移公式,得到線性遞減權重的粒子群算法,算法的全局和局部搜索得到了較好的平衡.Yan[2]等引入收縮因子,該因子控制粒子的移動軌跡,提升算法全局開發(fā)能力,使得算法能夠得到及時收斂.從算法的拓撲結構角度研究,Cheng[3]等設計的SLPSO將社會學習機制引入粒子群優(yōu)化,每個粒子向種群中任何一個更優(yōu)的粒子學習,將社會學習機制的能力即全局搜索能力最大化.梁靜等[4]提出隨機動態(tài)協(xié)同進化策略,將其應用到多種群粒子群優(yōu)化算法中,加強算法局部搜索能力.鄧先禮[5]通過賦予不同子種群不同的搜索特性,實現子種群間的協(xié)作和綜合性能的提升.除參數和拓撲結構,重新設計速度位移更新的規(guī)則也可以對提升算法的搜索能力,如經典的CLPSO算法[6]中,粒子以不同維度從各個粒子學習經驗來更新自身的速度.黃洋等[7]在算法的位移更新公式引入S型函數,利用粒子與種群之間的適應度比值關系自適應調整搜索步長,提高了算法的搜索效率.而當今較為流行的是將粒子群優(yōu)化算法與智能方法結合,反向學習策略是其中的佼佼者,Tizhoosh H R[8]中提出了反向學習(Opposition-based learning,OBL).夏學文[9]提出一種具備方向學習和局部學習能力的粒子群算法,反向學習保證全局探測能力,利用差分策略提升局部探測能力,較好的實現全局和局部雙重優(yōu)化.周凌云[10]將鄰域重心引入反向學習PSO中,保持種群多樣性的同時充分利用種群搜索經驗,增強全局搜索能力,有效提高了算法性能.

從中可以發(fā)現,目前的改進粒子群算法一般針對于局部搜索能力或全局搜索能力其中一方面進行強化.兼顧強化局部和全局搜索能力的算法也很容易會失去平衡搜索能力的控制力,最終導致算法本質上只強化部分能力,并未充分發(fā)揮粒子群算法的特點.針對該系列問題,受深度學習螢火蟲算法[11]和二階振蕩粒子群算法[12]的啟發(fā).本文提出了一種自適應變異優(yōu)化的學習策略,并將之應用到粒子群優(yōu)化算法.利用算法優(yōu)化神經網絡參數,實現新冠肺炎疫情傳播預測模型的構建.其創(chuàng)新點主要體現在4方面:

1.設計了柯西變異和高斯變異的方法.

2.設計了新的速度位移更新規(guī)則.

3.設計了基于算法進度的自適應變異優(yōu)化策略.

4.算法應用到前饋神經網絡完成新冠肺炎疫情預測模型.

最后通過實驗結果驗證了本文算法的性能優(yōu)于其他改進算法,且具有較高的實用性.

2 相關工作

2.1 基于正態(tài)分布衰減的慣性權重

為使自適應變異優(yōu)化策略性能最大化,針對傳統(tǒng)粒子群算法的慣性權重因子,本文引入基于正態(tài)分布衰減的慣性權重[13],慣性權重公式為式(1),慣性權重變化曲線如圖1所示.由圖1可見,正態(tài)分布衰減慣性權重變化規(guī)律可分為前后兩個時期.

(1)

其中ωmax,ωmin分別為最大和最小加權系數;tmax為最大迭代次數;t為當前迭代次數;θ描述了正態(tài)分布數據分布的離散程度,控制圖形曲線,文獻[13]提出滿足最佳衰減權重曲線的θ等于0.4433．

這樣的慣性權重衰減策略可以滿足以下規(guī)律:前期慣性權重處于最大值,使得算法全局搜索能力最大化,提高算法收斂速度;中期快速過渡,慣性權重衰減迅速,全局搜索能力減弱,局部開發(fā)能力增強;后期局部開發(fā)能力最大化,提高算法收斂精度.達到全局尋優(yōu)和局部尋優(yōu)共同優(yōu)化的效果.

2.2 自適應變異優(yōu)化

對粒子進行變異操作可以拓展算法的搜索范圍.若進行變異操作后,采用貪心選擇策略,粒子的適應度值優(yōu)于之前的粒子的適應度值,算法便將之前粒子取而代之,從而獲得更優(yōu)解.

表1 8個標準測試函數Table 1 Eight benchmark test functions

本文設計柯西變異和高斯變異用于自適應變異優(yōu)化.其中柯西變異參考柯西分布函數是一種數學期望不存在的連續(xù)型概率分布函數.其分布圖如圖2中的柯西分布所示,柯西變異操作如式(2)所示:

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

(2)

其中,x(i)是第i個粒子的位置;x(i)*是更新后的第i個粒子的位置;pbest(i)是第i個粒子的個體最優(yōu);Cauchy是基于柯西分布產生的隨機數.

圖1 慣性權重曲線Fig.1 Inertial weight curve

高斯變異則參考高斯分布,高斯分布是一種連續(xù)隨機型變量概率分布函數.其分布圖如圖2中的高斯分布所示,高斯變異操作如式(3)所示:

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

(3)

其中,x(i)是第i個粒子的位置;x(i)*是更新后的第i個粒子的位置;pbest(i)是第i個粒子的個體最優(yōu);Gaussian是基于柯西分布產生的隨機數.

圖2 柯西分布與高斯分布Fig.2 Cauchy distribution and Gaussian distribution

從圖2中可以看出,柯西分布在x軸上具有更寬的取值范圍,意味著對應的柯西變異能幫助擴大粒子搜索的解空間范圍.經過柯西變異的粒子能夠搜索到更多更優(yōu)的可行解,由此可得知柯西變異適合前期的全局搜索.而高斯變異在y軸上具有更深的取值范圍,經過高斯變異的粒子可以提升算法的收斂精度,可以得知高斯變異適合后期的局部搜索.

自適應變異優(yōu)化則是將算法整個過程分為兩個部分:前期與后期.前期對粒子更新完成的位置進行柯西變異,擴大全局搜索范圍;后期對粒子的位置進行高斯變異,提升算法收斂精度.

3 自適應變異優(yōu)化粒子群算法

3.1 速度公式的更新

為了避免改進的粒子群算法在搜索過程中陷入局部最優(yōu)和收斂精度過低的問題.給出了一種自適應速度更新公式,用來控制個體最優(yōu)和全局最優(yōu)對粒子速度的影響度.前期個體最優(yōu)影響度更大,后期全局最優(yōu)影響度逐漸變大,以此達到全局搜索和局部開發(fā)共同優(yōu)化的效果.給出粒子速度更新公式見公式(4).

(4)

其中vid(t+1)為更新后的粒子速度;ω為正態(tài)分布衰減慣性權重;pbest(t)是粒子在第t代所得的最優(yōu)位置信息;gbest(t)是種群在第t代所得的最優(yōu)位置信息;t/tmax為當前迭代次數與最大迭代次數的比值;xid(t)為第t代粒子的位置信息;r1、r2和rand為[0,1]之間均勻分布的隨機數.

3.2 自適應變異優(yōu)化策略

由于柯西變異適合前期全局搜索,高斯變異適合后期局部搜索[14].根據算法迭代次數進行自適應選擇變異方式,前期選擇柯西變異,后期選擇高斯變異.如式(2)和式(3)中,粒子利用自身找到的最優(yōu)信息完成相應的變異優(yōu)化.這樣的優(yōu)化方式可以結合式(4)中的局部和全局最優(yōu)的影響度,前期讓全局最優(yōu)的影響度最大化,使得算法前期能很好的拓展搜索范圍,尋得更多更優(yōu)的可行解;后期讓局部最優(yōu)的影響度最大化,大大提升算法的收斂速度與收斂精度.

3.3 算法流程

將新的速度更新公式和自適應變異優(yōu)化應用于粒子群優(yōu)化算法,得到本文的算法—自適應變異優(yōu)化粒子群算法(ADVPSO).

算法流程如下:

Step 1.采用均勻分布隨機初始化種群,生成由N個D維的粒子組成的種群P;

Step 2.計算評價種群P中各個粒子的適應度值.根據優(yōu)劣更新個體歷史最優(yōu)解Pbest、全局歷史最優(yōu)解Gbest;

Step 3.計算算法迭代次數與最大迭代次數的比值結果,用式(1)更新慣性權重ω;

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

Step 5.根據算法迭代次數與最大迭代次數的比值判斷,比值如果小于或等于1/2,用式(2)優(yōu)化更新粒子位置xi;否則用式(3)優(yōu)化更新粒子的位置xi.

Step 6.計算評價種群P中各個粒子的適應度值.將其與個體歷史最優(yōu)Pbest和全局歷史最優(yōu)Gbest比較,更新最優(yōu)解.

Step 7.判斷算法是否滿足終止條件,若滿足,算法停止;否則返回執(zhí)行Step 3.

4 實驗對比與結果分析

4.1 參數設置與測試函數

為進一步驗證ADVPSO的性能和優(yōu)勢,實驗選取了LDWPSO(1998)[1],RLPSO(2015)[9],MSMPSO(2018)[5],SAPSO(2019)[7]和NDPSO(2020)[13]對比.LDWPSO是原始粒子群算法,其中引入了線性衰減慣性權重參數;與RLPSO和MSMPSO對比,是為了驗證自適應變異優(yōu)化策略對比其他智能方法策略的優(yōu)越性;SAPSO和NDPSO是近幾年提出的新型改進PSO算法.為了比較的公平性,實驗設置在同一硬件環(huán)境下,6個算法的參數設置如下:種群大小N為30;維數D為500維;迭代優(yōu)化次數為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所示.其中測試函數的定義域為粒子的每一維度的數值取值范圍,最優(yōu)值為理論上對應測試函數的最優(yōu)解,而算法的目的就是要求得此最優(yōu)值.

4.2 實驗結果與分析

將6個算法根據以上要求設定初始值,運行20次后取平均最優(yōu)值進行比較,結果如表2所示.加粗值表示各算法中最優(yōu)值.第1組測試函數f1-f4是較為簡單的單峰測試函數.從表2結果來看,由于算法初始設定D=500維,而LDWPSO、RLPSO、MSMPSO、SAPSO 由于高維度的復雜性,幾乎不能找到單峰函數的最優(yōu)解,并且過早的陷入局部最優(yōu).ADVPSO在f1和f2上的收斂精度是最高的.除了f3和f4,ADVPSO解的平均最優(yōu)值都遠遠小于其他算法.而f3是單峰測試函數中較為復雜的病態(tài)測試函數,故而大部分算法在此函數上性能表現較差,但ADVPSO的解的精度仍要高于其他算法.在f4函數中,由于其特殊的階梯形狀,使得算法容易陷入局部最優(yōu).ADVPSO是根據迭代次數分別在前后期進行柯西變異,高斯變異,雖然可以跳出部分階梯,但仍會陷入局部最優(yōu),而其他算法幾乎無法跳出局部最優(yōu),所以盡管精度都不高,但ADVPSO仍然有較強的性能.

第2組測試函數f5-f8是較為復雜的多峰測試函數.這些測試函數往往有多個局部極小值,且分布位置特殊,極其容易引導算法陷入局部極小值.ADVPSO算法在多峰測試函數中表現良好,在f6-f7中,ADVPSO都取得了最優(yōu)解0.在f5和f8中,ADVPSO取得的解精度也遠遠高于其他算法,因為f8具有很深且距離最優(yōu)解較遠的局部極小值,相比其他算法,ADVPSO的正態(tài)分布衰減權重策略能擴大算法前期的全局搜索范圍,后期也有較好的局部搜索能力,很好的平衡了局部與全局搜索.

圖3 各算法在f1-f8上的收斂曲線Fig.3 Convergence curves of each algorithm on f1-f8

從圖3中可以看出,ADVPSO的收斂性能遠遠優(yōu)于LDWPSO、RLPSO、MSMPSO、SAPSO、NDPSO得益于ADVPSO算法的自適應變異優(yōu)化策略.圖3中(a,e,f,g,h)有一個明顯的曲線轉折點,當迭代次數為1000次時(即最大迭代次數的一半),解的精度大幅度提升.自適應變異優(yōu)化策略依靠局部和全局尋優(yōu)的影響度,圖2中可知柯西分布使粒子擁有較寬的取值范圍,意味著對應的柯西變異能幫助擴大粒子搜索的解空間范圍. 經過柯西變異的粒子能夠搜索到更多更優(yōu)的可行解,由此可得知柯西變異適合前期的全局搜索.而高斯分布在y軸上具有更深的取值范圍,經過高斯變異的粒子可以提升算法的收斂精度,可以得知高斯變異適合后期的局部搜索.當算法前期陷入局部最優(yōu)時利用正態(tài)分布慣性權重衰減策略的前期粒子收斂步長較大的特性,結合柯西變異拓展解空間,讓粒子有更多的可行解進行搜索,及時跳出局部最優(yōu),后期利用正態(tài)分布慣性權重衰減策略后期粒子步長較小的特性,結合高斯變異加強局部搜索能力,提高解的精度.

實驗分析后,ADVPSO算法性能優(yōu)于其他改進PSO算法,證明了自適應變異優(yōu)化策略的有效性.

5 算法在新冠肺炎疫情傳播預測中的應用

在全世界抗擊新冠肺炎的過程中,涌現出大量對新冠肺炎疫情傳播的研究.國內高校及科研院所利用模型對新冠肺炎疫情傳播進行預測分析,其中張琳[17]采用了次指數增長方式擬合了早期國內新冠肺炎疫情爆發(fā)的情況,并在擬合好的次指數增長模型基礎上,預測疫情當前階段的發(fā)展情況.盛華雄[18]對武漢封城前后的新冠肺炎疫情傳播進行建模分析,采用經典的SIR模型和差分遞推方法預測疫情.以此為例,本文爬取中華人民共和國國家衛(wèi)生健康委員會疫情通報中的每日新確診人數數據(1)http://www.nhc.gov.cn/xcs/yqtb/list_gzbd.shtml,使用神經網絡進行預測分析.其中神經網絡中的各個權重參數(初始權值和閾值)由本文提出的ADVPSO算法進行優(yōu)化.

將2020年3月14日-6月21日共100天的每日新確診人數進行數據與處理,處理結果如圖4所示.從圖中可以看出疫情爆發(fā)前期,每日新確診人數居高不下,后期即使減少也偶爾有人數爆發(fā),由于政府的有效控制以及人口流動等諸多未知因素,新確診人數呈現非線性、非平穩(wěn)和非高斯分布特性,因此數據的擬合存在困難且預測每日確診人數準確率較低.如果采用普通的神經網絡,則需要前期不斷調試網絡節(jié)點中的初始權值及閾值,這會花費大量的人力時間成本.本文因此采用改進的粒子群算法對神經網絡中的權重參數及隱含層節(jié)點數進行迭代優(yōu)化,使模型能更準確的預測,提高模型準確率.

實驗參數設置為:模型獨立預測次數為20次,分析所得數據后,將訓練集與測試集按2:1的比例進行數據分割.訓練集為2020年3月14日-5月16日,共64天的新確診人數數據,測試集為2020年5月17日-6月14日,共36天的新確診人數數據,模型輸入層節(jié)點數為3,隱含層節(jié)點數為4,輸出層節(jié)點數為1,其中粒子群優(yōu)化權重參數的參數為:迭代次數為500次c1=c2=2;ωmax為0.9,ωmin為0.4.

圖4 預處理后的新確診人數Fig.4 Number of newly diagnosed patients after pretreatment

實驗結果如圖5所示,在進化初期,曲線上升速度快,說明神經網絡具有較快的收斂速度,能有效的減弱常規(guī)進化算法的早熟收斂、易陷入局部最優(yōu)解的現象.算法適應度值隨著次數的增加而逼近最優(yōu)解,平均適應度值最佳為0.9546.

圖5 適應度值變化曲線Fig.5 Fitness curve

圖6 用ADVPSO預測新確診人數曲線與實際新確診 人數曲線比較圖Fig.6 Comparison between predicted and actual newly diagnosed cases

使用ADVPSO算法優(yōu)化的神經網絡預測模型在訓練后,預測2020年5月17日-2020年6月21日總計36天的新確診人數,其中實際新確診人數為實線,預測新確診人數為虛線,如圖6所示.

從圖6中可以看出,使用ADVPSO算法優(yōu)化的神經網絡預測模型在訓練后,預測新確診人數與實際新確診人數基本相同,由此可見本文使用的ADVPSO優(yōu)化神經網絡具有良好的預測新冠肺炎新確診人數的能力,通過對神經網絡的權值和閾值進行調整優(yōu)化,使得算法適應度值不斷逼近最優(yōu)解,與此同時,神經網絡預測模型的預測性能隨著適應度值的逼近也得到提升.

為了方便描述ADVPSO算法優(yōu)化神經網絡的優(yōu)勢,采用傳統(tǒng)粒子群算法與ADVPSO進行實驗比較,通過比較適應度值、誤差(訓練誤差即訓練集結果與元數據集的誤差,預測誤差為模型訓練完畢后新預測的結果與元數據集的誤差) 和所獲得的節(jié)點連接數,完成性能比較,實驗結果如表3所示,加粗值為比較后的最優(yōu)值.

表3 兩種算法實驗結果比較Table 3 Comparison of experimental results of two algorithms

6 結 語

本文提出了一種自適應變異優(yōu)化粒子群算法,以算法運行進度作為參考,將整個尋優(yōu)過程分為兩個階段.在此基礎上,采用高斯分布慣性權重衰減策略動態(tài)更新ω,在不同階段引導粒子的搜索行為.當粒子尋找到自身的最優(yōu)解,便利用個體最優(yōu)信息以及自適應變異機制優(yōu)化粒子,實現了算法的高效搜索及計算資源的合理利用.實驗結果表明ADVPSO具有良好的綜合性能,在單峰及高峰函數中都表現出較好的魯棒性.結合2020年新冠疫情爆發(fā)情況,本文將該算法應用至神經網絡來建立預測模型,用ADVPSO算法優(yōu)化神經網絡權重參數,提高預測模型準確率.為驗證ADVPSO算法的優(yōu)勢,將其與傳統(tǒng)PSO算法優(yōu)化的模型進行比較,ADVPSO仍具有較好的魯棒性和實用性.

其中,ADVPSO對尋優(yōu)過程的自適應劃分并非最優(yōu)劃分方式.前期的全局搜索和后期的局部搜索對整個尋優(yōu)過程的影響度還有待分析.這些研究將在后續(xù)工作中進一步解決.