基于分解的多目標(biāo)量子差分進(jìn)化算法

常新功　劉文娟　呂亞麗

(山西財(cái)經(jīng)大學(xué)信息管理學(xué)院　山西 太原 030031)

?

基于分解的多目標(biāo)量子差分進(jìn)化算法

常新功劉文娟呂亞麗

(山西財(cái)經(jīng)大學(xué)信息管理學(xué)院山西 太原 030031)

基于分解的多目標(biāo)進(jìn)化算法MOEA/D(Multi-objective Evolutionary Algorithm Based on Decomposition)具有收斂速度快、分布性好等特點(diǎn)，但其在非凸函數(shù)上的性能有待提高。鑒于量子進(jìn)化算法在多峰值函數(shù)上的優(yōu)良性能，將MOEA/D與量子進(jìn)化算法相結(jié)合，提出基于分解的多目標(biāo)量子差分進(jìn)化算法QD-MOEA/D(Quantum Differential Multi-objective Evolutionary Algorithm Based on Decomposition)。QD-MOEA/D的量子染色體采用實(shí)數(shù)編碼，節(jié)省存儲(chǔ)空間，加快運(yùn)算速度。為了加快算法收斂速度并提高算法探測(cè)能力，量子染色體采取差分進(jìn)化，其變異方式為量子非門(mén)。在多個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)的實(shí)驗(yàn)結(jié)果表明，該算法改進(jìn)了MOEA/D在非凸函數(shù)上的收斂性和分布性。

MOEA/D量子計(jì)算差分進(jìn)化實(shí)數(shù)編碼

0　引　言

在科學(xué)研究和實(shí)際應(yīng)用中存在多個(gè)目標(biāo)同時(shí)優(yōu)化的問(wèn)題，這些問(wèn)題稱(chēng)之為多目標(biāo)優(yōu)化問(wèn)題MOPs(Multi-objective Optimization Problems)。在MOPs中，多個(gè)目標(biāo)之間往往存在著沖突，如何在多個(gè)目標(biāo)之間進(jìn)行權(quán)衡得到最優(yōu)解，是求解MOPs的核心和關(guān)鍵。大量探索研究表明，進(jìn)化算法是求解MOPs的有效方法。通過(guò)進(jìn)化計(jì)算可以得到一組或多組最優(yōu)解[1,2]。

Zhang等人[3]于2007年提出基于分解的多目標(biāo)進(jìn)化算法MOEA/D。該算法將MOPs中的多個(gè)目標(biāo)以不同的權(quán)重分解為若干個(gè)單目標(biāo)優(yōu)化子問(wèn)題，然后進(jìn)化由這些子問(wèn)題的解組成的種群，逼近真實(shí)的Pareto前沿PF(Pareto Front)。MOEA/D算法因其簡(jiǎn)單、高效而備受關(guān)注[4,5]。

為改進(jìn)算法性能，在原版MOEA/D的基礎(chǔ)上引入DE算子，提高了算法的收斂速度，有效地解決了復(fù)雜PF問(wèn)題[4]；另一版本的MOEA/D采用動(dòng)態(tài)分配計(jì)算資源的策略，優(yōu)化了資源配置[6]。在MOEA/D中采用兩種不同聚合函數(shù)能降低選擇聚合函數(shù)的難度[7]。Noura等人將MOEA/D算法與PSO算法進(jìn)行結(jié)合，進(jìn)一步改善了算法的性能[8]。模糊Pareto支配的概念引入，明顯提高了算法的收斂速度[9]。針對(duì)MOEA/D中的交配池固定這一問(wèn)題，MOEA/D-AMS動(dòng)態(tài)調(diào)整個(gè)體交配池以避免陷入局部最優(yōu)[10]。在國(guó)內(nèi)，劉海林等人采用在超球面均勻取點(diǎn)構(gòu)造權(quán)重的策略，提高了非劣解的均勻性[11]；辜方清等人提出一種基于投影和等距插值的動(dòng)態(tài)權(quán)重設(shè)計(jì)方法，增強(qiáng)解的均勻性[12]；周攀等人將正交試驗(yàn)設(shè)計(jì)、自適應(yīng)占優(yōu)機(jī)制以及精英策略引入到MOEA/D算法中，提高了算法的性能[13]。

