基于余弦距離的多目標(biāo)粒子群優(yōu)化算法

方欣欣,龔如賓,李大為

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院,上?！?00093)

?

基于余弦距離的多目標(biāo)粒子群優(yōu)化算法

方欣欣,龔如賓,李大為

(上海理工大學(xué) 光電信息與計算機(jī)工程學(xué)院,上海200093)

摘要針對粒子群優(yōu)化算法具有的個體分布不均勻以及重復(fù)個體較多等缺陷,提出了一種基于余弦距離的多目標(biāo)粒子群優(yōu)化算法,該算法根據(jù)外部精英存儲策略,利用余弦距離排擠機(jī)制來選取最分散的粒子,擴(kuò)大 Pareto最優(yōu)解集的收斂性和多樣性,增強(qiáng)算法的全局尋優(yōu)能力。通過采用標(biāo)準(zhǔn)多目標(biāo)優(yōu)化問題ZDTl～ZDT3進(jìn)行仿真實(shí)驗(yàn)與粒子群算法、混沌粒子群算法、基于擁擠距離的多目標(biāo)優(yōu)化算法對比表明,該算法在Pareto前沿的收斂性和多樣性方面均優(yōu)于基于擁擠距離排擠機(jī)制,并具有較高的效率。

關(guān)鍵詞余弦距離;擁擠距離;多目標(biāo)優(yōu)化;粒子群;非支配解

Multi-objective Particle Swarm Optimization Algorithm Based on Cosine Distance

FANG Xinxin,GONG Rubin,LI Dawei

(School of Optica1-Electrical & Computer Engineering,University of Shanghai for Science and Technology,Shanghai 200093,China)

AbstractA multi-objective particle swarm optimization (PSO) algorithm based on cosine distance is proposed to tackle the drawbacks such as uneven individual distribution redundant overlapping individuals existing in standard particle swarm optimization.Based upon external elite storage strategy,this algorithm utilizes cosine distance crowing mechanism to select the most widely distributed particles.It amplifies the convergence and diversity of best solution set and strengthens the capacity of global optimization.Standard multi-objective optimization ZDTl~ZDT3 are adopted in simulation experiments to compare the proposed algorithm with the particle swarm optimization,chaos particle swarm optimization and multi-objective optimization algorithm based on crowing mechanism.Results show that the proposed algorithm not only outperforms other algorithms in terms of Pareto’s frontier convergence and diversity but also obtains preferable efficiency.

Keywordscosine distance;crowding distance;multi-objective optimization;particle swarm;non-dominated solutions

在科學(xué)研究和工程實(shí)踐中,常會遇到多目標(biāo)優(yōu)化問題,如旅行商[1],多播路由[2],車間調(diào)度[3]等。解決多目標(biāo)問題(Multi-Object Problem,MOP)的方法一般分為兩類:第一類統(tǒng)稱為“目標(biāo)歸一法”[4],這類求解方法按某種策略確定多個目標(biāo)之間的權(quán)衡方式,將多目標(biāo)問題轉(zhuǎn)換為單目標(biāo)優(yōu)化問題,并用這些單目標(biāo)優(yōu)化問題最優(yōu)解構(gòu)成的解集去近似MOP的Pareto最優(yōu)集。該類方法包括權(quán)值法、約束法、目標(biāo)規(guī)劃法等。運(yùn)用該類方法需要事先已知目標(biāo)信息,從而在目標(biāo)之間建立聯(lián)系,因此在求解許多工程問題上具有極限性。第二類是多目標(biāo)進(jìn)化算法(Multi-Object Evaluation Algorithm,MOEA),MOEA 無需事先充分了解各目標(biāo)的詳細(xì)信息,而是在搜索空間內(nèi)獲得一組Pareto最優(yōu)解來權(quán)衡各個目標(biāo)。近年來,越來越多的學(xué)者研究并廣泛應(yīng)用MOEA算法,具有代表性的有多目標(biāo)模擬退火算法、 多目標(biāo)蟻群優(yōu)化算法、 多目標(biāo)粒子群算法等[5]。

