一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法

何　騫，董軼群，徐文星*

(1.北京化工大學(xué)，北京 100029；2.北京石油化工學(xué)院，北京 102617)

?

一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法

何騫1，董軼群2，徐文星*2

(1.北京化工大學(xué)，北京 100029；2.北京石油化工學(xué)院，北京 102617)

針對(duì)多目標(biāo)粒子群優(yōu)化算法在迭代過(guò)程中收斂速度和多樣性方面的不足，提出一種改進(jìn)的多目標(biāo)粒子群優(yōu)化算法(IMOPSO)。采用基于柵格和擁擠距離的協(xié)同外部檔案維護(hù)策略，通過(guò)更準(zhǔn)確地選擇收斂性和多樣性性能更好的非劣粒子作為全局最優(yōu)值，加快整個(gè)種群的收斂速度；采用分段Logistic混沌映射、外部檔案檢測(cè)機(jī)制及修改的粒子速度更新公式，分別在初始化階段和迭代過(guò)程中增強(qiáng)種群的多樣性；最后，通過(guò)對(duì)標(biāo)準(zhǔn)測(cè)試函數(shù)仿真測(cè)試證明了改進(jìn)后的算法能夠快速收斂至Pareto最優(yōu)前沿并保持較好的多樣性。

多目標(biāo)優(yōu)化；粒子群優(yōu)化算法；分段Logistic混沌映射；擁擠距離

現(xiàn)實(shí)生活中的優(yōu)化問(wèn)題因具有較高復(fù)雜程度，優(yōu)化目標(biāo)往往不唯一。多目標(biāo)優(yōu)化問(wèn)題中不存在唯一最優(yōu)解，而是綜合不同目標(biāo)函數(shù)后所得到的一個(gè)最優(yōu)解集合[1]。因此，在各目標(biāo)函數(shù)之間相互制約的情況下，如何快速、準(zhǔn)確地獲取多目標(biāo)問(wèn)題的最優(yōu)解集合逐漸成為研究的熱點(diǎn)。作為一種新穎的群體智能進(jìn)化算法，粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)因模型簡(jiǎn)單，求解最優(yōu)解無(wú)需梯度信息，對(duì)目標(biāo)函數(shù)的復(fù)雜程度沒(méi)有太多要求，易于求解，收斂速度快等特點(diǎn)[2-3]，許多學(xué)者對(duì)其進(jìn)行了改進(jìn)研究。

近年來(lái)，Parsopoulos等[4]運(yùn)用動(dòng)態(tài)權(quán)重法將多個(gè)目標(biāo)函數(shù)整合為1個(gè)目標(biāo)，利用求解單目標(biāo)問(wèn)題的方法求解多目標(biāo)問(wèn)題。Mostaghim S等[5]采用ε支配的方式篩選全局最優(yōu)解，有效地提高了算法的多樣性，但是確定ε值存在一定困難。Coello等[6]提出用外部集合保留迭代過(guò)程中搜索到的非劣解，改善了算法的效能。Tsai等[7]利用特定的全局最優(yōu)值來(lái)代替?zhèn)€體最優(yōu)值，充分發(fā)揮全局最優(yōu)值的指導(dǎo)作用。賈樹(shù)晉等[8]結(jié)合增廣Lagrange乘子法的方法對(duì)種群篩選出愛(ài)的非劣解進(jìn)行局部搜索來(lái)逼近Pareto最優(yōu)解。黃敏等[9]提出自適應(yīng)的選取全局最優(yōu)解策略并結(jié)合局部搜索來(lái)增強(qiáng)種群的搜索能力。王亞輝等[13]提出一種環(huán)形鏈?zhǔn)酵負(fù)浣Y(jié)構(gòu)，將種群劃分為多個(gè)領(lǐng)域，進(jìn)行不同的速度位置更新策略。胡旺等[14]提出基于Pareto熵的策略，根據(jù)在平行格坐標(biāo)系統(tǒng)中的分布熵和差熵來(lái)衡量種群的性能。雖然嘗試了不同的改進(jìn)方式，但是種群的多樣性和收斂速度往往不能兼顧，針對(duì)這一問(wèn)題，筆者對(duì)粒子群算法進(jìn)行了改進(jìn)，利用標(biāo)準(zhǔn)測(cè)試函數(shù)來(lái)驗(yàn)證算法的性能，在同等條件下與經(jīng)典MOPSO和NSGA-II以及文獻(xiàn)[17]的實(shí)驗(yàn)結(jié)果對(duì)比，結(jié)果表明，提出的改進(jìn)算法能夠更好地保持種群多樣性的同時(shí)提高算法的收斂性。