上述研究主要針對(duì)算法的收斂性和分布性，很少對(duì)MOEA/D算法在非凸PF的MOPs上的不足進(jìn)行改進(jìn)。量子進(jìn)化算法QEA(Quantum Evolutionary Agorithm)[14-16]是一種收斂速度快、全局尋優(yōu)能力強(qiáng)的算法。該算法在量子計(jì)算的理論基礎(chǔ)上，結(jié)合進(jìn)化算法的思想，采用量子位編碼染色體，并用量子門(mén)更新種群完成進(jìn)化搜索。與傳統(tǒng)進(jìn)化算法相比，QEA能夠在探索與開(kāi)發(fā)之間取得平衡，尤其在多峰值函數(shù)上有著出色的表現(xiàn)。

鑒于量子進(jìn)化算法的優(yōu)良性能，本文試圖將MOEA/D與QEA結(jié)合以達(dá)到提高非凸PF問(wèn)題的性能的目的。但單純地將QEA引入到MOEA/D中不僅無(wú)法提高算法在非凸PF問(wèn)題的性能，還降低了算法在凸PF問(wèn)題的收斂性。由此，本文提出一種基于分解的多目標(biāo)量子差分進(jìn)化算法QD-MOEA/D。該算法按照權(quán)重將多個(gè)目標(biāo)分解為多個(gè)子問(wèn)題，每個(gè)子問(wèn)題的個(gè)體采用量子染色體編碼。其中，量子染色體采用實(shí)數(shù)編碼，利用差分算子進(jìn)行進(jìn)化，采用量子與非門(mén)進(jìn)行變異，探測(cè)后產(chǎn)生的實(shí)數(shù)個(gè)體用于更新鄰域。以期提高M(jìn)OEA/D在非凸PF的MOPs上的性能。

1　相關(guān)定義

1.1多目標(biāo)優(yōu)化問(wèn)題(MOP)

定義1多目標(biāo)優(yōu)化問(wèn)題(MOP)

多目標(biāo)優(yōu)化問(wèn)題由n個(gè)決策變量參數(shù)，m個(gè)目標(biāo)函數(shù)和c個(gè)約束條件組成，可描述為：

minimizeF(x)=[f1(x),f2(x),…,fm(x)]T

subject tog(x)=(g1(x),g2(x),…,gk(x))≤0

(1)

wherex=(x1,x2,…,xn)T∈Ω

1.2Pareto最優(yōu)解及Pareto前沿

定義2Pareto支配關(guān)系

對(duì)于任意決策向量a,b∈Ω，當(dāng)且僅當(dāng)?i∈{1,2,…,m}，有fi(a)≤fi(b)且?j∈{1,2,…,m}，使fj(a)

定義3Pareto最優(yōu)解

Pareto最優(yōu)解是指如果Ω中沒(méi)有支配x*的解，則稱(chēng)x*為式(1)中MOP的一個(gè)最優(yōu)解。

通常多目標(biāo)優(yōu)化問(wèn)題有多個(gè)Pareto最優(yōu)解，這些解的集合稱(chēng)為Pareto最優(yōu)解集。Pareto最優(yōu)解在目標(biāo)函數(shù)空間的像集稱(chēng)為Pareto前沿。

1.3量子編碼及測(cè)量

在量子進(jìn)化算法(QEA)中，采用量子編碼方式。在該編碼方式中，每個(gè)個(gè)體可由m個(gè)量子位組成。量子位是用一個(gè)二維列向量(α,β)T表示的QEA中最小信息單位，其中α,β∈R，且α2+β2=1，α2表示該量子位為0的概率，β2表示該量子位為1的概率。

一個(gè)l位的Q-bit組成的一個(gè)決策變量q可以表示為如下的2×l矩陣形式：

(2)

在進(jìn)化算法中，量子染色體表示一次進(jìn)化過(guò)程中所有決策變量的組合，可表示為：

(3)

其中，Qi代表第i個(gè)個(gè)體的染色體，i∈(1,2,…,g)，g為種群規(guī)模，n為決策變量的維度，l為每個(gè)決策變量的量子位個(gè)數(shù)。

探測(cè)是指將由量子染色體表示的種群轉(zhuǎn)化為滿(mǎn)足約束條件的決策變量種群的過(guò)程。具體步驟為：對(duì)量子染色體中每個(gè)量子位，隨機(jī)產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù)r，將r與量子位中表示的0的概率進(jìn)行比較，如果r較小，則該位取0，否則取1。

1.4切比雪夫法

在MOEA/D中，最常用的分解多目標(biāo)的方法是切比雪夫法，該分解方法如下所示：

(4)

2　基于分解的多目標(biāo)量子差分進(jìn)化算法

