多目標(biāo)pso算法綜述

1、<p>　　多目標(biāo)微粒群優(yōu)化算法研究</p><p>　　王艷1,2，曾建潮2</p><p>　　（1 蘭州理工大學(xué)電信工程學(xué)院 甘肅 蘭州730050）</p><p>　?。? 太原科技大學(xué)復(fù)雜系統(tǒng)和智能計(jì)算實(shí)驗(yàn)室 山西 太原 030024）</p><p>　　摘要：作為一種有效的多目標(biāo)優(yōu)化工具，微粒群優(yōu)化(PSO)算法已經(jīng)

2、得到廣泛研究與認(rèn)可。本文首先對多目標(biāo)優(yōu)化問題進(jìn)行了形式化描述，簡要介紹了微粒群優(yōu)化算法與遺傳算法的區(qū)別，并對多目標(biāo)微粒群優(yōu)化算法(MOPSO)進(jìn)行了分類，著重分析了各類算法的主要思想、特點(diǎn)及其代表性算法。其次，針對非支配解的選擇、外部檔案集的修剪、解集多樣性的保持以及微粒個(gè)體歷史最優(yōu)解和群體最優(yōu)解的選取等熱點(diǎn)問題進(jìn)行了詳細(xì)論述，并在此基礎(chǔ)上對各類典型算法進(jìn)行了比較。最后，根據(jù)當(dāng)前MOPSO算法的研究狀況，提出了該領(lǐng)域的發(fā)展方向。<

3、/p><p>　　關(guān)鍵詞： 多目標(biāo)優(yōu)化； 微粒群優(yōu)化算法；非支配解；外部檔案；多樣性</p><p>　　中圖分類號： TP301 文獻(xiàn)標(biāo)識碼：A</p><p>　　A Survey of Multi-Objective Particle Swarm Optimization Algorithm</p><p>　　WANG Yan1

4、,2, ZENG Jian-chao2</p><p>　　(1 College of Electrical and Information Engineering, Lanzhou University of Technology, Lanzhou 730050, China.)</p><p>　　(2 Complex System and Computational Intellig

5、ence Laboratory, Taiyuan University of Science and Technology, Taiyuan, 030024, China. Correspondent: ZENG Jian-chao, E-mail: zengjianchao@263.net)</p><p>　　Abstract As an effective multi-objective optimizer

6、, Particle Swarm Optimization (PSO) algorithms have been widely studied and approbated. This paper firstly described multi-objective problems formally and introduced the difference between PSO and Genetic Algorithm (GA).

7、 Then a classification of multi-objective PSO (MOPSO) algorithms was presented and the main idea, features and representative algorithms of each approach were analyzed. Secondly, such hot topics in MOPSO algorithms as se

8、lecting no</p><p>　　Key words multi-objective optimization; particle swarm optimization; nondominated solutions; archive; diversity</p><p><b>　　1引言</b></p><p>　　在科學(xué)實(shí)踐、工程

9、系統(tǒng)設(shè)計(jì)及社會(huì)生產(chǎn)活動(dòng)中，許多問題都是多目標(biāo)優(yōu)化問題。通常多目標(biāo)優(yōu)化問題中的各個(gè)目標(biāo)函數(shù)之間可能會(huì)存在沖突，這就意味著多目標(biāo)優(yōu)化問題不存在唯一的全局最優(yōu)解，使得所有目標(biāo)函數(shù)同時(shí)達(dá)到最優(yōu)。為了達(dá)到總目標(biāo)的最優(yōu)化，需要對相互沖突的目標(biāo)進(jìn)行綜合考慮，對各子目標(biāo)進(jìn)行折衷。最初，多目標(biāo)優(yōu)化問題往往通過加權(quán)等方式轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，但這樣需要事先知道每個(gè)目標(biāo)函數(shù)所占的權(quán)重，并且對目標(biāo)給定的次序也比較敏感。</p><p>

10、　　微粒群優(yōu)化(PSO)算法是1995年由Kennedy和Eberhart提出的一種基于群體智能的優(yōu)化算法，應(yīng)用于單目標(biāo)優(yōu)化問題時(shí)表現(xiàn)出了快速收斂的特點(diǎn)。隨著對PSO研究的深入，該算法已經(jīng)由用來解決單目標(biāo)優(yōu)化問題逐步拓展到用來解決多目標(biāo)優(yōu)化問題。1999年Moore 和Chapman首次提出將PSO算法應(yīng)用于解決多目標(biāo)優(yōu)化問題[1]，但這個(gè)思想未公開發(fā)表，從此后用PSO解決多目標(biāo)優(yōu)化問題開始得到研究人員的關(guān)注，但直到2002年Coell

11、o等和Ray等先后發(fā)表了多目標(biāo)微粒群優(yōu)化算法（MOPSO）的論文[2,3]，繼之多目標(biāo)微粒群優(yōu)化算法逐漸被研究者們重視，出現(xiàn)了大量研究成果[1-9]。</p><p>　　縱觀國內(nèi)外該領(lǐng)域的研究情況，國外Sierra and Coello在2006年發(fā)表了該領(lǐng)域的較為全面的綜述[4]，但主要是針對2005年以前的MOPSO算法，那時(shí)MOPSO算法的研究剛剛起步不久，研究成果并不是很多。而國內(nèi)該領(lǐng)域的綜述非常少[1

12、0]，并且只是簡單從算法設(shè)計(jì)和應(yīng)用方面回顧了其研究進(jìn)展，所以有必要對該領(lǐng)域進(jìn)行一個(gè)較為全面的介紹。</p><p>　　2 多目標(biāo)優(yōu)化問題的數(shù)學(xué)描述</p><p>　　(1) 多目標(biāo)優(yōu)化問題的形式化描述</p><p><b>　?。?）</b></p><p>　　其中，決策向量，目標(biāo)向量，是目標(biāo)函數(shù)，gi(X)0和

