版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
1、<p> 多目標(biāo)微粒群優(yōu)化算法研究</p><p> 王艷1,2,曾建潮2</p><p> ?。? 蘭州理工大學(xué)電信工程學(xué)院 甘肅 蘭州730050)</p><p> ?。? 太原科技大學(xué)復(fù)雜系統(tǒng)和智能計算實驗室 山西 太原 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)行了分類,著重分析了各類算法的主要思想、特點及其代表性算法。其次,針對非支配解的選擇、外部檔案集的修剪、解集多樣性的保持以及微粒個體歷史最優(yōu)解和群體最優(yōu)解的選取等熱點問題進(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é)實踐、工程
9、系統(tǒng)設(shè)計及社會生產(chǎn)活動中,許多問題都是多目標(biāo)優(yōu)化問題。通常多目標(biāo)優(yōu)化問題中的各個目標(biāo)函數(shù)之間可能會存在沖突,這就意味著多目標(biāo)優(yōu)化問題不存在唯一的全局最優(yōu)解,使得所有目標(biāo)函數(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)化問題,但這樣需要事先知道每個目標(biāo)函數(shù)所占的權(quán)重,并且對目標(biāo)給定的次序也比較敏感。</p><p>
10、 微粒群優(yōu)化(PSO)算法是1995年由Kennedy和Eberhart提出的一種基于群體智能的優(yōu)化算法,應(yīng)用于單目標(biāo)優(yōu)化問題時表現(xiàn)出了快速收斂的特點。隨著對PSO研究的深入,該算法已經(jīng)由用來解決單目標(biāo)優(yōu)化問題逐步拓展到用來解決多目標(biāo)優(yōu)化問題。1999年Moore 和Chapman首次提出將PSO算法應(yīng)用于解決多目標(biāo)優(yōu)化問題[1],但這個思想未公開發(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算法,那時MOPSO算法的研究剛剛起步不久,研究成果并不是很多。而國內(nèi)該領(lǐng)域的綜述非常少[1
12、0],并且只是簡單從算法設(shè)計和應(yīng)用方面回顧了其研究進(jìn)展,所以有必要對該領(lǐng)域進(jìn)行一個較為全面的介紹。</p><p> 2 多目標(biāo)優(yōu)化問題的數(shù)學(xué)描述</p><p> (1) 多目標(biāo)優(yōu)化問題的形式化描述</p><p><b> (1)</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. 個體間的支配關(guān)系:設(shè)p和q是進(jìn)化群體pop中的任意兩個不同的個體,稱p支配q,則必須滿足下列兩個條件:</p><p> ①對所有的子目標(biāo),p不比q差,即fi(p)≤fi(q), i=1,2,…k;</p><p>
14、②至少存在一個子目標(biāo)使p比q好,即。</p><p> 其中k為子目標(biāo)的數(shù)量,此時p為非支配的,q為被支配的,定義為,“”表示支配關(guān)系。</p><p> 定義2. Pareto最優(yōu)解集:對于決策空間中的向量,F(xiàn)是搜索區(qū)域,若在F區(qū)域內(nèi),X*是非支配的,則X*是F內(nèi)的一個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è)置少,實現(xiàn)簡單,決策變量是實數(shù),收斂速度快等特點,使其得到充分研究。標(biāo)準(zhǔn)PSO算法的運動方程
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)的全局最好位置,它是整個群體所經(jīng)歷的最好位置。 Xi(t
17、)與 Vi(t)為微粒i在時刻t的位置與速度。公式(2)表示微粒速度由3部分決定:慣性部分、認(rèn)知部分和社會部分,它們共同改變微粒飛行速度,但速度會受到最大速度 Vmax的限制。</p><p> PSO算法與遺傳算法不同,在PSO算法運行過程中,沒有選擇或變異操作,因而種群的規(guī)模是固定的,微粒不會被舍棄與替換,被替換的是迄今為止微粒經(jīng)歷的歷史最好位置(稱為個體極值,用pbest表示)和群體的最好位置(稱為全局極
18、值,用gbest表示),種群中所有微粒的調(diào)整均依賴于pbest和gbest的值。所以將PSO算法引入來解決多目標(biāo)優(yōu)化問題時,pbest和gbest的選取非常重要,而這在多目標(biāo)進(jìn)化算法的設(shè)計中是沒有的。</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ù)是線性時往往無法搜索到非凸解,當(dāng)聚集函數(shù)是非線性的時候就可以解決這個問題了[12]。在這種方法中較具有代表性的研究是文獻(xiàn)[8],[13]和[14]。&l
20、t;/p><p> 文獻(xiàn)[8]分析了固定權(quán)重、突變權(quán)重和動態(tài)權(quán)重這三種權(quán)重聚集方法。固定權(quán)重在優(yōu)化過程中權(quán)重是固定不變的,但計算量很大,并且無法找到非凸解。突變權(quán)重和動態(tài)權(quán)重可以克服這個缺點,只是突變權(quán)重一般是周期函數(shù)的復(fù)合函數(shù),變化比較頻繁,變化的尺度由周期函數(shù)的外層函數(shù)決定。動態(tài)權(quán)重在突變權(quán)重的基礎(chǔ)上將復(fù)合函數(shù)變成了周期函數(shù)的絕對值函數(shù),這樣變化的尺度相對突變權(quán)重要緩和一些。</p><p&
21、gt; 文獻(xiàn)[13]使用了一種線性權(quán)重聚集法。在這類方法中,整個群體被平均分成了若干個子群體,每個子群體被賦予不同的權(quán)重,每個子群體中的微粒都朝著自己所處子群中的最優(yōu)解“飛行”,然后通過線性權(quán)重進(jìn)行聚集,得到總目標(biāo)下群體全局最優(yōu)微粒。</p><p> 文獻(xiàn)[14]使用了一種類似于權(quán)重聚集的方法。首先找到在每個目標(biāo)下群體的全局極值和每個微粒在每個目標(biāo)下的個體極值,然后用各目標(biāo)下全局極值的均值作為整個群體在總目
22、標(biāo)下的全局極值,并通過判斷每個微粒在每個目標(biāo)下相對于該目標(biāo)下全局極值的離散程度來選取該粒子在總目標(biāo)下的個體極值。</p><p> 以上三種方法都比較簡單,容易實現(xiàn)。但是算法每迭代一次只能產(chǎn)生一個“最優(yōu)解”,所以要得到接近PFTrue的Pareto front則需要的迭代次數(shù)較大,從而帶來的計算量就會較大。并且這三種方法都沒有很好地體現(xiàn)出Pareto支配的概念,沒有精英解保留機(jī)制,這樣使解的質(zhì)量受到影響。<
23、;/p><p> (2) 基于目標(biāo)函數(shù)排序方法</p><p> 在這種方法中目標(biāo)函數(shù)通常要根據(jù)某個標(biāo)準(zhǔn)進(jìn)行排序,然后按照此順序?qū)δ繕?biāo)函數(shù)進(jìn)行優(yōu)化。比較具有代表性的方法是Hu and Eberhart的動態(tài)鄰域策略[15]及其擴(kuò)展[9]。前者主要針對兩個目標(biāo)函數(shù)在環(huán)形鄰域上進(jìn)行的優(yōu)化,沒有采用外部存儲體保存精英個體,后者在前者的基礎(chǔ)上引入了精英解的保留機(jī)制。這類方法的主要思想是首先根據(jù)第一
24、個目標(biāo)來計算當(dāng)前考查微粒與其他微粒的距離,并根據(jù)距離建立若干個鄰域,然后根據(jù)第二個目標(biāo)函數(shù)選取鄰域最優(yōu)解。</p><p> 這類方法中目標(biāo)函數(shù)的順序是非常重要的,并且這種方法處理的目標(biāo)函數(shù)往往較少。</p><p><b> (3) 子群法</b></p><p> 這類方法的基本思想是將整個群體劃分為若干個子群,每個子群中進(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]針對兩個優(yōu)化函數(shù)的多目標(biāo)優(yōu)化問題提出了用兩個子群體分別進(jìn)行單目標(biāo)優(yōu)化,然后把第一個子群得到的最優(yōu)解作為第二個子群更新速度的全局最優(yōu)解,將第二個子群的最優(yōu)解作為第一個子群更新速度的全局最優(yōu)解。[16]將此思想進(jìn)行改進(jìn),
26、把每一維目標(biāo)作為一個子群,每個子群進(jìn)行單目標(biāo)優(yōu)化得到最優(yōu)解,并將其作為鄰接子群更新速度的全局最優(yōu)解。</p><p> 文獻(xiàn)[17]對兩個目標(biāo)函數(shù)同時進(jìn)行優(yōu)化,根據(jù)多目標(biāo)優(yōu)化問題的特點將進(jìn)化群體劃分為第一個目標(biāo)下的全優(yōu),第一個目標(biāo)下的半優(yōu),第二個目標(biāo)下的全優(yōu),第二個目標(biāo)下的半優(yōu)以及兩個目標(biāo)下的全劣這幾個子群體。然后根據(jù)支配關(guān)系找出每個子群體中的全局最優(yōu)個體,它們構(gòu)成一個非支配集,從中選出群體的全局最優(yōu)解。<
27、;/p><p> 文獻(xiàn)[18]利用Pareto支配確定微粒的“飛行”方向,采用聚類的方法將微粒群分為幾個子群,每個子群體產(chǎn)生非支配解集,從其中隨機(jī)選擇一個作為每個子群執(zhí)行PSO算法時的全局最優(yōu)解,子群間通過移植不同子群中的非支配解交換信息。</p><p> (4) 基于Pareto的方法</p><p> 現(xiàn)在的大多數(shù)研究主要集中于這種方法,借鑒以前用進(jìn)化算法解
28、決多目標(biāo)優(yōu)化問題的一些成功經(jīng)驗,在進(jìn)化過程中經(jīng)常保持兩個群體,一個是進(jìn)化的基本種群population,另一個是用來存儲進(jìn)化過程中的精英個體的群體archive。首先通過evaluate來確定基本種群中個體的優(yōu)劣,然后通過確定基本種群的全局最優(yōu)個體和每個個體的歷史最好位置,利用PSO公式進(jìn)行更新,得到下一代基本群體。對archive一般要進(jìn)行兩種操作:update和truncate,前者用來更新archive中的個體保持為進(jìn)化中的最優(yōu)個
29、體,后者是當(dāng)要進(jìn)入archive中實際個體的數(shù)目大于archive容量時,對其中個體進(jìn)行修剪剔除。</p><p> 通常具有精英解保留機(jī)制的MOPSO算法偽碼如圖1所示,其中Quality (pbest)或Quality (gbest)是指個體歷史最優(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)典的算法,在這個算法中Coello等首次提出了除基本微粒群引入第二個群體來保存生成的非支配解,并第一次用(超)網(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)境選擇和配對選擇策略,并使用了密度估計技術(shù),提高了解的多樣性和搜索精度。但該算法中有三個群體,計算量較大。</p><
32、p> [20]在[2]的基礎(chǔ)上對算法進(jìn)行了兩方面的改進(jìn):①算法迭代到一定次數(shù)時對某個重要目標(biāo)進(jìn)行單目標(biāo)優(yōu)化,以此來解決MOPSO中出現(xiàn)的難以找到邊界點的問題;②對超出邊界的位置變量用一個隨機(jī)數(shù)來取代。這兩方面的改進(jìn)主要提高了Pareto解集的分布性,但要求事先知道各優(yōu)化目標(biāo)的重要程度。</p><p> [21]對[5]中的自適應(yīng)網(wǎng)格進(jìn)行了改進(jìn),加入了非支配解集中微粒密度估計信息,在剔除密度較大網(wǎng)格中微
33、粒的時候,確定了需要剔除的微粒的數(shù)量,給出了計算公式。并且該算法在全局最優(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ǔ)上,針對兩個目標(biāo)函數(shù)首先找到每一個目標(biāo)的最小值A(chǔ)和B,然后將這兩點用直線連接,如果需要找到n個非支配解,則在此線段上均勻地再選擇(n-1)個點,接著在這(n-1)個點上作直線AB的垂直線,非支配解中距離此垂直線最近的點被選中,其余各點被刪除。此算法為了避免早熟收斂而加入了擾動因子,隨著迭代次數(shù)的增加,擾動因子逐漸減小。此算法對約束處理方法以及參數(shù)自適應(yīng)調(diào)整等方面都進(jìn)行了研究。</p><p> 對于上述所分析
35、的MOPSO算法及其特征如表1所示。</p><p> 表1 經(jīng)典MOPSO算法及其特征</p><p> 5 多目標(biāo)微粒群算法研究熱點</p><p> 用PSO解決多目標(biāo)優(yōu)化問題往往借鑒多目標(biāo)進(jìn)化算法中的成功經(jīng)驗,但MOPSO既不同于MOEA,又不同于用PSO解決單目標(biāo)優(yōu)化問題,當(dāng)前對MOPSO算法的研究一般圍繞以下研究熱點進(jìn)行:如何選擇非支配解、如何剔除
36、archive集中的個體以保持其良好的分布性、如何保持解集多樣性和gbest和pbest如何選取等。</p><p> ?。?) 非支配解的選擇</p><p> 對于這個問題的研究涉及到傳統(tǒng)Pareto支配的概念及后來研究者們對其發(fā)起的挑戰(zhàn)?,F(xiàn)有的大多數(shù)研究都是基于傳統(tǒng)Pareto支配機(jī)制的,即個體支配機(jī)制。2002年,Laumanns and Deb等提出ε-支配[24]概念后其思想
37、被借鑒與改進(jìn),2003年Mostaghim等[25]將其引入到MOPSO算法中。ε-支配是一種基于格子的支配機(jī)制,格子的邊長為ε,所以ε決定格子的數(shù)目和大小。每個格子內(nèi)只允許有一個解,這樣支配的概念由原來個體間的比較轉(zhuǎn)化為格子間的比較,后來的研究中人們在選取非支配解時有些采用或改進(jìn)了ε-支配的概念。文獻(xiàn)[26]為了保持解集良好的分布性,針對原有ε-支配可能會丟失邊界點的情況提出了強ε-支配概念,在原有ε-支配概念的基礎(chǔ)上又加入了個體支配
38、的概念。</p><p> (2) archive集的修剪</p><p> 當(dāng)前MOPSO算法中絕大多數(shù)都用到了容量受限的archive集來保存精英解,所以一般要對archive集進(jìn)行修剪,剔除掉一部分非支配解,archive集中的結(jié)果就是將來要輸出的解,所以在剔除的過程中要考慮到多目標(biāo)優(yōu)化問題的特點,研究者們一般在這個階段考慮較多的是如何剔除archive集中的個體,保持解集良好的
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)非支配解的個數(shù)超過archive的容量時隨機(jī)地刪除archive集中的部分個體。這種修剪方法簡單,容易實
40、現(xiàn),但沒有充分考慮解集的分布性。</p><p> 小生鏡技術(shù)。這類方法一般通過小生鏡技術(shù)給archive集中的非支配解分配適應(yīng)度值,聚集程度越大的微粒適應(yīng)度越小。當(dāng)非支配解個數(shù)超出archive集的容量時,則刪除其中適應(yīng)度最小的部分個體。這種修剪方法可以提高解集的分布性,但需要小生鏡半徑的先驗信息,計算復(fù)雜度較大。</p><p> 網(wǎng)格技術(shù)?,F(xiàn)有的MOPSO算法很大一部分是在Coe
41、llo等的MOPSO算法[5]基礎(chǔ)上改進(jìn)的,而這個算法就是使用網(wǎng)格來保存非支配解的,所以現(xiàn)有很多算法都采用這種方法來保存和修剪archive集。這類方法的基本思想就是當(dāng)非支配解個數(shù)大于archive容量時,根據(jù)網(wǎng)格中微粒的數(shù)量來決定刪除哪些微粒。</p><p> 擁擠距離。近年來使用這類方法修剪archive集的算法越來越多。這類方法的基本思想就是通過archive集中個體的擁擠距離來判斷解之間的疏密程度,在
42、對archive集進(jìn)行修剪時,擁擠距離大的微粒被保留下來,擁擠距離小的微粒被刪除。</p><p> 密度熵。這類方法具有一定的特點,但在MOPSO中并不多見。其基本思想就是定義一個影響函數(shù)來衡量archive集中每兩個微粒間的相似程度,而archive中微粒的密度是周圍微粒對其影響因子的聚集。當(dāng)每個微粒的密度熵確定后,找出微粒中密度最大的進(jìn)行刪除。這類方法中archive集更新時計算復(fù)雜度為o(MN2),M為
43、子目標(biāo)個數(shù),N為archive集大小。</p><p> 聚類技術(shù)。這類修剪archive集的方法是借鑒于多目標(biāo)進(jìn)化算法的一種技術(shù),其基本思想是在算法的每一次迭代過程中,通過聚類方法將整個archive集中的非支配解分成若干個聚類,當(dāng)聚類的個數(shù)超過一定數(shù)量時將距離最近的兩個聚類合并,將合并后的中心點作為新類的位置。</p><p> ?。?) 保持解集多樣性</p><
44、;p> PSO算法最突出的一個特點就是收斂速度快,但這個特點同時也帶來了算法早熟收斂的問題。為了增加解的多樣性,避免早熟收斂,將PSO應(yīng)用于解決多目標(biāo)優(yōu)化問題時往往借鑒多目標(biāo)進(jìn)化算法中的變異算子,有的MOPSO算法對微粒進(jìn)行變異的同時對決策變量的范圍進(jìn)行變異,有的研究采用對“飛”出可行域的微粒進(jìn)行重新初始化的方法來保持非支配解集中解的多樣性。</p><p> 文獻(xiàn)[5]提出了一種使用變異因子來更新基本
45、種群中微粒和決策變量范圍的方法。該方法在搜索開始時對所有微粒進(jìn)行變異,隨著迭代次數(shù)的進(jìn)行,種群中變異的微粒數(shù)量迅速下降,對每個決策變量范圍也采用同樣操作。這樣,算法可以有一個很強的搜索能力,隨著迭代次數(shù)的增加,變異算子的作用逐漸減小,從而避免了算法早熟。文獻(xiàn)[32]也采用了同樣的方法來保持解的多樣性。</p><p> 文獻(xiàn)[28][31]使用了小概率隨機(jī)變異的方法來保持解集的多樣性。這類方法的基本思想是在基本
46、種群每次迭代的過程中隨機(jī)選擇(或從被支配解中選)很少一部分(例如變異概率為5%)微粒進(jìn)行變異,這樣以增強算法的全局搜索能力。</p><p> 文獻(xiàn)[20]對超出邊界的微粒不用傳統(tǒng)方法中將其拉至邊界的處理方式,而是用一個可行域內(nèi)的隨機(jī)數(shù)將其替代,這樣以增加解的多樣性。</p><p> ?。?) pbest和gbest的選取</p><p> 在PSO算法中,微
47、粒是在種群全局最優(yōu)位置gbest及個體歷史最優(yōu)位置pbest的指導(dǎo)下“飛行”的。將PSO算法應(yīng)用于解決多目標(biāo)優(yōu)化問題時,每次迭代不再是僅僅產(chǎn)生一個單個的pbest值和gbest值,而是一組非支配解,如何選擇合適的pbest和gbest來指導(dǎo)種群中微粒的“飛行”就顯得非常重要了。</p><p> 通常對于pbest的選取一般都基于Pareto支配概念,新產(chǎn)生的pbest與原來的pbest進(jìn)行比較,選擇非支配者作
48、為算法迭代中的pbest,若二者不存在支配關(guān)系,則隨機(jī)選擇其中之一即可。但也有算法根據(jù)所支配的群體中微粒的個數(shù)來選擇[35]。</p><p> gbest的選取是MOPSO算法設(shè)計中的關(guān)鍵,gbest的選取在很大程度上與archive集的修剪及更新方式相關(guān)。gbest選取最簡單最直接的方法就是從archive集中隨機(jī)選取一個微粒作為基本種群更新的全局最優(yōu)解[7][34][37]。文獻(xiàn)[28]采用輪盤賭概率方法
49、從archive中選取精英微粒作為gbest,文獻(xiàn)[30]通過隨機(jī)從archive中選取兩個微粒,從多個目標(biāo)函數(shù)中隨機(jī)選取一個目標(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ī)選擇一個非支配解,然后將此解與當(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、四個研究熱點進(jìn)行了討論。雖然MOPSO算法從出現(xiàn)至今不足十年,但其發(fā)展是非常迅猛的,在今后的研究中以下幾個方向應(yīng)該引起研究者們的重視。</p><p> 如何用PSO算法處理高維(m>5)多目標(biāo)優(yōu)化問題。對于高維多目標(biāo)優(yōu)化問題想要找到一組合適的Pareto最優(yōu)解是很困難的,許多在處理低維數(shù)目標(biāo)時不會出現(xiàn)的問題就會凸現(xiàn)出來[39],空間復(fù)雜度,時間復(fù)雜度以及選擇壓力等都將是需要重點考慮的問題。如何用PSO解
53、決高維多目標(biāo)優(yōu)化問題將是研究者們未來一段時間研究的內(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)化問題自身的特點來自適應(yīng)調(diào)整MOPSO參數(shù),這方面的研究已經(jīng)開始,估計將會成為今后一段時間研究的另一個熱點。</p><p> 有效的算法
54、停止準(zhǔn)則?,F(xiàn)有的MOPSO算法中,絕大多數(shù)算法都是通過預(yù)先設(shè)置迭代次數(shù)來停止算法,因為算法進(jìn)化到哪一代就達(dá)到最優(yōu)往往是無法判斷的。在單目標(biāo)PSO算法中,當(dāng)gbest在一定代數(shù)內(nèi)不再變化就可以認(rèn)為算法已經(jīng)收斂到了最優(yōu)解,可以停止迭代。但這種策略是不能直接應(yīng)用于MOPSO,因為在算法的執(zhí)行過程中很少會出現(xiàn)這種情況,即使有部分解與上一代相同,但多少個解相同就能說明算法已經(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é)報(自然科學(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ī)研究與發(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é)報(理學(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é)報。 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]金欣磊,馬龍華,劉波等. 基于動態(tài)交換策略的快速多目標(biāo)粒子群優(yōu)化算法研究[J]. 電路與
83、系統(tǒng)學(xué)報. 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ī)工程與應(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é)報(自然科學(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ī)基礎(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]王輝,錢鋒.基于擁擠度與變異的動態(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ī)工程與應(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ī)工程與應(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]孫小強,張求明.一種基于粒子群優(yōu)化的多目標(biāo)優(yōu)化算法[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ī)工程與應(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]. 電力系統(tǒng)及其自動化學(xué)報. 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é)報 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
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 基于PSO的多目標(biāo)優(yōu)化算法研究及應(yīng)用.pdf
- 多目標(biāo)優(yōu)化進(jìn)化算法比較綜述
- 基于PSO的動態(tài)多目標(biāo)優(yōu)化算法的研究.pdf
- 基于多族群PSO算法的森林空間動態(tài)多目標(biāo)優(yōu)化研究.pdf
- 基于GRA-PSO算法的正交車銑加工參數(shù)多目標(biāo)優(yōu)化.pdf
- 基于灰色pso算法的分布式電網(wǎng)多目標(biāo)調(diào)峰調(diào)度優(yōu)化研究
- 多目標(biāo)進(jìn)化算法總結(jié)
- 多目標(biāo)進(jìn)化算法總結(jié)
- PSO在決策支持中多目標(biāo)靜態(tài)優(yōu)化問題的算法應(yīng)用研究.pdf
- 基于灰色PSO算法的分布式電網(wǎng)多目標(biāo)調(diào)峰調(diào)度優(yōu)化研究.pdf
- 基于Pareto最優(yōu)解的多目標(biāo)PSO算法在電機(jī)優(yōu)化設(shè)計中的應(yīng)用.pdf
- 多目標(biāo)跟蹤算法研究.pdf
- 多目標(biāo)遺傳算法代碼
- 多目標(biāo)演化算法研究.pdf
- 多目標(biāo)進(jìn)化算法研究.pdf
- 多目標(biāo)優(yōu)化演化算法.pdf
- 多目標(biāo)模型算法控制研究.pdf
- 多目標(biāo)數(shù)據(jù)關(guān)聯(lián)算法研究.pdf
- 多目標(biāo)進(jìn)化算法的研究.pdf
- 多目標(biāo)DOA跟蹤算法研究.pdf
評論
0/150
提交評論