1　粒子群算法基本原理

人們?cè)谘芯盔B(niǎo)群覓食行為時(shí)發(fā)現(xiàn)，鳥(niǎo)類可以通過(guò)記憶追蹤自己曾經(jīng)發(fā)現(xiàn)過(guò)食物的位置以及和整個(gè)群體分享個(gè)體信息，來(lái)協(xié)助整個(gè)種群快速搜尋到目標(biāo)物。從而提出粒子群優(yōu)化算法來(lái)解決優(yōu)化問(wèn)題[11]。這種借助群體的信息交流與信息共享機(jī)制來(lái)智能地求解優(yōu)化問(wèn)題已經(jīng)成為新的研究熱點(diǎn)。每個(gè)粒子代表解空間的一個(gè)解，通過(guò)參考自身個(gè)體的最優(yōu)位置和全局最優(yōu)位置不斷進(jìn)行速度和位置的更新，并根據(jù)適應(yīng)度函數(shù)來(lái)評(píng)估每個(gè)粒子位置信息的好壞，進(jìn)行有限次的迭代，使粒子逐漸地逼近優(yōu)化的目標(biāo)。

(1)

(2)

其中：r1和r2的取值范圍為(0，1)，均服從均勻分布；c1和c2是相應(yīng)的步長(zhǎng)限定因子，通常取[1.2，2.0]區(qū)間內(nèi)的常數(shù)，c1的取值決定粒子朝著個(gè)體最優(yōu)方向逼近的步長(zhǎng)，c2的取值決定粒子朝著全局最優(yōu)值方向逼近的步長(zhǎng)。式(1)的第1項(xiàng)為動(dòng)量項(xiàng)，慣性權(quán)值w決定對(duì)粒子搜尋過(guò)程中行進(jìn)速度的參考權(quán)重，采用w由大至小線性遞減的策略，可以漸進(jìn)地加強(qiáng)局部搜索的能力；第2項(xiàng)表示粒子參考自身的歷史迭代信息而更新速度的過(guò)程；第3項(xiàng)為粒子間信息共享與互動(dòng)的過(guò)程，粒子參考全局最優(yōu)位置來(lái)更新自身速度的過(guò)程。

種群粒子能夠參考行進(jìn)過(guò)程中個(gè)體路過(guò)的最優(yōu)位置和整個(gè)種群比較后的最優(yōu)位置來(lái)快速尋找目標(biāo)，這是粒子群算法的一大優(yōu)點(diǎn)，同時(shí)這種過(guò)快的收斂速度也容易破壞整個(gè)種群的多樣性，筆者在速度更新的時(shí)候加入小量擾動(dòng)，避免整個(gè)種群對(duì)最優(yōu)解的依賴性過(guò)強(qiáng)，后文詳細(xì)說(shuō)明。

隨著種群中粒子更新過(guò)程的遞進(jìn)，粒子的位置向量可能超過(guò)所限制的決策向量邊界范圍，針對(duì)這一問(wèn)題，將超過(guò)邊界位置的粒子暫時(shí)停留在邊界處，同時(shí)修改粒子的行進(jìn)方向，擺脫邊界。

2　改進(jìn)后的粒子群優(yōu)化算法

針對(duì)粒子群算法本身存在的一些缺陷，筆者提出了以下幾點(diǎn)改進(jìn)策略：

(1)采用分段Logistic混沌映射生成初始粒子種群[10]，增強(qiáng)初始粒子種群的隨機(jī)性，使初始化粒子能夠更均勻地分布在決策空間內(nèi)。

