李子旭,吳凌宇,葛婉貞,趙新超

(北京郵電大學(xué) 理學(xué)院,北京 100876)

0 引言

粒子群算法(Particle Swarm Optimization,PSO)是1995年由Kennedy和Eberhart在文獻[1]中提出。它是一種以群體智能為基礎(chǔ)的隨機搜索算法。該算法以沒有質(zhì)量、沒有體積的粒子作為個體,模擬自然界鳥群搜索食物的行為方式,用以求解優(yōu)化問題。文獻[2-3]對算法進行了綜述:粒子群算法操作簡單、收斂能力較強,因此被廣泛應(yīng)用于優(yōu)化不同領(lǐng)域的優(yōu)化問題,但是粒子群算法仍有后期多樣性差和易于陷入局部最優(yōu)等不足。因此,近年來粒子群算法的改進與發(fā)展受到了許多領(lǐng)域相關(guān)學(xué)者的關(guān)注。粒子群算法的改進策略主要有兩類:一種是將粒子群算法與其他算法相結(jié)合,構(gòu)成新的融合算法。文獻[4]將差分進化算法與粒子群算法結(jié)合起來,在粒子群優(yōu)化算法中加入了差分變異策略,有效提高了種群的多樣性和算法的全局收斂能力。文獻[5]將量子粒子群算法和人工蜂群算法相結(jié)合識別模型參數(shù),在有噪聲數(shù)據(jù)的處理上,該算法表現(xiàn)良好。文獻[6]將人類學(xué)習(xí)優(yōu)化算法和粒子群算法相結(jié)合,增強了粒子的學(xué)習(xí)能力,提高了搜索效率。另一種則是對粒子群算法更新策略進行改進,文獻[7-9]采用混沌方法對粒子群算法進行了改進,提高了算法的優(yōu)化能力。文獻[10-11]則是通過不同擾動策略提升種群多樣性以增強算法性能。文獻[12]是通過改變粒子對最優(yōu)位置的學(xué)習(xí)策略來提升算法。文獻[13-19]在粒子迭代過程中引入新的參數(shù)因子,以此調(diào)整粒子的更新方式,從而在一定程度上改善算法早熟現(xiàn)象?？傮w而言,文獻[4-19]都是在粒子更新飛行速度和位置時盡可能多地利用當(dāng)代的信息,但是在此過程中卻忽略了對于自身有效歷史信息的學(xué)習(xí)。

除此之外,粒子群算法的研究成果還有很多,但是對于粒子群算法學(xué)習(xí)自身歷史信息的相關(guān)研究卻很少,使得粒子群在搜索過程中的很多有用信息得不到有效利用。因此,本文提出了一種基于搜索歷史信息的粒子群算法(History Information PSO,HIPSO),該算法在原有速度更新公式的基礎(chǔ)上,利用學(xué)習(xí)因子對上代飛行速度進行協(xié)同學(xué)習(xí),更加充分地挖掘利用粒子群體的當(dāng)前和歷史搜索信息,有效拓展了粒子飛行的路徑多樣性,很好地提升了算法的搜索能力。

1 粒子群算法

粒子群算法是啟發(fā)于鳥群協(xié)作覓食行為的一種元啟發(fā)式算法,是一種基于群體協(xié)作和信息共享的隨機搜索方法。在算法搜索過程中,優(yōu)化問題的每一個解被看作搜索空間中一個帶有速度的粒子,粒子通過速度向量和自身學(xué)習(xí)能力的強弱來決定它們飛行的方向和距離。因此,粒子速度和位置向量的更新運算是算法生成新解的主要方式。經(jīng)典粒子群算法具體步驟如下:

第一步,初始化粒子群,包括種群規(guī)模N,隨機初始位置xi和初始速度vi,其中xi=(xi1,xi2,…,xiD),vi=(vi1,vi2,…,viD),i=1,2,…,N,D表示問題的維數(shù)。

第二步,計算每個粒子個體的適應(yīng)度值,更新個體極值點pi和全局極值點g,其中pi=(pi1,pi2,…,piD),g=(g1,g2,…,gD)。

第三步,根據(jù)式(1)和(2)更新每個粒子的速度和位置向量:

式中:ω為慣性權(quán)重;c1、c2是兩個正的加速系數(shù),分別為自我學(xué)習(xí)因子和社會學(xué)習(xí)因子;r1、r2是分布在 [0,1]內(nèi)的均勻隨機數(shù);表示在第t+1次迭代中第i個粒子在第d維上的速度和位置分量。

2 基于搜索歷史信息的粒子群算法

2.1 思想啟蒙模型

