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

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

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