粒子群優(yōu)化算法(Particle Swarm Optimization,PSO)是一種群體智能算法,來源于對鳥群或魚群覓食行為的模擬。適合求解多目標(biāo)優(yōu)化問題[6]。多目標(biāo)優(yōu)化算法需保證Pareto前沿的收斂性和多樣性特征,因此合理的Pareto解集多樣性維持策略和粒子群全局最優(yōu)值更新操作是關(guān)鍵[7]。當(dāng)前在多目標(biāo)粒子群優(yōu)化算法的研究中,為擴(kuò)大Pareto解集的多樣性,大部分采用擁擠距離排擠機(jī)制。當(dāng)前的研究主要參考NSGA-II[8]算法中的擁擠距離機(jī)制代替多目標(biāo)粒子群優(yōu)化算法(Multi-objective Particle Swarm Optimization,MOPSO)算法中粒子位置更新策略。楊善學(xué)[9]引用了NSGA-II中的擁擠距離,計算出外部檔案中非支配解的擁擠度,采用競標(biāo)賽選擇法,選出每個粒子的全局最優(yōu)位置,從而引導(dǎo)每個粒子向處于較稀松區(qū)間的非支配解搜索,提高解的多樣性。李中凱等[10]基于擁擠距離值,引入文化進(jìn)化框架,從精英知識和條件知識中選擇處于最分區(qū)域的粒子。魏武等[11]引進(jìn)擁擠距離排序方法維護(hù)外部精英集和更新全局最優(yōu)值,通過采用小概率變異機(jī)制來保持非劣解的多樣性。

以上大部分文獻(xiàn)主要參考NSGA-II算法對Pareto解集分布性在擁擠距離排擠機(jī)制的基礎(chǔ)上作改動,由于擁擠距離排擠機(jī)制存在不穩(wěn)定性,導(dǎo)致解集分布性不好,而在此基礎(chǔ)上的改進(jìn)方法并不能消除這個缺點(diǎn),后續(xù)優(yōu)化也存在不穩(wěn)定性。本文對擁擠距離排擠機(jī)制的缺陷進(jìn)行深入的分析,引入余弦距離排擠機(jī)制來選取最分散的粒子,擴(kuò)大 Pareto最優(yōu)解集的收斂性和多樣性,增強(qiáng)算法的全局尋優(yōu)能力。

1多目標(biāo)粒子群優(yōu)化算法概述

1.1多目標(biāo)優(yōu)化問題描述

多目標(biāo)優(yōu)化問題中以一個求目標(biāo)的最小值為例可以描述為

(1)

式中,x=(x1,…,xn)∈X?Rn為n維決策變量;X為n維決策空間,y=(y1,y2,…,ym)∈Y?Rm為m維目標(biāo)向量;Y為m維目標(biāo)空間;F(x)定義了由決策空間向目標(biāo)空間的映射關(guān)系;g(x)和h(x)分別為q個不等式約束條件和p個等式約束條件。在非支配解集中決策者只能根據(jù)具體問題選擇最適合的一個非支配解作為最終解。

定義1對于?x∈X,若滿足式(1)的約束條件gi(x)<0,i=1,2,…,q和hj(x)=0,j=1,2,…,p,稱x為可行解。

定義2對于X中所有可行解構(gòu)成的集合記為Xf,滿足Xf∈X

定義3若xk,xl∈Xf為滿足式(1)的兩個可行解,稱xkPareto支配xl當(dāng)且僅當(dāng)滿足式(2)和式(3)兩個條件,記為xk?xl。

?i=1,2,…,m,fi(xk)≤fi(xl)

(2)

?j=1,2,…,m,fj(xk)

(3)

定義4若x*∈Xf為Pareto最優(yōu)解(非支配解),當(dāng)且僅當(dāng)滿足?x∈Xf,x*?x。

定義5所有Pareto最優(yōu)解x*的集合構(gòu)成Pareto最優(yōu)解集(非支配解集),記為P*。

1.2粒子群優(yōu)化算法(PSO)

