帶隨機變異及感知因子的粒子群優(yōu)化算法

黃懿, 梁放馳, 范成禮, 宋占福

(1.空軍工程大學(xué) 基礎(chǔ)部, 陜西 西安 710051; 2.空軍工程大學(xué) 防空反導(dǎo)學(xué)院, 陜西 西安 710051)

粒子群優(yōu)化算法(PSO)是一種群體性智能搜索算法[1-3],由Kenney于1995年提出,并因?qū)崿F(xiàn)容易、精度高、收斂快等優(yōu)點成為國內(nèi)外研究的熱點。但PSO算法在求解高維多峰問題時容易出現(xiàn)“早熟”現(xiàn)象,不能完全保證求得全局最優(yōu)[4]。針對此問題,國內(nèi)外學(xué)者提出了許多改進策略[5-15],如調(diào)整參數(shù)、精英選擇和混合算法等,或在前人的基礎(chǔ)上增加優(yōu)化因子。文獻[7-9]通過動態(tài)和自適應(yīng)控制慣性權(quán)重提高算法的搜索和挖掘能力,但其搜索范圍不一定能夠覆蓋整個空間,依然存在出現(xiàn)局部最優(yōu)的情況。文獻[10]提出了一種無慣性的自適應(yīng)精英變異策略,加快了算法的收斂過程,擴大了種群搜索范圍,但在高維問題求解上還需進一步實驗驗證。文獻[11]根據(jù)個體與全局最優(yōu)粒子間的距離分別對慣性系數(shù)ω、學(xué)習(xí)因子c1和c2求導(dǎo),給出了3種參數(shù)的確定性變化方向,達到參數(shù)自適應(yīng)控制的目的,但對局部最優(yōu)分散在整個搜索空間,并且與全局最優(yōu)相距很遠(yuǎn)的復(fù)雜問題求解能力不強。文獻[12]在自適應(yīng)調(diào)整慣性權(quán)重的量子粒子群優(yōu)化算法基礎(chǔ)上,對粒子位置進行了周期性變異,提高了全局搜索精度,但全局判據(jù)僅作為判斷優(yōu)化結(jié)果全局性的依據(jù),不會擴大算法搜索范圍。文獻[13]為解決粒子種群多樣性和收斂性的矛盾,引入了動態(tài)劃分多種群重構(gòu)粒子作為引導(dǎo)因子,對執(zhí)行階段的最優(yōu)個體實施混合變異,對時變概率實施反向?qū)W習(xí)或鄰域擾動策略,提高算法的開發(fā)與勘探能力,但頻繁使用該策略反而會降低部分函數(shù)的求解精度。文獻[14]在前人基礎(chǔ)上,提出了一種自適應(yīng)局部搜索啟動策略,提高了算法的收斂速度和精度,但其全局搜索能力有待驗證。文獻[15-16]分別將混沌云和單純形與基本粒子群算法相結(jié)合,以提高算法的全局搜索能力,多用于多模態(tài)復(fù)雜問題求解,對目標(biāo)函數(shù)求解問題需要進一步驗證。文獻[17]提出粒子速度或位置小概率隨機變異與自適應(yīng)逃逸策略相結(jié)合,但求解高維多峰等復(fù)雜問題時,其收斂速度較慢,需要迭代2 000次以上,才能求出最優(yōu)值。針對多模態(tài)優(yōu)化問題,文獻[18]通過構(gòu)建集成代理輔助模型,解決了區(qū)間多模態(tài)粒子群優(yōu)化計算代價高昂問題,但對多目標(biāo)多模態(tài)的適用性仍需進一步驗證?？傊?以上算法的改進大多采取參數(shù)選擇或參數(shù)自適應(yīng)控制策略,或混合其他算法,針對高維復(fù)雜問題的求解能力略顯不足,不能從根本上克服“早熟”的固有弊端。