在市場經(jīng)濟領(lǐng)域中有一個蛛網(wǎng)經(jīng)濟模型,該模型是通過上一階段的價格來調(diào)控下一階段的產(chǎn)量,即通過上一階段的經(jīng)驗對下一階段的決策進行指導(dǎo)[20]。蛛網(wǎng)經(jīng)濟模型的基本假定如下:商品的本期產(chǎn)量Qts取決于前一期的價格Pt-1,商品本期的需求量Qtd取決于本期的價格Pt。蛛網(wǎng)經(jīng)濟模型可用方程組表示:

其中,α、β、δ和γ均為常數(shù)且大于零[21]。

蛛網(wǎng)模型利用本期產(chǎn)量和需求量建立了前一期價格與本期價格之間的聯(lián)系,用前一期經(jīng)驗指導(dǎo)本期的相關(guān)行為。受此機制啟發(fā),本文使粒子群中每個粒子個體的速度除了正常向當(dāng)代群體的精英粒子學(xué)習(xí),還向上一代粒子學(xué)習(xí),進而對新個體的搜索進行協(xié)同的調(diào)整和指導(dǎo),以此加強粒子群體對歷史信息的有效再利用,從而使得粒子的飛行路徑更加多樣化和差異化,最終提升算法的性能。

2.2 HIPSO算法

HIPSO算法沿用經(jīng)典PSO算法的架構(gòu),對粒子速度歷史信息學(xué)習(xí)的機制通過與當(dāng)前飛行速度的協(xié)作而實現(xiàn),即在式(1)與式(2)之間加入

其中,λ為學(xué)習(xí)因子,用以調(diào)整對粒子速度歷史信息的利用強度。

本文提出的HIPSO算法共有3種策略:

1)靜態(tài)學(xué)習(xí)因子的HIPSO算法。靜態(tài)學(xué)習(xí)因子是指算法在迭代過程中,學(xué)習(xí)因子是一個常數(shù),不隨迭代而改變。如圖1所示,經(jīng)典PSO算法中新粒子在三個平行四邊形區(qū)域A(只向pt-xt方向?qū)W習(xí))、區(qū)域B(同時向pt-xt與g-xt方向?qū)W習(xí))、區(qū)域C(只向g-xt方向?qū)W習(xí))中由幾種啟發(fā)式信息協(xié)同生成,而HIPSO算法生成的新粒子則是在區(qū)域D中由幾種啟發(fā)式信息協(xié)同生成,搜索區(qū)域得到了擴充。

圖1 PSO與HIPSO搜索區(qū)域區(qū)別示意圖Fig.1 Thesearch area difference diagram of PSO and HIPSO

通過圖1可以看出,通過學(xué)習(xí)因子的動態(tài)調(diào)節(jié),可動態(tài)調(diào)整新粒子可能的飛行方向與原粒子飛行方向之間的跨度,以此擴大粒子的飛行范圍,進而增強算法搜索尋優(yōu)能力。

2)隨機學(xué)習(xí)因子的HIPSO算法。針對靜態(tài)學(xué)習(xí)因子參數(shù)不易確定的問題,進一步提出隨機學(xué)習(xí)因子HIPSO算法。該算法在每一代的迭代過程中,每一個粒子對應(yīng)的學(xué)習(xí)因子在給定因子集合中隨機選取。通過學(xué)習(xí)因子的隨機選擇,使得粒子的飛行軌跡進一步多樣化,增強了種群總體搜索區(qū)域的多樣性。λ的選取方式為

其中,α為學(xué)習(xí)因子集合,length(α)為集合長度,i為1到length(α)之間的隨機整數(shù),αi為集合中第i個學(xué)習(xí)因子。

3)最優(yōu)學(xué)習(xí)因子的HIPSO算法。隨機選擇學(xué)習(xí)因子一方面可以多樣化飛行軌跡,增強尋優(yōu)能力;另一方面,隨機選擇的學(xué)習(xí)因子會難以避免的使粒子向較差的方向飛行,從而浪費算法的計算資源。因此,需要指導(dǎo)每代種群中每個粒子在因子集合中選取使得上一代中生成新個體最優(yōu)的學(xué)習(xí)因子,以此對粒子飛行方向進行指導(dǎo),尤其是加強精英粒子的經(jīng)驗指導(dǎo)。λ的選取方式為

其中,α為學(xué)習(xí)因子構(gòu)成的集合,λ是因子集合所有學(xué)習(xí)因子中對應(yīng)的使個體適應(yīng)度值f(x)最優(yōu)的學(xué)習(xí)因子。

2.3 越界處理

本文采用的越界處理方式為,若子代個體xnew飛出下界,則xnew取xmax與2xmin-xnew之間的最小值;若子代個體xnew飛出上界,則xnew取xmin與2xmax-xnew之間的最大值,即

其中,xnew為生成的新個體,xmin為粒子下界,xmax為粒子上界。

2.4 算法流程

算法具體步驟如下:

第一步,初始化粒子群規(guī)模N,初始位置xi和初始速度vi。