粒子群優(yōu)化算法(PSO)是一種模擬群聚生物的行為而得到的群聚智能算法[12]。該算法中,粒子就相當(dāng)于解空間的其中一個解,其的飛行狀態(tài)隨自身的飛行經(jīng)驗(yàn)和同伴的飛行經(jīng)驗(yàn)而改變,每個個體相當(dāng)于搜索空間中以一定的速度飛行的一個沒有體積沒有質(zhì)量的粒子。

粒子群算法的數(shù)學(xué)模型描述如下:設(shè)有m維搜索空間和N規(guī)模的粒子群。在第t代,第i個粒子在搜索空間的位置可表示為Xi(t)=(Xi1,Xi2,…,Xim);局部最優(yōu)位置Pi(t)是指第i個粒子在m維搜索空間中的歷史最優(yōu)位置;全局最優(yōu)位置Gi(t)是指整個粒子群的所有粒子在m維搜索空間中的歷史最優(yōu)位置;第i個粒子的速度定義為Vi(t)。每個粒子將按照式(4)和式(5)來更新自己的位置和飛行速度[11]

Vi(t+1)=wVi(t)+c1r1(Pi(t)-Xi(t))+c2r2(Gi(t)-Xi(t))

(4)

Xi(t+1)=Xi(t)+Vi(t+1)

(5)

其中,c1,c2為正常數(shù),稱為學(xué)習(xí)因子;ω是慣性因子;r1,r2是[0,1]間的隨機(jī)數(shù);設(shè)速度變化范圍為[vl,vu],粒子的第i個分量的位置變化范圍為[pl,pu],在迭代過程中,若該粒子的位置和速度超過了其取值邊界范圍,則取其邊界值。

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

2.1基于擁擠距離的缺陷分析

為有效處理約束,采用改進(jìn)的Pareto最優(yōu)解不斷“排擠”不滿足約束條件的解,從而使最后得到的最優(yōu)解滿足約束條件,在NSGA-II算法中擁擠距離是用來估計一個解周圍其他解的密集程度。對于每個目標(biāo)函數(shù),首先采用精英選擇策略進(jìn)行分層排序,結(jié)果每個個體均會處于某個層級上,統(tǒng)一層級上與該個體相鄰的前后兩個個體在各個子目標(biāo)方向上的距離之和定義為擁擠距離。計算所得擁擠距離越小,則所得的解越密集,其多樣性越小,反之說明所得解越稀疏,多樣性越大。最后根據(jù)計算所得擁擠距離的大小對粒子重新進(jìn)行降序排列。

如圖1所示,X和Y為問題域的兩個子目標(biāo),個體i的擁擠距離D[i]即圖中虛線四邊形的長與寬之和。即

(6)

當(dāng)有K個目標(biāo)時

(7)

其中,fn(i)為個體i在第n個目標(biāo)上的適應(yīng)度值。

圖1　擁擠距離計算方法

在NSGA-II算法中,擁擠距離大的個體周圍的分布性較好,更有可能被選擇;反之,擁擠距離小的個體被淘汰的概率更大。擁擠距離策略的優(yōu)點(diǎn)是保持種群的分布均勻,解集具有較好的多樣性,但該策略存在以下局限性:如圖2所示,個體a和個體b的擁擠距離近似無窮大,被擁擠距離策略保留的概率較大。但其代表極端偏向目標(biāo)Y或X的情況,雖對單目標(biāo)的適應(yīng)度較好,但對其他目標(biāo)的適應(yīng)度過差,應(yīng)將其淘汰;個體c和個體d的擁擠距離相同,在精英保留策略中會同時被淘汰或保留。但實(shí)際上個體c和個體d距離接近,只需保留一個;在第n+1層上,個體e的分布情況比f好,被保留的概率較大。但從全局考慮,結(jié)合第n層級可發(fā)現(xiàn),e周圍的個體遠(yuǎn)比f周圍緊密。

由以上分析可知,在擁擠距離策略中存在以下缺陷:(1)極限個體易被保留下;(2)好的個體可能被淘汰而差個體可能會被保留;(3)基于單個層級的擁擠距離考慮欠缺完整性,不能保證在全局的分布。