13、hi(X)＝0是約束條件。</p><p>　　Pareto最優(yōu)解集和Pareto最優(yōu)邊界</p><p>　　定義1. 個(gè)體間的支配關(guān)系：設(shè)p和q是進(jìn)化群體pop中的任意兩個(gè)不同的個(gè)體，稱p支配q，則必須滿足下列兩個(gè)條件：</p><p>　?、賹λ械淖幽繕?biāo)，p不比q差，即fi(p)≤fi(q), i=1,2,…k；</p><p>　　

14、②至少存在一個(gè)子目標(biāo)使p比q好，即。</p><p>　　其中k為子目標(biāo)的數(shù)量，此時(shí)p為非支配的，q為被支配的，定義為，“”表示支配關(guān)系。</p><p>　　定義2. Pareto最優(yōu)解集：對于決策空間中的向量，F(xiàn)是搜索區(qū)域，若在F區(qū)域內(nèi)，X*是非支配的，則X*是F內(nèi)的一個(gè)Pareto最優(yōu)解。由搜索空間中所有Pareto最優(yōu)解組成的解集就稱為Pareto最優(yōu)解集，即。</p>

15、<p>　　定義3. Pareto最優(yōu)邊界：Pareto最優(yōu)解表現(xiàn)在目標(biāo)空間上就是Pareto最優(yōu)邊界，或稱為Pareto前沿（Pareto front），即。</p><p>　　3 微粒群優(yōu)化(PSO)算法</p><p>　　PSO算法是一種基于種群的啟發(fā)式優(yōu)化算法，由于其參數(shù)設(shè)置少，實(shí)現(xiàn)簡單，決策變量是實(shí)數(shù)，收斂速度快等特點(diǎn)，使其得到充分研究。標(biāo)準(zhǔn)PSO算法的運(yùn)動(dòng)方程

16、[11]如下：</p><p><b>　　(2)</b></p><p><b>　　(3)</b></p><p>　　其中w為慣性權(quán)重，c1、c2為加速常數(shù)，r1、r2表示區(qū)間[0,1]內(nèi)均勻分布的隨機(jī)數(shù)。 Pi為粒子自身經(jīng)歷的最好歷史位置，而 Pg為粒子所對應(yīng)的全局最好位置，它是整個(gè)群體所經(jīng)歷的最好位置。 Xi(t

17、)與 Vi(t)為微粒i在時(shí)刻t的位置與速度。公式(2)表示微粒速度由3部分決定：慣性部分、認(rèn)知部分和社會(huì)部分，它們共同改變微粒飛行速度，但速度會(huì)受到最大速度 Vmax的限制。</p><p>　　PSO算法與遺傳算法不同，在PSO算法運(yùn)行過程中，沒有選擇或變異操作，因而種群的規(guī)模是固定的，微粒不會(huì)被舍棄與替換，被替換的是迄今為止微粒經(jīng)歷的歷史最好位置(稱為個(gè)體極值，用pbest表示)和群體的最好位置(稱為全局極

18、值，用gbest表示)，種群中所有微粒的調(diào)整均依賴于pbest和gbest的值。所以將PSO算法引入來解決多目標(biāo)優(yōu)化問題時(shí)，pbest和gbest的選取非常重要，而這在多目標(biāo)進(jìn)化算法的設(shè)計(jì)中是沒有的。</p><p>　　4 多目標(biāo)微粒群算法分類</p><p>　　多目標(biāo)微粒群算法大致可以分為以下幾類：聚集函數(shù)法、基于目標(biāo)函數(shù)排序法、子群法、基于Pareto支配算法和其他方法。</

19、p><p><b>　　(1) 聚集函數(shù)法</b></p><p>　　聚集函數(shù)法是解決多目標(biāo)優(yōu)化問題的一種最直接的方法，基本思想就是將多目標(biāo)優(yōu)化問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題。聚集函數(shù)可以是線性的，也可以是非線性的，當(dāng)聚集函數(shù)是線性時(shí)往往無法搜索到非凸解，當(dāng)聚集函數(shù)是非線性的時(shí)候就可以解決這個(gè)問題了[12]。在這種方法中較具有代表性的研究是文獻(xiàn)[8],[13]和[14]。&l

20、t;/p><p>　　文獻(xiàn)[8]分析了固定權(quán)重、突變權(quán)重和動(dòng)態(tài)權(quán)重這三種權(quán)重聚集方法。固定權(quán)重在優(yōu)化過程中權(quán)重是固定不變的，但計(jì)算量很大，并且無法找到非凸解。突變權(quán)重和動(dòng)態(tài)權(quán)重可以克服這個(gè)缺點(diǎn)，只是突變權(quán)重一般是周期函數(shù)的復(fù)合函數(shù)，變化比較頻繁，變化的尺度由周期函數(shù)的外層函數(shù)決定。動(dòng)態(tài)權(quán)重在突變權(quán)重的基礎(chǔ)上將復(fù)合函數(shù)變成了周期函數(shù)的絕對值函數(shù)，這樣變化的尺度相對突變權(quán)重要緩和一些。</p><p&

21、gt;　　文獻(xiàn)[13]使用了一種線性權(quán)重聚集法。在這類方法中，整個(gè)群體被平均分成了若干個(gè)子群體，每個(gè)子群體被賦予不同的權(quán)重，每個(gè)子群體中的微粒都朝著自己所處子群中的最優(yōu)解“飛行”，然后通過線性權(quán)重進(jìn)行聚集，得到總目標(biāo)下群體全局最優(yōu)微粒。</p><p>　　文獻(xiàn)[14]使用了一種類似于權(quán)重聚集的方法。首先找到在每個(gè)目標(biāo)下群體的全局極值和每個(gè)微粒在每個(gè)目標(biāo)下的個(gè)體極值，然后用各目標(biāo)下全局極值的均值作為整個(gè)群體在總目

22、標(biāo)下的全局極值，并通過判斷每個(gè)微粒在每個(gè)目標(biāo)下相對于該目標(biāo)下全局極值的離散程度來選取該粒子在總目標(biāo)下的個(gè)體極值。</p><p>　　以上三種方法都比較簡單，容易實(shí)現(xiàn)。但是算法每迭代一次只能產(chǎn)生一個(gè)“最優(yōu)解”，所以要得到接近PFTrue的Pareto front則需要的迭代次數(shù)較大，從而帶來的計(jì)算量就會(huì)較大。并且這三種方法都沒有很好地體現(xiàn)出Pareto支配的概念，沒有精英解保留機(jī)制，這樣使解的質(zhì)量受到影響。<