第二步,計算每個粒子個體的適應(yīng)度值,并更新個體極值pi和全局極值g。

第三步,選取學(xué)習(xí)因子。其中靜態(tài)學(xué)習(xí)因子策略賦予定值,隨機學(xué)習(xí)因子策略讓個體在每次迭代時根據(jù)式(5)(6)選取,最優(yōu)學(xué)習(xí)因子策略則是根據(jù)式(7)選取。

第四步,利用式(1)(2)(4)更新粒子速度和位置。

第五步,進行越界檢測,如果越界,通過式(8)進行越界處理。

第六步,判定是否符合終止條件,如果是,輸出結(jié)果,如果否,返回第二步,重復(fù)此循環(huán)。

算法整體架構(gòu)較為簡單,靜態(tài)與隨機學(xué)習(xí)因子策略的加入并沒有增加粒子群算法的算法復(fù)雜度。而最優(yōu)學(xué)習(xí)策略在每次迭代中加入了一次比較排序,該策略的算法復(fù)雜度為O(nlogn)。

算法流程圖見圖2。

圖2 HIPSO的算法流程圖Fig.2 Flow chart of HIPSO

3 學(xué)習(xí)因子的有效性分析

為驗證本文所提思想與算法的有效性,用靜態(tài)學(xué)習(xí)因子粒子群算法HIPSO(λ分別取0.75、0.5以及0.25),隨機學(xué)習(xí)因子算法HIPSOR、最優(yōu)學(xué)習(xí)因子算法HIPSOB與經(jīng)典PSO算法進行對比分析。

3.1 測試函數(shù)與參數(shù)設(shè)置

在CEC2014函數(shù)測試集的各類函數(shù)中選取代表性算例構(gòu)成本文的函數(shù)測試集[22],所選函數(shù)如下:單峰函數(shù)f1、f2、f3,多峰函數(shù)f4、f5、f12、f15,混合函數(shù)f17、f20,組合函數(shù)f23、f26、f28。為方便起見,本文把這些函數(shù)重新標(biāo)記為F1～F12。函數(shù)簡單信息如表1所示,有關(guān)測試函數(shù)詳細信息請參看文獻[22]。

表1 函數(shù)測試集Tab.1 Benchmark functions

對比仿真試驗的參數(shù)設(shè)置如下:種群規(guī)模N=100,搜索空間維數(shù)D=50,慣性權(quán)重,加速系數(shù)c1=c2=0.5+ln 2,HIPSO的學(xué)習(xí)因子λ分別為0.75、0.5、0.25,HIPSOR與 HIPSOB的學(xué)習(xí)因子λ的集合為{0,0.25,0.5,0.75,1-10-6},最大評估次數(shù)是10 000D,算法獨立運行次數(shù)是30。

3.2 數(shù)值試驗對比

六種算法的數(shù)值統(tǒng)計結(jié)果如表2所示,統(tǒng)計結(jié)果包括30次獨立試驗最終結(jié)果的最優(yōu)值、平均值和標(biāo)準(zhǔn)差,最優(yōu)結(jié)果用加粗黑體表示。從表2的結(jié)果可以看出:

表2 6種算法數(shù)值結(jié)果統(tǒng)計Tab.2 Experimental results of six algorithms

1)HIPSOB在“最優(yōu)值”統(tǒng)計項上取得10個最優(yōu)結(jié)果,在“平均值”上統(tǒng)計項全部取得最優(yōu)結(jié)果;HIPSOR在這兩個統(tǒng)計項上分別為4個和2個。利用最優(yōu)學(xué)習(xí)因子的HIPSOB表現(xiàn)最好,利用隨機學(xué)習(xí)因子的HIPSOR表現(xiàn)次之,利用靜態(tài)學(xué)習(xí)因子的三種算法緊隨其后,從而說明動態(tài)利用歷史飛行信息對現(xiàn)有飛行方向進行調(diào)整具有很好的效果和較好的潛力。

2)三種靜態(tài)學(xué)習(xí)因子粒子群算法HIPSO(λ=0.75)、HIPSO(λ=0.5)、HIPSO(λ=0.25)較經(jīng)典PSO算法有明顯改善,且學(xué)習(xí)因子越大,對應(yīng)算法的綜合性能越好,從而說明粒子飛行歷史信息對粒子群算法的搜索方向改善具有明顯的效果。

3)加入學(xué)習(xí)因子后,對四種類型函數(shù)算法均有所改善,在單峰問題上最為明顯。需要說明的是,加入學(xué)習(xí)因子和利用歷史飛行信息并沒有引入任何有代價的額外運算。

