基于最優網格距離的改進多目標粒子群算法研究

冷 蕊，袁 戀，劉衍民

（1.五邑大學數學與計算科學學院，廣東江門529020；2.貴州民族大學數據科學與信息工程學院貴州貴陽550025；3.遵義師范學院數學學院，貴州遵義563006）

粒子群算法（Particle Swarm Optimization,PSO）[1]是一種源于對鳥類覓食行為的模擬的隨機搜索算法，它是在1995年由Eberhart和Kennedy等人提出，算法具有操作簡單、求解速度快等優點，在求解單目標優化問題中得到了廣泛的應用。但現實遇到的優化問題中，很多優化問題都是多目標優化，因此，如何設計將單目標 PSO用于優化問題成為了研究熱點，多目標粒子群算法（MOPSO）[2]為處理和解決這類問題提供了思路和方法，并廣泛地應用到了相關優化問題中。在將單目標擴展到多目標的過程中遇到如下挑戰：在單目標優化過程中，因目標單一的特點能夠簡單的通過比較來選取學習樣本 pbest和gbest，而在多目標粒子群算法迭代過程中，存在多個相互制約的目標，粒子不能簡單的通過單個目標的比較來確定學習樣本。因此，如何在外部存檔中判斷個體的優劣是多目標粒子群算法的關鍵步驟；另外，由于多目標優化問題往往存在一組非劣解，如何從這些非劣解中選取信息多樣化的解來供決策者選擇是一個巨大的挑戰。針對這些關鍵問題，學者們紛紛提出了相應的策略使得單目標粒子群算法能有效處理多目標優化問題。

Coello等人[3]第一次將粒子群算法擴展到多目標,利用外部存檔思想和pareto占優的基本原理，提出了MOPSO算法。但該算法遇到非凸、多峰以及解空間中出現許多弱支配關系個體時，則容易陷入局部最優和多樣性差的缺點。為防止MOPSO在迭代過程中容易導致早熟收斂，陷入局部最優解，一些學者也提出了一些解決方法，如Deb等人提出了最近鄰密度估計法[4]和核心密度估計法[5]，該方法主要從粒子間的距離來研究學習樣本的選取；Mostaghim和Teich提出了Sigma法[6]，它主要利用當前外部檔案中目標函數的Sigma值來確定學習樣本的選取；也有學者為保持解的多樣性方面提出了小生境法、聚集密度法[7]以及信息熵[8]等；這些改進策略對于粒子跳出局部最優都有一定的效果，但在求解精度和實現上仍有很大的改進空間。

根據單目標粒子群算法處理多目標優化問題的關鍵，在MOPSO的基礎上，本文提出了一種新的改進算法HMOPSO，算法利用最優網格技術對每個個進行改進，實驗結果表明，體的全局學習樣本相比多目標粒子群算法MOPSO具有較好的性能，是對標準多目標粒子群算法的一種有效改進。

1 基本概念

1.1 粒子群算法

粒子群算法因其結構簡單、操作方便等特點，在許多工程應用等領域得到了廣泛的應用。它是一種通過個體之間自我認知和相互協助來尋找最優解的隨機優化的智能技術。假設每個粒子的搜索空間是維，粒子 在維空間由時刻 到1時刻的位置與速度更新公式如下：

1.2 基本定義

定義1.1假設一個有n個決策變量，m個目標的最小化多目標優化問題表示如下：

xu）當且僅當

定義1.3 pareto最優解集：對于多目標優化問題，最優解集可定義為

1.3 粒子群算法流程

在算法迭代過程中，每個粒子存在一個潛在的解，粒子在解空間中根據個體最優粒子與全局最優粒子飛行方向更新迭代逐漸靠近最優解。

第一步：初始化種群中所有粒子的速度和位置，并對每個粒子位置進行變異操作。設置加速常數c1和c2，并計算其適應值。

第二步：對于每個粒子，將當前迭代的適應值與該粒子所經歷的最好適應值進行排序比較，如果優于后者，則被替代，反之不然；若相等，則隨機選取一個。

第三步：建立外部存檔，利用網格技術對粒子進行外部存檔控制并予以更新。

第四步：對每個粒子選擇全局學習樣本。利用輪盤賭方法對每個粒子所在網格隨機選擇其學習樣本進行飛行。

第五步：根據公式（1）和（2）更新每個粒子的位置和速度。

第六步：判斷是否滿足終止條件，若滿足，輸出結果，算法結束；若不滿足，返回第二步。

2 基于最優網格距離的改進算法

2.1 學習樣本的選取

多目標優化問題不同于單目標優化問題，每個目標之間存在相互制約的情況，在迭代的過程中會產生一組非劣解，而如何在這些非劣解中選取學習樣本成為該算法的關鍵。本文提出了一種新的選取社會學習樣本的策略，其定義如下：

定義2.1網格的邊界坐標.設在決策空間中，第m個目標對應函數的最小值、最大值分別為則在第m個目標上網格上下邊界：這里是網格劃分數，根據種群規模來取決定值。

