基于改進有效序值的高維多目標(biāo)算法

胥 寧，魏靜萱，趙 龍

(西安電子科技大學(xué) 計算機學(xué)院，陜西 西安 710071)

基于改進有效序值的高維多目標(biāo)算法

胥 寧，魏靜萱，趙 龍

(西安電子科技大學(xué) 計算機學(xué)院，陜西 西安 710071)

針對有效序值排序高維多目標(biāo)優(yōu)化算法的不足，文中提出一種基于改進的有效序值的高維多目標(biāo)優(yōu)化算法。該算法提出多邊形雜交算子，用以提高種群的多樣性，同時，文中還提出基于ε-占優(yōu)的有效序值排序方法，從而增加收斂壓力，提高收斂速度。通過標(biāo)準(zhǔn)測試函數(shù)實驗驗證了所提算法的有效性。

高維多目標(biāo)優(yōu)化；有效序值； ε-占優(yōu)

隨著多目標(biāo)優(yōu)化問題在實際應(yīng)用[1-2]中目標(biāo)個數(shù)越來越多，高維多目標(biāo)優(yōu)化問題(目標(biāo)個數(shù)大于或等于4個)已經(jīng)成為進化領(lǐng)域的研究熱點問題。但是隨著目標(biāo)個數(shù)的增加，高維多目標(biāo)優(yōu)化問題存在一些難點問題[3-4]。為解決這些難點問題，文獻[5]提出新的占優(yōu)機制來解決高維多目標(biāo)優(yōu)化問題。Zhang和Li等人[6-8]將傳統(tǒng)的數(shù)學(xué)規(guī)劃方法應(yīng)用到多目標(biāo)優(yōu)化問題，用單目標(biāo)優(yōu)化算法來解決高維多目標(biāo)優(yōu)化問題。Deb等人[9-10]提出基于參考點的非支配排序算法法，通過參考點找出最優(yōu)解。文獻[11]提出的有效序排序算法(Preference Order Genetic Algorithm, POGA)，采用一種新的排序方式來解決高維多目標(biāo)問題。

雖然POGA算法能夠很好的解決高維多目標(biāo)優(yōu)化問題，但仍存在不足，例如采用單點交叉，解的多樣性受到了限制。為解決這些不足，本文首先提出一種新的交叉算子(多面體交叉算子)，目的是為了提交解的多樣性。然后提出一種基于ε-占優(yōu)的有效序值的算法，為了提高解的收斂壓力和收斂速度。最后提出一種新的計算擁擠度算法(超體積算法)。

1 高維多目標(biāo)中的概念

1.1 高維多目標(biāo)問題的相關(guān)定義

對于一個具有n個決策變量，m個目標(biāo)變量，p+q個約束問題可表示為

(1)

其中，x=(x1,x2,…,xn)∈X?Rn為n維決策矢量；y=(y1,y2,…,yn)∈Y?Rm為m維的目標(biāo)矢量。Y為目標(biāo)空間，目標(biāo)函數(shù)F(x)定義了決策空間向目標(biāo)空間的映射函數(shù)。

對高維多目標(biāo)算法中的非支配最優(yōu)解集的定義如下：

定義1Pareto占優(yōu)：假設(shè)xA,xB∈X當(dāng)且僅當(dāng)?i∈{1,2,…,m};fi(xA)≤fi(xB)

∧?i∈{1,2,…,m}:fi(xA)

(2)

定義2Pareto最優(yōu)解：當(dāng)且僅當(dāng)?x∈X:xx*時，這個解x*∈X被稱為Pareto最優(yōu)解。

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

p*{x*|?x∈X:xx*}

(3)

其中，p*表示最優(yōu)解集；x*表示最優(yōu)解。

定義4Pareto前沿面：

PF={F(x*)=(f1(x*),…,fm(x*))|x*∈P*}

(4)

其中，p*表示最優(yōu)解集；PF表示最優(yōu)解集構(gòu)成的Pareto前沿面。

1.2 高維多目標(biāo)解集的評價指標(biāo)

由于多目標(biāo)優(yōu)化問題的最優(yōu)解是一個解集，因此評價解集只能從收斂性、多樣性和均勻性三個方面來評價解集的好壞。下面是Generational Distance(GD)[12]評價指標(biāo)的定義。

假設(shè)S是多目標(biāo)優(yōu)化問題的目標(biāo)向量集合，P中的點均勻分布在整個理想的PF面上，GD計算S到P的距離，定義

(5)

其中，|S|表示集合S中元素的個數(shù)；GD表示的集合的收斂性，GD值越小表示收斂性越好。

2 改進的有效序值算法

改進的有效序值算法(Improved Prefer- ence Order Genetic Algorithm，IPOGA)主要的改進有以下3方面：(1)提出一種新的雜交算子(多邊形雜交算子)；(2)提出基于ε-占優(yōu)的有效序排序方法；(3)提出新的計算擁擠度算法(超體積算法)。

2.1 多邊行雜交算子

