融合隸屬度函數的自適應慣性權重模式的粒子群優(yōu)化算法

毛煥宇 王文東

1(浙江紡織服裝職業(yè)技術學院信息媒體學院 浙江 寧波 315211)2(延安大學數學與計算機科學學院 陜西 延安 716000)

0 引 言

作為一種智能種群優(yōu)化算法，PSO算法[1]與其他種群進化算法相似，是以隨機解組成的種群進行初始化的。不同之處在于，傳統(tǒng)的PSO并不僅僅是一次性的適者生存法則，它對于物種行為的模擬，其每一個候選解均與一個進化速率相關。PSO的優(yōu)勢取決于粒子朝著全局最優(yōu)解進化的收斂速度[2]。粒子群進化算法不僅簡單，且運行頻率較高，適應性好，廣泛應用于多目標最優(yōu)化和路徑規(guī)化問題研究中。然而，如何在當前空間的搜索與新搜索空間的開發(fā)上取得一定的平衡是粒子群進化的關鍵問題。對于傳統(tǒng)的粒子群優(yōu)化而言，搜索初期的粒子可以較快收斂至較優(yōu)解周圍，但搜索晚期會出現眾多粒子密集聚焦同一區(qū)域的情況。文獻[3]的研究結果證實，粒子搜索最優(yōu)解過程中，若慣性權重值過大，則搜索過程近似全局搜索機制，對于新區(qū)域的不斷搜索會導致粒子過度分散，無法聚焦和收斂，得不到最終穩(wěn)定的種群；而過小的慣性權重則使得搜索近似局部搜索機制，粒子收斂過快，而陷入局部極值點中。

文獻[4]提出通過一種模糊控制機制和隨機化方法，實現對粒子迭代進化中的慣性權重調整，但是得到的粒子收斂性性能并不理想，原因在于其算法計算復雜度較高，計算時間過長。文獻[5]引入一種收斂因子對種群進行迭代處理，以一種參數動態(tài)配置方法防止部分種群粒子的進化方向出現過大偏離，無法到達最優(yōu)區(qū)域，可以實現控制收斂。文獻[6]提出一種動態(tài)拓撲結構控制粒子移動，使初始階段的進化過程中鄰居粒子數量降低，隨著迭代搜索的進行，再根據粒子間距更新粒子活動鄰近區(qū)域，極大地提升了粒子種群的多樣性，但算法收斂需要的迭代次數較大。文獻[7]將集群化的粒子群中的中心粒子視為最優(yōu)粒子，將聚類后得到的全局聚類中心作為全局最優(yōu)粒子，進而以聚類的方式實現了最優(yōu)粒子的鄰近區(qū)域的更新規(guī)則。文獻[8]設計一種動態(tài)聚簇的粒子群算法，使相近特點的粒子可組成群，以群體方式共同進化，以此改變粒子尋優(yōu)性能。文獻[9]則利用小世界網絡思想改善粒子尋優(yōu)能力，避免了種群早熟。

不同于以上工作，本文在每次迭代過程中更新粒子速度的同時，將當前的參考粒子與全局種群的最優(yōu)粒子間的距離考慮到進化過程中，并根據該距離值，設計一種隸屬度函數動態(tài)地為粒子調整其慣性權重。該自適應的調整方法使得離最優(yōu)粒子較遠的粒子可以擁有更大的慣性權重，從而提高全局搜索性能，而離最優(yōu)粒子較近的粒子可以擁有更小的慣性權重，提高其局部搜索性能。

1 粒子群優(yōu)化及其早熟分析

對于PSO，設m個粒子分布在d維度空間中，每個粒子的維度以速度和位置進行描述，在t次迭代時，分別表示為：

(1)

迭代過程中，單個粒子已搜索到的最優(yōu)位置表示為Pi=(pi1,pi2,…,pid)，將其稱為pbest，即個體最優(yōu)解。而所有粒子搜索到的最優(yōu)位置為Pg=(pg1,pg2,…,pgd)，即全局最優(yōu)gbest。PSO即是所有粒子更新其粒子速度和位置的尋優(yōu)過程，可表示為：

(2)

式中：t表示迭代次數；d表示搜索空間的維度；w表示慣性權重值，w∈[0.1,0.9]；rand()表示隨機數，rand()∈[0,1]；c1和c2為常量，稱為認知因子。