23、;/p><p>　　(2) 基于目標(biāo)函數(shù)排序方法</p><p>　　在這種方法中目標(biāo)函數(shù)通常要根據(jù)某個(gè)標(biāo)準(zhǔn)進(jìn)行排序，然后按照此順序?qū)δ繕?biāo)函數(shù)進(jìn)行優(yōu)化。比較具有代表性的方法是Hu and Eberhart的動(dòng)態(tài)鄰域策略[15]及其擴(kuò)展[9]。前者主要針對兩個(gè)目標(biāo)函數(shù)在環(huán)形鄰域上進(jìn)行的優(yōu)化，沒有采用外部存儲(chǔ)體保存精英個(gè)體，后者在前者的基礎(chǔ)上引入了精英解的保留機(jī)制。這類方法的主要思想是首先根據(jù)第一

24、個(gè)目標(biāo)來計(jì)算當(dāng)前考查微粒與其他微粒的距離，并根據(jù)距離建立若干個(gè)鄰域，然后根據(jù)第二個(gè)目標(biāo)函數(shù)選取鄰域最優(yōu)解。</p><p>　　這類方法中目標(biāo)函數(shù)的順序是非常重要的，并且這種方法處理的目標(biāo)函數(shù)往往較少。</p><p><b>　　(3) 子群法</b></p><p>　　這類方法的基本思想是將整個(gè)群體劃分為若干個(gè)子群，每個(gè)子群中進(jìn)行單目標(biāo)優(yōu)

25、化，然后通過子群間交換信息或?qū)⒆尤盒畔⒔M合來產(chǎn)生群體的最優(yōu)解。比較具有代表性的方法有Parsopoulos等的[8]及其改進(jìn)算法VEPSO[16]，張利彪等的[17]。</p><p>　　文獻(xiàn)[8]針對兩個(gè)優(yōu)化函數(shù)的多目標(biāo)優(yōu)化問題提出了用兩個(gè)子群體分別進(jìn)行單目標(biāo)優(yōu)化，然后把第一個(gè)子群得到的最優(yōu)解作為第二個(gè)子群更新速度的全局最優(yōu)解，將第二個(gè)子群的最優(yōu)解作為第一個(gè)子群更新速度的全局最優(yōu)解。[16]將此思想進(jìn)行改進(jìn)，

26、把每一維目標(biāo)作為一個(gè)子群，每個(gè)子群進(jìn)行單目標(biāo)優(yōu)化得到最優(yōu)解，并將其作為鄰接子群更新速度的全局最優(yōu)解。</p><p>　　文獻(xiàn)[17]對兩個(gè)目標(biāo)函數(shù)同時(shí)進(jìn)行優(yōu)化，根據(jù)多目標(biāo)優(yōu)化問題的特點(diǎn)將進(jìn)化群體劃分為第一個(gè)目標(biāo)下的全優(yōu)，第一個(gè)目標(biāo)下的半優(yōu)，第二個(gè)目標(biāo)下的全優(yōu)，第二個(gè)目標(biāo)下的半優(yōu)以及兩個(gè)目標(biāo)下的全劣這幾個(gè)子群體。然后根據(jù)支配關(guān)系找出每個(gè)子群體中的全局最優(yōu)個(gè)體，它們構(gòu)成一個(gè)非支配集，從中選出群體的全局最優(yōu)解。<

27、;/p><p>　　文獻(xiàn)[18]利用Pareto支配確定微粒的“飛行”方向，采用聚類的方法將微粒群分為幾個(gè)子群，每個(gè)子群體產(chǎn)生非支配解集，從其中隨機(jī)選擇一個(gè)作為每個(gè)子群執(zhí)行PSO算法時(shí)的全局最優(yōu)解，子群間通過移植不同子群中的非支配解交換信息。</p><p>　　(4) 基于Pareto的方法</p><p>　　現(xiàn)在的大多數(shù)研究主要集中于這種方法，借鑒以前用進(jìn)化算法解

28、決多目標(biāo)優(yōu)化問題的一些成功經(jīng)驗(yàn)，在進(jìn)化過程中經(jīng)常保持兩個(gè)群體，一個(gè)是進(jìn)化的基本種群population，另一個(gè)是用來存儲(chǔ)進(jìn)化過程中的精英個(gè)體的群體archive。首先通過evaluate來確定基本種群中個(gè)體的優(yōu)劣，然后通過確定基本種群的全局最優(yōu)個(gè)體和每個(gè)個(gè)體的歷史最好位置，利用PSO公式進(jìn)行更新，得到下一代基本群體。對archive一般要進(jìn)行兩種操作：update和truncate，前者用來更新archive中的個(gè)體保持為進(jìn)化中的最優(yōu)個(gè)

29、體，后者是當(dāng)要進(jìn)入archive中實(shí)際個(gè)體的數(shù)目大于archive容量時(shí)，對其中個(gè)體進(jìn)行修剪剔除。</p><p>　　通常具有精英解保留機(jī)制的MOPSO算法偽碼如圖1所示，其中Quality (pbest)或Quality (gbest)是指個(gè)體歷史最優(yōu)位置的選取和種群全局最優(yōu)微粒的選取。Mutation是可以選擇的，用來對微粒進(jìn)行變異，以保持基本種群的多樣性。</p><p>　　圖1