定義2.2網格坐標（Gm）.設fm(X)為粒子X在第m維目標上的函數值，則對應的網格坐標為：

定義2.3最優網格距離（HGD）．定義個體到所在網格的最小邊界點的歐氏距離作為最優網格距離來判斷同一網格內個體的優劣：

其中，fm(xi)為個體xi的實際函數值，Gm(xi)為個體xi的網格坐標．個體的最優網格距離越小，說明離實際最優邊界越近，在排序值相同的情況下應當被優先選取．在圖2中，個體p2，p3在同一網格內，其排序值相同（即網格坐標相同），但是從圖1中可以明顯看出，p2的最優網格距離小于p3，說明p2個體離真實最優邊界近，在這種情況下p3應該被排除。

圖1 最優網格距離實例

問題：一個多目標最小化問題，在某次迭代中，假設有n個粒子所占p個網格，某個網格中有k個粒子，m個目標，建立了一個c×c個網格。在排序值相同的情況下，同一網格內的粒子最優網格距離越小，該粒子越優。

又因為HGD1(x1)＜HGD（2x2），

所以f1(x1)＜ f1(x2)∧ f2(x1)≤f2(x2)或 f1(x1)≤f1(x2)∧f2(x1)＜ f2(x2)

由定義1.2可知x1x2；同理，粒子i可推廣到n個，故定義2.3成立。

若存在b（b(1,k)）個最優粒子的最優網格距離相等，則隨機選擇一個粒子作為全局學習樣本進行飛行。

2.2 算法流程

由于多目標優化問題各目標之間相互制約，所以在選取全局學習樣本時具有一定的盲目性，采用隨機法選取學習樣本來引導其它粒子飛行會導致算法收斂性較差。因此，本文提出了一種新的學習樣本選取策略，利用最優網格技術代替隨機法，圖2給出HMOPSO算法流程圖。

圖2 HMOPSO算法主要流程圖

3 實驗結果與討論

3.1 測試函數的選取

為測試算法的性能，選取國際公認的五個基準函數來測試算法的運行效果，檢測函數表達式如下：

1)ZDT1函數：

2)ZDT2函數：

3)ZDT3函數：

4)ZDT4函數：

5)ZDT6函數：

3.2 實驗結果與討論：

實驗參數設置如下：算法種群規模為200，檢測函數為30維，最大迭代次數為200，網格劃分數為50，外部存檔規模200，其它參數設置與算法提出時一致。選取國際上公認的五個測試函數 ZDT1、ZDT2、ZDT3、ZDT4、ZDT6函數進行測試，并與之相應的MOPSO算法進行對比仿真。

圖3分別給出了5個MOPSO和HMOPSO檢測函數的對比圖，可以看出不管是對于求解凸函數的pareto前沿能力而言，還是遇到pareto前沿面是凹型、不連續的以及包含多個局部極值，相比MOPSO算法，HMOPSO算法表現出了更好的收斂性與分布性。

圖3 檢測函數的收斂特征圖

表1 MOPSO和HMOPSO在檢測函數上的GD指標

表2 MOPSO和HMOPSO在檢測函數上的Spacing指標

表1和表2分別給出了兩種算法在檢測函數上運行5次的收斂性（GD）指標和多樣性（Spacing）指標，分別從最大值、最小值以及平均值分析。從表1中可以看出，HMOPSO算法在收斂性能上基本上比MOPSO算法的收斂性要好；表2中HMOPSO算法在多樣性指標基本上也比MOPSO算法的多樣性指

標要好，與圖1中的結果一致。

圖4 不同算法的GD指標的盒狀統計圖（0-MOPSO;1-HMOPSO）

圖4和圖5分別給出不同算法獨立運行5次的GD評價指標和Spacing評價指標盒狀統計圖。從圖2中可以看出，HMOPSO算法在ZDT1-ZDT6上都獲得了最小值；在圖3中，HMOPSO算法在ZDT1、ZDT4、ZDT6上也明顯的比MOPSO獲得了較好的非劣解，雖然在ZDT2、ZDT3函數上沒有獲得更好的非劣解，但相比MOPSO算法差別并不明顯，這與表1和表2中的定性分析一致。

圖5 不同算法的Spacing指標的盒狀統計圖（0-MOPSO;1-HMOPSO）

4 結論

為了更好的提高解的收斂性和多樣性，本文提出了基于最優網格距離的改進多目標粒子群算法研究。該算法借鑒了pareto占優排序原理，融合了最優網格距離的網格技術，利用輪盤賭策略對網格中每個粒子選擇局部最優粒子作為學習樣本進行飛行，增加了種群的多樣性，使優化效果更佳，進而提升了算法的尋優能力。仿真實驗結果表明，通過對比實驗與MOPSO算法在同一實驗環境下，驗證了HMOPSO算法在大多數測試函數中均表現出了更好的收斂性和分布性，使獲得的最優解集更加靠近真實的pareto前沿。