基于分解的多目標量子差分進化算法

常新功　劉文娟　呂亞麗

(山西財經大學信息管理學院　山西 太原 030031)

?

基于分解的多目標量子差分進化算法

常新功劉文娟呂亞麗

(山西財經大學信息管理學院山西 太原 030031)

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

MOEA/D量子計算差分進化實數編碼

0　引　言

在科學研究和實際應用中存在多個目標同時優化的問題，這些問題稱之為多目標優化問題MOPs(Multi-objective Optimization Problems)。在MOPs中，多個目標之間往往存在著沖突，如何在多個目標之間進行權衡得到最優解，是求解MOPs的核心和關鍵。大量探索研究表明，進化算法是求解MOPs的有效方法。通過進化計算可以得到一組或多組最優解[1,2]。

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

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

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

鑒于量子進化算法的優良性能，本文試圖將MOEA/D與QEA結合以達到提高非凸PF問題的性能的目的。但單純地將QEA引入到MOEA/D中不僅無法提高算法在非凸PF問題的性能，還降低了算法在凸PF問題的收斂性。由此，本文提出一種基于分解的多目標量子差分進化算法QD-MOEA/D。該算法按照權重將多個目標分解為多個子問題，每個子問題的個體采用量子染色體編碼。其中，量子染色體采用實數編碼，利用差分算子進行進化，采用量子與非門進行變異，探測后產生的實數個體用于更新鄰域。以期提高MOEA/D在非凸PF的MOPs上的性能。

1　相關定義

1.1多目標優化問題(MOP)

定義1多目標優化問題(MOP)

多目標優化問題由n個決策變量參數，m個目標函數和c個約束條件組成，可描述為：

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最優解及Pareto前沿

定義2Pareto支配關系

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

定義3Pareto最優解

Pareto最優解是指如果Ω中沒有支配x*的解，則稱x*為式(1)中MOP的一個最優解。

通常多目標優化問題有多個Pareto最優解，這些解的集合稱為Pareto最優解集。Pareto最優解在目標函數空間的像集稱為Pareto前沿。

1.3量子編碼及測量

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

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

(2)

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

(3)

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

探測是指將由量子染色體表示的種群轉化為滿足約束條件的決策變量種群的過程。具體步驟為：對量子染色體中每個量子位，隨機產生一個0到1之間的隨機數r，將r與量子位中表示的0的概率進行比較，如果r較小，則該位取0，否則取1。

1.4切比雪夫法

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

(4)

2　基于分解的多目標量子差分進化算法

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

2.1實數量子染色體編碼

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

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

(5)

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

(6)

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

2.2基于差分進化的量子染色體更新

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

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

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

(7)

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

量子交叉操作: 將新產生的量子變異個體種群與父代個體種群混合產生新個體種群。

(8)

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

2.3量子變異與測量

量子門是量子進化算法進化的動力，量子門有多種，本文采用量子非門對量子染色體進行變異，量子非門的變異處理方法如下:

(9)

令變異概率為PM，若rand

量子染色體是二維向量，經過測量后才能在多目標函數中進行計算，測量的方法如下：

(10)

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

2.4算法流程

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

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

在進化過程中，QD-MOEA/D 要保存的信息有:

① 組成群體的G條實數量子染色體：θ1,θ2,…,θG∈ΩQEA，其中θi為子問題i的量子染色體；

② 組成群體的G個滿足約束條件實數個體：x1,x2,…,xG∈ΩMOP，其中xi為子問題i的當前最優解；

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

④ z=(z1,z2,…,zm)T,其中zi為目標函數fi目前為止所找到的最優值;

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

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

輸入：

① MOP (1);

② 結束條件;

③ G：QD-MOEA/D 所分解的子問題個數;

④ λ1,λ2,…,λG：分布均勻的G個權向量;

⑤ T:權向量的鄰域的大小。

輸出：EP。

Step 1初始化。

Step 1.1設置EP=φ。

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

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

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

Step 2更新。

For i=1,2,…,G do

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

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

Step 2.3更新鄰域數值：在第i個子問題中，令每個鄰域下標b∈B(i)，對于每個鄰域個體xb，如果gte(y|λb,z)≤gte(xb|λb,z),則xb=y，FVb=F(y)。

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

Step 3停止判斷:若滿足停止準則,則算法停止,輸出EP,否則返回Step2。

3　算法測試及結果分析

為了分析測試QD-MOEA/D的收斂性和分布性，本文選擇9個標準的測試函數，分別為ZDT1、ZDT2、ZDT3、ZDT4、ZDT6、DTLZ1、DTLZ2、DTLZ3、DTLZ4[19,20]作為測試用例。并通過計算QD-MOEA/D與MOEA/D和NSGAII[21]的評價指標來驗證QD-MOEA/D算法的性能。

3.1測試函數

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

3.2評價指標

為了能夠更加準確、全面地對該算法進行評價，避免單個性能度量指標的片面性，本文采用以下三個常用的性能評價指標來分析算法的收斂性和分布性。在下面性能指標中，P*為真實PF上均勻分布的 Pareto 最優解集合, X是通過多目標進化算法得到的近似 Pareto 最優解集，m為目標函數的個數，|X|為集合X中元素的個數。

(1) Generational Distance (GD)指標[22]

GD指標度量X到P*的距離,定義為:

(12)

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

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