QD-MOEA/D主要針對(duì)MOEA/D在求解非凸MOP函數(shù)上的不足，利用量子進(jìn)化算法在多峰值函數(shù)上優(yōu)良性能，將量子計(jì)算引入到MOEA/D中。在算法中，量子染色體采用實(shí)數(shù)編碼，簡(jiǎn)化量子計(jì)算；差分進(jìn)化量子染色體，加快收斂速度；采用量子非門(mén)進(jìn)行變異，有效地保障了進(jìn)化種群的多樣性。

2.1實(shí)數(shù)量子染色體編碼

量子染色體采用實(shí)數(shù)編碼減少存儲(chǔ)空間，簡(jiǎn)化運(yùn)算，提高算法性能[17]。在傳統(tǒng)的量子進(jìn)化算法中，由于量子比特(α,β)T。可以用實(shí)數(shù)θ表示為：(cosθ,sinθ)T，問(wèn)題式(1)的決策變量維度為n，令每個(gè)決策變量用1個(gè)量子位表示，則第i個(gè)體xi可以表示為：

xi=(|xi,1|xi,2|∧|xi,n|)

(5)

其中，θ=2πrand，rand是[0,1]范圍內(nèi)的隨機(jī)數(shù)，i∈(1,2,…,g)，g為進(jìn)化算法的進(jìn)化過(guò)程中種群的規(guī)模。

(6)

其中，i∈(1,2,…,g)，g為進(jìn)化算法的進(jìn)化過(guò)程中種群的規(guī)模，j∈(1,2,…,n)，n為決策變量維度。

2.2基于差分進(jìn)化的量子染色體更新

差分進(jìn)化算法(DE)[18]是一種基于種群的全局啟發(fā)式全局搜索算法，具有原理簡(jiǎn)單、受控參數(shù)少、魯棒性強(qiáng)等特點(diǎn)。將差分進(jìn)化算法應(yīng)用到量子染色體的更新，能夠充分利用鄰域信息，加快算法收斂速度。

差分進(jìn)化算法有多種形式，在算法QD-MOEA/D中，采用DE/rand/1/bin的方式對(duì)量子染色體進(jìn)行進(jìn)化，其交叉、變異操作具體所示：

量子變異操作: 隨機(jī)當(dāng)前個(gè)體的鄰域中選擇一個(gè)量子染色體，用其量子位作為基向量和另外兩個(gè)不同的鄰域量子染色體的量子位作為差分向量，生成的方法如下:

(7)

其中，s1、s2、s3是個(gè)體i的鄰域中的三個(gè)不同的個(gè)體，F(xiàn)∈[0,1]為收縮因子，k表示當(dāng)前種群，k+1表示下一代種群。

量子交叉操作: 將新產(chǎn)生的量子變異個(gè)體種群與父代個(gè)體種群混合產(chǎn)生新個(gè)體種群。

(8)

其中，j∈(1,2,…,n)，n為決策變量維度，rand是[0,1]之間的隨機(jī)數(shù)，CR為量子交叉因子，一般是[0,1]區(qū)間的數(shù)。

2.3量子變異與測(cè)量

量子門(mén)是量子進(jìn)化算法進(jìn)化的動(dòng)力，量子門(mén)有多種，本文采用量子非門(mén)對(duì)量子染色體進(jìn)行變異，量子非門(mén)的變異處理方法如下:

(9)

令變異概率為PM，若rand

量子染色體是二維向量，經(jīng)過(guò)測(cè)量后才能在多目標(biāo)函數(shù)中進(jìn)行計(jì)算，測(cè)量的方法如下：

(10)

其中r是隨機(jī)產(chǎn)生的一個(gè)0到1之間的隨機(jī)數(shù)，i∈(1,2,…,g)，g為進(jìn)化算法的進(jìn)化過(guò)程中種群的規(guī)模，j∈(1,2,…,n)，n為決策變量的維度。

2.4算法流程

QD-MOEA/D采用Tchebycheff分解方法。設(shè)G為種群的規(guī)模,λ1,λ2,…,λg為一個(gè)分布均勻的權(quán)向量集,z*為參考點(diǎn),QD-MOEA/D將求解PF的問(wèn)題式(1)采用Tchebycheff方法分解為G個(gè)單目標(biāo)子問(wèn)題,第i個(gè)子問(wèn)題可描述為:

在 QD-MOEA/D 中，從權(quán)向量λi所在的集合{λ1,λ2,…,λG}中選擇與λi距離最近的T個(gè)權(quán)向量作為λi的鄰域，權(quán)向量λi的鄰域所在的子問(wèn)題就是第i子問(wèn)題的鄰域。每一代種群由各個(gè)子問(wèn)題的當(dāng)前最優(yōu)解構(gòu)成，而每一個(gè)子問(wèn)題的優(yōu)化用到鄰域信息。