在POGA算法中采用SBX[13]方式進行交叉,從父代中選出兩個個體進行單點交叉。這種交叉算子雖然能夠很好的保證解的質(zhì)量，但是無法保證解的多樣性。因此本文提出多變形雜交算子，對于m維的多目標(biāo)優(yōu)化問題，每次從最優(yōu)解中選出m個個體構(gòu)成一個多邊形，計算出多邊形的重心，然后以這個重心向外或者向內(nèi)擴展構(gòu)成新的多邊形，最后在新的多邊形上產(chǎn)生m個子代。如圖1所示，A、B和C構(gòu)成一個三角形，重心為G，對三角形進行向外擴張產(chǎn)生子代A2，B2和C2，向內(nèi)收縮的方式產(chǎn)生子代A1，B1和C1。這樣保證了每次通過向外擴或者向內(nèi)收縮可以產(chǎn)生子代個體。

圖1 三角形雜交算子

2.2 基于ε-占優(yōu)的有效序值算法

POGA算法[11]采用NSGA-II算法[14]的框架，對第一層非支配通過降維的方式，將 維不能比較的解降到m-1維進行比較。由于第一次層的解比較多，采用有效序值給第一層每個非支配分配一個有效序值，然后根據(jù)有效序值進行排序。但是由于同一有效序值的點比較少，故采用ε-占優(yōu)的方式，即對每個目標(biāo)值減去一個ε值，目的是為了讓更多的解具用相同的有效序值，提高算法的收斂速度。算法如下：

步驟1對非支配解集P，解集的大小|P|=N，目標(biāo)個數(shù)為m，每個解的有效序值k=1，且都是無效的efficient=0；

步驟2目標(biāo)空間降到m-1維，對于任意一個m-1維的子空間，都存在一個同一的非支配解A，則解A的有效序值為k=k+1,且是有效的efficient=1；

步驟3由于k值相同的解比較少，對有效序值為k+1的解采用ε-占優(yōu)，對每個目標(biāo)值減去ε值，這樣可以將有效序值為k+1的解的有效序值更改為k；

步驟4如果k

步驟5如果m-1>0，轉(zhuǎn)移到步驟2，否則算法結(jié)束。

2.3 超體積算法

由于高維多目標(biāo)優(yōu)化算法中的的目標(biāo)函數(shù)構(gòu)成了一個空間，不是一個平面。因此空間解與解之間的擁擠度采用超體算法來計算，算法如下

步驟1非支配解集大小N=|P|，P為非支配解集，目標(biāo)個數(shù)為M。

步驟2對屬于P中每一個個體x，令其擁擠度為cd(x)=0。

步驟3對第m個目標(biāo)，所有個體根據(jù)函數(shù)值進行排序，第一個和最后的一個的擁擠度為∞,即cd[1].m=dc[N].m=∞。

步驟5如果m=M，算法結(jié)束，否則轉(zhuǎn)移到步驟3。

2.4 算法過程

IPOGA算法的主要過程：

步驟1令t=0，初始化種群P(t)，種群個數(shù)為N，目標(biāo)個數(shù)為m；

步驟2計算P(t)中每個個體的適應(yīng)度值；

步驟3將P(t)分成m份，從每份中選出一個采用多邊形雜交算子進行雜交，最后生成N個子代；

步驟4對種群P(t)執(zhí)行變異操作；

步驟5將原始種群的N個個體和新產(chǎn)生的N個個體結(jié)合產(chǎn)生2N個個體，對其進行改進的有效序值排序方法，從中選出N個個體。

步驟6若算法滿足結(jié)束條件則結(jié)束，否則，令t=t+1，轉(zhuǎn)移到步驟3。

3 仿真實驗與結(jié)果分析

3.1 實驗

為了驗證IPOGA算法的有效性，本文選擇文獻[15]中的測試集試集DTLZ1～DTLZ2。通過實驗證明算法的有效性。實驗中設(shè)置種群的規(guī)模為100，運行10次，每次迭代300次。最后比較10次運行結(jié)果的平均(mean)值和方差(std)值。實驗結(jié)果如表1～表4所示。實驗通過比較IPOGA算法，POGA算法[12]和NSGA-II算法[14]的收斂性來驗證IPOGA的算法的有效性。

表1 DTLZ1的GD mean的實驗結(jié)果

表2 DTLZ1的GD std的實驗結(jié)果

表3 DTLZ2的GD mean的實驗結(jié)果

表4 DTLZ2的GD std的實驗結(jié)果

3.2 實驗結(jié)果分析

從表1 可以看出對于DTLZ1測試集，IPOGA算法的GD mean值的效果全部都比POGA算法和NSGA-II算法好，說明IPOGA的收斂性比NSGA-II和POGA好。從表2 可以看出對于DTLZ1測試集，IPOGA算法的GD std值的效果基本全部都比NSGA-II算法和POGA算法好。但在目標(biāo)維數(shù)為7時沒有NSGA-II和POGA算法效果那么好，在目標(biāo)維數(shù)為8時，比POGA算法好，但沒有NSGA-II效果好。這說明了IPOGA算法的收斂性波動比較小。