對于傳統(tǒng)的粒子群而言，更小的慣性權重更利于局部搜索，慣性權重增加則利于全局搜索。因此，若w值在迭代過程中保持恒定不變會降低PSO的性能。文獻[10-11]中的研究表明，w值在迭代過程中的線性降低可以明顯地增強PSO的收斂性能。具體方式為：賦予迭代初期的粒子更優(yōu)的全局搜索能力，而賦予迭代后期的粒子更優(yōu)的局部搜索能力。換言之，在迭代過程早期，需要設置較大w值；在迭代過程晚期，需要設置較小w值。針對這一問題，文獻[12]通過利用慣性權重最值wmax和wmin設計了一種線性遞減機制對w值進行動態(tài)調整：

(3)

式中：tmax為種群迭代的最大次數。

式(3)中的慣性權重調整策略表明w值是線性遞減的，而線性遞減并不能表現粒子間的差異。為了反映每次迭代過程中粒子間的差異，根據粒子間距，本文利用隸屬度函數的概念，設計了一種可對粒子慣性權重進行自適應更新的改進粒子群算法。并且，為了使得具有更高適應度的粒子被選擇為全局最優(yōu)粒子的概率更大，還設計了一種Roulette(輪盤賭)方法進行最優(yōu)粒子的選擇。

2 基于自適應慣性權重的粒子群算法

2.1 粒子間的距離度量

定義1以Xi=[xi1,xi2,…,xid]表示粒子i，f表示粒子的適應度，種群中粒子i與粒子j間的距離定義為：

(4)

根據定義1可知，對于任意粒子i、j和k，粒子間的距離將具備以下性質：

性質1非負性。粒子i和j間的距離是非負的，即D(i,j)≥0。

性質2粒子與本身間的距離為零值，即D(i,i)=0。

性質3對稱性。粒子i到粒子j的距離等于粒子j和粒子i的距離，即D(i,j)=D(j,i)。

性質4粒子間的距離滿足三角形邊長性質，即D(i,j)≤D(i,k)+D(k,j)。

不同于其他粒子距離度量方法，式(4)利用曼哈坦距離(Manhattan Distance)[13]度量粒子間距，不僅考慮了無關參數間的距離，而且還考慮了目標函數間的距離。

定義2粒子間的最大距離定義為：

Dmax=max{D(i,j)}

(5)

定義3若N為粒子數量，粒子間的平均距離為所有粒子對的間距之和與粒子數量的商值，可定義為：

(6)

定義4粒子與種群中的最優(yōu)粒子間的平均距離定義為：

(7)

2.2 隸屬度函數及其自適應規(guī)則

對于PSO, 粒子速度的慣性權重更新僅與當前迭代的次數相關，并未考慮粒子本身的特點?，F實情況是:粒子需要以自身與最優(yōu)粒子間距離為依據，動態(tài)調整慣性權重值。當粒子與最優(yōu)粒子相距較遠時，粒子需要擁有更大的慣性權重，這有助于搜索全局最優(yōu)，并更快地收斂。若粒子距離最優(yōu)粒子較近，則應該賦予更小慣性權重?；诖?，根據D(i,pg)和慣性權重w，算法設計以下模糊規(guī)則：

規(guī)則1：若D(i,pg)較小，則慣性權重w也較??；

規(guī)則2：若D(i,pg)中等，則慣性權重w也中等；

規(guī)則3：若D(i,pg)較大，則慣性權重w也較大。

PSO-AIWA算法中D(i,pg)與w的隸屬度函數[14]如圖1和圖2所示，圖中δ和θ表示隸屬度因子。

進行粒子更新時，若僅考慮粒子最優(yōu)位置pi和全局最優(yōu)粒子Pg，可能導致最終得到局部最優(yōu)。針對該問題，算法選擇若干個最優(yōu)粒子在確定距離內參與迭代過程。具體地，在每次迭代中，選擇任意k個全局最優(yōu)粒子為候選粒子，通過Roulette方法從k個粒子選擇最終的全局最優(yōu)粒子。

為了使單個具有更大適應度的粒子當選為全局最優(yōu)粒子的概率更高，需要增加擁有更大適應度粒子的慣性權重。在k個全局最優(yōu)粒子中，計算選擇粒子m為全局最優(yōu)粒子的概率為：

(8)

式中：fit(x)表示粒子x的適應度。

(9)

利用Roulette方法，對于任意的r∈[0,1]，如果式(10)得到滿足，則粒子m被選擇為全局最優(yōu)粒子。

(10)

本文提出的PSO-AIWA算法將根據粒子與最優(yōu)粒子間距對慣性權重進行動態(tài)調整。當粒子與最優(yōu)粒子間的距離大于門限值TH時，粒子則擁有更大的慣性權重；反之則賦予更小值。門限值TH設置為Daverage。粒子慣性權重的自適應調整方式為：

(11)