(2)修改種群粒子的更新策略，為了避免種群對(duì)粒子的個(gè)體性能和社會(huì)性能過(guò)分依賴而影響粒子的多樣性，在迭代過(guò)程中加入少量擾動(dòng)。

(3)把每個(gè)粒子的全局最優(yōu)值的選取和檔案維護(hù)相結(jié)合，將整個(gè)種群向Pareto前沿逼近的過(guò)程分為2個(gè)階段，分別適應(yīng)于不同階段，對(duì)非劣解進(jìn)行維護(hù)和篩選優(yōu)秀的非劣解指導(dǎo)整個(gè)種群的收斂。

(4)對(duì)外部檔案實(shí)施實(shí)時(shí)監(jiān)測(cè)機(jī)制，對(duì)于當(dāng)前迭代次數(shù)內(nèi)因?yàn)榉N群無(wú)法產(chǎn)生出更好的非劣解，而使得整個(gè)種群集中在歷史最優(yōu)解附近甚至收斂至極值點(diǎn)處的問(wèn)題做出了有效的解決。

2.1初始化粒子群

多目標(biāo)粒子群(Multi-objective Particle Swarm Optimization，MOPSO)有較強(qiáng)的初值敏感性。傳統(tǒng)的MOPSO采用的是在決策變量空間隨機(jī)生成與種群個(gè)數(shù)相對(duì)應(yīng)的隨機(jī)數(shù)，確定初始種群時(shí)雖然具備一定的隨機(jī)性，但是初始種群的分布較為散亂。為了使初始種群盡可能均勻地分布在全部決策空間內(nèi)，在不失初始種群粒子的隨機(jī)性上增加初始種群的分布性能，引入分段Logistic混沌映射在種群初始值的確定中[10]。

混沌映射的數(shù)學(xué)達(dá)式為：

(3)

其中，3.569 945 6…≤μ≤4，a0∈(0，1)。

a0在(0，1)范圍內(nèi)取值，服從均勻分布，根據(jù)a0的數(shù)值大小結(jié)合式(1)給出的范圍，選擇一種計(jì)算方式進(jìn)行計(jì)算，重復(fù)操作每1個(gè)粒子，直至達(dá)到種群數(shù)量的要求。

2.2全局最優(yōu)值的選取

迭代過(guò)程中粒子全局最優(yōu)值的選取和對(duì)外部存儲(chǔ)非劣解的檔案維護(hù)是MOPSO算法設(shè)計(jì)的2個(gè)重要部分。外部檔案的維護(hù)有2個(gè)關(guān)鍵點(diǎn)：第1是如何從外部檔案中篩選收斂性和多樣性表現(xiàn)較好的非劣解作為全局最優(yōu)值指導(dǎo)粒子朝更好的方向搜索，關(guān)鍵是對(duì)粒子的性能評(píng)判；第2是存儲(chǔ)非劣解的外部檔案如果超過(guò)預(yù)先設(shè)置的大小后，如何剔除收斂性和多樣性相對(duì)不好的非劣解。筆者利用柵格法和擁擠距離相互協(xié)調(diào)的方式共同調(diào)整外部檔案的非劣粒子的排列方式，從而選取相對(duì)性能更好的非劣粒子作為指導(dǎo)粒子。

在整個(gè)種群迭代過(guò)程的前期，外部檔案集里面存儲(chǔ)的非劣粒子相對(duì)較少，如何從稀疏的集合中篩選出收斂性和多樣性表現(xiàn)更好的粒子作為全局最優(yōu)解來(lái)指導(dǎo)種群收斂成為關(guān)鍵。假設(shè)待優(yōu)化的目標(biāo)有2個(gè)，分別記為f1和f2，則迭代過(guò)程前期外部檔案粒子分布狀況如圖1所示。

如果令C來(lái)存儲(chǔ)外部非劣解檔案中多樣性和收斂性能較好的粒子作為選取全局最優(yōu)值的候選集合，其中x4，x5，x6，x74個(gè)粒子多樣性表現(xiàn)較好，而對(duì)于前3個(gè)粒子來(lái)講，多樣性能差不多，x3距離原點(diǎn)最近，收斂性能更好，則候選集合C=[x3，x4，x5，x6，x7]。