從表3可以看出對于測試集DTLZ2，IPOGA算法的GD mean值基本比POGA算法和NSGA-II的算法GD mean 效果好，但是對于目標(biāo)維數(shù)為4和8時，IPOGA算法的GD mean值沒有其他兩個算法的效果好。說明IPOGA跟POGA的收斂性基本差不多。

從表4可以看出對于測試集DTLZ2，IPOGA算法中的GD std值基本上都比POGA和NSGA-II算法中的GD std值效果相當(dāng)。但是在目標(biāo)維數(shù)為4和7時，IPOGA算法的GD std值的效果比POGA跟NSGA-II的算法好，但在其他目標(biāo)維數(shù)數(shù)上的GD std值的效果就沒有POGA算法好。

綜上所述，在DTLZ1測試集中IPOGA算法的的收斂性明顯優(yōu)于NSGA-II算法和POGA算法。在DTLZ2的測試集上IPOGA算法的收斂性明顯比NSGA-II算法的收斂性好，與POGA算法的收斂性基礎(chǔ)保持一致。

4 結(jié)束語

本文對POGA算法進行改進，加入多邊形雜交算子和基于ε-占優(yōu)有效序值排序方法，能夠較好地提高高維多目標(biāo)算法的收斂壓力，提高收斂速度。經(jīng)過實驗驗證IPOGA確實能夠提高算法的收斂性。后續(xù)工作將對本算法繼續(xù)改進，使其更加有效的解決高維多目標(biāo)優(yōu)化問題。

[1] 丁岳偉,竇飛飛.多目標(biāo)貓群優(yōu)化算法支持下的云計算任務(wù)調(diào)度[J].電子科技,2016,29(2): 4-8.

[2] 明麗洪,呂光宏,向虹佼.多QoS約束條件下的多目標(biāo)網(wǎng)絡(luò)優(yōu)化[J].電子科技,2014,27(3):18-21.

[3] Bechikh S,Elarbi M,Said L B.Many objective optimization using evolutionary algorithms:a survey[M].Germany:Springer International Publishing,2017.

[4] 過曉芳.高維多目標(biāo)優(yōu)化算法研究綜述[J].科技視界,2015(15):21-22.

[5] Aguirre H,Tanaka K.Adaptive ε-Ranking on many-objective problems[J]. Evolutionary Intelligence,2009,2(4): 183-206.

[6] Zhang Q,Li H.MOEA/D:A multiobjective evolutionary algorithm based on decomposition[J].IEEE Transaction on Evolutionary Computation,2007,11(6):712-731.

[7] Li K,Deb K,Zhang Q,et al.An evolutionary many-objective optimization algorithm based on dominance and decomposition[J].IEEE Transactions on Evolutionary Computation,2015,19(5):694-716.

[8] Li K,Kwong S,Zhang Q,et al. Interrelationship-based selection for decomposition multiobjective optimization[J].IEEE Transactions on Cybernetics,2015,45(10):2076-2088.

[9] Deb K,Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondomi- nated sorting approach, part I: solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation,2014,18(4):577-601.

[10] Jain H,Deb K.An evolutionary many-objective optimization algorithm using reference-pointbased nondominated sorting approach, part II: handling constraints and extending to an adaptive approach[J].IEEE Transactions on Evolutionary Computation, 2014,18(4):602-622.

[11] Di Pierro F,Khu S T,Savic D A.An investigation on preference order ranking scheme for multiobjective evolutionary optimization[J].IEEE Transactions on Evolutionary Computation,2007,11(1): 17-45.

[12] Van Veldhuizen D A,Lamont G B. Multiobjective evolutionary algorithm test suites[C].France:Proceedings of the 1999 ACM Symposium on Applied Computing,1999.

[13] Yu Z,Wong H S,Wang D,et al. Neighborhood knowledge-based evolu- tionary algorithm for multiobjective optimization problems[J].IEEE Transactions on Evolutionary Computation,2011,15(6):812-831.

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

[15] Deb K,Thiele L,Laumanns M,et al.Scalable multi-objective optimization test problems[C].Grace:Proceedings of the 2002 Congress on Evolutionary Computation,CEC′02,IEEE,2002.

An Many-Objective Algorithm Based on Improved Effective Ordering

XU Ning,WEI Jingxuan,ZHAO Long

(School of Computer Science and Technology,Xidian University,Xi’an 710071,China)

To overcome the shortcomings of the efficient ranking of many-objective optimization algorithm, an improved efficient ranking of many-objective optimization algorithm is proposed..A new recombination operat- or called polygon recombination operator is proposed by the algorithm in order to improve the diversity of the po- pulation,and a ε-dominance-based efficient ranking method is proposed in order to increase the convergence pres- sure and speed. Finally, the effectiveness of the algorithm is verified by the standard test functions.

many-objective optimization; effective ranking; ε-dominance

2017- 03- 20

國家自然科學(xué)基金(61203372)

胥寧(1989-)，男，碩士研究生。研究方向：智能計算。魏靜萱(1981-)，女，博士，副教授。研究方向：智能計算。

TN953;TP301.6

A

1007-7820(2018)02-029-04