在進(jìn)化過(guò)程中，QD-MOEA/D 要保存的信息有:

① 組成群體的G條實(shí)數(shù)量子染色體：θ1,θ2,…,θG∈ΩQEA，其中θi為子問(wèn)題i的量子染色體；

② 組成群體的G個(gè)滿(mǎn)足約束條件實(shí)數(shù)個(gè)體：x1,x2,…,xG∈ΩMOP，其中xi為子問(wèn)題i的當(dāng)前最優(yōu)解；

③ FV1,FV2,…,FVG,其中FVi=F(xi)，i=1,2,…,N;

④ z=(z1,z2,…,zm)T,其中zi為目標(biāo)函數(shù)fi目前為止所找到的最優(yōu)值;

⑤ 外部群體(EP),用于存儲(chǔ)搜索過(guò)程中所找到的非支配解。

QD-MOEA/D算法的流程如下

輸入：

① MOP (1);

② 結(jié)束條件;

③ G：QD-MOEA/D 所分解的子問(wèn)題個(gè)數(shù);

④ λ1,λ2,…,λG：分布均勻的G個(gè)權(quán)向量;

⑤ T:權(quán)向量的鄰域的大小。

輸出：EP。

Step 1初始化。

Step 1.1設(shè)置EP=φ。

Step 1.2計(jì)算任意兩個(gè)權(quán)向量的歐氏距離,為每個(gè)權(quán)向量選出最近的T個(gè)向量作為它的鄰域。設(shè)第i個(gè)子問(wèn)題的鄰域權(quán)向量下標(biāo)為B(i)={i1,i2,…,iT}，其中i=1,2,…,G，即λi1,λi2,…,λiT為距離λi最近的T個(gè)權(quán)向量。

Step 1.3按照式(5)生成隨機(jī)的量子染色體θ1,θ2,…,θG，按照式(6)對(duì)染色體進(jìn)行空間變換，按照式(10)對(duì)染色體進(jìn)行探測(cè)，得到初始化種群x1,x2,…,xG,設(shè)FVi=F(xi)，其中i=1,2,…,G。

Step 1.4根據(jù)計(jì)算得到目標(biāo)函數(shù)的函數(shù)值，初始化z=(z1,z2,…,zm)T。

Step 2更新。

For i=1,2,…,G do

Step 2.1產(chǎn)生新個(gè)體：從B(i)中隨機(jī)選出三個(gè)不同的元素s1、s2、s3，取出其對(duì)應(yīng)的量子染色體，按照式(7)進(jìn)行量子變異操作，按照式(8)進(jìn)行量子交叉操作，按照式(9)對(duì)量子染色體進(jìn)行量子非門(mén)變異操作，按照式(6)進(jìn)行空間變換，按照式(10)探測(cè)，生成新解y。

Step 2.2更新最優(yōu)解：對(duì)每個(gè)函數(shù)fj，若zj>fj(y),則zj=fj(y)，其中j=1,2,…,m。

Step 2.3更新鄰域數(shù)值：在第i個(gè)子問(wèn)題中，令每個(gè)鄰域下標(biāo)b∈B(i)，對(duì)于每個(gè)鄰域個(gè)體xb，如果gte(y|λb,z)≤gte(xb|λb,z),則xb=y，F(xiàn)Vb=F(y)。

Step 2.4更新EP：將EP中所有被F(y)支配的解移出EP;若F(y)不被EP中的任意解支配,則將F(y)移入EP。

Step 3停止判斷:若滿(mǎn)足停止準(zhǔn)則,則算法停止,輸出EP,否則返回Step2。

3　算法測(cè)試及結(jié)果分析

為了分析測(cè)試QD-MOEA/D的收斂性和分布性，本文選擇9個(gè)標(biāo)準(zhǔn)的測(cè)試函數(shù)，分別為ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1、DTLZ2、DTLZ3、DTLZ4[19,20]作為測(cè)試用例。并通過(guò)計(jì)算QD-MOEA/D與MOEA/D和NSGAII[21]的評(píng)價(jià)指標(biāo)來(lái)驗(yàn)證QD-MOEA/D算法的性能。

3.1測(cè)試函數(shù)