采用網(wǎng)格法進(jìn)行分類，粒子x2，x3在同1個(gè)網(wǎng)格里，根據(jù)輪盤(pán)賭方式從該網(wǎng)格中選擇1個(gè)粒子，假設(shè)選擇的是x3，最終外部檔案NP中表現(xiàn)出多樣性較好的粒子候選集合C表現(xiàn)為：C=[x1，x3，x4，x5，x6，x7]，但是網(wǎng)格法操作起來(lái)有2個(gè)弊端：一是算法復(fù)雜度較高，運(yùn)算速度較慢；二是在算法的前期，數(shù)值收斂性能判斷不出來(lái)，依靠輪盤(pán)賭選擇的粒子具有一定的隨機(jī)性。同時(shí)由圖1可知，如果粒子數(shù)目較多，因?yàn)榫W(wǎng)格的關(guān)系，一些表現(xiàn)不好的非劣粒子因?yàn)楠?dú)自占有1個(gè)網(wǎng)格，同樣會(huì)被選取，而影響這個(gè)種群的收斂特性，并且粒子較多的時(shí)候就不能完全選擇出如上所示的粒子了。

常用的擁擠距離精英策略同樣存在一定的弊端，如圖1所示，粒子x5相鄰的2個(gè)粒子x4，x6，以x4，x6為2個(gè)對(duì)角頂點(diǎn)構(gòu)成正方形，則該正方形對(duì)角線長(zhǎng)度即為x5的擁擠距離值。那么根據(jù)擁擠距離降序排列則是[x1，x7，x6，x4，x5，x3，x2]，一般將邊界解設(shè)置為Inf，精英法則選取外部檔案大小的20%的粒子作為指導(dǎo)粒子，最終候選集合C=[x1，x7]，在迭代過(guò)程前期，外部檔案中粒子較少的情況下，傳統(tǒng)的采用基于精英擁擠距離策略來(lái)篩選全局最優(yōu)粒子顯然缺失多樣性。

在算法迭代初期，外部檔案存儲(chǔ)的粒子數(shù)目較少時(shí)，利用柵格法將粒子所在空間的一側(cè)均勻分成k個(gè)柵格，分割的目的和網(wǎng)格法相似，但是算法運(yùn)算復(fù)雜度會(huì)小很多，目的是將目標(biāo)函數(shù)所在區(qū)域空間均等劃分，如圖2所示。粒子x1，x2，x3在同一個(gè)柵格內(nèi)，多樣性指導(dǎo)方面，3個(gè)粒子的指導(dǎo)性相近，但是在收斂性方面，x3距離坐標(biāo)原點(diǎn)最近，收斂性能表現(xiàn)最強(qiáng)，所以選擇x3，其他粒子依次選擇為C=[x3，x4，x5，x6，x7]。這種方法設(shè)計(jì)簡(jiǎn)單，在粒子尋優(yōu)迭代前期，能夠以最快的速度篩選出最合適作為全局最優(yōu)值候選解的集合。

當(dāng)檔案中非劣粒子的數(shù)目達(dá)到數(shù)值K時(shí)，再使用上述篩選策略就存在一定的局限性，因?yàn)樵谖粗繕?biāo)問(wèn)題的前提下，1個(gè)柵格內(nèi)距離原點(diǎn)最近的粒子不一定足夠代表該粒子具有更好的收斂性能，當(dāng)1個(gè)柵格內(nèi)同時(shí)存在過(guò)多粒子時(shí)，選取方面就會(huì)產(chǎn)生較大障礙。因此使用擁擠距離評(píng)估法。由圖2可知，定義邊界粒子x1，x7的擁擠距離為這2個(gè)粒子分別到與他們各自相鄰那個(gè)粒子之間的歐氏距離，非邊界粒子的定義方式，如x5的擁擠距離定義方式，取x5分別到x4和x6的歐氏距離d54和d56，用d5代表x5的擁擠距離，則數(shù)學(xué)表達(dá)式為d5=(d54+d56)/2。這種定義方式運(yùn)算簡(jiǎn)便，并且能夠直觀準(zhǔn)確地表示1個(gè)粒子對(duì)于相鄰2個(gè)粒子的擁擠程度。邊界粒子的擁擠距離取Inf，會(huì)導(dǎo)致在根據(jù)擁擠距離排序時(shí)邊界粒子始終會(huì)被選擇成為指導(dǎo)粒子，并且在好幾代種群中都無(wú)法被替換掉，該定義方式能夠有效避免這一惡性循環(huán)。