基于以上分析,根據(jù)粒子群在空間中的搜索和分布特點,通過增加隨機變異和感知因子,改進粒子群的速度和位置更新策略,提出帶隨機變異因子和感知因子的粒子群優(yōu)化算法(PSORMP),擴大粒子在空間中的搜索范圍,有效解決了粒子群因搜索范圍不足或粒子過于聚集而陷入局部最優(yōu)問題。通過典型函數(shù)測試、算法對比實驗、參數(shù)影響分析等仿真實驗,驗證了PSORMP算法具有很強的快速收斂、全局搜索與精確挖掘能力。

1 基本PSO算法

設(shè)一個D維空間中,由N個初始搜索粒子組成一個群落,則第k代第i個粒子的D維向量表示為

(1)

第k代第i個粒子的飛行速度為

(2)

截至k代,第i個粒子經(jīng)歷的最優(yōu)位置稱為個體最優(yōu),記為

(3)

截至k代,整個粒子群經(jīng)歷的最優(yōu)位置稱為全局最優(yōu),記為

(4)

由此,基本PSO算法粒子的速度和位置更新公式為

(5)

式中:c1和c2為學(xué)習(xí)因子;r1和r2為[0,1]范圍內(nèi)的隨機數(shù)。

針對慣性系數(shù)ω,采用非線性遞減權(quán)重策略

(6)

式中:f表示粒子實時的目標(biāo)函數(shù)值;favg和fmin分別表示當(dāng)前粒子群的平均值和最小目標(biāo)值[19]。

由基本PSO算法的迭代公式可以發(fā)現(xiàn),粒子的尋優(yōu)方向由粒子群的自身歷史最優(yōu)位置和全局最優(yōu)位置所決定,因此,如果全局最優(yōu)位置是解空間的局部最優(yōu)位置,就很容易導(dǎo)致粒子群陷入局部收斂。許多高維空間求解問題都是復(fù)雜多峰函數(shù),如果算法跳出局部最優(yōu)的能力不足,這些峰值很容易吸引粒子群發(fā)生“早熟”現(xiàn)象,算法的可靠性和穩(wěn)定性難以保證。

2 PSORMP算法

為了使算法更具跳出局部最優(yōu)能力,根據(jù)粒子群的運動特性,提出帶隨機變異及感知因子的PSO算法,改變粒子的速度和位置更新策略,以提高全局搜索與挖掘能力。

2.1 帶隨機變異因子的速度更新策略

為擴大粒子的搜索范圍,避免粒子群受初始種群的限制,在速度更新公式中增加一個基于粒子自身鄰域、個體最優(yōu)和全局最優(yōu)的隨機變異因子,以提高粒子的運動能力,更新的速度公式為

(9)

(10)

式中:r4為[-0.5,0.5]的隨機數(shù)(由函數(shù)測試得出,具體見本文3.3節(jié));xmax為最大可行變異區(qū)間,這里同自變量的取值范圍。

(11)

(12)

最后,進行負(fù)理想點映射,得映射點xR

xR=xC+α(xC-xF)

(13)

式中,α為負(fù)理想點映射系數(shù),一般取α=1.3～0.5遞減。

圖1 為負(fù)理想點時粒子運動過程

圖2 為負(fù)理想點時粒子運動過程

2.2 帶感知因子的位置更新策略

針對算法容易陷入局部最優(yōu)的不足,本文提出一種帶感知因子的位置更新修正策略,使種群粒子盡可能分散于整個搜索空間,提升全局搜索能力。其主要思想為:粒子自身虛擬感知與其他粒子之間的距離,粒子間的距離小于平均距離的粒子,該部分粒子自身觸發(fā)感知排斥,將自身與其他粒子的距離控制在平均距離之外,從而保持跳出局部搜索。如圖3所示,黃色點代表個體最優(yōu)粒子,紅色點代表全局最優(yōu)粒子,若粒子群出現(xiàn)圖3a)表示的情況,個體最優(yōu)附近粒子群數(shù)量比全局最優(yōu)數(shù)量多,且距離較近,容易使結(jié)果陷入局部最優(yōu)。此時,局部緊密粒子存在斥力,觸發(fā)感知排斥,而經(jīng)過感知因子調(diào)整后,粒子群空間分布如圖3b)所示,從而防止陷入局部最優(yōu)。

圖3 感知因子對粒子群修正示意圖

為更好地理解該策略,引入以下2個定義。

