高慶吉 王瑞雪 談 政

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

0 引 言

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

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

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

1 MOPSO算法模型

1.1 多目標優(yōu)化問題

多目標優(yōu)化問題的數(shù)學模型[10]如下：

(1)

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

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

1.2 標準粒子群算法

一開始最原始的粒子群算法的速度項并沒有系數(shù)，后經(jīng)Shi等[11]科研人員的改進，引進了系數(shù)權(quán)重，構(gòu)成了現(xiàn)在常用的PSO算法更新公式。設(shè)種群里的每一個粒子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)

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

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

2 改進多目標粒子群算法

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

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

(4)

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

(5)

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

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

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

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

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

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

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

2.3 算法流程

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

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

Step2更新局部最優(yōu)粒子、全局最優(yōu)粒子和粒子位置。

Step3高斯變異位置更新。

Step4外部檔案更新。

Step5迭代次數(shù)加1，判斷是否達到迭代次數(shù)，若達到迭代次數(shù)，結(jié)束更新。否則繼續(xù)執(zhí)行Step2。

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

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

3 仿真實驗及結(jié)果分析

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

3.1 評價指標

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

(6)

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

(7)

(8)

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

3.2 算法參數(shù)設(shè)置及實驗結(jié)果分析

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

表1 優(yōu)化算法的參數(shù)設(shè)置

MDPSO算法和改進MOPSO。

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

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

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

表2 MOPSO與改進MOPSO在ZDT函數(shù)上性能指標

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

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

圖4 ZDT1的IGD趨勢

圖5 ZDT2的IGD趨勢

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

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

圖6 ZDT1的HVR趨勢

圖7 ZDT2的HVR趨勢

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

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

4 結(jié) 語

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