帶隨機變異及感知因子的粒子群優化算法

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

(1.空軍工程大學 基礎部, 陜西 西安 710051; 2.空軍工程大學 防空反導學院, 陜西 西安 710051)

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

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

1 基本PSO算法

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

(1)

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

(2)

截至k代,第i個粒子經歷的最優位置稱為個體最優,記為

(3)

截至k代,整個粒子群經歷的最優位置稱為全局最優,記為

(4)

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

(5)

式中:c1和c2為學習因子;r1和r2為[0,1]范圍內的隨機數。

針對慣性系數ω,采用非線性遞減權重策略

(6)

式中:f表示粒子實時的目標函數值;favg和fmin分別表示當前粒子群的平均值和最小目標值[19]。

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

2 PSORMP算法

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

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

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

(9)

(10)

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

(11)

(12)

最后,進行負理想點映射,得映射點xR

xR=xC+α(xC-xF)

(13)

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

圖1 為負理想點時粒子運動過程

圖2 為負理想點時粒子運動過程

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

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

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

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

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

(14)

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

(15)

(16)

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

2.3 PSORMP算法步驟

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

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

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

step3 計算粒子的適應度值;

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

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

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

3 實驗與結果分析

3.1 算法的選擇與比較

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

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

3.2 測試函數的選擇與參數設置

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

圖4 Schwefel函數的二維圖像

表2 測試函數及參數設置

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

表3 對比算法的參數設置

3.3 測試結果及分析

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

圖5 測試函數收斂曲線圖

表4 函數f1測試結果對比

表6 函數f3測試結果對比

表7 函數f4測試結果對比

表8 函數f5測試結果對比

表9 函數f6測試結果對比

表10 函數f7測試結果對比

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

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

3.4 算法參數的影響分析

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

3.5 算法復雜性分析

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

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

表11 算法運行時間對比 s

4 結 論

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