測(cè)試函數(shù)的選擇關(guān)系到算法的評(píng)價(jià), 選擇科學(xué)合理的測(cè)試函數(shù)有助于對(duì)算法的評(píng)價(jià)。選擇測(cè)試函數(shù)通用的做法是選擇大眾認(rèn)可的具有代表性的測(cè)試函數(shù)。本文中采用了5個(gè)標(biāo)準(zhǔn)的兩目標(biāo)的的函數(shù)ZDT1、ZDT2、ZDT3、ZDT4、ZDT6[19]，其中函數(shù)ZDT1、ZDT4的為凸函數(shù)，ZDT2、ZDT6為凹函數(shù)，ZDT3為分段函數(shù)。同時(shí)采用了4個(gè)標(biāo)準(zhǔn)三目標(biāo)的函數(shù)DTLZ1、DTLZ2、DTLZ3、DTLZ4[20]，其中DTLZ1為凸函數(shù)，DTLZ2、DTLZ3、DTLZ4為非凸函數(shù)。并且上述函數(shù)的決策變量的維數(shù)均設(shè)置為10。上述所選9個(gè)測(cè)試用例能夠客觀地表現(xiàn)QD-MOEA/D的性能。

3.2評(píng)價(jià)指標(biāo)

為了能夠更加準(zhǔn)確、全面地對(duì)該算法進(jìn)行評(píng)價(jià)，避免單個(gè)性能度量指標(biāo)的片面性，本文采用以下三個(gè)常用的性能評(píng)價(jià)指標(biāo)來(lái)分析算法的收斂性和分布性。在下面性能指標(biāo)中，P*為真實(shí)PF上均勻分布的 Pareto 最優(yōu)解集合, X是通過(guò)多目標(biāo)進(jìn)化算法得到的近似 Pareto 最優(yōu)解集，m為目標(biāo)函數(shù)的個(gè)數(shù)，|X|為集合X中元素的個(gè)數(shù)。

(1) Generational Distance (GD)指標(biāo)[22]

GD指標(biāo)度量X到P*的距離,定義為:

(12)

其中,d(v,P*)是v距離P*的最小歐氏距離。因此,該指標(biāo)越低，表明算法得到的解收斂性越好，越接近真實(shí)PF。如果GD(A,P*)=0表明所求得的每個(gè)近似 Pareto 最優(yōu)解都是真實(shí)Pareto最優(yōu)解,這是最理想的情況。

(2) IGD(Inverted Generational Distance)指標(biāo)[22]

IGD指標(biāo)度量X到P*的距離,定義為:

(13)

其中，d(y*,P)是y*距離X的最小歐氏距離。若P*中真實(shí)的Pareto解足夠多且能描繪出完整的Pareto前沿，則IGD指標(biāo)在一定的程度上能同時(shí)反映出所求得的近似PF的多樣性和收斂性。 IGD指標(biāo)值越小,所求得的近似PF越接近整個(gè)真實(shí)PF,而不能遺漏任何一部分。

(3) Spacing(S)指標(biāo)[23]

S指標(biāo)定義為:

(14)

式中，S指標(biāo)用于評(píng)估算法所求得的近似Pareto解在目標(biāo)空間上的均勻性。該指標(biāo)越小，表明所求得的Pareto解在目標(biāo)空間上分布越均勻。

3.3參數(shù)設(shè)置

本文中所有算法對(duì)所有測(cè)試函數(shù)均采用以下設(shè)置：進(jìn)化群體規(guī)模G=100，鄰居大小T=20；縮放因子F=0.5，交叉因子CR=0.5,變異概率PM=0.05。

3.4實(shí)驗(yàn)結(jié)果及分析

為了驗(yàn)證QD-MOEA/D算法是否能夠得到最優(yōu)解，分別將該算法在9個(gè)函數(shù)上運(yùn)行50次。為了更直觀地看出算法的收斂性和非支配解的分布性，將QD-MOEA/D算法得到的非劣解繪制成近似PF，并與真實(shí)PF進(jìn)行比較，如圖1-圖9所示。

圖1　QD-MOEA/D在ZDT1上的測(cè)試結(jié)果

圖2　QD-MOEA/D在ZDT2上的測(cè)試結(jié)果　　　　　　圖3　QD-MOEA/D在ZDT3上的測(cè)試結(jié)果

圖4　QD-MOEA/D在ZDT4上的測(cè)試結(jié)果　　　　　　圖5　QD-MOEA/D在ZDT6上的測(cè)試結(jié)果

圖6　QD-MOEA/D在DTLZ1上的測(cè)試結(jié)果　　　　　　圖7　QD-MOEA/D在DTLZ2上的測(cè)試結(jié)果

圖8　QD-MOEA/D在DTLZ3上的測(cè)試結(jié)果　　　　　　圖9　QD-MOEA/D在DTLZ4上的測(cè)試結(jié)果