2.3外部檔案維護(hù)

整個(gè)種群如果過(guò)分依賴全局最優(yōu)值，很快會(huì)收斂至全局最優(yōu)值附近，如果全局最優(yōu)值不能完全代表整個(gè)種群的多樣性性能，則這種過(guò)快收斂就會(huì)在一定程度上破壞種群的多樣性。筆者提出一種將外部檔案中未被選擇成為全局最優(yōu)值的粒子作為小量擾動(dòng)，加入到速度更新公式中，則速度更新公式為：

vi=wvi+c1r1(pi-xi)+c2r2(pg-xi)+

(4)

其中，c3r3(pd-xi)即是擾動(dòng)項(xiàng)，擾動(dòng)項(xiàng)太大，則會(huì)影響粒子的收斂，因此擾動(dòng)因子c3數(shù)值較小，定義范圍和c1，c2一樣。r3的取值在區(qū)間(0，1)范圍內(nèi)，并服從均勻分布。pd表示該項(xiàng)的擾動(dòng)粒子，外部檔案中的非劣解沒(méi)有被選成全局最優(yōu)值的粒子，利用輪盤(pán)賭的方式選擇1個(gè)作為擾動(dòng)粒子，以避免整個(gè)種群對(duì)歷史最優(yōu)解的過(guò)分依賴而導(dǎo)致的集群收斂。

隨著迭代過(guò)程的推進(jìn)，群體中產(chǎn)生的非劣解的數(shù)量也越來(lái)越多，外部檔案中存儲(chǔ)的非劣解的數(shù)量基數(shù)太大，收斂性能和多樣性性能表現(xiàn)相差無(wú)幾的粒子無(wú)法被淘汰掉，檔案中粒子冗余嚴(yán)重，因此需要對(duì)外部檔案進(jìn)行維護(hù)。筆者基于擁擠距離參數(shù)逐個(gè)淘汰機(jī)制來(lái)剔除檔案中表現(xiàn)不好的非劣解，以保證檔案中非劣解的質(zhì)量，如圖3所示。

由圖3(a)可知，假設(shè)當(dāng)前外部檔案中有7個(gè)粒子，如果外部檔案最大能容納粒子數(shù)為4，那么就需要剔除多余的粒子。如果檔案中按照擁擠距離排序，將擁擠距離數(shù)值排在末尾的粒子剔除掉，則維護(hù)完檔案后如圖3(b)所示，如果采用基于擁擠距離逐個(gè)淘汰機(jī)制來(lái)維護(hù)檔案，首先剔除擁擠距離值最小的x4，接著重新計(jì)算當(dāng)前檔案中各粒子的擁擠距離值，并排序后剔除排在末尾的粒子x2，重復(fù)上述操作，直至檔案大小滿足要求。最終結(jié)果如圖3(c)所示。從圖3可以清晰地看出，基于擁擠距離逐個(gè)淘汰機(jī)制的作用。

針對(duì)粒子陷入極值的狀況，筆者提出一種監(jiān)測(cè)選擇機(jī)制，具體過(guò)程如下：

Step1設(shè)NP為外部檔案，令NP的極限大小為nmax，當(dāng)前NP的大小為M，P為粒子群體。初始化外部檔案，比較初始粒子群中各個(gè)粒子的非劣關(guān)系，將非劣解存入外部檔案NP中；