定義1各維度粒子間的距離定義為

(14)

定義2則各維度的平均距離定義為

(15)

(16)

為簡化計算過程和保證種群收斂,令慣性權(quán)重系數(shù)ω3的遞減策略與慣性權(quán)重系數(shù)ω1相同,采取非線性遞減的方式,以達到后期的局部挖掘能力。

2.3 PSORMP算法步驟

根據(jù)基本粒子群算法求解過程,結(jié)合帶隨機變異粒子的速度更新策略和帶感知因子的位置更新策略,PSORMP算法的尋優(yōu)步驟為

step1 輸入初始化PSORMP算法參數(shù),設(shè)置初始種群規(guī)模N,粒子維數(shù)D,最大迭代次數(shù)Tmax,學(xué)習(xí)因子c1,c2,粒子速度閾值vmin,vmax和粒子各維閾值xmin,xmax;

step2 計算并記錄粒子群的位置和速度;

step3 計算粒子的適應(yīng)度值;

step4.1 利用隨機變異粒子的速度更新策略進行速度更新;

step4.2 利用感知因子的位置更新策略進行位置更新;

step6 判斷是否滿足終止條件t=Tmax,若滿足,則轉(zhuǎn)至step7,若不滿足,則轉(zhuǎn)至step4;

3 實驗與結(jié)果分析

3.1 算法的選擇與比較

為驗證算法的有效性和優(yōu)越性,本文選取5種算法進行對比,分別是基本PSO算法和4個基于PSO算法的改進算法,即PSOPC[20]、RPSO[21]、NPSO[22]和RFRPSO[23],其中,①PSOPC算法:為避免生物群在信息共享時存在自私行為導(dǎo)致形成被動群體,從而無法獲得全局最優(yōu),提出在粒子群中加入一個被動群模型,提高算法粒子運動活力。②RPSO算法:排斥PSO算法利用在粒子間設(shè)置幾種排斥機制,使種群粒子從被認(rèn)為個體最佳的位置移開,從而促使粒子探索空間中的新區(qū)域,并在后期切換原有探索模式,達到跳出局部最優(yōu)的可能。③NPSO算法:負(fù)粒子優(yōu)化算法的優(yōu)化策略是在原有粒子群優(yōu)化算法的基礎(chǔ)上,采取將粒子遠(yuǎn)離個體和群體負(fù)理想解的理念,來達到尋優(yōu)目的。④RFRPSO算法:帶反向預(yù)測與斥力因子的PSO算法,其優(yōu)化策略為降低粒子在運動過程中的惰性,引入反向預(yù)測因子以改變粒子速度更新方式,為使粒子分散于搜索空間,引入帶斥力的位置修正策略。以上算法的速度更新公式如表1所示。

表1 算法速度更新公式比較

3.2 測試函數(shù)的選擇與參數(shù)設(shè)置

為驗證算法的穩(wěn)定性和可行性,本文通過求解7個具有代表性的標(biāo)準(zhǔn)基準(zhǔn)函數(shù)的最小值問題來驗證算法,主要包括Sphere、Quartic、Rosenbrock、Griewank、Ackley、Rastrigrin和Schwefel。其中,Sphere函數(shù)除了全局極小值外,還具有D(維度)個局部極小值,對高維粒子求解困難;Quartic函數(shù)是存在隨機干擾的單峰函數(shù),對算法驗證極具代表性;Rosenbrock函數(shù)的全局最優(yōu)位于一個狹窄的拋物線谷中,雖然山谷容易找到,但很難收斂到最小值,是很難求解極小值的典型二次函數(shù);Griewank函數(shù)具有很多局部極小值,可驗證算法跳出局部最優(yōu)能力;Ackley函數(shù)在二維形式中,呈現(xiàn)出外部平坦,中心下沉的一個深坑狀態(tài),并具有眾多的局部極小值,對容易產(chǎn)生“早熟”現(xiàn)象的算法求解帶來了很大困難;Rastrigrin函數(shù)為復(fù)雜多峰函數(shù),在求解過程中很容易陷入全局最優(yōu)附近的局部極小點;如圖4所示,Schwefel函數(shù)具有均勻隨機性,其局部最優(yōu)分散在整個搜索空間,并且與全局最優(yōu)相距很遠(yuǎn),欺騙性強,算法必須擁有很強的全局搜索能力才能得到全局最優(yōu)。實驗過程中測試函數(shù)的相關(guān)信息如表2所示。

