混合策略改進的粒子群算法

朱茂桃,劉 歡,吳佘胤,商高高

(江蘇大學 汽車與交通工程學院, 江蘇 鎮(zhèn)江 212013)

0 引言

粒子群算法(particle swarm optimization,PSO)是Kennedy等[1]在1995年提出的,因其結(jié)構(gòu)簡單,參數(shù)少且易于實現(xiàn),受到眾多學者的研究,并被廣泛運用于交通、物流、特征選擇等多個領(lǐng)域[2-3]。但粒子群算法本身也存在收斂精度低、速度慢、易早熟等缺點。

目前,眾多學者提出了不同策略來改進PSO算法。錢曉宇等[4]提出基于局部搜索的反向?qū)W習競爭粒子群優(yōu)化算法,將初始種群隨機分成四類,將類中粒子按照適應值大小進行排序并執(zhí)行相應的搜索策略,豐富了種群的多樣性,在算法后期各粒子相互競爭,增強了粒子跳出局部最優(yōu)的能力,在高維測試中也表現(xiàn)出較好的性能,但所需迭代的次數(shù)較多。李國森等[5]提出基于鄰域驅(qū)動的粒子群算法,引入鄰域驅(qū)動策略將粒子劃分到不同的鄰域中,通過鄰域間的信息交流,自適應更新粒子的位置,較好地平衡了全局搜索能力與局部勘探的能力,但沒有驗證算法在高維度上的性能。陳曦等[6]引入萊維飛行和黃金正弦公式對粒子的速度和位置進行更新,增大了粒子的搜索范圍,在一定程度上提升了算法的收斂速度和精度,但跳出局部最優(yōu)能力仍有提高的空間。劉清等[7]在線性遞減慣重粒子群算法的基礎(chǔ)上,將目標函數(shù)的梯度信息以擾動的形式添加到速度更新公式中,粒子進行迭代時隨機選擇速度更新方式,在不影響收斂精度的同時提高了算法的速率,但無法收斂到最優(yōu)解。于海波等[8]提出帶偏向性輪盤賭的多算子協(xié)同優(yōu)化算法,根據(jù)輪盤賭策略對種群執(zhí)行不同的搜索機制,將每次迭代后的信息進行交流匯總并對全局最優(yōu)施加高斯變異,雖然增強了算法的收斂性能,但在求解多極值問題時效果欠佳。

為進一步提升PSO算法的性能,本文中提出了一種改進的粒子群算法。將精英反向?qū)W習策略[9]與Circle映射[10]引入到種群初始化,提升種群質(zhì)量同時擴大搜索范圍;通過改變粒子速度更新公式,更好地平衡PSO算法的全局探索與局部勘探能力;結(jié)合基于自適應t分布的變異策略,進一步增強了全局探索和跳出局部極值能力。通過15個測試函數(shù)表明,改進的PSO算法在高維和低維函數(shù)上具有很強的尋優(yōu)能力與穩(wěn)定性。

1 相關(guān)算法的介紹

1.1 粒子群算法

粒子群算法是一種基于群體智能的優(yōu)化算法[11],最初起源于對魚群和鳥群等自然現(xiàn)象的模擬。粒子在搜索過程中,通過相互間的信息交流不斷改變自身的速度與位置,最終聚集到最優(yōu)解附近。粒子速度更新公式如式(1)所示,位置更新如式(2)所示。

(2)

1.2 黑寡婦優(yōu)化算法(BWOA)

蜘蛛在網(wǎng)中的運動模型有線性與螺旋2種,如圖1所示。表達式見式(3),Xi(t+1)為更新后的蜘蛛位置,Xbest為當前最好的蜘蛛位置,m為[0.4,0.9]的隨機數(shù),β為[0,1]的隨機數(shù),Xr1(t)為隨機選擇的第r1個蜘蛛,Xi(t)為當前蜘蛛的位置。

圖1 線性(linear movement)與螺旋(spiral movement)運動

(3)

定義信息素為

(4)

式中: fitnessmax與fitnessmin是最好與最差的適應值;fitness(i)是第i個蜘蛛的適應值。信息素低的蜘蛛會被替換:

(5)

式中:Xi(t)為信息素低的蜘蛛的位置;r1、r2為1到種群數(shù)量N之間隨機的2個不相等的數(shù);σ為二進制數(shù){0,1}。

1.3 反向?qū)W習