30、 MOPSO算法框架</p><p>　　該類方法中，比較具有代表性的算法有Coello等提出的MOPSO[2][5]以及后來研究者對其進(jìn)行的改進(jìn)[18][19][20][21]。</p><p>　　MOPSO算法是基于PSO求解多目標(biāo)優(yōu)化問題中最經(jīng)典的算法，在這個(gè)算法中Coello等首次提出了除基本微粒群引入第二個(gè)群體來保存生成的非支配解，并第一次用（超）網(wǎng)格來保存精英解。[5]是對[

31、2]的改進(jìn)，將原來固定的（超）網(wǎng)格變?yōu)樽赃m應(yīng)（超）網(wǎng)格，并使用了變異算子來更新種群微粒和決策變量的范圍，變異尺度與進(jìn)化代數(shù)成比例。這種方法成為后來研究者們改進(jìn)的基礎(chǔ)，也是研究者們對比算法優(yōu)劣的重要參照。</p><p>　　[19]在[2]的基礎(chǔ)上借鑒SPEA2[22]算法中環(huán)境選擇和配對選擇策略，并使用了密度估計(jì)技術(shù)，提高了解的多樣性和搜索精度。但該算法中有三個(gè)群體，計(jì)算量較大。</p><

32、p>　　[20]在[2]的基礎(chǔ)上對算法進(jìn)行了兩方面的改進(jìn)：①算法迭代到一定次數(shù)時(shí)對某個(gè)重要目標(biāo)進(jìn)行單目標(biāo)優(yōu)化，以此來解決MOPSO中出現(xiàn)的難以找到邊界點(diǎn)的問題；②對超出邊界的位置變量用一個(gè)隨機(jī)數(shù)來取代。這兩方面的改進(jìn)主要提高了Pareto解集的分布性，但要求事先知道各優(yōu)化目標(biāo)的重要程度。</p><p>　　[21]對[5]中的自適應(yīng)網(wǎng)格進(jìn)行了改進(jìn)，加入了非支配解集中微粒密度估計(jì)信息，在剔除密度較大網(wǎng)格中微

33、粒的時(shí)候，確定了需要剔除的微粒的數(shù)量，給出了計(jì)算公式。并且該算法在全局最優(yōu)解的選取方式上也進(jìn)行了改進(jìn)。</p><p><b>　　(5) 其他方法</b></p><p>　　文獻(xiàn)[23]提出了一種新的多目標(biāo)微粒群算法：EMOPSO，該算法在MOEA的基礎(chǔ)上進(jìn)行了修改。對非支配解集分布性的保持提出了一種新穎的”hyper-plane”方法，該方法在[5]中超網(wǎng)格的基

34、礎(chǔ)上，針對兩個(gè)目標(biāo)函數(shù)首先找到每一個(gè)目標(biāo)的最小值A(chǔ)和B，然后將這兩點(diǎn)用直線連接，如果需要找到n個(gè)非支配解，則在此線段上均勻地再選擇(n-1)個(gè)點(diǎn)，接著在這(n-1)個(gè)點(diǎn)上作直線AB的垂直線，非支配解中距離此垂直線最近的點(diǎn)被選中，其余各點(diǎn)被刪除。此算法為了避免早熟收斂而加入了擾動(dòng)因子，隨著迭代次數(shù)的增加，擾動(dòng)因子逐漸減小。此算法對約束處理方法以及參數(shù)自適應(yīng)調(diào)整等方面都進(jìn)行了研究。</p><p>　　對于上述所分析

35、的MOPSO算法及其特征如表1所示。</p><p>　　表1 經(jīng)典MOPSO算法及其特征</p><p>　　5 多目標(biāo)微粒群算法研究熱點(diǎn)</p><p>　　用PSO解決多目標(biāo)優(yōu)化問題往往借鑒多目標(biāo)進(jìn)化算法中的成功經(jīng)驗(yàn)，但MOPSO既不同于MOEA，又不同于用PSO解決單目標(biāo)優(yōu)化問題，當(dāng)前對MOPSO算法的研究一般圍繞以下研究熱點(diǎn)進(jìn)行：如何選擇非支配解、如何剔除

36、archive集中的個(gè)體以保持其良好的分布性、如何保持解集多樣性和gbest和pbest如何選取等。</p><p>　　（1） 非支配解的選擇</p><p>　　對于這個(gè)問題的研究涉及到傳統(tǒng)Pareto支配的概念及后來研究者們對其發(fā)起的挑戰(zhàn)?，F(xiàn)有的大多數(shù)研究都是基于傳統(tǒng)Pareto支配機(jī)制的，即個(gè)體支配機(jī)制。2002年，Laumanns and Deb等提出ε－支配[24]概念后其思想

37、被借鑒與改進(jìn)，2003年Mostaghim等[25]將其引入到MOPSO算法中。ε－支配是一種基于格子的支配機(jī)制，格子的邊長為ε，所以ε決定格子的數(shù)目和大小。每個(gè)格子內(nèi)只允許有一個(gè)解，這樣支配的概念由原來個(gè)體間的比較轉(zhuǎn)化為格子間的比較，后來的研究中人們在選取非支配解時(shí)有些采用或改進(jìn)了ε－支配的概念。文獻(xiàn)[26]為了保持解集良好的分布性，針對原有ε－支配可能會(huì)丟失邊界點(diǎn)的情況提出了強(qiáng)ε－支配概念，在原有ε－支配概念的基礎(chǔ)上又加入了個(gè)體支配

38、的概念。</p><p>　?。?） archive集的修剪</p><p>　　當(dāng)前MOPSO算法中絕大多數(shù)都用到了容量受限的archive集來保存精英解，所以一般要對archive集進(jìn)行修剪，剔除掉一部分非支配解，archive集中的結(jié)果就是將來要輸出的解，所以在剔除的過程中要考慮到多目標(biāo)優(yōu)化問題的特點(diǎn)，研究者們一般在這個(gè)階段考慮較多的是如何剔除archive集中的個(gè)體，保持解集良好的

39、分布性。通常采用的方法有：隨機(jī)選擇[27]，小生鏡技術(shù)[28][29]，網(wǎng)格技術(shù)[2][5][7][21]，擁擠距離[30][31][32][33]，密度熵[34]，聚類技術(shù)[23][35][36]等。</p><p>　　隨機(jī)選擇。這類方法的基本思想是將算法迭代過程中產(chǎn)生的非支配解存放于archive集中，當(dāng)非支配解的個(gè)數(shù)超過archive的容量時(shí)隨機(jī)地刪除archive集中的部分個(gè)體。這種修剪方法簡單，容易實(shí)