圖4 Schwefel函數(shù)的二維圖像

表2 測試函數(shù)及參數(shù)設(shè)置

實驗過程中,設(shè)置初始粒子群規(guī)模N=200,最大迭代次數(shù)Tmax=1 000,慣性權(quán)重系數(shù)ωmax=0.9,ωmin=0.5,維數(shù)D=30,學(xué)習(xí)因子c1=c2=2,可接受誤差為0.1。實驗環(huán)境為:AMD Ryzen 7 4800H with Radeon Graphics 2.90 GHz,RAM 16.0GB,Windows10操作系統(tǒng),MATLAB2019a。比較算法的參數(shù)根據(jù)文獻[19-23]的最佳參數(shù)而定,如表3所示。

表3 對比算法的參數(shù)設(shè)置

3.3 測試結(jié)果及分析

將每個測試函數(shù)獨立運行100次,記錄每個算法的成功率(S,在規(guī)定的可接受誤差范圍內(nèi),成功求解的次數(shù)與總運行次數(shù)的比值)、平均最優(yōu)值(Bm,每種算法對每個測試函數(shù)獨立運行100次后得到的平均最優(yōu)值,此結(jié)果能衡量算法的穩(wěn)定性)、最終適應(yīng)值(Bf,表示每種算法對每個測試函數(shù)獨立運行100次后得到的最優(yōu)適應(yīng)值,此結(jié)果可以衡量算法的求解精度)、平均運行時間(Tm每個算法對測試函數(shù)獨立運行100次的平均運行時間)和Adjusted p-value(P,表示本文算法與其他算法對比的顯著性差異水平),如表4～10所示,除Adjusted p-value外,最優(yōu)值用粗體顯示,次優(yōu)值用斜體顯示。各類對比算法對7個測試函數(shù)的收斂過程如圖5所示。

圖5 測試函數(shù)收斂曲線圖

表4 函數(shù)f1測試結(jié)果對比

表6 函數(shù)f3測試結(jié)果對比

表7 函數(shù)f4測試結(jié)果對比

表8 函數(shù)f5測試結(jié)果對比

表9 函數(shù)f6測試結(jié)果對比

表10 函數(shù)f7測試結(jié)果對比

表4～10的實驗結(jié)果表明:在求解成功率上,PSORMP算法取得5個最高值,2個次高值,平均成功率為97%,明顯高于其他算法;在平均最優(yōu)值上,PSORMP算法得到6個平均最優(yōu)結(jié)果和1個平均次優(yōu)結(jié)果,PSO、RPSO、RFRPSO 3種算法共得到3個平均最優(yōu)結(jié)果和6個次優(yōu)平均結(jié)果,驗證了本文算法的尋優(yōu)能力;在最終適應(yīng)值上,PSORMP算法得到6個最優(yōu)結(jié)果和1個次優(yōu)結(jié)果,PSO、RPSO、RFRPSO 3種算法共得到5個最優(yōu)結(jié)果和6個次優(yōu)結(jié)果,驗證了本文算法的求解精度;在平均運行時間上,PSORMP算法得到5個最優(yōu)結(jié)果,2個次優(yōu)結(jié)果;根據(jù)Adjusted p-value,僅在函數(shù)f3～f5測試結(jié)果中,與RFRPSO算法的對比結(jié)果為P>0.05,即沒有顯著差別,其他測試結(jié)果顯示本文算法顯著優(yōu)于其他算法,驗證了本文算法的優(yōu)越性和穩(wěn)定性。從算法的求解精度看,本文算法針對f1,f4～f7共5個函數(shù)求得理想的全局最優(yōu),對f2,f3函數(shù)求得最優(yōu)值與理想值非常接近,并優(yōu)于其他算法。分析其主要原因在于依托增加隨機變異因子和粒子感知因子后,使粒子群在種群空間中的多樣性和聚集性達到了合理分配,從而能夠有效求解高維復(fù)雜多峰函數(shù),特別是對函數(shù)f1,f4～f7,取得了理想全局最優(yōu)解,并且在成功率和穩(wěn)定性上也優(yōu)于其他算法,表現(xiàn)了算法較強的魯棒性。