圖2　擁擠距離排擠機(jī)制的缺陷分析

2.2余弦距離的引入

每個粒子的全局最優(yōu)位置不僅決定非支配解的分布,且影響算法的收斂性?；镜亩嗄繕?biāo)粒子群算法基于存檔策略,而本文采用一種基于外部檔案的方案來存儲整個迭代過程中產(chǎn)生的非支配解,從外部檔案中隨機(jī)選擇每個粒子全局最優(yōu)位置,按這種策略選擇的大多數(shù)是處于稠密區(qū)域的非支配解,這樣帶來種群的多樣性的損失,會導(dǎo)致算法陷入局部最優(yōu)或提前收斂。為確保解的多樣性和非支配解分布的均勻性,應(yīng)使粒子向空間中非支配解相對少的區(qū)域搜索。因此,引入了一種基于余弦距離的排擠機(jī)制。

余弦距離度量機(jī)制在文本分類領(lǐng)域有著廣泛的應(yīng)用。文本空間和多目標(biāo)空間均屬于多維空間,具有一定相似性,在這種啟發(fā)下,文中將余弦距離度量機(jī)制應(yīng)用到多目標(biāo)優(yōu)化算法中,個體的每個目標(biāo)可看作是向量的一個維度,相應(yīng)的可建立表示該個體的目標(biāo)向量,利用目標(biāo)向量之間的余弦距離,確定個體之間的密集度關(guān)系。

假設(shè)多目標(biāo)優(yōu)化問題中有n個目標(biāo):(D1,D2,…,Dn),每個目標(biāo)都有確定的目標(biāo)函數(shù)。設(shè)種群規(guī)模為m,對種群內(nèi)第i個個體,其目標(biāo)函數(shù)值為(Vi1,Vi2,…,Vin)。由于不同目標(biāo)函數(shù)之間的數(shù)量級差異可能較大,若直接用函數(shù)值計算余弦距離,就不能平均反應(yīng)出每個目標(biāo)的特性,所以必須求出個體i的每個目標(biāo)函數(shù)之間的權(quán)重比

(8)

其中,Vki是個體i在目標(biāo)維度k上的實(shí)際函數(shù)值;ωki為計算獲得個體i的目標(biāo)維度k與所有目標(biāo)的權(quán)重比。

得到個體i的目標(biāo)向量di=(ωi1,ωi2,…,ωin),根據(jù)余弦公式可得兩個目標(biāo)的余弦距離為

(9)

兩個目標(biāo)向量之間的夾角為

〈di,dj〉=arccos(cos(di,dj))

(10)

2.3余弦距離排擠機(jī)制

余弦距離排擠機(jī)制的主要思想是用目標(biāo)向量之間的夾角值作為評價個體密集度的主要參數(shù)。不失一般性,為方便討論,選擇兩個目標(biāo)x、y進(jìn)行描述。

步驟1首先計算每個個體在x、y兩個目標(biāo)上的函數(shù)值,根據(jù)該目標(biāo)的函數(shù)值對每個個體進(jìn)行分層,保證每層個體相對于下一層都是Pareto非支配解。

步驟4對每個夾角進(jìn)行降序排序之后,根據(jù)預(yù)設(shè)的臨界夾角,分別比較臨界向量與單目標(biāo)向量X和Y的夾角,淘汰極端個體的向量。

2.4加速因子的選取

粒子的搜索過程主要包括全局搜索和局部搜索,若全局搜索較強(qiáng),則易忽略局部的最優(yōu)值,而若局部搜索過強(qiáng),又易使粒子陷入局部最優(yōu)。因此,在調(diào)整參數(shù)的過程中,需盡量避免出現(xiàn)兩種極端狀況,以保證得到最優(yōu)的Pareto解集。

在式(4)中,c1r1(Pi(t)-Xi(t))為局部認(rèn)知部分,初期較大的c1值可增強(qiáng)粒子群的局部搜索能力,c2r2(Gi(t)-Xi(t))為社會認(rèn)知部分,后期較大的c2值能增強(qiáng)粒子群的全局搜索能力。