受機器學習中反向?qū)W習概念的啟發(fā),Tizhoosh[13]于2005年提出反向?qū)W習算法。精英反向?qū)W習算法[14]的核心思想為:在種群進行搜索時,同時搜索當前解與其動態(tài)反向解,并將較好的解保留到下一代。

反向解的定義:設(shè)X=(x1,x2,…,xD)為D維空間上的一點,xi∈[li,ui],則其反向解為

(6)

動態(tài)反向解的定義:設(shè)X=(x1,x2,…,xD)為D維空間上的一點,則其動態(tài)反向解為

(7)

式中:xi∈[li,ui],k∈(0,1)。

2 本文改進的算法

2.1 融合Circle映射與精英反向?qū)W習的種群初始化

混沌映射因其具有遍歷性、規(guī)律性等特點[14],常被用于種群的初始化中,但群數(shù)量較低時,無法覆蓋到較好的點,使得算法的搜索效率降低。因此,本文將精英反向?qū)W習策略融入到混沌映射中,充分利用混沌映射遍歷性的特性,在初始化種群時,同時搜索混沌映射解與其動態(tài)反向解,進一步擴大算法的搜索范圍,選擇較優(yōu)的解作為初始種群,避免盲目性,提升初始種群的質(zhì)量。引入Circle映射,如式(8)所示。

式中:xi+1, j為第i+1個粒子的第j維上的混沌序列值;xi, j為第i個粒子在第j維上的序列值。

使用融合Circle映射與精英反向?qū)W習策略,Circle映射對數(shù)量為20的種群分別在100維及200維上進行初始化,在Sphere函數(shù)上進行30次測試,并設(shè)置最大迭代次數(shù)為100。實驗統(tǒng)計結(jié)果見表1,收斂曲線如圖2所示,結(jié)合圖表可以看出使用融合Circle映射與精英反向?qū)W習策略進行種群初始化的PSO收斂速度最快,且精度最高,這是因為引入了精英反向?qū)W習的Circle映射使得種群在2個空間上同時進行搜索,可以擴大種群的搜索范圍,結(jié)合精英淘汰制提升了初始化種群的質(zhì)量,從而提升算法的搜索效率。

表1 Sphere函數(shù)測試結(jié)果

圖2 不同策略初始化種群時Sphere收斂曲線(30D)

種群初始化的步驟如下。

步驟1：隨機初始化第一個粒子混沌序列值x1, j,j=1,2,…,D,D為種群的維數(shù)。

步驟2：依次計算每個粒子的序列值,如式(8)。

步驟3：生成種群動態(tài)反向解,如式(7)。

步驟4：計算粒子的初始化位置,如式(9),其中,Xlj、Xuj分別為粒子在第j維的上下界。

步驟5：選取適應度值較好的粒子作為初始化種群。

Xi, j=Xlj+(Xuj-Xlj)×xi, j

(9)

2.2 改進慣性權(quán)重與學習因子

慣性權(quán)重可以影響粒子群算法的全局搜索能力與局部勘探能力,較大時利于全局搜索,此時種群的搜索范圍擴大,較小時利于局部勘探,此時粒子在當前點附近進行精細搜尋,算法跳出局部極值的能力增強。提出一種非線性遞減的慣性權(quán)重策略:

w=wmax-(wmax-wmin)·

(10)

式中:wmax、wmin分別為慣性權(quán)重最大值與最小值;k為當前迭代次數(shù);α、β為系數(shù)。

對學習因子改進的公式如式(11)所示。cmax、cmin分別為慣性權(quán)重最大值與最小值;k、K分別為當前迭代次數(shù)與最大迭代次數(shù);c1為個體學習因子,c2為社會學習因子,前期應使c1大一些,c2小一些,粒子多向自身進行學習,提升算法的全局探索能力,后期則剛好相反,多向全局歷史最優(yōu)學習,增強局部勘探能力。

(11)

選取Sphere和Griewank作為測試函數(shù)(見表2),設(shè)置種群數(shù)為50,最大迭代次數(shù)為100,在每個測試函數(shù)上進行30次測試,將本節(jié)改進算法(PSO-IW)與其他3種相關(guān)粒子群算法進行對比,收斂曲線如圖3所示,實驗統(tǒng)計結(jié)果如表3所示,參數(shù)設(shè)置如表4所示。

表2 基準測試函數(shù)

表3 Sphere與Griewank函數(shù)測試表

表4 相關(guān)粒子群參數(shù)設(shè)置