40、現(xiàn)，但沒有充分考慮解集的分布性。</p><p>　　小生鏡技術(shù)。這類方法一般通過小生鏡技術(shù)給archive集中的非支配解分配適應(yīng)度值，聚集程度越大的微粒適應(yīng)度越小。當(dāng)非支配解個(gè)數(shù)超出archive集的容量時(shí)，則刪除其中適應(yīng)度最小的部分個(gè)體。這種修剪方法可以提高解集的分布性，但需要小生鏡半徑的先驗(yàn)信息，計(jì)算復(fù)雜度較大。</p><p>　　網(wǎng)格技術(shù)?，F(xiàn)有的MOPSO算法很大一部分是在Coe

41、llo等的MOPSO算法[5]基礎(chǔ)上改進(jìn)的，而這個(gè)算法就是使用網(wǎng)格來保存非支配解的，所以現(xiàn)有很多算法都采用這種方法來保存和修剪archive集。這類方法的基本思想就是當(dāng)非支配解個(gè)數(shù)大于archive容量時(shí)，根據(jù)網(wǎng)格中微粒的數(shù)量來決定刪除哪些微粒。</p><p>　　擁擠距離。近年來使用這類方法修剪archive集的算法越來越多。這類方法的基本思想就是通過archive集中個(gè)體的擁擠距離來判斷解之間的疏密程度，在

42、對archive集進(jìn)行修剪時(shí)，擁擠距離大的微粒被保留下來，擁擠距離小的微粒被刪除。</p><p>　　密度熵。這類方法具有一定的特點(diǎn)，但在MOPSO中并不多見。其基本思想就是定義一個(gè)影響函數(shù)來衡量archive集中每兩個(gè)微粒間的相似程度，而archive中微粒的密度是周圍微粒對其影響因子的聚集。當(dāng)每個(gè)微粒的密度熵確定后，找出微粒中密度最大的進(jìn)行刪除。這類方法中archive集更新時(shí)計(jì)算復(fù)雜度為o（MN2），M為

43、子目標(biāo)個(gè)數(shù)，N為archive集大小。</p><p>　　聚類技術(shù)。這類修剪archive集的方法是借鑒于多目標(biāo)進(jìn)化算法的一種技術(shù)，其基本思想是在算法的每一次迭代過程中，通過聚類方法將整個(gè)archive集中的非支配解分成若干個(gè)聚類，當(dāng)聚類的個(gè)數(shù)超過一定數(shù)量時(shí)將距離最近的兩個(gè)聚類合并，將合并后的中心點(diǎn)作為新類的位置。</p><p>　?。?） 保持解集多樣性</p><

44、;p>　　PSO算法最突出的一個(gè)特點(diǎn)就是收斂速度快，但這個(gè)特點(diǎn)同時(shí)也帶來了算法早熟收斂的問題。為了增加解的多樣性，避免早熟收斂，將PSO應(yīng)用于解決多目標(biāo)優(yōu)化問題時(shí)往往借鑒多目標(biāo)進(jìn)化算法中的變異算子，有的MOPSO算法對微粒進(jìn)行變異的同時(shí)對決策變量的范圍進(jìn)行變異，有的研究采用對“飛”出可行域的微粒進(jìn)行重新初始化的方法來保持非支配解集中解的多樣性。</p><p>　　文獻(xiàn)[5]提出了一種使用變異因子來更新基本

45、種群中微粒和決策變量范圍的方法。該方法在搜索開始時(shí)對所有微粒進(jìn)行變異，隨著迭代次數(shù)的進(jìn)行，種群中變異的微粒數(shù)量迅速下降，對每個(gè)決策變量范圍也采用同樣操作。這樣，算法可以有一個(gè)很強(qiáng)的搜索能力，隨著迭代次數(shù)的增加，變異算子的作用逐漸減小，從而避免了算法早熟。文獻(xiàn)[32]也采用了同樣的方法來保持解的多樣性。</p><p>　　文獻(xiàn)[28][31]使用了小概率隨機(jī)變異的方法來保持解集的多樣性。這類方法的基本思想是在基本

46、種群每次迭代的過程中隨機(jī)選擇（或從被支配解中選）很少一部分（例如變異概率為5％）微粒進(jìn)行變異，這樣以增強(qiáng)算法的全局搜索能力。</p><p>　　文獻(xiàn)[20]對超出邊界的微粒不用傳統(tǒng)方法中將其拉至邊界的處理方式，而是用一個(gè)可行域內(nèi)的隨機(jī)數(shù)將其替代，這樣以增加解的多樣性。</p><p>　?。?） pbest和gbest的選取</p><p>　　在PSO算法中，微

47、粒是在種群全局最優(yōu)位置gbest及個(gè)體歷史最優(yōu)位置pbest的指導(dǎo)下“飛行”的。將PSO算法應(yīng)用于解決多目標(biāo)優(yōu)化問題時(shí)，每次迭代不再是僅僅產(chǎn)生一個(gè)單個(gè)的pbest值和gbest值，而是一組非支配解，如何選擇合適的pbest和gbest來指導(dǎo)種群中微粒的“飛行”就顯得非常重要了。</p><p>　　通常對于pbest的選取一般都基于Pareto支配概念，新產(chǎn)生的pbest與原來的pbest進(jìn)行比較，選擇非支配者作

48、為算法迭代中的pbest，若二者不存在支配關(guān)系，則隨機(jī)選擇其中之一即可。但也有算法根據(jù)所支配的群體中微粒的個(gè)數(shù)來選擇[35]。</p><p>　　gbest的選取是MOPSO算法設(shè)計(jì)中的關(guān)鍵，gbest的選取在很大程度上與archive集的修剪及更新方式相關(guān)。gbest選取最簡單最直接的方法就是從archive集中隨機(jī)選取一個(gè)微粒作為基本種群更新的全局最優(yōu)解[7][34][37]。文獻(xiàn)[28]采用輪盤賭概率方法

