一種多目標(biāo)粒子群優(yōu)化算法

一種多目標(biāo)粒子群優(yōu)化算法

0基于多目標(biāo)進(jìn)化算法的群體決策在過去10年中，先進(jìn)的計(jì)算方法在解決多目標(biāo)優(yōu)化問題上發(fā)揮了良好的優(yōu)勢(shì)，因?yàn)樗梢哉业蕉鄠€(gè)解算方法，并將其收斂到相對(duì)均勻的區(qū)域，分布相對(duì)均勻?，F(xiàn)在進(jìn)化計(jì)算方法與決策理論結(jié)合在一起,在多目標(biāo)決策中發(fā)揮作用,是一個(gè)重要的研究熱點(diǎn)。其特點(diǎn)是不再注重于近似整個(gè)Pareto前沿,而是集中于決策者所關(guān)心的那些Pareto最優(yōu)解,使得搜索的效率更佳。但多目標(biāo)進(jìn)化算法應(yīng)用于群體決策方面的研究還非常缺乏。文獻(xiàn)中介紹了解決群體決策問題的一種遺傳算法方法,決策者的偏好用參考點(diǎn)(概念詳見2.1節(jié))表示,再通過分層排序或者距離引導(dǎo)種群向群體解進(jìn)化。而在決策支持系統(tǒng)中,有關(guān)群體決策的研究已經(jīng)較為深入。但是其中大部分研究都是基于以下兩點(diǎn)不是很符合實(shí)際問題的假設(shè):其一,大部分情況下,只有少數(shù)幾個(gè)可選方案,而在這幾個(gè)方案中必須選擇一個(gè)作為最后群體解決方案,而很少關(guān)注到如何在一個(gè)數(shù)量巨大的可選擇空間中進(jìn)行優(yōu)化;其二,通常假設(shè)群體是同類的,因此可以整合到一個(gè)通用的偏好函數(shù)?；谝陨霞僭O(shè)后,可以應(yīng)用名義群體技術(shù)、DELPHI方法、層次分析法等方法以類似于單決策者的方式進(jìn)行決策。但是,決策群體都同意一個(gè)公共的偏好函數(shù),是不太實(shí)際的,特別是對(duì)于群體成員較多的情形,是非常困難或者根本無法得到公共偏好函數(shù)的。本文的目的,是將多目標(biāo)粒子群優(yōu)化方法應(yīng)用于群體決策,決策者的偏好也以參考點(diǎn)表示,但不再直接使用分層排序或距離方式,而是在支配概念或者距離閾值下,使用了群體決策中應(yīng)用最廣的投票規(guī)則進(jìn)行求解。我們的重點(diǎn)在于搜索群體關(guān)心的一小集合的Pareto最優(yōu)解,并且用ZDT問題進(jìn)行驗(yàn)證。1般mopso算法多目標(biāo)優(yōu)化問題(MOP)一般定義如下:其中X是Rn空間中的決策變量,D是其定義域,fi:Rn→R,i=1,2,…,k是目標(biāo)函數(shù);gi,hj:Rn→R;i=1,2,…,m;j=1,2,…,q是約束函數(shù)。對(duì)于多目標(biāo)優(yōu)化問題,一般沒有一個(gè)使得所有目標(biāo)函數(shù)均為最優(yōu)的解,所以采用的多是Pareto解。在MOPSO中,由粒子群到當(dāng)前為止所發(fā)現(xiàn)的非支配解都存儲(chǔ)在外部種群檔案(externalarchive)中。每個(gè)粒子除了向自己所經(jīng)歷的某個(gè)非支配歷史位置(pbest)學(xué)習(xí)外,同時(shí)從外部種群檔案中按照一定規(guī)則選擇一個(gè)解作為引導(dǎo)者(leader)。外部種群檔案隨著計(jì)算的進(jìn)行不斷更新,其所包含的解在運(yùn)行結(jié)束時(shí)一般也是最終輸出結(jié)果。一般MOPSO流程如下:算法1一般的MOPSO算法BeginInitializeswarmInitializeleadersinanexternalarchiveQuality(leaders)Iteration=0While(Iteration<max_Iteration)ForeachparticleSelectleaderUpdatePosition(Flight)MutationEvaluationUpdatepBestEndForUpdateleadersintheexternalarchiveQuality(leaders)Iteration++EndWhileReportresultsintheexternalarchiveEnd其中“Quality(leaders)”一般是計(jì)算粒子的擁擠距離或適應(yīng)度或其它粒子密度的評(píng)價(jià)值,以便后面有一定規(guī)則為每一粒子從外部種群檔案中選擇leader,使得粒子在向Pareto前沿飛翔的同時(shí)保持較好的分布性。在MOPSO中,各種算法不同的地方,主要在于外部種群檔案的設(shè)計(jì)及剪枝策略、leader的選擇方法、pbest的更新方法。2基于選定的mopso參數(shù)2.1群體偏好信息在決策者偏好信息方面,有多種表示方式。決策者不同,其給出的偏好信息也會(huì)不相同。在相關(guān)文獻(xiàn)中,主要有以下幾種方式:目標(biāo)的重要性優(yōu)先次序,目標(biāo)的重要性權(quán)重,參考點(diǎn),參考區(qū)域,參考方向等定義。本文假設(shè)群體成員的偏好信息以參考點(diǎn)表示。偏好參考點(diǎn)表示用戶的期望目標(biāo),表現(xiàn)為目標(biāo)空間中一個(gè)點(diǎn)。設(shè)群體中有N個(gè)決策者,每個(gè)決策者偏好都用一個(gè)參考點(diǎn)Rn(Rn1,Rn2,RnNF),n=1,2,…,N描述,NF是目標(biāo)函數(shù)個(gè)數(shù)。任一解x與參考點(diǎn)的距離用歐幾里德距離公式定義:(2)其中fi是第i個(gè)目標(biāo)函數(shù),fmaxiimax(x)、fminiimin(x)是第i目標(biāo)函數(shù)的最大值、最小值,其作用在于進(jìn)行規(guī)范化。2.2決策參與規(guī)則收集好群體成員的偏好后,進(jìn)行決策時(shí),就要根據(jù)不同的決策方法對(duì)其偏好進(jìn)行整合,以期找到群體偏好的解。在群體決策中,應(yīng)用最廣的是投票方法,群體成員根據(jù)每個(gè)人自己的偏好,對(duì)決策方案進(jìn)行投票,然后進(jìn)行匯集,根據(jù)約定的規(guī)則,選擇最后方案。應(yīng)用最多的是多數(shù)規(guī)則,即多數(shù)決策者同意的解是最終群體解,但也有其它規(guī)則。對(duì)于以參考點(diǎn)表示的群體成員偏好,我們定義如下的投票規(guī)則,以應(yīng)用多目標(biāo)優(yōu)化方法進(jìn)行求解。(1)參與群體成員的參考點(diǎn)定義1(基于支配的解定義)某個(gè)解是群體決策的完全一致解,當(dāng)且僅當(dāng)它是非支配解并且它支配所有群體成員的參考點(diǎn)。定義1對(duì)解的要求非常高,很容易無解。如果某個(gè)參考點(diǎn)不在可行域,則此方法將找不出任何解。此方法也叫一票否決制。定義2(基于距離的解定義)某個(gè)解是群體決策的完全一致解,當(dāng)且僅當(dāng)它是非支配解并且它與所有群體成員的參考點(diǎn)的距離都小于閾值δ。(2)支配多數(shù)群體成員的參考點(diǎn)定義3(基于支配的解定義)某個(gè)解是群體決策的絕對(duì)多數(shù)決定解,當(dāng)且僅當(dāng)它是非支配解并且它支配多數(shù)群體成員的參考點(diǎn)。定義4(基于距離的解定義)某個(gè)解是群體決策的絕對(duì)多數(shù)決定解,當(dāng)且僅當(dāng)它是非支配解并且它與多數(shù)群體成員的參考點(diǎn)的距離都小于閾值δ。這里與完全一致是相近的,只是現(xiàn)在需要滿足多數(shù)決策者參考點(diǎn)要求,而不是全部。按規(guī)則,多數(shù)可能是1/2或2/3等。(3)支配的參考點(diǎn)定義5(基于支配的解定義)某個(gè)解是群體決策的相對(duì)多數(shù)決定解,當(dāng)且僅當(dāng)它是非支配解并且它相對(duì)于其它解來說,支配更多的群體成員參考點(diǎn)。此定義不要求支配超過半數(shù)的參考點(diǎn),只要求其相對(duì)其它解而言支配更多的參考點(diǎn)即可。定義6(基于距離的解定義)某個(gè)解是群體決策的相對(duì)多數(shù)決定解,當(dāng)且僅當(dāng)它是非支配解并且它相對(duì)于其它解來說,與更多的群體成員參考點(diǎn)距離小于閾值δ。此定義不要求與超過半數(shù)的參考點(diǎn)距離小于閾值δ,只要求其相對(duì)其它解而言與更多的參考點(diǎn)距離小于閾值δ即可。根據(jù)以上定義,在搜索群體解時(shí),即是搜索既靠近Pareto前沿而又滿足基于支配概念或距離概念下投票規(guī)則的解。2.3嵌入操作機(jī)制的ledas更新規(guī)則以參考點(diǎn)定義用戶偏好后,MOPSO所要找到的解除了滿足收斂到Pareto前沿并具有分布均勻特點(diǎn)外,還要靠近群體的偏好域。以下介紹解決群體決策問題的基于參考點(diǎn)和相對(duì)多數(shù)決定投票規(guī)則的MOPSO算法策略:(1)基于投票機(jī)制的錦標(biāo)賽選擇leader的方法首先對(duì)外部種群檔案按其支配的參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))進(jìn)行排序,支配參考點(diǎn)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))較多的前50%精英粒子作為候選粒子。然后采用錦標(biāo)賽方式,從候選粒子中選擇支配參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))較多的解為leader。本文采用的錦標(biāo)賽規(guī)模為2。(2)嵌入投票機(jī)制的pbest更新規(guī)則從當(dāng)前粒子和歷史最優(yōu)中選擇兩者中非支配解為pbest;若相互不支配,則選擇支配參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))較多的解為pbest;若相互不支配,支配參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))又一樣,則隨機(jī)選擇一個(gè)為pbest。(3)外部種群檔案leaders更新規(guī)則若當(dāng)前粒子相對(duì)整個(gè)外部種群檔案中粒子而言為非支配解,則加入到外部種群檔案中。并刪除外部種群檔案中被新加入粒子支配的解。(4)嵌入投票機(jī)制的外部種群檔案剪枝規(guī)則檔案容量超過預(yù)設(shè)大小時(shí),如果其中的粒子支配參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))不一樣,則首先刪除支配參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))少的粒子。如果每個(gè)粒子支配的參考點(diǎn)個(gè)數(shù)(或距離閾值δ內(nèi)的參考點(diǎn)個(gè)數(shù))都一樣,則去除密度較大的粒子,以達(dá)到均勻分布要求?；趨⒖键c(diǎn)和投票機(jī)制的MOPSO群體決策方法,主要是在各步驟中嵌入了投票規(guī)則,使得粒子向與群體多數(shù)決策者偏好的Pareto前沿收斂。因?yàn)橹挥谜页霾糠值腜areto前沿,在種群規(guī)模、進(jìn)化代數(shù)方面可以大大減少,使得算法的效率更佳。3模擬實(shí)驗(yàn)3.1zdt1優(yōu)化問題ZDT1問題具有凸的、連續(xù)的Pareto前沿。以下實(shí)驗(yàn)均以ZDT1優(yōu)化問題為例進(jìn)行說明。多目標(biāo)粒子群算法的種群大小是100,最大進(jìn)化代數(shù)為100,外部種群檔案大小為20,距離閾值δ=0.3。(1)基于距離閾值的正演分析假設(shè)三位決策成員偏好的參考點(diǎn)分別是(0.2,0.9)、(0.3,0.8)和(0.8,0.3),它們均位于可行域。為了節(jié)省篇幅,基于支配概念和基于距離閾值下應(yīng)用相對(duì)多數(shù)投票規(guī)則運(yùn)行的結(jié)果顯示在一起,如圖1所示。從圖1可以看出,對(duì)于參考點(diǎn)均是可行點(diǎn)而言,基于支配概念或距離閾值應(yīng)用投票規(guī)則均可以得到群體決策解,兩者解稍有不同,但對(duì)于決策而言影響不是很大。(2)群體解的驗(yàn)證三位決策成員偏好的參考點(diǎn)分別是(0.1,0.6),(0.2,0.5)和(0.8,0.3),它們均位于不可行域。結(jié)果如圖2所示。從圖2可以看出,對(duì)于參考點(diǎn)都在不可行區(qū)域的情況,基于距離與基于支配概念的群體決策結(jié)果非常不一樣?；谥涓拍畹慕?分散于整個(gè)Pareto前沿,實(shí)際上其支配的參考點(diǎn)數(shù)目都是0,可以認(rèn)為此時(shí)沒有找到群體解。但基于距離的方法可以求出與多數(shù)參考點(diǎn)相近的部分Pareto前沿,與多數(shù)規(guī)則相符合。(3)基于距離和選舉規(guī)則的多目標(biāo)優(yōu)化分兩種情況討論。第一種情況是可行參考點(diǎn)較少,不可行參考點(diǎn)較多,結(jié)果如圖3所示?？梢钥闯?基于支配概念與基于距離概念的解相差懸殊,同樣可以看出,基于距離概念所得到的群體解,與大部分決策成員的意愿較相近,而基于支配概念的解只與少數(shù)參考點(diǎn)在可行域的決策者意愿相近。第二種情況是可行參考點(diǎn)較多,不可行參考點(diǎn)較少,結(jié)果如圖4所示。結(jié)果與圖1是幾乎一樣的。從以上仿真結(jié)果可以看出,在決策者給出其偏好參考點(diǎn)情況下,基于距離和投票規(guī)則的多目標(biāo)粒子群優(yōu)化方法都可以用較小的種群規(guī)模和較少的進(jìn)化代數(shù)就可以找出分布較好、與真實(shí)Pareto前沿貼近的,并較符合群體偏好的部分Pareto解,這對(duì)于加快群體決策是非常有益的。而基于支配概念的方法對(duì)參考點(diǎn)的要求較高,只在部分情況下可以求出相應(yīng)較符合群體意愿的解。所以后面實(shí)驗(yàn)只以基于距離和投票規(guī)則進(jìn)行說明。3.2因素參考點(diǎn)ZDT3問題的Pareto解是非連續(xù)的。實(shí)驗(yàn)中設(shè)置了四位決策者的參考點(diǎn),距離閾值δ=0.4,結(jié)果如圖5所示。從圖5可以看出,對(duì)于非連續(xù)的多目標(biāo)優(yōu)化問題,基于距離和投票規(guī)則的粒子群算法,也可以找出較好的群體解。3.3外部種群檔案粒子輸出對(duì)于絕對(duì)多數(shù)決定和完全一致決定,算法主要過程與相對(duì)多數(shù)決定是一樣的,只在最后一步“外部種群檔案中的最終leaders為結(jié)果”要進(jìn)行修改,不能輸出全部