圖3 不同策略改進PSO時收斂曲線(30D)

4種算法均沒有找到最優(yōu)解,但PSO-IW在單峰和多峰上函數(shù)上都具有較快的收斂速度,同時可以注意到PSO-IW不僅在2個測試函數(shù)上均找到了最小精度的解,同時平均值、標準差均比其他3種算法少,這說明PSO-IW有著穩(wěn)定的尋優(yōu)能力。

2.3 引入蜘蛛移動策略

在標準PSO中,粒子通過不斷朝著自身歷史最優(yōu)與全局最優(yōu)的方向飛行來尋找最優(yōu)解,粒子在飛行過程中找到某個局部最優(yōu)點后難以擺脫,且可能會吸引其他粒子向其周圍聚集,使種群陷入局部最優(yōu),同時隨著其他粒子越來越接近全局最優(yōu)粒子,種群多樣性降低,收斂速度會大幅下降甚至發(fā)生進化停滯。

受BWOA位置更新公式的啟發(fā),對粒子的速度更新公式進行調(diào)整。并引入概率p∈[0,1],當p<0.3時,采用式(12)更新速度,否則采用式(13)更新粒子速度,其中m為[0.4,0.9]的隨機數(shù),β為[0,1]的隨機數(shù),(-1)σ為方向控制因子,σ為二進制數(shù){0,1}。

(12)

(13)

將改進速度更新公式后的PSO(PSO-IC)與標準PSO分別在單峰測試函數(shù)Sphere和多峰測試函數(shù)Griewank上進行30次測試,種群數(shù)設(shè)置為50,最大迭代次數(shù)為100,收斂曲線如圖4所示,實驗統(tǒng)計結(jié)果如表5所示?？梢钥闯?引入蜘蛛策略后的PSO算法具有更快的收斂速度,這是因為與標準PSO相比,改進后的PSO算法中粒子以線性與螺旋形2種方式來搜尋最優(yōu)解,擴大了算法的搜索范圍,豐富了種群多樣性,進而加快收斂速度,在2個測試函數(shù)上,引入蜘蛛策略后的PSO算法雖然都有過一段時間的停滯,但均跳出了局部最優(yōu)并找到了最優(yōu)解,這是通過引入方向控制因子,粒子以線形和螺旋形2種方式圍繞粒子個體最優(yōu)位置和全局最優(yōu)位置進行震蕩式來回搜索,不僅進一步豐富粒子飛行方向的多樣性,還極大地增強了粒子跳出局部最優(yōu)的能力。通過對比可以得出,無論在單峰還是多峰函數(shù)上,引入蜘蛛移動策略改進的PSO有著很強的適用性。

表5 Sphere與Griewank函數(shù)測試

圖4 蜘蛛移動策略改進PSO曲線(30D)

再結(jié)合改進的慣性權(quán)重與學習因子,更好地平衡PSO算法的全局搜索能力與局部勘探的能力。

2.4 自適應t變異策略

t分布又稱學生分布[17],自由度n為其唯一參數(shù),當n向正無窮發(fā)生變化時,其形態(tài)也由平緩變成陡峭。t(n=1)=c(0,1),t(n→∞)=N(0,1),其中N(0,1)為高斯分布,c(0,1)柯西分布。如圖5所示,將迭代次數(shù)作為t分布變異的自由度,可以很好地結(jié)合高斯變異與柯西變異的優(yōu)點,在算法迭代前期,曲線靠近柯西分布,可以增大算法的搜索空間,在迭代后期,曲線向高斯分布靠攏,此時有利于算法的局部開發(fā)。t變異公式為

圖5 高斯分布、t分布、柯西分布曲線

(14)

式中:η為步長參數(shù);T(t)為以算法的迭代次數(shù)t為自由度的t變異。

若η為一個常數(shù),并不利于算法的尋優(yōu),在PSO算法前中期,η應較大些,有利于跳出局部極值,算法后期,η應較小些,提高收斂能力。因此本文采用一種指數(shù)型的變異步長:

η=expt(-d/D)

(15)

式中:d為當前迭代步長;D為最大迭代步長。

為了進一步增強粒子跳出局部最優(yōu)的能力,提出基于t分布變異的策略。每次迭代完成后,在最優(yōu)解附近生成基于t變異的新解并對比取優(yōu),變異如式(14)所示。前期算法處于探索階段,此時變異的步長需要大一些,擴大粒子的搜索范圍,增強算法的多樣性,隨著迭代次數(shù)的增加,粒子已逐漸接近最優(yōu)解,算法進入局部搜索階段,此時需要較小的步長來保證算法在最優(yōu)解附近進行小范圍的精確搜索。