49、從archive中選取精英微粒作為gbest，文獻(xiàn)[30]通過隨機(jī)從archive中選取兩個(gè)微粒，從多個(gè)目標(biāo)函數(shù)中隨機(jī)選取一個(gè)目標(biāo)進(jìn)行比較的方法來選取gbest。張利彪等[14]使用最優(yōu)解評估選取的方式來選擇種群更新的gbest，文獻(xiàn)[38]也使用了這種方法。</p><p>　　現(xiàn)有MOPSO算法中，gbest的選取除了隨機(jī)選擇外通過密度信息來進(jìn)行選擇的較多。文獻(xiàn)[2][5]使用（超）網(wǎng)格中微粒的密度信息，密度

50、小者優(yōu)先的方法來選取gbest，后來在其算法基礎(chǔ)上進(jìn)行改進(jìn)的一些算法一般沿用了這種方式，或?qū)ζ渖宰髡{(diào)整[21]。</p><p>　　還有其他的一些選取gbest的方法。[26]使用了一種極值變異的方法來選擇gbest，首先從archive中隨機(jī)選擇一個(gè)非支配解，然后將此解與當(dāng)前gbest比較，較好者作為此次迭代的gbest，若兩者一樣好，則根據(jù)極值變異概率來決定gbest是否需要重新從archive中隨機(jī)選擇。

51、[35]將距離當(dāng)前微粒最近的archive集中的非支配解作為更新群體所用的gbest。</p><p><b>　　6 總結(jié)與展望</b></p><p>　　本文首先介紹了多目標(biāo)優(yōu)化問題的形式化描述及相關(guān)概念，然后簡要介紹了微粒群算法及其與傳統(tǒng)遺傳進(jìn)化算法的區(qū)別。接著對MOPSO進(jìn)行了分類，分析了各類算法的基本思想以及每類算法中的典型算法。最后對當(dāng)前MOPSO算法的

52、四個(gè)研究熱點(diǎn)進(jìn)行了討論。雖然MOPSO算法從出現(xiàn)至今不足十年，但其發(fā)展是非常迅猛的，在今后的研究中以下幾個(gè)方向應(yīng)該引起研究者們的重視。</p><p>　　如何用PSO算法處理高維(m>5)多目標(biāo)優(yōu)化問題。對于高維多目標(biāo)優(yōu)化問題想要找到一組合適的Pareto最優(yōu)解是很困難的，許多在處理低維數(shù)目標(biāo)時(shí)不會(huì)出現(xiàn)的問題就會(huì)凸現(xiàn)出來[39]，空間復(fù)雜度，時(shí)間復(fù)雜度以及選擇壓力等都將是需要重點(diǎn)考慮的問題。如何用PSO解

53、決高維多目標(biāo)優(yōu)化問題將是研究者們未來一段時(shí)間研究的內(nèi)容之一。</p><p>　　MOPSO算法自適應(yīng)參數(shù)的選擇?，F(xiàn)在MOPSO算法對處理單目標(biāo)優(yōu)化問題的PSO算法中的參數(shù)沒有作太大調(diào)整，但多目標(biāo)優(yōu)化問題與單目標(biāo)優(yōu)化問題的特征相差較大，如何根據(jù)多目標(biāo)優(yōu)化問題自身的特點(diǎn)來自適應(yīng)調(diào)整MOPSO參數(shù)，這方面的研究已經(jīng)開始，估計(jì)將會(huì)成為今后一段時(shí)間研究的另一個(gè)熱點(diǎn)。</p><p>　　有效的算法

54、停止準(zhǔn)則。現(xiàn)有的MOPSO算法中，絕大多數(shù)算法都是通過預(yù)先設(shè)置迭代次數(shù)來停止算法，因?yàn)樗惴ㄟM(jìn)化到哪一代就達(dá)到最優(yōu)往往是無法判斷的。在單目標(biāo)PSO算法中，當(dāng)gbest在一定代數(shù)內(nèi)不再變化就可以認(rèn)為算法已經(jīng)收斂到了最優(yōu)解，可以停止迭代。但這種策略是不能直接應(yīng)用于MOPSO，因?yàn)樵谒惴ǖ膱?zhí)行過程中很少會(huì)出現(xiàn)這種情況，即使有部分解與上一代相同，但多少個(gè)解相同就能說明算法已經(jīng)收斂于Pareto front，至今還沒有這方面的證明。</p&g

55、t;<p>　　參考文獻(xiàn)（References）</p><p>　　[1]Jacqueline Moore and Richard Chapman. Application of particle swarm to multi-objective optimization. Department of Computer Science and Software Engineering, Aubur

56、n University, 1999</p><p>　　[2]Carlos A. Coello Coello and Maximino Salazar Lechuga. MOPSO: A Proposal for Multiple Objective Particle Swarm Optimization. [C] In Congress on Evolutionary Computation (CEC’200

57、2), volume 2:1051-1056, Piscataway, New Jersey, May 2002, IEEE Service Center.</p><p>　　[3]Tapabrata Ray, Tai Kang and Seow Kian Chye. Multi-objective Design Optimization by and Evilutionary Algorithm.[J] En

58、gineering Optimization, 2002.</p><p>　　[4] Margarita Reyes-Sierra and Carlos A. Coello Coello. Multi-Objective Particle Swarm Optimizers: A Survey of the State-op-the-Art [J] International Journal of Computa

59、tional Intelligence Research. 2006, 2(3): 287-308.</p><p>　　[5] Carlos A. Coello Coello, Gregorio Toscano Pulido and Maximino Salazar Lechuga. Handling Multiple Objectives With Particle Swarm Optimization. [

60、J] IEEE Transactions on Evolutionary Computation. June 2004, 8(3):256-279</p><p>　　[6] Carlos A. Coello Coello and Gregorio Toscano Pulido. Using Clustering Techniques to Improve the Performance of a Multi-O

61、bjective Particle Swarm Optimizer. In Genetic and Evolutionary Computation Conference. 2004</p><p>　　[7]Leticia Cagnina, Susana Esquivel and Carlos A. Coello Coello. A Particle Swarm Optimizer for Multi-Obje