Step2每次迭代更新NP過(guò)程中，取xi∈P，(i=1，…，N)，其中N為種群大小，比較xi與xj∈NP(j=1，…，M)的非劣關(guān)系，如果xi?xj，則xi加入NP，相應(yīng)的xj從NP中剔除；如果xj?xi，則i=i+1；如果兩者無(wú)支配關(guān)系，也將xi存入NP中。比較粒子支配關(guān)系過(guò)程中，目標(biāo)函數(shù)值相等的情況也將被加入外部檔案中，也就是說(shuō)，檔案里面允許相等的值同時(shí)存在；

Step3在更新檔案后，如果檔案中出現(xiàn)重復(fù)粒子，則判斷種群有陷入局部極值的可能性，設(shè)置陷入局部極值標(biāo)志位為1，否則為0。同時(shí)如果判斷有陷入局部極值的可能性，則在粒子更新位置和速度時(shí)導(dǎo)入第2套速度更新方案。即保留當(dāng)前種群70%的粒子，為保證公平性，這些粒子是隨機(jī)選擇的，同時(shí)再產(chǎn)生30%的新粒子混合進(jìn)入種群，增加種群的多樣性，從而在目標(biāo)空間產(chǎn)生更多的位置來(lái)輔助跳出局部極值。如果陷入局部極值標(biāo)志位為0，則正常更新粒子位置和速度；

Step4如果M>nmax，則采用基于擁擠距離逐個(gè)淘汰機(jī)制修剪檔案的大小，剔除表現(xiàn)不好的非劣解，確保檔案的有限性。

2.4IMOPSO算法流程

采用基于柵格和擁擠距離的協(xié)同外部檔案維護(hù)策略加速收斂，采用分段Logistic混沌映射、外部檔案監(jiān)測(cè)選擇機(jī)制及修改的粒子速度更新公式增強(qiáng)多樣性，得到的IMOPSO算法完整步驟如下：

Step1初始化算法的基本參數(shù)信息，使用分段Logistic混沌映射方法初始化粒子種群；

Step2計(jì)算種群的初始位置，以粒子當(dāng)前的位置作為個(gè)體初始最優(yōu)值，比較粒子之間的非劣關(guān)系，確定初始外部檔案NP，利用柵格法在NP中篩選每個(gè)粒子的初始全局最優(yōu)值gbest；

Step3判斷粒子陷入局部極值標(biāo)志位，如果為0，則通過(guò)式(4)更新粒子當(dāng)前的速度，通過(guò)式(2)更新粒子當(dāng)前的位置，判斷速度、位置信息是否超出所限制的邊界，做邊界限制，如果局部極值標(biāo)志位為1，則保留原先種群70%的原始粒子，導(dǎo)入30%的新粒子混合進(jìn)種群協(xié)同搜索；

Step4比較新一代粒子的位置信息，確定個(gè)體最優(yōu)值，如果新粒子的位置信息非劣于原個(gè)體最優(yōu)位置信息，則替換原個(gè)體最優(yōu)位置，否則不替換；

Step5比較新一代粒子和檔案中粒子的非劣性，添加更好的非劣粒子進(jìn)入檔案，同時(shí)剔除檔案中被支配的粒子。判斷外部檔案中當(dāng)前粒子數(shù)M是否小于K，如果是，則采用柵格法在外部檔案中篩選全局最優(yōu)值，如果否，則采用擁擠距離策略篩選全局最優(yōu)值，通過(guò)輪盤(pán)賭的方式選擇未成為全局最優(yōu)值的粒子成為擾動(dòng)量pd；

Step6基于擁擠距離逐個(gè)淘汰和監(jiān)測(cè)選擇機(jī)制維護(hù)外部檔案；

Step7判斷迭代次數(shù)是否滿足終止條件，如果滿足終止條件則算法結(jié)束，不滿足終止條件則跳轉(zhuǎn)Step3，繼續(xù)搜尋。

3　性能測(cè)試

