基于最優(yōu)網(wǎng)格距離的改進多目標粒子群算法研究

冷 蕊，袁 戀，劉衍民

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

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

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

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

1 基本概念

1.1 粒子群算法

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

1.2 基本定義

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

xu）當且僅當

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

1.3 粒子群算法流程

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

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

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

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

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

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

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

2 基于最優(yōu)網(wǎng)格距離的改進算法

2.1 學習樣本的選取

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

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

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

定義2.3最優(yōu)網(wǎng)格距離（HGD）．定義個體到所在網(wǎng)格的最小邊界點的歐氏距離作為最優(yōu)網(wǎng)格距離來判斷同一網(wǎng)格內(nèi)個體的優(yōu)劣：

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

圖1 最優(yōu)網(wǎng)格距離實例

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

又因為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)）個最優(yōu)粒子的最優(yōu)網(wǎng)格距離相等，則隨機選擇一個粒子作為全局學習樣本進行飛行。

2.2 算法流程

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

圖2 HMOPSO算法主要流程圖

3 實驗結(jié)果與討論

3.1 測試函數(shù)的選取

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

1)ZDT1函數(shù)：

2)ZDT2函數(shù)：

3)ZDT3函數(shù)：

4)ZDT4函數(shù)：

5)ZDT6函數(shù)：

3.2 實驗結(jié)果與討論：

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

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

圖3 檢測函數(shù)的收斂特征圖

表1 MOPSO和HMOPSO在檢測函數(shù)上的GD指標

表2 MOPSO和HMOPSO在檢測函數(shù)上的Spacing指標

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

標要好，與圖1中的結(jié)果一致。

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

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

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

4 結(jié)論

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