62、ctive Optimization. JCS&T December 2005, 5(4) :204-210</p><p>　　[8]K.E. Parsopoulos and M.N. Vrahatis. Particle Swarm Optimization Method in Multiobjective Problems. SCA2002, Madrid, Spain</p><

63、;p>　　[9]Xiaohui Hu, Russell C. Eberhart and Yuhui Shi. Particle Swarm with Extended Memory for Multiobjective Optimization, in Proc.2003 IEEE Swarm Intelligence Symp, Indianapolis, Apr.2003, 193-197</p><p&g

64、t;　　[10]鄭友蓮，樊俊青 多目標(biāo)粒子群優(yōu)化算法研究 [J] 湖北大學(xué)學(xué)報(bào)（自然科學(xué)版），Dec.2008, 30(4):351-355</p><p>　　Zheng You-lian, Fan Jun-qing. Study on multi-objective particle swarm optimization algorithm[J]. Journal of Hubei University (N

65、atural Science). Dec.2008, 30(4):351-355（Chinese）</p><p>　　[11]曾建潮，介婧，崔志華 微粒群算法[M] 北京：科學(xué)出版社, 2004 </p><p>　　Zeng Jian-chao, Jie Jing, Cui Zhi-hua Particle Swarm Optimization Algorithm[M]. Beijin

66、g: Science Publisher, 2004.(Chinese)</p><p>　　[12]鄭金華 多目標(biāo)進(jìn)化算法及其應(yīng)用[M] 北京：科學(xué)出版社, 2007 </p><p>　　ZHENG Jin-hua. Multi-Objective Evolutionary Algorithm and Application[M]. Beijing: Science Publisher

67、, 2007.(Chinese)</p><p>　　[13]U. Baumgartner, Ch. Magele and W. Renhart. Pareto Optimality and Particle Swarm Optimization. IEEE Transations on Magnetics, 2004, 40(2):1172-1175</p><p>　　[14]張利彪，

68、周春光，馬銘，劉小華 基于粒子群算法求解多目標(biāo)優(yōu)化問題[J]. 計(jì)算機(jī)研究與發(fā)展 July 2004, 41(7):1286-1291</p><p>　　ZHANG Li-biao, ZHOU Chun-guang, Ma Ming, et al. Solutions of Multi-Objective Optimization Problems Based on Particle Swarm Optimiz

69、ation [J]. Journal of Computer Research and Development, July 2004, 41(7):1286-1291 (Chinese) </p><p>　　[15]Xiaohui Hu and Russell C. Eberhart. Multiobjective Optimization Using Dynamic Neithborhood Particle

70、 Swarm Optimization[C]. IEEE CEC’2002,vol.2: 1677-1681</p><p>　　[16] ]K.E. Parsopoulos , D. K. Tasoulis and M.N. Vrahatis. Multiobjective Optimization Using Parallel Vector Evaluated Particle Swarm Optimizat

71、ion[C]. IEEE CEC’2004, </p><p>　　[17]張利彪，周春光，劉小華等. 求解多目標(biāo)優(yōu)化問題的一種多子群體進(jìn)化算法[J]. 控制與決策. Nov.2007 22(11):1313-1320</p><p>　　ZHANG Li-biao, ZHOU Chun-guang, Liu Xiao-hua et al. A multiple subswarms wvo

72、lutionary algorithm for multi-objective optimization problems. Nov.2007, 22(11):1313-1320(Chinese)</p><p>　　[18]Gregorio Toscano Pulido and Carlos A. Coello Coello. Using Clustering Techniques to Improve the

73、 Performance of a Particle Swarm Optimizer [C]. GECCO’2004: 225-237, Seattle, Washington, USA, June 2004. Spinger-Verlag, Lecture Notes in Computer Science Vol.3102</p><p>　　[19]熊盛武，劉麟，王瓊，史敏 改進(jìn)的多目標(biāo)粒子群算法[J].武

74、漢大學(xué)學(xué)報(bào)（理學(xué)版）. June 2005. 51(3):308-312</p><p>　　XIONG Sheng-wu, LIU Lin, WANG Qiong, et al. Improved Multi-Objective Particle Swarm Algorithm [J]. Wuhan University transaction( Nat. Sci. Ed.), 2005,51(3): 308-

75、312 (Chinese).</p><p>　　[20]S.Chamaani, S.A. Mirtaheri, M.Teshnehlab, M.A.Shoorehdeli and V.Seydi. Modified Multi-Objective Particle Swarm Optimization for Electromagnetic Absorber Design. Progress in Electr

76、omagnetics Research, PIER 79,353-366,2008</p><p>　　[21]楊俊杰，周建中，方仍存等. 基于自適應(yīng)網(wǎng)格的多目標(biāo)粒子群優(yōu)化算法[J]. 系統(tǒng)仿真學(xué)報(bào)。 Nov. 2008, 20(21):5843-5847</p><p>　　Yang Jun-jie, Zhou Jian-zhong, Fang Reng-cun et al. Multi

77、-objective Particle Swarm Optimization Based on Adaptive Grid Algorithms[J]. Journal of System Simulation. Nov.2008, 20(21):5843-5847(Chinese)</p><p>　　[22]Zitzler E, Laumanns M,Thiele L. SPEA2: Improving th

78、e Strength Pareto Evolutionary Algorithm[R]. Zurich:Swiss Federal Institute of Technology Zurich (ETH),2001</p><p>　　[23] Gregorio Toscano Pulido, Carlos A. Coello Coello and Luis Vicente Santana-Quintero. E

79、MOPSO: A Multi-Objective Particle Swarm Optimizer with Emphasis on Efficiency[C]. Proceeding of Evolutionary Multi-objective Optimization 2007,272-285</p><p>　　[24]Laumanns M, Thiele L, Deb K, Zitzler E. Com

80、bining Convergence and Diversity in Evolutionary Multi-Objective Optimization[J]. Evolutionary Computation, 2002, 10(3):263-282</p><p>　　[25]Mostaghim S, Teich J. The Role of Dominance in Multi-Objective Par