從以上QD-MOEA/D算法求解的近似PF可知，該算法在9個(gè)測(cè)試函數(shù)得到的近似PF多數(shù)逼近真實(shí)的PF，且分布比較均勻，只有ZDT4函數(shù)的測(cè)試效果較差，與真實(shí)PF距離較遠(yuǎn)。但從整體上看，QD-MOEA/D算法具有較好的收斂性，最后求解得出的Pareto解分布比較均勻，尤其是在非凸函數(shù)上，這種優(yōu)勢(shì)更加明顯。

為了更加科學(xué)地分析QD-MOEA/D算法的性能，將算法與MOEA/D和NSGAII進(jìn)行對(duì)比實(shí)驗(yàn)。QD-MOEA/D算法與QD-MOEA/D算法的參數(shù)設(shè)置如3.3節(jié)所示，NSGAII算法的種群規(guī)模為100，將三種算法分別在9個(gè)測(cè)試函數(shù)中運(yùn)行50次，并計(jì)算度量指標(biāo)GD、IGD、S的均值(mean)和方差(std)，對(duì)算法的收斂性、分布性進(jìn)行比較分析。GD、IGD、S的統(tǒng)計(jì)結(jié)果如表1所示(效果較好的已用黑體標(biāo)出)。

表1　各算法的GD、IGD、S均值和方差

由表1可知，在相同的條件下，與MOEA/D及NSGAII相比，QD-MOEA/D的收斂性、分布性在所測(cè)試的大多數(shù)函數(shù)中表現(xiàn)良好，且各個(gè)性能指標(biāo)的方差非常小，表明算法具有良好的魯棒性。

在表1中，對(duì)GD和IGD數(shù)據(jù)的均值和方差進(jìn)行比較，除了凸函數(shù)ZDT4外， QD-MOEA/D在其他測(cè)試函數(shù)上的GD值和IGD值均小于MOEA/D，表明該算法的收斂性均優(yōu)于MOEA/D。但在三目標(biāo)優(yōu)化函數(shù)DTLZ1和DTLZ3上，QD-MOEA/D和MOEA/D的GD值和IGD值高于NSGAII，故NSGAII在函數(shù)DTLZ1和DTLZ3的收斂性?xún)?yōu)于QD-MOEA/D和MOEA/D。對(duì)GD和IGD數(shù)據(jù)結(jié)果分析表明，QD-MOEA/D算法改進(jìn)了MOEA/D在非凸函數(shù)上的收斂性。

表1中S指標(biāo)用于度量算法的分布性，從指標(biāo)S的數(shù)據(jù)中可知，QD-MOEA/D的分布性在ZDT1、ZDT2、ZDT4上略差于MOEA/D，在DTLZ1和DTLZ3上略差于NSGAII。QD-MOEA/D的分布性和多樣性表現(xiàn)欠佳的原因?yàn)椋毫孔尤旧w進(jìn)行差分進(jìn)化時(shí)，隨機(jī)從鄰域選取三個(gè)點(diǎn)，在進(jìn)化初期，因?yàn)閭€(gè)體均不相同，因此進(jìn)化速度很快。到了進(jìn)化后期，隨著對(duì)領(lǐng)域的更新，使得很多個(gè)體的決策變量相同，尤其是在三個(gè)目標(biāo)的函數(shù)中更為明顯。鄰域中相似的個(gè)體越多，種群的多樣性越小，隨機(jī)從鄰域中選取的個(gè)體相同的概率就越大。因此新產(chǎn)生的個(gè)體很可能與原有個(gè)體相同，使種群失去進(jìn)化能力，從而導(dǎo)致種群個(gè)體多樣性低，分布性差。所以在算法運(yùn)行后期，需要調(diào)整量子染色體的進(jìn)化策略，從而提高算法性能。但從整體上看，QD-MOEA/D算法的收斂性、分布性均優(yōu)于MOEA/D和NSGAII，且其魯棒性強(qiáng)。

QD-MOEA/D與MOEA/D相比具有以下特點(diǎn)：

QD-MOEA/D是在MOEA/D的基礎(chǔ)上引入QEA，在算法中用Q-bit對(duì)染色體進(jìn)行編碼，每個(gè)Q-bit都表示該量子在某種狀態(tài)時(shí)的概率，對(duì)Q-bit的進(jìn)化會(huì)影響到與之對(duì)應(yīng)種群。在前期探查中，Q-bit通過(guò)對(duì)整個(gè)目標(biāo)空間的搜索，保障了種群的多樣性；探查的后期，Q-bit趨于某個(gè)固定的概率，使算法收斂。因此QD-MOEA/D對(duì)PF的形狀不敏感，在非凸函數(shù)上依舊有良好的性能。

