冷 蕊，袁 戀，劉衍民

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

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

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

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

1 基本概念

1.1 粒子群算法

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

1.2 基本定義

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

xu）當(dāng)且僅當(dāng)

定義1.3 pareto最優(yōu)解集：對(duì)于多目標(biāo)優(yōu)化問(wèn)題，最優(yōu)解集可定義為

1.3 粒子群算法流程

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

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

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

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

第四步：對(duì)每個(gè)粒子選擇全局學(xué)習(xí)樣本。利用輪盤(pán)賭方法對(duì)每個(gè)粒子所在網(wǎng)格隨機(jī)選擇其學(xué)習(xí)樣本進(jìn)行飛行。

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

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

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

2.1 學(xué)習(xí)樣本的選取

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

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

定義2.2網(wǎng)格坐標(biāo)（Gm）.設(shè)fm(X)為粒子X(jué)在第m維目標(biāo)上的函數(shù)值，則對(duì)應(yīng)的網(wǎng)格坐標(biāo)為：

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

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

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

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

又因?yàn)镠GD1(x1)＜HGD（2x2），

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

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

若存在b（b(1,k)）個(gè)最優(yōu)粒子的最優(yōu)網(wǎng)格距離相等，則隨機(jī)選擇一個(gè)粒子作為全局學(xué)習(xí)樣本進(jìn)行飛行。

2.2 算法流程

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

圖2 HMOPSO算法主要流程圖

3 實(shí)驗(yàn)結(jié)果與討論

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

為測(cè)試算法的性能，選取國(guó)際公認(rèn)的五個(gè)基準(zhǔn)函數(shù)來(lái)測(cè)試算法的運(yùn)行效果，檢測(cè)函數(shù)表達(dá)式如下：

1)ZDT1函數(shù)：

2)ZDT2函數(shù)：

3)ZDT3函數(shù)：

4)ZDT4函數(shù)：

5)ZDT6函數(shù)：

3.2 實(shí)驗(yàn)結(jié)果與討論：

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

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

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

表1 MOPSO和HMOPSO在檢測(cè)函數(shù)上的GD指標(biāo)

表2 MOPSO和HMOPSO在檢測(cè)函數(shù)上的Spacing指標(biāo)

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

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

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

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

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

4 結(jié)論

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