IGD指標度量X到P*的距離,定義為:

(13)

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

(3) Spacing(S)指標[23]

S指標定義為:

(14)

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

3.3參數設置

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

3.4實驗結果及分析

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

圖1　QD-MOEA/D在ZDT1上的測試結果

圖2　QD-MOEA/D在ZDT2上的測試結果　　　　　　圖3　QD-MOEA/D在ZDT3上的測試結果

圖4　QD-MOEA/D在ZDT4上的測試結果　　　　　　圖5　QD-MOEA/D在ZDT6上的測試結果

圖6　QD-MOEA/D在DTLZ1上的測試結果　　　　　　圖7　QD-MOEA/D在DTLZ2上的測試結果

圖8　QD-MOEA/D在DTLZ3上的測試結果　　　　　　圖9　QD-MOEA/D在DTLZ4上的測試結果

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

為了更加科學地分析QD-MOEA/D算法的性能，將算法與MOEA/D和NSGAII進行對比實驗。QD-MOEA/D算法與QD-MOEA/D算法的參數設置如3.3節所示，NSGAII算法的種群規模為100，將三種算法分別在9個測試函數中運行50次，并計算度量指標GD、IGD、S的均值(mean)和方差(std)，對算法的收斂性、分布性進行比較分析。GD、IGD、S的統計結果如表1所示(效果較好的已用黑體標出)。

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

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

在表1中，對GD和IGD數據的均值和方差進行比較，除了凸函數ZDT4外， QD-MOEA/D在其他測試函數上的GD值和IGD值均小于MOEA/D，表明該算法的收斂性均優于MOEA/D。但在三目標優化函數DTLZ1和DTLZ3上，QD-MOEA/D和MOEA/D的GD值和IGD值高于NSGAII，故NSGAII在函數DTLZ1和DTLZ3的收斂性優于QD-MOEA/D和MOEA/D。對GD和IGD數據結果分析表明，QD-MOEA/D算法改進了MOEA/D在非凸函數上的收斂性。

表1中S指標用于度量算法的分布性，從指標S的數據中可知，QD-MOEA/D的分布性在ZDT1、ZDT2、ZDT4上略差于MOEA/D，在DTLZ1和DTLZ3上略差于NSGAII。QD-MOEA/D的分布性和多樣性表現欠佳的原因為：量子染色體進行差分進化時，隨機從鄰域選取三個點，在進化初期，因為個體均不相同，因此進化速度很快。到了進化后期，隨著對領域的更新，使得很多個體的決策變量相同，尤其是在三個目標的函數中更為明顯。鄰域中相似的個體越多，種群的多樣性越小，隨機從鄰域中選取的個體相同的概率就越大。因此新產生的個體很可能與原有個體相同，使種群失去進化能力，從而導致種群個體多樣性低，分布性差。所以在算法運行后期，需要調整量子染色體的進化策略，從而提高算法性能。但從整體上看，QD-MOEA/D算法的收斂性、分布性均優于MOEA/D和NSGAII，且其魯棒性強。

QD-MOEA/D與MOEA/D相比具有以下特點：

QD-MOEA/D是在MOEA/D的基礎上引入QEA，在算法中用Q-bit對染色體進行編碼，每個Q-bit都表示該量子在某種狀態時的概率，對Q-bit的進化會影響到與之對應種群。在前期探查中，Q-bit通過對整個目標空間的搜索，保障了種群的多樣性；探查的后期，Q-bit趨于某個固定的概率，使算法收斂。因此QD-MOEA/D對PF的形狀不敏感，在非凸函數上依舊有良好的性能。

QD-MOEA/D的量子染色體采用實數編碼。采用這種編碼方式，在不減少個體信息前提下，節省了存儲空間，與MOEA/D相比，在每個個體只需多記錄一行實數值。此外，實數編碼避免了傳統QEA不同進制之間的轉換，與MOEA/D相比，僅增加了量子染色體探測的過程，在每次迭代時，其時間復雜度僅增加O(1)，對整體的時間復雜度無太大的影響。

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

QD-MOEA/D采用量子非門進行變異。傳統的QEA中，量子門是算法進化的動力，但在QD-MOEA/D中，采用量子非門是為了增加個體的多樣性，避免個體陷入局部最優。

上述實驗結果也表明，QD-MOEA/D在進化后期種群的多樣性減少，這主要是因為到了進化后期，更新鄰域后鄰域的個體都有重復，進行差分計算后新個體很有可能與原個體相同，使算法失去了進化能力。為了進一步提高算法的性能，可在對Q-bit進行差分計算時動態地增加一個θ值，這將是QD-MOEA/D未來的研究方向。

4　結　語

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

[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].軟件學報,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] 辜方清.多目標進化算法中多樣性與均勻性策略研究[D].廣州:廣東工業大學,2011.

[13] 周攀,張冬梅,龔文引,等.基于正交設計的自適應ε占優MOEA/D算法研究[J].計算機應用與軟件,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] 陳曉峰,楊廣明,黃明.一種實數編碼的量子差分進化算法[J].小型微型計算機系統,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。山西省自然科學基金項目(2013011016-4，2014011022-2)；山西省高校科技創新項目(2013124)。常新功，教授，主研領域：進化計算，數據挖掘。劉文娟，碩士生。呂亞麗，副教授。

TP301

A

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