81、ticle Swarm Optimization Methods[C]. Proc.of Congress on Evolutionary Computation, IEEE CEC 2003, 1764-1771</p><p>　　[26]蔣浩，鄭金華，陳良軍 一種求解多目標(biāo)優(yōu)化問題的粒子群算法[J]. 模式識別與人工智能. Oct. 2007. 20(5):606-610</p><p&

82、gt;　　Jiang Hao, Zheng Jin-hua, Chen Liang-jun. A Particle Swarm Algorithm for Multi-Objective Problem[J]. PR&AI Oct.2007, 20(5): 606-610(Chinese)</p><p>　　[27]金欣磊，馬龍華，劉波等. 基于動(dòng)態(tài)交換策略的快速多目標(biāo)粒子群優(yōu)化算法研究[J]. 電路與

83、系統(tǒng)學(xué)報(bào). Apr.2007. 12(2):78-82</p><p>　　Jin Xin-lei, Ma Long-hua, Liu Bo et al. A fast multi-objective particle swarm optimization based on dynamic exchange strategy [J]. Journal of Circuits and Systems. Apr. 2

84、007, 12(2):78-82 (Chinese)</p><p>　　[28]李寧，鄒彤，孫德寶等. 基于粒子群的多目標(biāo)優(yōu)化算法[J]. 計(jì)算機(jī)工程與應(yīng)用，2005, 23(43-46)</p><p>　　Li Ning, Zou Tong, Sun De-bao. Multi-objective optimization utilizing particle swarm[J]. C

85、omputer Engineering and Applications. 2005, 23(43-46) (Chinese)</p><p>　　[29]Salazar-Lechuga M, Rowe J E. Particle Swarm Optimization and Fitness Sharing to Solve Multi-Objective Optimization Problems[C]. Pr

86、oc. Of Congress on Evolutionary Computation, IEEE CEC 2005,1204-1211</p><p>　　[30]王小剛，李明杰，王福利等，一種新的多目標(biāo)粒子群算法的研究與應(yīng)用[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版）.Oct.2008, 29(10):1377-1380</p><p>　　Wang Xiao-gang, Li Ming-jie

87、, Wang Fu-li et al. Study on a Now MOPSO and Its Applications[J]. Journal of Northeastern University (Natural Science). Oct.2008, 29(10):1377-1380 (Chinese)</p><p>　　[31]李中凱，譚建榮，馮毅雄等. 基于擁擠距離排序的多目標(biāo)粒子群優(yōu)化算法及其應(yīng)用

88、[J].計(jì)算機(jī)基礎(chǔ)制造系統(tǒng). July 2008, 14(7):1329-1336</p><p>　　Li Zhong-kai, Tan Jian-rong, Feng Yi-xiong et al. Multi-objective particle swarm optimization algorithm based on crowding distance sorting and its applicati

89、on[J]. Computer Integrated Manufacturing Systems. July 2008, 14(7):1329-1336 (Chinese)</p><p>　　[32]王輝，錢鋒.基于擁擠度與變異的動(dòng)態(tài)微粒群多目標(biāo)優(yōu)化算法[J].控制與決策. Nov.2008, 23(11):1238-1242</p><p>　　Wang Hui, Qian Feng.

90、 Improved PSO-based multi-objective optimization by crowding with mutation and particle swarm optimization dynamic changing[J]. Control and Decision. Nov.2008. 23(11):1238-1242 (Chinese)</p><p>　　[33]王洪剛，馬良，

91、李高雅. 多目標(biāo)微粒群優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用.2008. 44(34):64-66</p><p>　　Wang Hong-gang, Ma Liang, Li Gao-ya. Multi-objective particle swarm optimization. Computer Engineering and Applications. 2008, 44(34):64-66 (Chinese)&l

92、t;/p><p>　　[34]宋武，鄭金華.基于密度熵的多目標(biāo)粒子群算法[J].計(jì)算機(jī)工程與應(yīng)用.2007. 43(26):41-44</p><p>　　Song Wu, Zheng Jin-hua. MOPSO algorithm based on density entropy[J].Computer Engineering and Applications. 2007, 43(26):

93、41-44 (Chinese)</p><p>　　[35]孫小強(qiáng)，張求明.一種基于粒子群優(yōu)化的多目標(biāo)優(yōu)化算法[J].計(jì)算機(jī)工程與應(yīng)用.2006,18:40-42</p><p>　　Sun Xiao-qiang, Zhang Qiu-ming. A Particle Swarm Optimization Method for Multi-objective Optimization[J]

94、. Computer Engineering and Applications. 2006,18:40-42 (Chinese)</p><p>　　[36]Janson S, Merkle D. A New Multi-Objective Particle Swarm Optimization Using Clustering Applied to Automated Docking[C]. Proc. Of

95、Hybrid Metaheuristics, 2005,128-141</p><p>　　[37]王俊年，劉建勛，陳湘州. 一種多目標(biāo)微粒群算法及其收斂性分析[J].計(jì)算機(jī)工程與應(yīng)用.2007, 43(22):53-55</p><p>　　Wang Jun-nian, Liu Jian-xun, Chen Xiang-zhou. Multi-objective particle swa

96、rm optimization and it’s convergence analysis[J]. Computer Engineering and Applications. 2007, 43(22):53-55 (Chinese)</p><p>　　[38]胡德峰，張步涵，姚建光. 基于改進(jìn)粒子群算法的多目標(biāo)最優(yōu)潮流計(jì)算[J]. 電力系統(tǒng)及其自動(dòng)化學(xué)報(bào). Jun.2007, 19(3):51-57</

97、p><p>　　Hu De-feng, Zhang Bu-han, Yao Jian-guang. Improved Particle Swarm Optimization Algorithm for Multi-Objective Optimal Power Flow[J].Proceedings of CSU-EPSA. Jun.2007, 19(3):51-57 (Chinese)</p><

98、;p>　　[39]公茂果，焦李成，楊咚咚等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào) February 2009, 20(2):271-289</p><p>　　Gong Mao-guo, Jiao Li-cheng, Yang Dong-dong et al. Reseach on Evolutionary Multi-Objective Optimization Algorithms[J].Jour