式中：pg表示通過Roulette方法選擇的種群中的全局最優(yōu)粒子；wmax和wmin分別表示慣性權重值的最大值與最小值。

算法1給出了PSO-AIWA算法的偽代碼。

算法1PSO-AIWA算法

1. 輸入：tmax,N,k,wmax,wmin,c1,c2,δ,θ

2. 輸出：全局最優(yōu)解pg

3. 初始化粒子種群

4. 計算最優(yōu)粒子pi和pg

5. 當t≤tmax

6. 計算粒子距離Daverage

7. 計算距離的隸屬度

8. 利用輪盤轉選擇規(guī)則計算w

9. 根據式(2)更新粒子速度和位置

10. 更新最優(yōu)粒子pi和pg

11. 更新迭代次數t

12. 返回全局最優(yōu)解pg

算法輸入參數包括：最大迭代次數、粒子總數、候選粒子數量、慣性權重最大值和最小值、認知因子、隸屬度因子，算法輸出全局最優(yōu)粒子，即步驟1和步驟2。步驟3初始化種群粒子，包括粒子位置和速率。步驟4獲取初始種群的最優(yōu)粒子。步驟5表明，若當前迭代次數小于或等于最大迭代次數。步驟6計算粒子間的平均距離。步驟7計算基于粒子距離的隸屬度。步驟8利用Roulette方法與相應的模糊規(guī)則計算當前的慣性權重。步驟9利用式(2)對粒子速度和位置進行更新。步驟10更新當前粒子搜索到的最優(yōu)位置和所有粒子的最優(yōu)位置。步驟11更新迭代次數，返回步驟5繼續(xù)搜索過程。最終在步驟12返回收斂的全局最優(yōu)粒子，即最優(yōu)解。

3 仿真實驗

3.1 實驗配置與基準函數

利用MATLAB平臺實現了融合隸屬度函數的自適應慣性權重粒子群算法的仿真測試。選取6種基準算法，包括：Sphere函數、Rastrigin函數、Rosenbrocks函數、Quadric函數、Griewank函數和Rotated Quadric函數，以上測試函數是廣泛應用于粒子群進化問題測試的經典函數。6種基準函數中，Rosenbrocks函數、Rastrigin函數、Rotated Quadric函數和Griewank函數為多峰值函數，其他函數為單峰值函數。表1給出了以上6種基準函數的相關搜索參數聲明。表2給出了算法中屬于粒子群的相關參數設置。為了證明算法性能的有效性，使用隨機慣性權重的經典PSO算法和線性慣性權重的PSO-LDIW算法[12]作為性能的對比算法。

表1 測試函數聲明

表2 參數設置

1) Sphere函數:

(12)

2) Quadric函數:

(13)

3) Rosenbrocks函數:

(14)

4) Rastrigin函數:

(15)

5) Griewank函數:

(16)

6) Rotated Quadric函數:

(17)

3.2 實驗結果

1) 種群粒子分布情況。實驗1觀察了3種算法利用測試基準函數f5得到的迭代次數分別為50、100和200時的粒子分布情況，結果如圖3所示。種群中粒子的分布可以一定程度地反映種群個體的多樣性。PSO利用的是隨機化的慣性權重值對粒子狀態(tài)進行調整，所得到的種群粒子分布在不同的迭代次數下始終處于較為分散的狀態(tài)，即圖3(a)。在粒子進化的后期，部分粒子已經逐漸陷入一些局部極值點的區(qū)域內，即使繼續(xù)進行狀態(tài)進化與搜索，也無法有進一步改進。相比隨機慣性權重PSO，PSO-LDIW算法在全局收斂性上表現更加優(yōu)秀，其多數粒子均可以在迭代次數的后期逐漸進入到全局最優(yōu)點的區(qū)域內，原因在于該算法利用慣性權重值是線性遞減式改變的，尋優(yōu)性能得到了提升。而本文提出的PSO-AIWA算法比較另外兩種算法而言，其粒子具有更好的聚集性，粒子進化過程中并沒有過早地使自身聚焦至局部極值點附近的區(qū)域，從而導致早熟，影響整體尋優(yōu)結果。主要原因在于：PSO-AIWA算法可以根據設計隸屬度函數動態(tài)的調整粒子慣性權重，而隸屬度函數又是基于當前粒子與全局最優(yōu)粒子間的距離得到的。

(a) 利用隨機慣性權重的PSO粒子分布

(b) 利用線性遞減慣性權重的PSO-LDIW粒子分布

(c) 利用隸屬度的動態(tài)自適應慣性權重的PSO-AIWA粒子分布圖3 種群粒子分布情況