在粒子群算法中,粒子通過自身歷史最優(yōu)與全局粒子最優(yōu)不斷調(diào)整自身的飛行方向,自適應t變異使得算法在迭代前期會產(chǎn)生較大的擾動,算法逃離局部極值的能力得到增強,避免局部極值對粒子飛行軌跡的誤導,進一步提升算法的收斂速度,收斂后期,隨著擾動的減小,算法會在局部位置進行精確搜索,配合蜘蛛移動策略,使得算法有更好的局部尋優(yōu)能力。

2.5 改進粒子群算法(ICPSO-CT)的執(zhí)行步驟

具體執(zhí)行步驟如下。

步驟1：初始化種群,設(shè)置最大迭代次數(shù)、種群數(shù)量、問題維度,按式(7)—式(9)初始化種群的位置。

步驟2：計算各粒子的適應度值,找出個體最優(yōu)值pb與全局最優(yōu)值gb。

步驟3：生成概率p,若p<0.3,按式(12)更新粒子速度,否則,按式(13)更新粒子速度。

步驟4：根據(jù)式(2)計算粒子的位置,并對粒子做越界處理。

步驟5：執(zhí)行t變異策略,并對粒子做越界處理。

步驟6：判斷是否達到最大迭代次數(shù),若是,則進行步驟7,否則進行步驟2。

步驟7：結(jié)束程序,輸出算法找到的最優(yōu)結(jié)果。

3 函數(shù)測試及結(jié)果分析

3.1 測試函數(shù)

本文選取了15個基準測試函數(shù),包括9個單峰函數(shù)和6個多峰函數(shù)。單峰函數(shù)因其極值的唯一性,常用來測試算法的收斂速度。多峰函數(shù)具有多個局部最優(yōu),幾乎難以優(yōu)化,一般用來測試算法的收斂精度?；鶞蕼y試函數(shù)信息如表2所示。

3.2 實驗環(huán)境

測試環(huán)境如下:Windows 10操作系統(tǒng),處理器為Intel(R) Core(TM) i5-11400H @ 2.70 GHz,在Matlab 2018a上進行測試實驗。

3.3 算法參數(shù)設(shè)置

為驗證所提出的改進算法(ICPSO-CT)的有效性,選取原始粒子群算法(PSO)、IPSO-CSC[15]、黑寡婦算法(BWO)[18]進行對比。為避免實驗的隨機性,設(shè)置各個算法的種群數(shù)為50,最大迭代次數(shù)為100次,在每個測試函數(shù)上獨立運行30次,記錄各自的平均值、標準差及最優(yōu)值。算法參數(shù)設(shè)置如表6所示。

表6 算法參數(shù)設(shè)置

3.4 單峰函數(shù)測試

4種算法在單峰函數(shù)的測試結(jié)果如圖6所示,表7給出了實驗統(tǒng)計結(jié)果?？梢钥闯鲈?個單峰函數(shù)測試中,ICPSO-CT算法的收斂速度最快,且收斂速度明顯優(yōu)于IPSO-CSC,這是因為同Circle映射的種群初始化相比,融合了Circle映射與精英反向?qū)W習策略的種群初始化不但提升了種群質(zhì)量,而且更加豐富了種群多樣性,進而加快算法的收斂速度。在函數(shù)F1—F8上,ICPSO-CT與IPSO-CSC均找到了最優(yōu)解,但在函數(shù)F6、F8上ICPSO-CT算法的平均值和標準差均低于IPSO-CSC且均為0,而平均值與標準差可以反映算法的尋優(yōu)精度與穩(wěn)定性,說明通過引入蜘蛛移動策略,不僅加快了算法的收斂速度,同時還增大了粒子的搜索范圍,避免了基本粒子算法存在的搜索盲區(qū),提升了算法的收斂精度。對于函數(shù)F9,4種算法均沒有找到最優(yōu)解, IPSO-CSC找到的最優(yōu)解精度最低且平均值最小,說明在函數(shù)F9上,IPSO-CSC擁有較好的普適性。但對于總體單峰函數(shù)測試效果而言, ICPSO-CT具有更強的適應性。

表7 單峰函數(shù)測試結(jié)果