QD-MOEA/D的量子染色體采用實(shí)數(shù)編碼。采用這種編碼方式，在不減少個(gè)體信息前提下，節(jié)省了存儲(chǔ)空間，與MOEA/D相比，在每個(gè)個(gè)體只需多記錄一行實(shí)數(shù)值。此外，實(shí)數(shù)編碼避免了傳統(tǒng)QEA不同進(jìn)制之間的轉(zhuǎn)換，與MOEA/D相比，僅增加了量子染色體探測(cè)的過(guò)程，在每次迭代時(shí)，其時(shí)間復(fù)雜度僅增加O(1)，對(duì)整體的時(shí)間復(fù)雜度無(wú)太大的影響。

QD-MOEA/D沿用了MOEA/D的差分進(jìn)化，但差分進(jìn)化的對(duì)象不再是個(gè)體，而是量子染色體。差分計(jì)算使量子染色體在目標(biāo)空間內(nèi)進(jìn)行啟發(fā)式全局搜索，使量子染色體充分利用鄰域信息，加快算法收斂速度，為進(jìn)化提供新的動(dòng)力。

QD-MOEA/D采用量子非門(mén)進(jìn)行變異。傳統(tǒng)的QEA中，量子門(mén)是算法進(jìn)化的動(dòng)力，但在QD-MOEA/D中，采用量子非門(mén)是為了增加個(gè)體的多樣性，避免個(gè)體陷入局部最優(yōu)。

上述實(shí)驗(yàn)結(jié)果也表明，QD-MOEA/D在進(jìn)化后期種群的多樣性減少，這主要是因?yàn)榈搅诉M(jìn)化后期，更新鄰域后鄰域的個(gè)體都有重復(fù)，進(jìn)行差分計(jì)算后新個(gè)體很有可能與原個(gè)體相同，使算法失去了進(jìn)化能力。為了進(jìn)一步提高算法的性能，可在對(duì)Q-bit進(jìn)行差分計(jì)算時(shí)動(dòng)態(tài)地增加一個(gè)θ值，這將是QD-MOEA/D未來(lái)的研究方向。

4　結(jié)　語(yǔ)

本文提出了一種基于分解的量子差分進(jìn)化算法。該算法將MOEA/D與QEA相結(jié)合，對(duì)量子染色體進(jìn)行實(shí)數(shù)編碼并用差分進(jìn)化、非門(mén)進(jìn)行更新，增加個(gè)體的多樣性，測(cè)量后更新鄰域，充分利用鄰域知識(shí)，加快進(jìn)化速度。在9個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)上的實(shí)驗(yàn)結(jié)果表明，該算法明顯改善了MOEA/D算法在非凸函數(shù)上的收斂性和分布性。但實(shí)驗(yàn)也反映出該算法由于依賴(lài)鄰域信息，在進(jìn)化后期使個(gè)體的多樣性減少，從而使函數(shù)的分布性變差。因此，下一步的研究工作是如何在產(chǎn)生新個(gè)體時(shí)增加個(gè)體的多樣性。

[1] Back T,Hammel U,Schwefel H P.Evolutionary computation:Comments on the History and Current State[J].IEEE Transactions on Evolutionary Computation,1997,1(1):3-17.

[2] Eiben A E,Smith J E.Introduction to Evolutionary Computing[M].Springer:Berlin,2003.

[3] Zhang Q,Li H.MOEA/D:A Multi-objective Evolutionary Algorithm Based on Decomposition[J].IEEE Transactions on Evolutionary Computation,2007,11(6):712-731.

[4] Li H,Zhang Q.Multiobjective Optimization Problems with Complicated Pareto Sets,MOEA/D and NSGA-II[J].IEEE Transaction on Evolutionary Computation,2009,12(2):284-302.

[5] 公茂果,焦李成,楊咚咚,等.進(jìn)化多目標(biāo)優(yōu)化算法研究[J].軟件學(xué)報(bào),2009,20(2):271-289.

[6] Zhang Q,Liu w,Li H.The Performance of a New Version of MOEA/D.CEC09 Unconstrained MOP Test Instances[C]//Austria:CEC’09.IEEE Congress,2009:203-208.

[7] Ishibuchi H,Sakane Y,Tsukamoto N,et al.Simultaneous use of different scalarizing functions in MOEA/D[C]//USA:Process of Genetic and Evolutionary Computation Conference-GECCO,2010:519-526.