為了驗(yàn)證改進(jìn)后算法的性能，利用經(jīng)典測(cè)試函數(shù)ZDT-1、ZDT-2和ZDT-3進(jìn)行仿真實(shí)驗(yàn)[15]，并與文獻(xiàn)[17]所提出算法的實(shí)驗(yàn)結(jié)果進(jìn)行比較。為了方便與文獻(xiàn)[17]中的算法做比較，令文獻(xiàn)[17]中的算法名稱為X，改進(jìn)算法定義為IMOPSO，目標(biāo)函數(shù)評(píng)價(jià)次數(shù)為25 000次，算法運(yùn)行30次。

3.1性能指標(biāo)

(1)世代距離(GD)是描述算法運(yùn)算求解得到的非劣解與目標(biāo)問(wèn)題的真實(shí)Pareto前沿之間距離的參數(shù)，數(shù)學(xué)表達(dá)式為[16]：

(5)

式中，di表示相應(yīng)的第i個(gè)粒子與真實(shí)Pareto前沿的最短距離。

(2)分布均勻度量(SP)是評(píng)價(jià)算法求解得到的Pareto最優(yōu)解集中分布性能好壞的一個(gè)參數(shù)。其數(shù)學(xué)表達(dá)式為：

(6)

3.2實(shí)驗(yàn)結(jié)果及分析

不同算法的GD和SP數(shù)值在3個(gè)測(cè)試函數(shù)上面的性能表現(xiàn)如表1所示，不同算法針對(duì)不同的測(cè)試函數(shù)的運(yùn)行時(shí)間如表2所示，改進(jìn)后粒子群算法針對(duì)3個(gè)測(cè)試函數(shù)的測(cè)試結(jié)果如圖4～圖6所示。

由表2可以看出，提出的改進(jìn)算法IMOPSO在運(yùn)行時(shí)間上與其他3種算法相比，收斂速度明顯加快，能夠以更快的速度逼近最優(yōu)Pareto前沿。分析表1中記錄的SP統(tǒng)計(jì)參數(shù)可以看出，對(duì)于ZDT-1和ZDT-2，IMOPSO的表現(xiàn)更好，ZDT-3則和文獻(xiàn)[17]提出的算法

表1　4種算法對(duì)比測(cè)試結(jié)果

表2　平均運(yùn)行時(shí)間　s

相差無(wú)幾，比傳統(tǒng)的MOPSO和NSGA-II有較大的變化，多樣性性能表現(xiàn)更好。分析GD指標(biāo)的均值和方差可以看出，在方差值相差不大，也就是穩(wěn)定性能表現(xiàn)良好的前提下，GD的數(shù)值IMOPSO要比文獻(xiàn)[17]提出的算法高1個(gè)數(shù)量級(jí)，比MOPSO和NSGA-II高1～2個(gè)數(shù)量級(jí)，證明IMOPSO的收斂性能表現(xiàn)更好。

4　結(jié)論

通過(guò)引入Logistic混沌映射初始化種群，改進(jìn)了基于非劣分類和密度距離淘汰機(jī)制，對(duì)外部檔案中的粒子進(jìn)行預(yù)判斷，有效避免了粒子陷入極值的狀況。根據(jù)外部檔案里的非劣粒子數(shù)量提出不同狀態(tài)下選取全局最優(yōu)值的方法，加快了種群的收斂速度。同時(shí)將檔案中未被選擇成為全局最優(yōu)解的粒子篩選出來(lái)成為擾動(dòng)項(xiàng)并加入粒子更新過(guò)程中，避免了種群對(duì)全局最優(yōu)解和個(gè)體最優(yōu)解的過(guò)分依賴而喪失多樣性。通過(guò)benchmark的仿真測(cè)試，證實(shí)了筆者提出的IMOPSO算法，在穩(wěn)定性、收斂速度和多樣性方面表現(xiàn)優(yōu)異。

[1]Steuer R E. Multiple criteria Optimization: Theory， Computation and Application[M]. New York: Wiley， 1986

[2]Kennedy J， Eberhart R. Particle swarm optimization[C]. IEEE International Conference on Neural Networks， 1995. Proceedings. 1995,4:1942-1948.

[3]Eberhart R， Kennedy J. A new optimizer using particle swarm theory[C]. International Symposium on MICRO Machine and Human Science, 1995:39-43.

