基于高斯變異和自適應參考點的MOPSO優化算法

高慶吉 王瑞雪 談 政

(中國民航大學電子信息與自動化學院 天津 300300)

0 引 言

通常在多目標優化問題當中，要求在幾個相互關聯的約束條件下，實現此類問題的全局優化，多目標優化問題解集不是唯一的，要想使得優化問題中的每個目標函數值達到最佳效果，要求針對這些目標函數進行進一步的優化處理。

粒子群優化算法(Particle swarm optimization，PSO)的原型是虛擬大量的生物群體活動，例如進行尋找食物行為等，提出的一種群體智能優化方法[1]。具有簡易迅速的優化特點[2]，已經很好地在求解單目標最優問題當中實現[3]。近幾年PSO優化算法再次引起國內外學者關注并成功被應用到多目標的優化問題中[4]，同時也成為了處理多目標優化問題的優選算法之一，取得良好的應用效果。文獻[5]討論了一種特殊的以分解和差分進化為基礎的MOPSO優化算法，引用方向角概念，保證了粒子分布的均勻性，同時用隱式精英保持策略與差分進化修正方法挑選出整體最優粒子，防止粒子陷入局部最優Pareto前沿。文獻[6]討論了以QPSO和擁擠距離排序為基礎的MOPSO優化方法，利用粒子重置方法確保了群體的多樣性。

目前大多數PSO算法的研究主要集中在種群多樣性和目標收斂性方面[7]，標準PSO易陷入局部最優解，收斂性較差[8,9]。為了改善PSO在尋找最優解集時的多樣性，提出了一種利用高斯變異位置更新方法避免早熟現象，為了提高算法的收斂性，提出了一種采用自適應參考點的外部檔案維護策略，將收斂性較差的粒子剔除。實驗表明該算法具有快速的收斂性，同時在解的多樣性和分布性上也表現出很好的性能。在解決復雜多目標難題時，該改進方法的性能指標得到較大改善。

1 MOPSO算法模型

1.1 多目標優化問題

多目標優化問題的數學模型[10]如下：

(1)

式中：x=(x1,x2,x3,…,xn)T，x∈A為函數的搜索域，t是函數的時間變量，T和s是此數學模型的等式與不等式的約束條件，n是決策變量的維數，f是隨時間變化的D維目標函數。

在多目標優化問題求解過程中，最好的求解結果是使得到最優解最大程度地接近或收斂于真正Pareto前沿，并且此解集的分布盡量可能平均。

1.2 標準粒子群算法

一開始最原始的粒子群算法的速度項并沒有系數，后經Shi等[11]科研人員的改進，引進了系數權重，構成了現在常用的PSO算法更新公式。設種群里的每一個粒子i(i∈N),N是群體大小，粒子活動的空間是D維的，t時刻到t+1時刻的速度更新和位置更新為[12]：

vi(t+1,d)=ωvi(t,d)+c1rand(gbest(t,d)-xi(t,d))+
c2rand(pbest(t,d)-xi(t,d))

(2)

xi(t+1,d)=xi(t,d)+vi(t+1,d),d=1,2,…,D

(3)

式中：ω是關系系數，代表著上一時刻的速度大小對下一時刻速度大小的影響大小；c1、c2是能力系數，分別表示全局學習能力的大小和局部學習能力大小，c1越大表示粒子全局學習能力越強，越趨向于全局最優位置，c2越小代表粒子局部搜察能力越弱；gbest代表整個粒子群中所有的粒子所經歷過的最優坐標；pbest是粒子個體i曾經經歷的最優位置；rand為(0, 1)上產生的隨機數；d為粒子i的d維變量。

標準PSO簡單而且在單目標求解中獲得了很好的應用[13,14],但在更新個體最優值和全局最優值的過程中，粒子通常會表現出早熟的跡象[15,16]，種群粒子提前終止進化，陷入局部最優。

2 改進多目標粒子群算法

2.1 基于高斯變異的位置更新

標準PSO優化算法在更新個體最優值和全局最優值的過程中，粒子通常會表現出早熟的現象，整個粒子群中的粒子提早終止變異，陷入部分極值。研究發現，在粒子位置更新過程中，適當地添加一些擾動，很容易使某些解值跳出局部最優。所以，將高斯變異的思想帶入PSO算法的尋找最優解過程當中，從而改善粒子在求解過程當中的多樣性。采用實時變異，即在位置的更新上加入動態變異，使迭代次數也參與變異，可以使變異呈隨時間變化而變化的動態形式。由于在位置更新的過程中，初始時刻的解接近最優解的較少，大部分的解距離最優解較遠，而隨著時間的推移，有越來越多解接近最優解，變異解個數應隨時間的流逝而呈遞減狀態，因此定義每一代粒子參加變異的個數隨迭代次數的遞增而呈單調衰減，保證了一些較優的解不變異。根據高斯概率函數的分布情況重構了基于高斯變異的函數Gi(t)，具體的構造表達式如下：

(4)

式中：xbest是目前總體的最優解，δ是高斯分布標準差，當迭代次數達到一定值后，大部分的粒子將向xbest的位置移動，導致所有的解值過早的停止尋優，此刻利用Gi(t)函數來增加擾動,使粒子逃脫xbest的束縛，減小了粒子進入部分最優的概率。應用高斯變異擾動迭代更新，其公式如下：

(5)

2.2 基于自適應參考點外部檔案維護

在本小節中外部檔案的主要作用是來存儲粒子在迭代過程中求得的較好的非支配解。每次將所得到的非支配解存儲到外部檔案中，將外部檔案中解的個數與最大值比較，當數量超過最大數量時，就必須從中選擇一些解將其剔除，同時保持解集多樣性和收斂性。為了改善這兩種性能指標，提出了一種基于自適應參考點的外部檔案維護策略。首先選出密度函數最大的標準線，其次將標準線所在的解集中收斂程度最小的粒子剔除，然后將外部檔案的大小與容量最大值進行比較，判斷是否需要從外部檔案中剔除多余的解值。具體步驟如下：