為平衡粒子在搜索空間中的探測和開發(fā)能力,保證粒子的全局尋優(yōu)能力。c1按照式(11)在2～1范圍進(jìn)行線性遞減,c2按照式(12)在1～2范圍線性遞增

(11)

(12)

其中,currentGen為當(dāng)前迭代次數(shù),MaxGen為總迭代次數(shù)。

2.5外部精英種群的存儲策略

多目標(biāo)粒子群優(yōu)化算法的關(guān)鍵是如何確定每個粒子的全局最優(yōu)位置,因其不僅影響算法的收斂性,還對非支配解的多樣性起決定作用,在此采用外部精英種群存儲策略,將整個迭代過程中產(chǎn)生的非支配解存儲于一個外部精英種群中,每個粒子的全局最優(yōu)位置從外部精英種群中隨機(jī)選擇。

2.6局部最優(yōu)和全局最優(yōu)選擇策略

設(shè)在一次迭代中外部精英種群中的粒子已按余弦距離降序排列,去除極端粒子后,對于個體i的局部最優(yōu)位置有

(13)

而全局最優(yōu)值Gbest的選擇與局部最優(yōu)值類似。選取的Gbest應(yīng)處于Pareto前沿最分散的區(qū)域,所以本文選擇余弦距離最大的粒子最為全局最優(yōu)。

3實(shí)驗(yàn)與結(jié)果分析

3.1多目標(biāo)優(yōu)化測試的性能指標(biāo)

為更加準(zhǔn)確的說明兩種算法的分布度差異,本文中主要采用Schott在文獻(xiàn)[13]中提到的分布性評價方法對兩種算法的結(jié)果進(jìn)行定量分析。

(1)非支配解在目標(biāo)空間上的分布范圍SP,定義為

(14)

(2)最大散布范圍D,定義為

(15)

表示測量空間中Pareto解集中的兩個極值解的距離,反映所得非支配解的散布范圍D越大,所獲得解的范圍越廣。

3.2實(shí)驗(yàn)對比分析

為評價本文改進(jìn)的粒子群算法性能,選取3個測試函數(shù)對本文算法進(jìn)行驗(yàn)證。這3個測試函數(shù)是Deb在文獻(xiàn)[14]中提出的經(jīng)典ZDT系列函數(shù),其真實(shí)Pareto解集曲線分別為凸型、凹型和非連續(xù)型,具有一定的代表性。實(shí)驗(yàn)中對比PSO、CPSO(Chaos Particle Swarm Optimization)、基于擁擠距離的MOPSO算法,4種算法均采用實(shí)數(shù)編碼方式,參數(shù)設(shè)置如下:種群規(guī)模為100,進(jìn)化代數(shù)為100,被評價的個體為種群規(guī)模和進(jìn)化代數(shù)的乘積,即10 000個,慣性權(quán)重取0.5,加速因子按照上文策略選取。測試函數(shù)ZDT1~ZDT3表達(dá)式如下:

ZDT1:

(16)

m=30;0

ZDT2:

(17)

m=30;0

ZDT3:

(18)

m=30;0

圖3～圖5分別展示了兩種算法在ZDT1、ZDT2和ZDT3上的對比實(shí)驗(yàn)效果。從圖像對比中可看出,本文的改進(jìn)算法比PSO、CPSO、基于擁擠距離的MOPSO算法具有更好的分布性。

圖3　ZDT1的測試曲線

圖4　ZDT2 的測試曲線

圖5　ZDT3 的測試曲線

從表1和表2的30次實(shí)驗(yàn)對比結(jié)果可看出,本文所得ZDT1~ZDT3的平均SP值均較小,D值均較大,本文改進(jìn)算法與基于擁擠距離的MOPSO算法在解集的分布性上相比具有較大的分散性[15-16]。

表1　測試函數(shù)ZDT1-ZDT3的SP值結(jié)果對比

表2　測試函數(shù)ZDT1-ZDT3的D值結(jié)果對比

4結(jié)束語