圖6 單峰函數(shù)測試結(jié)果曲線(30D)

3.5 多峰函數(shù)測試

圖7給出了4種算法在多峰函數(shù)的收斂曲線,實驗統(tǒng)計結(jié)果如表8所示。可以看出ICPSO-CT算法明顯快于其他3種算法,進一步說明了融合了Circle映射與精英反向?qū)W習策略的有效性。在測試函數(shù)F10、F14、F15上,ICPSO-CT可以在較小的步長內(nèi)找到最優(yōu)值,證明算法在多峰函數(shù)上依然有良好的尋優(yōu)能力,這是因為通過引入蜘蛛移動策略改變了粒子的飛行方式,擴大了算法的搜索范圍,從而加快了算法收斂速度,而由于方向因子的存在,使得粒子在收斂后期圍繞著自身歷史最優(yōu)與全局歷史最優(yōu)進行震蕩式來回搜索,極大地提升了粒子跳出最優(yōu)的概率。在函數(shù)F14上,雖然ICPSO-CT存在短暫的停滯,但很快跳出并找到理論最優(yōu)解,說明算法有很強的收斂能力,證明算法擁有很強的跳出局部極值的能力,這是因為自適應t變異策略的存在,粒子的搜索范圍會得到進一步提升,當粒子陷入局部最優(yōu)時,仍然有一定幾率擺脫局部極值的束縛,再結(jié)合震蕩式來回搜索,算法跳出局部最優(yōu)能力得到極大提升。在函數(shù)F10上,只有ICPSO-CT找到了最優(yōu)解,這無疑再次證明了算法跳出局部最優(yōu)的能力。在函數(shù)F12和F15上,ICPSO-CT與IPSO-CSC均找到了理論最優(yōu)解,但IPSO-CSC的平均值與理論最優(yōu)解并不相等,而ICPSO-CT的最優(yōu)解與平均值相同,說明在多峰函數(shù)上算法依舊具有很強的穩(wěn)定性。

表8 多峰函數(shù)測試結(jié)果

3.6 高維函數(shù)測試

為進一步測試函數(shù)的收斂穩(wěn)定性,將ICPSO-CT與IPSO-CSC在100維的函數(shù)F1、F6、F13、F15進行實驗。圖8給出了收斂曲線,實驗統(tǒng)計結(jié)果如表9所示。在函數(shù)F1、F6、F15上,雖然ICPSO-CT與IPSO-CSC均找到了理論最優(yōu)解,ICPSO-CT的最優(yōu)解與平均值、方差均為0,說明在高維函數(shù)上ICPSO-CT依舊有穩(wěn)定的尋優(yōu)性能。在F13上,2種算法均沒有找到最優(yōu)解,且有相同的收斂精度,但ICPSO-CT算法所用的迭代步數(shù)較少,說明融合了Circle映射與精英反向?qū)W習策略在高維函數(shù)上依舊保持有效性。綜合以上圖表可以得出:在迭代步長相同時,ICPSO-CT的收斂精度小于其他3種算法,在收斂精度相同時,ICPSO-CT的收斂速度較快。說明ICPSO-CT較其他3種算法而言,在收斂速度、收斂精度和跳出局部最優(yōu)能力3個方面有較大優(yōu)勢。

表9 高維函數(shù)測試結(jié)果曲線(100D)

圖8 高維函數(shù)測試結(jié)果(100D)

4 結(jié)論

針對基本粒子群算法存在的缺陷,提出一種混合策略改進的粒子群算法。首先,通過融合Circle映射與精英反向?qū)W習策略進行種群初始化,提升種群的質(zhì)量,有利于加快算法的收斂速度;然后通過改變慣性權(quán)重w,學習因子c1、c2和粒子速度更新公式,更好地平衡ICPSO-CT全局搜索與局部勘探的能力;最后提出自適應t變異策略,提高了算法的尋優(yōu)精度與跳出局部最優(yōu)的能力。通過15個測試函數(shù)表明算法在不同維度的單峰函數(shù)、多峰函數(shù)上具有較好的收斂精度和良好的尋優(yōu)穩(wěn)定性。

通過實驗可以發(fā)現(xiàn),若將初始種群點全部設(shè)在邊界處,在單峰函數(shù)上算法的收斂速度和尋優(yōu)精度會得到進一步加強,這可能是與實際生活中大部分最優(yōu)解均在邊界處取得有關(guān)。