Step1計算粒子密度函數。算出每代粒子x的密度函數集合M。

Step2計算粒子的收斂程度S。

Step3取密度函數最大的集合Mmax，從中任意選擇出當中的一條作為標準線j。

Step4將標準線j所在的解集M中收斂程度S最小的粒子剔除。

Step5將外部檔案的大小與容量最大值進行比較，如果超過，就執行Step 1；否則，將該解存入外部存儲器。

2.3 算法流程

以上述操作作為基本原則，改進粒子群算法的具體步驟如下：

Step1初始化，首先設置參數的最初數，例如粒子群的大小、外部檔案的大小、最大迭代次數。然后初始化粒子群的搜索范圍、將外部檔案設置為零。

Step2更新局部最優粒子、全局最優粒子和粒子位置。

Step3高斯變異位置更新。

Step4外部檔案更新。

Step5迭代次數加1，判斷是否達到迭代次數，若達到迭代次數，結束更新。否則繼續執行Step2。

算法的流程圖如圖1所示。

圖1 該進粒子群算法的工作流程

3 仿真實驗及結果分析

判斷一個多目標優化算法是否優于其他方法時，其中最重要的判斷方法就是該方法是否能夠尋找到真正的Pareto前沿，并且在該條件下，將得到的解集的收斂性和多樣性與沒有改進時的性能進行對比，最終得出算法的評價結果。為驗證本文改進的基于高斯變異和自適應參考點的多目標粒子群優化算法的性能，選取ZDT1、ZDT2[17,18]測試函數來驗證。選以上函數作為驗證函數是因為ZDT1函數為凸函數，ZDT2函數為凹函數，其中f1和f2分別是兩個目標函數。利用不同的多目標函數來驗證高斯變異和自適應參考點的多目標粒子群優化算法的收斂性和多樣性。

3.1 評價指標

非靜態的多目標優化算法的目的就是在非靜態的條件中，使最多的解集能夠快速的收斂于該函數的Parto前沿P*(t)，并且需要保持解集合S(t)的多樣性。本文采用反向代距離[19](Inverse gener-ation distance, IGD)和超體積比 (Hypervolume ratio,HVR)指標來評價所提算法的收斂新和多樣性。其中,IGD的定義如下：

(6)

IGD(t)函數能夠判斷該方法的收斂性。在理想狀態下IGD(t)值為0，表示S(t)達到了最好的收斂效果。超體積比[20]HVR是以超體積 (Hypervolume, HV)為基準演變過來的，其數值的大小直接能夠反映出算法尋找解的多樣性能力，計算公式如下所示：

(7)

(8)

根據HVR(t)值的大小能夠得出該算法多樣性是否豐富的結果，當S(t)和P*(t)的值大小相等時，HVR(t)的值最大，且為1。由此可以得出HVR(t)的數值越大，就表示該算法在多樣性這方面的性能越好。

3.2 算法參數設置及實驗結果分析

為了證明本文方法具有一定的改善效果，本算法的所有參數設置如下：其中慣性系數ωmax=0.9、ωmin=0.4，學習系數C1=C2=1.5。ZDT函數所有算法均取種群數量為200，外部存檔數量為200。為了體現出公正性，表1是對不同算法的參數設置。

表1 優化算法的參數設置

MDPSO算法和改進MOPSO。

算法在ZDT1、ZDT2函數上的對比如圖2、圖3所示，其性能指標如表2所示。

(a) MOPSO (b) 改進MOPSO圖2 算法在ZDT1函數上的對比

(a) MOPSO (b) 改進MOPSO圖3 算法在ZDT2函數上的對比

表2 MOPSO與改進MOPSO在ZDT函數上性能指標

由表2可知，改進MOPSO在加入高斯變異和自適應參考點的外部檔案維護策略后，在測試函數ZDT1和ZDT2上的IGD和HVR性能指標都有了明顯的提高。

MOPSO算法與改進MOPSO算法在ZDT1、ZDT2函數上的IGD趨勢如圖4、圖5所示。

圖4 ZDT1的IGD趨勢

圖5 ZDT2的IGD趨勢

由圖4和圖5可知，改進MOPSO在加入高斯變異和自適應參考點的外部檔案維護策略后，在相同的迭代次數后Pareto解的收斂性明顯高于MOPSO。

MOPSO算法與改進MOPSO算法在ZDT1、ZDT2函數上的HVR趨勢如圖6、圖7所示。

圖6 ZDT1的HVR趨勢

圖7 ZDT2的HVR趨勢

由圖6和圖7可知，改進MOPSO在加入高斯變異和自適應參考點的外部檔案維護策略后，在相同的迭代次數時Pareto解的多樣性明顯高于MOPSO。

綜上所述，改進MOPSO在加入高斯變異和自適應參考點的外部檔案維護策略后，最優解集向標準的Pareto解集收斂的速度加快了，同時粒子能夠跳出局部最優極值的能力增強了，尋優的精度也變高了。

4 結 語

針對動態多目標優化問題，本文提出了一種基于高斯變異和自適應參考點的多目標粒子群優化算法。該算法利用高斯變異的位置更新方法避免早熟現象，提高了PSO在尋優過程中搜索解的多樣性，采用自適應參考點的外部檔案維護策略提高算法的收斂性。仿真實驗結果表明：改進MOPSO算法在多目標優化中具有良好的效果，同時，該算法結構簡單，具有良好的可移植性，可為后續多目標優化算法的研究提供參考。