綜上所述,HIPSOB算法表現(xiàn)最好,HIPSOR次之,三種靜態(tài)學(xué)習(xí)因子均比經(jīng)典PSO算法的結(jié)果更要好,說明粒子飛行歷史信息的開發(fā)利用對算法性能的改善是有益的,而且動態(tài)學(xué)習(xí)因子策略要比靜態(tài)學(xué)習(xí)因子策略更具優(yōu)勢,并且?guī)в袉l(fā)式指導(dǎo)性的動態(tài)選取策略要比隨機選取策略效果更顯著。

4 與其他經(jīng)典PSO算法的仿真對比試驗

為了進一步分析驗證算法性能,將兩種動態(tài)學(xué)習(xí)因子的PSO算法HIPSOR、HIPSOB與其他經(jīng)典PSO算法NmP3PSO[10]和CLPSO[12]進行數(shù)值仿真對比試驗,以此分析驗證與其他更有競爭力同類算法對比時的綜合性能。

4.1 測試函數(shù)與參數(shù)設(shè)置

測試函數(shù)及維度和HIPSOR、HIPSOB的算法參數(shù)與上一組試驗相同,而CLPSO、NmP3PSO算法參數(shù)設(shè)置均與原文相同。

4.2 數(shù)值試驗對比分析

四種算法的數(shù)值統(tǒng)計結(jié)果如表3所示,結(jié)果包含三十次獨立試驗最終結(jié)果的最優(yōu)值、平均值、標(biāo)準(zhǔn)差,最優(yōu)結(jié)果用黑體加粗標(biāo)示。從表3可以看出:

表3 4種算法數(shù)值結(jié)果統(tǒng)計Tab.3 Experimental results of four algorithms

1)在“最優(yōu)值”和“平均值”統(tǒng)計項上,HIPSOB表現(xiàn)最優(yōu),分別取得了10個和9個最優(yōu)結(jié)果。

2)在單峰、多峰和混合函數(shù)上HIPSOB綜合表現(xiàn)最優(yōu),但是在組合函數(shù)上CLPSO表現(xiàn)較為穩(wěn)定,原因可能是CLPSO綜合的學(xué)習(xí)方式可以獲得更多優(yōu)秀粒子個體有益的飛行信息。

綜合表3數(shù)據(jù)結(jié)果以及對比分析情況綜合可知HIPSOB算法具有最好的性能。

4.3 算法進化趨勢對比

為了考查四種算法的動態(tài)平均進化趨勢,本文選取單峰函數(shù)F1、多峰函數(shù)F6、混合函數(shù)F8以及組合函數(shù)F11進行在線性能對比分析,對比結(jié)果如圖3所示。

圖3 算法收斂趨勢對比圖Fig.3 Evolutionary comparison of convergence trends

通過圖3收斂曲線趨勢可以看出:對單峰函數(shù)F1,HIPSOB算法不僅收斂速度最快,而且收斂精度明顯高于其他算法,HIPSOR也取得了不錯的結(jié)果;對于多峰函數(shù)F6,HIPSOB算法收斂速度依舊是最快,收斂精度略高于其他算法;對于混合函數(shù)F8,HIPSOB算法收斂速度最快,并且收斂精度較其他算法高出了2～4個數(shù)量級,HIPSOR僅次于HIPSOB;對于組合函數(shù)F11,HIPSOB算法的收斂速度最快,但是陷入了局部陷阱,在收斂精度上略遜于CLPSO。總體而言,在四類函數(shù)中,本文提出的HIPSOB的收斂速度均為最快,而收斂精度綜合表現(xiàn)最好,因此在算法整體收斂趨勢統(tǒng)計對比試驗中,HIPSOB的綜合表現(xiàn)最佳,從而進一步說明本文提出的基于粒子飛行歷史信息再利用機制的有效性。

5 結(jié)論

為了充分利用群體飛行的歷史速度信息,在經(jīng)典PSO算法的基礎(chǔ)上,本文引入了一種對歷史速度信息的學(xué)習(xí)機制,從而提出基于搜索歷史速度信息的粒子群算法:靜態(tài)學(xué)習(xí)因子HIPSO算法和動態(tài)學(xué)習(xí)因子HIPSO算法(HIPSOR、HIPSOB)。HIPSO算法通過該學(xué)習(xí)機制,在一定程度上改善了算法的早熟現(xiàn)象,靜態(tài)選取計算量小,但同時也限制了搜索方向。因此,在此基礎(chǔ)上提出了HIPSOR、HIPSOB,進一步提升了算法性能。以CEC2014測試函數(shù)集進行數(shù)值仿真對比試驗,驗證了粒子飛行速度信息再利用機制是有效的;然后,將 HIPSOR、HIPSOB與經(jīng)典 PSO算法變種NmP3PSO、CLPSO進行數(shù)值對比試驗與進化趨勢對比分析,結(jié)果表明本文所提出的最優(yōu)學(xué)習(xí)因子算法HIPSOB的收斂速度與收斂精度的綜合表現(xiàn)性能最佳。