[8] Noura A I Moubayed,Andrei Petrovski,John McCall.A Novel Smart Multi-Objective Particle Swarm Optimization Using Decomposition[C]//USA:PPSN,2010:1-10.

[9] Nasir M D,Mondall A K,Sengupta S,et al.An Improved Mutiobjective Evolutionary Algorithm based on Decomposition with Fuzzy Dominance[C]//USA:CEC,2011:765-772.

[10] Chiang Tsungche,Lai Yungpin.MOEA/D-AMS:Improving MOEA/D by an Adaptive Mating Selection Mechanism[C]//USA:CEC,2011:1473-1480.

[11] Liu Hailin,Li Xueqiang.The multiobjective evolutionary algorithm based on determined weight and sub-regional search[C]//IEEE Congress on Evolutionary Computation,2009:1928-1934.

[12] 辜方清.多目標(biāo)進(jìn)化算法中多樣性與均勻性策略研究[D].廣州:廣東工業(yè)大學(xué),2011.

[13] 周攀,張冬梅,龔文引,等.基于正交設(shè)計(jì)的自適應(yīng)ε占優(yōu)MOEA/D算法研究[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(2):58-64,124.

[14] Hey T.Quantum computing:An introduction[J].Computing and Control Engineering Journal,1996,10(3):105-112.

[15] Narayanan A,Moore M.Quantum-inspired genetic algorithms[C]//Proceedings of the International Congress on Evolutionary Computation,Piscataway:IEEE Press,July 1996:61-66.

[16] Han K H,Park K H,Lee C H,et al.Parallel Quantum-inspired genetic algorithm for combinational optimization problems[C]//Proceedings of the 2001 Congress on Evolutionary Computation:IEEE Press, May 2001.

[17] 陳曉峰,楊廣明,黃明.一種實(shí)數(shù)編碼的量子差分進(jìn)化算法[J].小型微型計(jì)算機(jī)系統(tǒng),2013,34(5):1141-1146.

[18] Storn R,Price K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization,1997,11(4):341-359.

[19] Zitzler E,Deb K,Thiele L.Comparison of multiobjeetive evolutionary a1gorithms: empirical results[J].Evolutionary Computation,2000,8(2):173-195.

[20] Deb K,Thiele L,Laumanns M,et al.Scalable multiobjective optimization test problems[C]//Process of IEEE Congress on Evolutionary Computation (CEC’02),New Jersey:IEEE press,2002:825-830.

[21] Deb K,Pratap A,Agarwal S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].IEEE Transactions on Evolutionary Computation,2002,6(2):182-197.

[22] Zitzler E,Thiele L,Laumanns M,et al.Performance assessment of multiobjective optimizers:an analysis and review[J].IEEE Trans.on Evolutionary Computation,2003,7(2):117-132.

[23] Schott J.Fault Tolerant Design Using Single and Multicriteria Genetic Algorithm Optimization[D].Master Thesis.Department of Aeronautics and Astronautics,Massachusetts Institute of Technology,Cambridge,MA,1995.

A QUANTUM DIFFERENTIAL MULTI-OBJECTIVE EVOLUTIONARY ALGORITHM BASED ON DECOMPOSITION

Chang XingongLiu WenjuanLü Yali

(FacultyofInformationandManagement,ShanxiUniversityofFinanceandEconomics,Taiyuan030031,Shanxi,China)

Multi-objective evolutionary algorithm based on decomposition (MOEA/D) is featured by high convergence rate and good distribution. However, its performance in non-convex functions is not good enough. In view of the excellent properties of quantum evolutionary algorithm in multi-peak functions, we combined MOEA/D with QEA and proposed the decomposition-based quantum differential multi-objective evolutionary algorithm (QD-MOEA/D). The quantum chromosome of QD-MOEA/D adopts real number in encoding, this saves memory space and accelerates operation speed. In order to speed up convergence speed and improve detection ability of algorithm, the quantum chromosome adopts differential evolution, and its mutation way is the quantum non-gate. Results of experiments on several standard test functions showed that the algorithm improved the convergence and the distribution of MOEA/D in non-convex functions.

MOEA/DQuantum computationDifferential evolutionReal-encoding

2015-01-23。山西省自然科學(xué)基金項(xiàng)目(2013011016-4，2014011022-2)；山西省高?？萍紕?chuàng)新項(xiàng)目(2013124)。常新功，教授，主研領(lǐng)域：進(jìn)化計(jì)算，數(shù)據(jù)挖掘。劉文娟，碩士生。呂亞麗，副教授。

TP301

A

10.3969/j.issn.1000-386x.2016.08.062