本文在現(xiàn)有多目標(biāo)粒子群算法基礎(chǔ)上提出了一種基于余弦距離機(jī)制的多目標(biāo)粒子群優(yōu)化算法,該算法可提高粒子群的全局搜索能力和局部搜索能力,使粒子群搜索到的非支配解更逼近真實(shí)的Pareto前沿,擴(kuò)大了Pareto最優(yōu)解集的收斂性和多樣性,增強(qiáng)算法的全局尋優(yōu)能力。通過實(shí)驗(yàn)結(jié)果分析,與PSO、CPSO、基于擁擠距離的排擠機(jī)制MOPSO算法進(jìn)行比較,證實(shí)本文的算法在Pareto前沿的收斂性和多樣性方面均優(yōu)于PSO、CPSO、基于擁擠距離排擠機(jī)制,具有較高的效率。

參考文獻(xiàn)

[1]Wang B,Hou C.Multicast routing and its qos extension:problems,algorithms and protocols[J].IEEE Network,2000,14(1):22-36.

[2]ZhongW,ZhangJ,ChenW.Anoveldiscreteparticleswarmoptimizationtosolvetravelingsalesmanproblem[C].Singapore:IEEE:CongressonEvolutionaryComputation,2007.

[3]王凌,劉波.微粒群優(yōu)化與調(diào)度算法[M].北京:清華大學(xué)出版社,2008.

[4]GuanZ.Operatorsanalyzingofthenodominatedsortinggeneticalgorithm(NSGA)[J].JournalofIndustrialEngineeringManagement,2004(1):56-60.

[5]肖曉偉,肖迪,林錦國,等.多目標(biāo)優(yōu)化問題的研究概述[J].計算機(jī)應(yīng)用研究,2011,28(3):805-808,827.

[6]唐賢倫.混沌粒子群優(yōu)化算法理論及應(yīng)用研究[D].重慶:重慶大學(xué),2007.

[7]李娟,楊琳,劉金龍,等.基于自適應(yīng)混沌粒子群優(yōu)化算法的多目標(biāo)無功優(yōu)化[J].電力系統(tǒng)保護(hù)與控制,2011,39(9):26-31.

[8]KalyanmoyD,AgrawalS,PratabA,etal.Afastelitistnon-dominatedsortinggeneticalgorithmformulti-objectiveoptimization,KanGALreport200001[R].Kanpur,India:IndianInstituteofTechnology,2000.

[9]楊善學(xué).基于擁擠距離的多目標(biāo)粒子群算法[J].計算機(jī)工程與應(yīng)用,2009,45(22):24-26.

[10]李中凱,李艾民,朱真才.擁擠距離排序的多目標(biāo)文化粒子群優(yōu)化算法[J].控制與決策,2012,27(9):1406-1410.

[11]魏武,郭燕.基于擁擠距離的動態(tài)粒子群多目標(biāo)優(yōu)化算法[J].計算機(jī)工程與設(shè)計,2011,47(4):1422-1425.

[12]黃少榮.粒子群優(yōu)化算法綜述計[J].計算機(jī)工程與設(shè)計,2009(8):1977-1980.

[13]KennedyJ.Theparticleswarm:socialadaptationofknowledge[C].Berlin:EvolutionaryComputation,1997.

[14]SantanaRA,PontesMR,Bastos-FilhoCJA.Amultipleobjectiveparticleswarmoptimizationapproachusing[J].IEEETransactionsonComputerScience,2011,39(2):1511-1519.

[15]Crowdingdistanceandroulettewheel[C].Nanjing:NinthInternationalConferenceonIntelligentSystemsDesignandApplications,2009.

[16]DebK,PratapA,AgarwalS,etal.Afastandelitistmulti-objectivegeneticalgorithm:NSGA-II[J].IEEETransactionsonEvolutionaryComputation,2002,6(2):182-197.

中圖分類號TP301.6

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)03-048-06

doi:10.16180/j.cnki.issn1007-7820.2016.03.012

作者簡介:方欣欣(1989—),男,碩士研究生。研究方向:人工智能。龔如賓(1963—),男,教授。研究方向:多媒體視覺等。

收稿日期:2015- 08- 15