2) 算法收斂性。實驗2觀察了3種算法的收斂性性能，實驗目的是比較3種算法在擁有相同初始數據情況下的收斂速度和效率。實驗在完全相同的條件下測試了所有6種基準函數下的收斂性能，其他參數與實驗1也是相同的。從圖4的結果可以看到，無論是單峰值基準函數還是多峰值基準函數情況，PSO-AIWA算法在收斂速度和精確度上均要優(yōu)于PSO算法和PSO-LDIW算法。測試中，在搜索能力上，PSO-LDIW算法要優(yōu)于傳統(tǒng)PSO算法。而PSO-AIWA算法比PSO-LDIW算法則表現出更好的性能，其搜索能力更佳。綜合來看，采用自適應慣性權重調整機制的PSO-AIWA算法可以從根本上改善對比算法中對慣性權重的單一計算方式，降低搜索性能對于初始參數設置的過多依賴。

(a) Sphere函數

(b) Quadric函數

(c) Rosenbrocks函數

(d) Rastrigin函數

(e) Griewank函數

(f) Rotated Quadric函數圖4 最優(yōu)適應度收斂性

3) 性能的統(tǒng)計分析。實驗3以統(tǒng)計方法觀察算法得到的適應度值的變化，結果如表3所示。由于在可行區(qū)域中僅有一個全局極值點，且越接近極值點其變化越小，選擇Sphere函數進行本實驗的測試。結果表明，相同條件下，PSO-AIWA算法和PSO-LDIW算法得到的結果的準確性上明顯優(yōu)于隨機慣性權重PSO，這表明慣性權重的調整策略在改進粒子個體多樣性和維持迭代進化的性能上是有效可行的。相比PSO-LDIW算法，PSO-AIWA算法則擁有更佳的表現，在相同的配置條件下，其得到的最小值、最大值和平均最優(yōu)值更接近于全局最優(yōu)，這表明本文所設計的基于隸屬度的慣性權重自適應調整策略是可以增強粒子個體的搜索能力的，在最優(yōu)粒子的影響下，其粒子進化方向選擇更優(yōu)。另外，在多峰值測試基準函數下，PSO-AIWA算法同樣優(yōu)于PSO-LDIW和PSO算法。在20次的實驗中，比較PSO、PSO-AIWA和PSO-LDIW算法得到的結果顯然更加接近于全局最小值，這表明粒子慣性權重的自適應更改可以增加粒子的搜索能力。而本文在不同階段中所應用的慣性權重自適應調整策略則有效地提升了粒子進化，更好地指導了粒子的尋優(yōu)。

表3 統(tǒng)計結果

續(xù)表3

綜合以上的分析，在算法得到的粒子分布性能方面，本文算法得到的粒子分布相對于其他算法可以更快地實現粒子的聚集。一方面證明了利用隸屬度的動態(tài)自適應慣性權重調整機制是有效可行的，另一方面也證實了它對隨機慣性權重和線性遞減慣性權重能夠更好地描述粒子的差異，給予不同粒子不同程度的尋優(yōu)方向和尋優(yōu)能力，有效避免了粒子陷入局部最優(yōu)。粒子較好的聚焦性也顯示出算法也將具有更好的收斂性，即圖4的結果；更快地收斂可使得粒子得到的平均適應度會趨于穩(wěn)定，即表明已搜索到全局最優(yōu)解上。在粒子適應度值的統(tǒng)計分析上，本文算法得到的適應度值也是優(yōu)于對比算法的，這表明慣性權重的調整策略在改進粒子個體多樣性和維持迭代進化的性能上是有效可行的。同時，無論是利用多峰函數還是單峰函數進行測試，結果都比較穩(wěn)定，這表明粒子慣性權重的自適應更改可以增加粒子的搜索能力，不會由于測試基準函數性質的改變而改變粒子的尋優(yōu)性能。

4 結 語

本文為粒子群算法設計了一種新的慣性權重自適應調整策略，解決了傳統(tǒng)粒子群算法忽略粒子間的差異，利用相同的慣性權重到所有種群粒子上的缺陷。算法的主要思想是可以根據與全局最優(yōu)粒子間的(距離)不同，通過基于粒子間距的隸屬度函數動態(tài)調整粒子的慣性權重，使得每次迭代中，粒子可以根據當前狀態(tài)在每個維度上的搜索空間內選擇合適的慣性權重進行狀態(tài)更新。通過覆蓋單峰函數和多峰函數的6組基準函數進行了大量仿真實驗，結果表明，比較隨機式慣性權重和線性遞減式慣性權重的調整策略，本文算法在收斂速度、求解準確性及參數敏感性上均表現出了更好的效果。