本文通過增加隨機變異因子和感知因子,動態(tài)調(diào)整了粒子的散布態(tài)勢,擴大了搜索空間,調(diào)整了粒子聚集時間。從函數(shù)的收斂圖像可以看出,針對函數(shù)f1～f4,各類算法均求得了最優(yōu)值,根本原因是函數(shù)f1和f2本身就是單峰函數(shù),求解最優(yōu)值相對容易,而函數(shù)f3在維度超過15維后,函數(shù)特性趨向于單峰,函數(shù)f4的全局最優(yōu)與可達到的局部最優(yōu)之間有一道狹窄的山谷,求解最優(yōu)也相對容易,但本文算法在收斂速度和求解精度上相對于其他算法更有優(yōu)勢;函數(shù)f5～f7為具有大量局部最優(yōu)的復(fù)雜多峰函數(shù),在求解過程中容易陷入局部最優(yōu),但本文算法在收斂速度、求解精度上明顯由于其他算法,尤其是相對于PSO、PSOPC、RPSO、NPSO算法,在迭代500次時,本文算法均收斂并取得最優(yōu)值,而其他算法還未收斂或未求解全局最優(yōu)值.由此表明,PSORMP算法具有很好的跳出局部最優(yōu)和快速求解能力。

3.4 算法參數(shù)的影響分析

圖6 不同r4取值范圍Schwefel函數(shù)收斂曲線圖

3.5 算法復(fù)雜性分析

本文引入的隨機變異因子和感知因子,是在基本粒子群算法的基礎(chǔ)上引入的速度和位置更新策略,需進一步分析PSORMP算法的計算復(fù)雜度,以證明算法的優(yōu)越性。假設(shè)T表示最大迭代次數(shù),D表示維度,N表示初始粒子群規(guī)模。則隨機變異因子的復(fù)雜度為Cr1(N)=D×N×T,感知因子的復(fù)雜度為Cr2(N)=N×T,基本粒子群算法的復(fù)雜度為Cr3(N)=D×N×T。則PSORMP算法復(fù)雜度為Cr(N)=D×N×T+N×T+D×N×T≈D×N×T=Cr3(N)。所以,PSORMP算法與基本PSO算法的復(fù)雜度在理論上屬于同一數(shù)量級。

為進一步驗證上述結(jié)論,采取3.1節(jié)和3.2節(jié)的參數(shù)設(shè)置,選用基本PSO算法、PSOPC、RPSO、NPSO、RFRPSO算法及本文算法PSORMP,對7個測試函數(shù)在同一初始種群條件下,獨立運行100次,記錄每個函數(shù)平均運行時間Tm,系統(tǒng)運行環(huán)境與3.2節(jié)相同,最終結(jié)果如表11所示。其中最優(yōu)值加粗表示,次優(yōu)值用斜體表示。通過給出的結(jié)果可以看出,PSORMP算法與其他算法運行時間處于同一數(shù)量級,引入的因子沒有增加計算的復(fù)雜程度。

表11 算法運行時間對比 s

4 結(jié) 論

本文為解決高維空間中粒子群算容易產(chǎn)生早熟問題,根據(jù)粒子群在空間中的運動規(guī)律和散布特點,提出了一種帶隨機變異因子和動態(tài)感知因子的粒子群優(yōu)化算法,改進了粒子的速度和位置更新策略,有效解決了傳統(tǒng)PSO算法在求解高維復(fù)雜多峰函數(shù)時容易陷入局部最優(yōu)問題,提高了跳出局部最優(yōu)能力和收斂速度。并通過測試函數(shù)和算法對比,驗證了算法的有效性和優(yōu)越性,適合解決工程應(yīng)用中高維空間中的復(fù)雜函數(shù)的優(yōu)化問題。另外,算法是否適用于動態(tài)優(yōu)化求解及可能存在的問題是未來研究的重點。