[4]Parsopoulos K E， Vrahatis M N. Particle swarm optimization method in multiobjective problems[C]. ACM Symposium on Applied Computing, 2002:603-607.

[5]Mostaghim S， T eich J. The role ofε-dominance in multi-objective particle swarm optimization method[C]. Proc of the 2003 Congress on Evolutionary Computation. Canberra: IEEE， 2003:1764-1771.

[6]Coello C C A， Pulido G T， Lechunga M S. Handling multiple objectives with particle swarm optimization[J]. IEEE Trans on Evolutionary Computation， 2004，8(3):256-279.

[7]Tsai S J， Sun T Y， Liu C C， et al. An improved multi-objective particle swarm optimizer for multi-objective problems[J]. Expert Systems with Applications， 2010，37(8):5872-5886.

[8]賈樹(shù)晉，杜斌，岳恒.基于局部搜索與混合多樣性策略的多目標(biāo)粒子群算法[J].控制與決策，2012(6):813-818，826.

[9]黃敏，江渝，毛安，等.基于全局最優(yōu)位置自適應(yīng)選取與局部搜索的多目標(biāo)粒子群優(yōu)化算法[J].計(jì)算機(jī)應(yīng)用，2014(4)：1074-1079.

[10]范九倫，張雪鋒.分段Logistic混沌映射及其性能分析[J].電子學(xué)報(bào)，2009(4)：720-725.

[11]Kennedy J. The Particle Swarm: Social Adaptation of Knowledge[C]. Proceedings of IEEE International Conference on Evolutionary Computation， Indianapolis， Indiana， 1997.

[12]雷德明，吳智銘.Pareto檔案多目標(biāo)粒子群優(yōu)化[J].模式識(shí)別與人工智能，2006(4)：475-480.

[13]王亞輝，唐明奇. 多鄰域鏈?zhǔn)浇Y(jié)構(gòu)的多目標(biāo)粒子群優(yōu)化算法[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2015(1)：365-372，358.

[14]胡旺，Gary G. YEN，張?chǎng)?基于Pareto熵的多目標(biāo)粒子群優(yōu)化算法[J].軟件學(xué)報(bào)，2014(5)：1025-1050.

[15]Zitzler E， Deb K， Thiele L. Comparison of multiobjective evolutionary algorithms: empirical results[J]. Evolutionary Computation， 2000，8(2):173-195.

[16]Veldhuizen D A V， Lamont G B. Evolutionary computation and convergence to a pareto front[C]. Stanford University California， 1999:221-228.

[17]陶新民，徐鵬，劉福榮，等.一種組合粒子群和差分進(jìn)化的多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)仿真，2013(4)：313-316.

An Improved Multi-Objective Particle Swarm Optimization Algorithm

HE Qian1, DONG Yi-qun2, XU Wen-xing*2

(1.Beijing University of Chemical Technology， Beijing 100029， China;2.Beijing Institute of Petrochemical Technology， Beijing 102617， China)

An improved multi-objective particle swarm optimization algorithm is proposed to improve the convergence speed and diversity in the iterative process of multi objective particle swarm optimization algorithm. Based on grid and crowding distance collaborative external archive maintenance strategies, the algorithm utilizes the non-inferior particles which have more accurate selection of convergence and diversity of better performance as the global optimum value, to accelerate the speed of convergence of the whole population. By using the piecewise Logistic chaotic map, the external file detection mechanism and the modified particle velocity updating formula, the diversity of the population is enhanced during the initialization phase and the iteration process. Finally, the improved algorithm can quickly converge to the Pareto optimal front and maintain a good diversity by the simulation test of the standard test function.

multi objective optimization; particle swarm optimization algorithm; piecewise logistic chaotic map; crowding distance

2016-03-16

國(guó)家自然科學(xué)基金項(xiàng)目(61304217)；北京市教委科技項(xiàng)目(KM20150017003)。

何騫(1990—)，男，碩士研究生，研究方向?yàn)槎嗄繕?biāo)粒子群優(yōu)化算法，E-mail:heqian916@163.com。

TP18

A