陳曉紀(jì)，石 川，周愛民，吳 斌

1(北京郵電大學(xué) 計算機學(xué)院，北京 100876)

2(邢臺職業(yè)技術(shù)學(xué)院 信息工程系，河北 邢臺 054000)

3(華東師范大學(xué) 計算機科學(xué)與軟件工程學(xué)院，上海 200062)

多目標(biāo)優(yōu)化問題(multiobjective optimization problem，簡稱MOP)是指那些同時優(yōu)化多個目標(biāo)的問題.一般來說，這些單個目標(biāo)是相互沖突的，而且總體目標(biāo)沒有單個最優(yōu)解[1].求解多目標(biāo)優(yōu)化問題常常是困難的，它不像單目標(biāo)優(yōu)化問題(single objective optimization problem，簡稱SOP)那樣只有一個最優(yōu)解，多目標(biāo)優(yōu)化問題得到的是一組最優(yōu)解.因為進(jìn)化算法(EAs)是基于種群的優(yōu)化算法，能夠多次迭代優(yōu)化逼近MOP的Pareto前沿，所以進(jìn)化算法(EAs)廣泛應(yīng)用于解決MOP問題[2].這些EAs被稱為多目標(biāo)進(jìn)化算法(MOEAs).近年來，大量MOEAs被提出，這些算法可以分為3類[1]:基于Pareto支配的算法[3?6]、基于指標(biāo)的算法[7?9]和基于分解的算法[10，11].MOEA/D[10]是最近最具代表性的基于分解的算法，其基本思想是:將MOP分解為一組標(biāo)量目標(biāo)子問題.相鄰子問題相互協(xié)作產(chǎn)生新的后代解集，而新產(chǎn)生的解不僅會更新相應(yīng)子問題，也會更新相鄰子問題.通過這種方式，所有子問題同時被優(yōu)化，最終，所有子問題的解集構(gòu)成了原始MOP的Pareto解集(PS)與Pareto前沿(PF).

后代選擇是MOEA的核心問題之一[12]，后代選擇顯著地影響了迭代優(yōu)化的收斂速度和解集的多樣性.目前主要有3種后代選擇方式.

(1) 非支配排序是一種非常流行的方法.對于多目標(biāo)優(yōu)化問題，通常存在一個解集，這些解之間對于所有目標(biāo)函數(shù)而言是無法比較優(yōu)劣的，其特點是無法在改進(jìn)任何目標(biāo)函數(shù)的同時不削弱至少一個目標(biāo)函數(shù).它根據(jù)解之間的支配關(guān)系對所有解進(jìn)行排序，稱其為非支配排序.典型的非支配排序算法包括NSGA-II[4]和SPEA2[5].非支配排序方法往往不適用于代價昂貴的多目標(biāo)優(yōu)化問題；

(2) 代理也是選擇后代最優(yōu)解的常用方法.代理模型是指計算量小、但其計算結(jié)果和高精度模型的計算分析結(jié)果相近的分析模型.在優(yōu)化設(shè)計時，可以用代理模型替代高精度分析模型.典型的利用代理模型解決多目標(biāo)優(yōu)化問題的算法包括MOEA/D-EGO[13]和MOEA/D-RBF[14].通常，利用某些方法獲取的樣本點集構(gòu)造代理模型往往需要擬合復(fù)雜的數(shù)學(xué)模型，這個過程是非常耗時的.同時，為了保證代理模型具有較高的精度，代理模型需要優(yōu)化許多參數(shù)[15]；

(3) 最近，分類也成為選擇后代最優(yōu)解的常用方法.分類就是按照某種標(biāo)準(zhǔn)給對象設(shè)置標(biāo)簽，再根據(jù)標(biāo)簽來區(qū)分歸類.分類算法利用有監(jiān)督機器學(xué)習(xí)方法構(gòu)造分類器，用于后代選擇.典型的分類算法包括MOEA/D-CPS[16]，CPS-MOEA[12]和MOEA/D-SVM[17].分類算法將后代選擇看成是一個分類問題.然而，分類后優(yōu)良解的數(shù)量往往不止一個，利用隨機選擇方式很難從優(yōu)良解集中獲取最優(yōu)解.此外，構(gòu)建復(fù)雜分類器往往存在優(yōu)化參數(shù)耗時等問題.

考慮到現(xiàn)有后代選擇方式的缺陷，本文提出了一種融合分類與代理的混合個體選擇機制；進(jìn)一步基于經(jīng)典的MOEA/D框架，利用混合個體選擇機制設(shè)計了新的多目標(biāo)進(jìn)化算法，稱為MOEA/D-CS(MOEA/D based on classification and surrogate).由于分類能夠以較小的時間代價提升算法性能以及代理能夠較為準(zhǔn)確地估計目標(biāo)值，有許多工作利用分類或者代理實現(xiàn)后代選擇.但是單獨利用分類或者代理存在上述缺陷，本文融合二者的優(yōu)點實現(xiàn)了一種混合個體選擇機制.在混合個體選擇機制實現(xiàn)過程中，首先利用分類器過濾候選解并且只有優(yōu)良解被保留下來；然后利用輕量級代理模型估計優(yōu)良解的目標(biāo)值；最后，利用目標(biāo)值排序策略獲得最優(yōu)解.在19個具有2目標(biāo)或3目標(biāo)的多目標(biāo)優(yōu)化測試函數(shù)上，本文比較了MOEA/D-CS算法與其他多個當(dāng)前流行的基于分解多目標(biāo)進(jìn)化算法.實驗結(jié)果表明:在沒有顯著增加時間代價的情況下，MOEA/D-CS算法在絕大部分測試函數(shù)上取得了最好的性能.

本文第1節(jié)介紹相關(guān)工作.第2節(jié)介紹算法實現(xiàn)的細(xì)節(jié).第3節(jié)進(jìn)行大規(guī)模實驗，并對實驗結(jié)果和敏感性參數(shù)進(jìn)行深入分析.第4節(jié)總結(jié)全文，并對未來的研究工作進(jìn)行闡述.

1 相關(guān)工作

在過去的二十幾年時間里，各種多目標(biāo)進(jìn)化算法相繼被提出.總體來說，多目標(biāo)進(jìn)化算法主要包含3類.

· 第1類算法的特點是基于個體支配關(guān)系與精英保留策略.David等人[18]設(shè)計的多目標(biāo)進(jìn)化算法VEGA被認(rèn)為是利用進(jìn)化算法解決多目標(biāo)優(yōu)化問題的先驅(qū)工作.Srinivas和Deb[19]提出的NSGA奠定了多目標(biāo)進(jìn)化算法的基本框架.NSGA-II[4]是NSGA的改進(jìn)版本.NSGA-II使用精英保留策略，保留最好的父代個體和子代個體.Zitzler和 Thiele[20]提出的SPEA利用外部種群實現(xiàn)精英保留策略.SPEA的改進(jìn)版本SPEA2[5]也相繼被提出.SPEA2[5]使用最近鄰密度估計來實現(xiàn)更高搜索效率，新的歸檔截斷方法保證邊界解被保留下來；

· 第2類算法的特點是使用指示器指導(dǎo)搜索過程.Zitzler和Künzli[7]首先提出了一種基于指標(biāo)的進(jìn)化算法(IBEA).在IBEA中，不需要任何額外的多樣性保留機制.與其他MOEAs相比，IBEA只比較成對的個體而不是整個近似集.Basseur和Zitzler[8]提出了一個以指標(biāo)為基礎(chǔ)的處理不確定性問題的模型，其中每個解在目標(biāo)空間中被分配一個概率.Bader和Zitzler[9]提出了一種基于快速超體積的MOEA算法，該算法用于處理多個目標(biāo)的優(yōu)化問題.為了減少超體積計算的開銷，提出了一種基于蒙特卡羅模擬的快速估計超體積近似集的方法；

· 第3類算法使用分解和降維[21]來解決多目標(biāo)優(yōu)化問題.這個類型的典型算法是MOEA/D[10，11].這種方法將MOP分解為一組子問題并同時優(yōu)化這些子問題.后代繁殖和環(huán)境選擇都是基于子問題的.

伴隨著多目標(biāo)進(jìn)化算法的發(fā)展歷程，多目標(biāo)進(jìn)化算法在理論研究方面也取得了一定的進(jìn)展.在一個基于種群的多目標(biāo)問題上，Laumanns等人[22]首次分析了算法的運行時間.在某些多目標(biāo)優(yōu)化問題上，Laumanns等人[23]證明了基于特定種群的多目標(biāo)優(yōu)化算法具有較低的運行時間以及算法運行時間與Pareto前沿是密切相關(guān)的，而且算法總的運行時間是有界的.Qian等人[24]從理論上研究了重組算子對多目標(biāo)進(jìn)化算法的影響.在一系列多目標(biāo)優(yōu)化基準(zhǔn)問題上，結(jié)合重組算子的多目標(biāo)進(jìn)化算法不僅可以縮短算法的運行時間，而且能夠使最優(yōu)解集更靠近Pareto前沿.

利用多目標(biāo)進(jìn)化算法解決多目標(biāo)優(yōu)化問題，如何選擇后代個體是關(guān)鍵.在多目標(biāo)進(jìn)化算法中，主要有3種后代選擇方式.

(1) 傳統(tǒng)的算法使用非支配排序[4，5]選擇后代解集.NSGA-II[4]算法首先利用非支配排序找出種群中的非支配解；然后，一部分非支配解通過交叉與變異生成子代解，并且利用實際目標(biāo)值評價每一個子代解；最后，整合父代種群與子代種群，利用非支配排序保存下一次迭代優(yōu)化需要的種群.SPEA2[5]算法除了采用傳統(tǒng)的交叉與變異產(chǎn)生子代解，還利用非支配排序與密度估計方法計算個體的適應(yīng)值，算法精度要高于NSGA-II[4]；

(2) 近年來，許多文獻(xiàn)利用代理選擇后代最優(yōu)解.文獻(xiàn)[25，26]利用回歸或排序技術(shù)用來構(gòu)建代理模型，這樣可以減少目標(biāo)值評價的次數(shù).文獻(xiàn)[27]使用代理模型進(jìn)行局部搜索和預(yù)選擇.MOEA/D-EGO[13]利用高斯隨機過程解決代價昂貴的多目標(biāo)優(yōu)化問題.MOEA/D-EGO[13]利用高斯過程為每個目標(biāo)分別建模，然后獲得每個分解子問題的模型.但是MOEA/D-EGO[13]利用種群的聚類信息建立代理模型，沒有考慮種群的整體信息對代理模型精度的影響，這可能導(dǎo)致算法的精度較低，而且需要調(diào)整較多參數(shù).同時，利用局部信息更新代理模型可能導(dǎo)致錯誤的搜索.文獻(xiàn)[14]利用集成的徑向基函數(shù)網(wǎng)絡(luò)構(gòu)建代理模型MOEA/D-RBF[14]，它保持了固定大小的訓(xùn)練集，但是只針對較小的種群規(guī)模和迭代次數(shù)；

(3) 最近，隨著機器學(xué)習(xí)算法的廣泛應(yīng)用，有監(jiān)督分類算法已經(jīng)成為選擇后代最優(yōu)解的常用方法.Yu等人[28]提出了RACOS算法，該算法利用分類模型對優(yōu)良解與不良解進(jìn)行分類.RACOS算法在處理高維優(yōu)化問題時具有明顯的優(yōu)勢.Zhang等人[16]提出的MOEA/D-CPS算法利用非支配排序和KNN[29]構(gòu)造分類器模型，在具有復(fù)雜Pareto前沿的多目標(biāo)優(yōu)化問題上取得了較好的性能.Zhang等人[12]利用非支配排序和CART[30]構(gòu)造分類器模型，與NSGA-II[4]算法結(jié)合，提出了CPS-MOEA算法，在大量多目標(biāo)優(yōu)化測試函數(shù)上取得了較好的性能.Lin等人[17]利用SVM[31]訓(xùn)練分類器，提出了MOEA/D-SVM算法，提升了MOEA/D的性能.

然而，上述后代選擇方式普遍存在著時間代價較高、難以準(zhǔn)備準(zhǔn)確的正例和負(fù)例樣本或者很難保證代理模型的精度.因此，往往不適用于代價昂貴的多目標(biāo)優(yōu)化問題.

2 MOEA/D-CS算法

后代選擇是多目標(biāo)進(jìn)化算法中一個非常重要的問題.不同于以往的后代選擇方式，本文融合分類與代理的混合個體選擇機制獲取最優(yōu)解，基于混合個體選擇機制設(shè)計了新穎的多目標(biāo)進(jìn)化算法.本節(jié)首先簡單介紹基本的MOEA/D框架；然后詳細(xì)論述融合分類與代理的混合個體選擇機制的具體實現(xiàn)過程，包括如何利用非支配排序策略[4]與k近鄰(KNN)[29]算法構(gòu)建有監(jiān)督分類器模型以及相似性度量方法構(gòu)建輕量級代理模型；最后介紹本文設(shè)計的融合分類與代理個體選擇機制的MOEA/D-CS算法框架及其時間復(fù)雜度.

2.1 基于分解的多目標(biāo)進(jìn)化算法框架

MOEA/D將MOP問題分解為一組子問題{g1，g2，…，gN}，并且同時優(yōu)化這些子問題.每個子問題的最優(yōu)解有可能成為MOP問題的Pareto最優(yōu)解[32].本文使用切比雪夫(Tchebycheff)方法作為MOEA/D的分解方法.每個子問題i被定義為

2.2 融合分類與代理的混合個體選擇機制

在基于分解的多目標(biāo)進(jìn)化算法中，如果每個子問題產(chǎn)生的后代候選解越多，那么獲得最優(yōu)解的幾率就越大，但是計算多個后代候選解花費的時間代價也越高.因此，傳統(tǒng)方式利用實際目標(biāo)值評價不適用于這類問題.目前，基于分類與代理獲取最優(yōu)解的相關(guān)算法越來越多.分類算法普遍存在著如下問題:難以構(gòu)造準(zhǔn)確的分類器模型；利用局部信息構(gòu)建的代理模型精度難以保證；而利用全局信息構(gòu)建的代理模型雖然精度較高，但是需要花費的時間代價太大.鑒于單獨利用分類與代理獲取最優(yōu)解存在的諸多問題，本文提出了融合分類與代理的混合個體選擇機制，實現(xiàn)從后代候選集中選擇最優(yōu)解，在沒有顯著增加時間代價的前提下，提升了獲取最優(yōu)解的概率.

下面詳細(xì)介紹融合分類與代理的混合個體選擇機制實現(xiàn)過程.

· 首先，使用k近鄰(KNN)[29]構(gòu)建分類器[16].

設(shè)置〈x，y〉為一組訓(xùn)練數(shù)據(jù)，其中，x是數(shù)據(jù)點的個體向量，y∈L是數(shù)據(jù)點對應(yīng)的標(biāo)簽，L是一組標(biāo)簽集合.個體向量與標(biāo)簽之間的對應(yīng)關(guān)系可以表示為y=Class(x).訓(xùn)練分類器的目的是找到一個關(guān)系基于訓(xùn)練數(shù)據(jù)集可以近似地表示實際的對應(yīng)關(guān)系y=Class(x).

本文引入兩個外部種群P+和P?，P+包含了迄今為止發(fā)現(xiàn)的標(biāo)簽為+1的優(yōu)良解集合，P?包含了標(biāo)簽為?1的不良解集合.為了獲得P+和P?，本文使用非支配排序策略[4].令q=NDS(p，n)表示該方法從p中選擇最好的n個解存儲在q中，這里所指的“最好的n個解”包含3種情況.

(1) 非支配解的數(shù)量等于n，最好的n個解就是全部非支配解的集合；

(2) 非支配解的數(shù)量大于n，算法利用擁擠距離[4]過濾掉多余的非支配解；

(3) 非支配解的數(shù)量小于n，此時根據(jù)序關(guān)系和擁擠距離[4]從支配解中找出一部分最靠近Pareto前沿的解，再與非支配解集組成最好的n個解.

令P為初始種群，N為種群P的大小.P+和P?被初始化為

設(shè)x是一個個體向量，L={+1，?1}，其中，+1是優(yōu)良解的標(biāo)簽，?1是不良解的標(biāo)簽.本文使用k近鄰(KNN)[29]作為分類算法.其中，k近鄰(KNN)[29]的訓(xùn)練數(shù)據(jù)包括當(dāng)前整個種群P:

N(x)表示訓(xùn)練集中與x最近鄰的K個鄰居個體，K設(shè)置為奇數(shù).sign(x)的執(zhí)行過程為:從N(x)中依次選擇個體向量t，將個體向量t對應(yīng)的標(biāo)簽yt累加求和，累加求和的結(jié)果只能是正數(shù)或負(fù)數(shù).此時，如果累加求和的結(jié)果為正數(shù)，sign(x)返回+1，則x標(biāo)記為優(yōu)良解；否則，sign(x)返回?1，x標(biāo)記為不良解.

令Q表示每一代中新產(chǎn)生的一組最優(yōu)解集合，Q+和Q?分別表示包含非支配和被支配關(guān)系解集.然后，P+和P?按照如下方式進(jìn)行更新:

· 其次，利用相似性度量方法構(gòu)建輕量級代理模型.

傳統(tǒng)的代理模型時間代價較高，往往不適用于代價昂貴的多目標(biāo)優(yōu)化問題.本文構(gòu)建了一個輕量級代理模型，能夠以較小的時間代價保證代理模型具有較高的精度.文獻(xiàn)[35，36]指出，連續(xù)MOP問題在決策空間PS可以定義為分段連續(xù)的流形結(jié)構(gòu)，那么對于MOP來說，目標(biāo)空間PF也應(yīng)該是分段連續(xù)的.因此，連續(xù)多目標(biāo)優(yōu)化具有如圖1所示的性質(zhì).圖1(a)展示了PS與PF之間的對應(yīng)關(guān)系.圖1(b)中，x1，x2，x3∈D(決策向量空間)，z1，z2，z3∈F(D)(目標(biāo)向量空間)，相比x3，x1與x2更接近，因此z1與z2也就更接近.同理，對于D中的任意兩個相近的解，相應(yīng)的F(D)中目標(biāo)值也應(yīng)該越相近.

Fig.1 Characteristics of continuous multiobjective optimization problem圖1 連續(xù)多目標(biāo)優(yōu)化問題的性質(zhì)

由于每個子問題的后代候選解都是由其鄰域個體通過DE[33]算子和多項式變異[34]生成的，并且執(zhí)行分類操作后只有優(yōu)良解被保留下來.因此，本文利用相似性度量方法計算每個優(yōu)良解與對應(yīng)鄰域個體之間的相似性，利用最近鄰域個體的目標(biāo)值作為每個優(yōu)良解的估計目標(biāo)值.目前，有許多方法用來度量相似性.本文利用余弦相似性度量每個優(yōu)良解與鄰域個體之間的相似程度.余弦相似性主要利用向量空間中兩個向量的余弦夾角進(jìn)行計算.余弦相似性的計算公式如下:

x1和x2表示向量空間中具有相同維度的兩個向量，sim(x1，x2)越接近1，x1和x2就越相似.

2.3 算法框架與分析

MOEA/D-CS算法框架如圖2所示.MOEA/D-CS算法流程主要包括4部分.

1) 初始化工作:生成每個子問題對應(yīng)的個體xi，鄰域信息Bi，初始化理想點z*(第1行)；

2) 利用非支配排序[4]獲取正例P+和負(fù)例P?樣本，訓(xùn)練有監(jiān)督分類器模型(第3行)；

3) 循環(huán)選擇每一個子問題:首先，利用classifier對候選解進(jìn)行分類(第6行)；然后，如果條件滿足，則利用輕量級代理模型估計每個優(yōu)良解的目標(biāo)值并保存最優(yōu)解(第7行～第13行)；最后，更新理想點z*和種群P(第14行)；

4) 更新正例P+和負(fù)例P?樣本(第16行).

Fig.2 MOEA/D-CS algorithm framework圖2 MOEA/D-CS算法框架

針對MOEA/D-CS算法的每一個子問題，其時間復(fù)雜度主要包含3部分.

1) 利用非支配排序[4]將初始種群劃分為正例P+和負(fù)例P?樣本.非支配排序[4]算法的時間復(fù)雜度是O(mN2)，其中，m是目標(biāo)個數(shù)，N是種群大??；

2) 利用有監(jiān)督分類器執(zhí)行分類操作.對于每一個后代候選解，它需要與分類器中的每個樣本計算歐式距離.因此比較次數(shù)是N，所以時間復(fù)雜度是O(MN)，其中，M是后代候選解的數(shù)量；

3) 利用余弦相似性計算每個優(yōu)良解與鄰域個體的相似程度.鄰域個體的數(shù)量上限是N，M是優(yōu)良解數(shù)量的上限，每個優(yōu)良解最多需要計算N次，所以時間復(fù)雜度是O(MN).

本文主要針對2目標(biāo)或3目標(biāo)，每個子問題的后代候選解數(shù)量M=3，所以有m≤M.因為MOEA/D-CS算法需要同時優(yōu)化N個子問題，所以MOEA/D-CS算法的時間復(fù)雜度為O(mN3)+O(MN2)+O(MN2)，近似為O(MN3).本文以函數(shù)評價次數(shù)作為終止條件，這里假設(shè)函數(shù)評價次數(shù)為C，那么終止條件折合成迭代次數(shù)就是C/N.所以MOEA/D-CS算法總的時間復(fù)雜度近似為O(CMN2).

3 實 驗

3.1 實驗設(shè)置

為了驗證MOEA/D-CS算法的有效性，將其與當(dāng)前多個有代表性的MOEA算法進(jìn)行對比實驗.

1) MOEA/D-CPS[16].MOEA/D-CPS[16]首先利用DE[33]算子和多項式變異[34]為每個子問題生成3個后代候選解，然后利用有監(jiān)督分類器執(zhí)行分類操作；

2) MOEA/D-DE[11].MOEA/D-DE[11]利用DE[33]算子和多項式變異[34]為每個子問題生成1個后代解；

3) MOEA/D-MO[37].MOEA/D-MO[37]首先利用DE[33]算子和多項式變異[34]為每個子問題生成3個后代候選解，然后直接利用實際目標(biāo)值函數(shù)評價每個后代候選解；

4) MOEA/D-SIM.為了對比僅使用代理模型的后代個體選擇機制，本文設(shè)計了 MOEA/D-SIM算法.MOEA/D-SIM首先利用DE[33]算子和多項式變異[34]為每個子問題生成3個后代候選解；然后，利用余弦相似性度量每個后代候選解與鄰域個體的相似性；最后，將最近鄰域個體的目標(biāo)值作為當(dāng)前后代候選解的估計目標(biāo)值.

本文采用文獻(xiàn)[38]中使用的9個多目標(biāo)優(yōu)化測試函數(shù)F1～F9與文獻(xiàn)[39]中使用的10個無約束多目標(biāo)優(yōu)化測試函數(shù)ZZF1～ZZF10.

本文使用IGD[36]指標(biāo)評價算法的性能.令P*是一組沿著PF均勻分布的點，P在目標(biāo)空間中近似于PF.IGD[36]定義為

其中，d(v，P)是v和P中任何一點的最短歐氏距離；|P*|表示P*的基數(shù)，如果P*足夠大，它就可以更好地表示PF*；IGD(P*，P)同時衡量P的收斂性和多樣性，IGD(P*，P)指標(biāo)越小，P就越接近于PF*.在本文的實驗中，對于2目標(biāo)函數(shù)，從PF*中選擇500個均勻分布的點代表PF*.對于3目標(biāo)函數(shù)，選擇990個均勻分布的點代表PF*.

相關(guān)參數(shù)設(shè)置如下.

1) 對于所有測試函數(shù)，決策變量的維度n=30.針對2目標(biāo)函數(shù)，種群規(guī)模設(shè)置為N=300；針對3目標(biāo)函數(shù)，種群規(guī)模設(shè)置為N=595；

2) 在每個測試函數(shù)上，所有算法獨立運行30次，停止條件是函數(shù)評價次數(shù)(FES).針對2目標(biāo)函數(shù)，算法執(zhí)行150 000次評價后停止；針對3目標(biāo)函數(shù)，算法執(zhí)行297 500次評價后停止；

3) 鄰域大小T=20，鄰域搜索概率δ=0.9，子問題更新數(shù)目c=2，變異概率，多項式變異算子η=20；

4) 在MOEA/D-CPS，MOEA/D-MO，MOEA/D-SIM和MOEA/D-CS算法中，后代候選解個數(shù)M=3，DE算子中的參數(shù)F={0.5，0.7}；在MOEA/D-DE算法中，DE算子中的參數(shù)F=0.5；

5) 在MOEA/D-CPS，MOEA/D-SIM和MOEA/D-CS算法中，2目標(biāo)函數(shù)的鄰域大小T=15，3目標(biāo)函數(shù)的鄰域大小T=30.在MOEA/D-CPS和MOEA/D-CS算法中，最近鄰的數(shù)量K=3.

3.2 有效性實驗

本文分別在F1～F9和ZZF1～ZZF10測試函數(shù)集上做了對比實驗.所有算法均獨立運行30次.在每個測試函數(shù)上，分別計算每種算法的IGD均值和標(biāo)準(zhǔn)差.IGD均值越小，說明算法的收斂性和多樣性越好；標(biāo)準(zhǔn)差越小，說明算法穩(wěn)定性越好.同時，本文還分別統(tǒng)計了每種算法在F1～F9和ZZF1～ZZF10兩個測試函數(shù)集上的平均運行時間.所有統(tǒng)計結(jié)果分別展示在表1與表2中(‘+’與‘?’分別表示每一種算法優(yōu)(等于)與劣于其他算法).

Table 1 Statistical results of mean IGD and Std obtained by five algorithms on F1～F9 over 30 runs表1 5種算法在F1～F9測試函數(shù)上獨立運行30次獲得的IGD均值與標(biāo)準(zhǔn)差統(tǒng)計結(jié)果

Table 2 Statistical results of mean IGD and Std obtained by five algorithms on ZZF1～ZZF10 over 30 runs表2 5種算法在ZZF1～ZZF10測試函數(shù)上獨立運行30次獲得的IGD均值與標(biāo)準(zhǔn)差統(tǒng)計結(jié)果

通過深入分析表1和表2，可以發(fā)現(xiàn)如下現(xiàn)象.

1) MOEA/D-CS算法在大多數(shù)情況下表現(xiàn)出最好的性能.

在F1～F9測試函數(shù)集中，MOEA/D-CS算法有5個表現(xiàn)最好；在ZZF1～ZZF10測試函數(shù)集中，MOEA/D-CS算法有6個表現(xiàn)最好.然后，在F1～F9與ZZF1～ZZF10測試函數(shù)集中，本文進(jìn)一步比較MOEA/D-CS與其他算法之間的性能差異.

(1) MOEA/D-CS與MOEA/D-CPS算法相比，MOEA/D-CS算法有15個表現(xiàn)最好，說明增加輕量級代理模型提高了獲取最優(yōu)解的概率.MOEA/D-CS利用分類獲得的優(yōu)良解更靠近P+，而P+更靠近PS，所以優(yōu)良解也靠近PS.由于PS是近似于分段連續(xù)的，目標(biāo)空間也是分段連續(xù)的，所以可以通過估計優(yōu)良解的目標(biāo)值近似代替優(yōu)良解的實際目標(biāo)值.因為優(yōu)良解是由鄰域個體生成的，此時利用相似性度量方法作為輕量級代理模型估計每個優(yōu)良解最相似鄰域個體，然后可以用最近鄰域個體的目標(biāo)值作為優(yōu)良解的估計目標(biāo)值.對于所有優(yōu)良解，只需要利用其近似目標(biāo)值計算優(yōu)良解的排序關(guān)系，就可以從所有優(yōu)良解中找出一個最優(yōu)解.雖然MOEA/D-CPS算法設(shè)計的分類器是有效的，然而MOEA/D-CPS算法采用隨機選擇優(yōu)良解作為最優(yōu)解，這種方式不能保證以較高的概率獲得最優(yōu)解.因此，MOEA/D-CS要比MOEA/D-CPS更有效；

(2) MOEA/D-CS與MOEA/D-DE算法相比，MOEA/D-CS算法有13個表現(xiàn)最好.MOEA/D-CS基于MOEA/D框架，說明融合分類與輕量級代理模型的MOEA/D-CS算法，確實提升了MOEA/D的性能；

(3) MOEA/D-CS與MOEA/D-MO算法相比，MOEA/D-CS算法有14個表現(xiàn)最好.因為MOEA/D-MO算法對所有后代候選解均采用實際目標(biāo)值評價，那么在相同評價次數(shù)作為終止條件下，MOEA/D-MO算法的運行代數(shù)要遠(yuǎn)遠(yuǎn)少于MOEA/D-CS算法.這說明MOEA/D-CS要比MOEA/D-MO算法更有優(yōu)勢，表現(xiàn)也會更好；

(4) MOEA/D-CS與MOEA/D-SIM算法相比，MOEA/D-CS算法有16個表現(xiàn)最好.MOEA/D-CS算法首先采用有監(jiān)督分類，能夠很好地區(qū)分優(yōu)良解與不良解；然后利用輕量級代理模型可以從優(yōu)良解中找出最優(yōu)解.而MOEA/D-SIM直接估計每個候選解與最近鄰域個體的相似性，如果候選解不是優(yōu)良解也很可能通過估計目標(biāo)值被誤認(rèn)為是最優(yōu)解，這樣，MOEA/D-SIM算法的誤差就會非常大，所以MOEA/DCS算法的效果也會優(yōu)于MOEA/D-SIM算法.

從表1與表2還可以看出，本文提出的MOEA/D-CS算法在大多數(shù)測試函數(shù)上標(biāo)準(zhǔn)差都是最小的，說明MOEA/D-CS算法是非常穩(wěn)定的.

2) MOEA/D-CS算法花費的時間代價低于MOEA/D-SIM，但是要高于其他算法.

由于MOEA/D-CS算法的性能最好，在權(quán)衡精度與時間代價的情況下，MOEA/D-CS算法花費的時間代價是可以接受的.

(1) MOEA/D-DE算法利用DE算子生成1個后代解，然后利用實際目標(biāo)值評價與更新操作，因此，MOEA/D-DE算法在兩個測試函數(shù)集上花費的時間代價最小；

(2) MOEA/D-CPS算法首先利用KNN[29]構(gòu)建分類器并執(zhí)行分類操作，然后隨機選擇一個優(yōu)良解作為后代解，最后利用實際目標(biāo)值評價后代解并執(zhí)行更新操作.因此，MOEA/D-CPS算法花費的時間代價要高于MOEA/D-DE算法；

(3) MOEA/D-MO算法利用DE算子生成3個后代候選解，每個候選解均使用實際目標(biāo)值進(jìn)行評價.因此，MOEA/D-MO算法花費的時間代價要高于MOEA/D-DE與MOEA/D-CPS算法；

(4) MOEA/D-SIM直接利用余弦相似性估計每個候選解的目標(biāo)值，這需要花費相當(dāng)大的時間代價.因此，MOEA/D-SIM花費的時間代價最高；

(5) MOEA/D-CS算法融合分類與輕量級代理模型執(zhí)行后代個體選擇.MOEA/D-CS算法花費的時間代價高于前3種算法，其主要原因有兩個:第一，本文利用余弦相似性構(gòu)建輕量級代理模型，因為每個優(yōu)良解都需要與鄰域個體計算相似度，所以會耗費一定的運行時間；第二，本文使用的測試函數(shù)都相對簡單，每個子問題產(chǎn)生的后代解數(shù)量較少，評價個體目標(biāo)值花費的運行時間要少于計算相似度花費的運行時間.MOEA/D-CS算法花費的時間代價低于第4種算法，其主要原因是MOEA/D-CS算法采用先分類后估計優(yōu)良解目標(biāo)值的方式，相比于MOEA/D-SIM算法采用估計全部候選解目標(biāo)值的方式，時間代價要小.

為了深入分析不同類型多目標(biāo)測試函數(shù)對算法性能的影響，本文從F1～F9與ZZF1～ZZF10測試函數(shù)集中選擇了一部分有代表性的測試函數(shù)F3，F(xiàn)4，F(xiàn)6，ZZF1，ZZF7和ZZF9.在這些測試函數(shù)中，包含MOEA/D-CS算法性能明顯優(yōu)于其他算法的測試函數(shù)(F3，F(xiàn)4，ZZF7)，也包含其性能遜于其他算法(F6，ZZF9)或者與其他算法取得相同性能(ZZF1)的測試函數(shù).其中，F(xiàn)3，F(xiàn)4，ZZF1，ZZF7和ZZF9是2目標(biāo)函數(shù)，它們具有相似的PF，而它們的PS形狀是不同的非線性曲線.F3和F4具有比其他2目標(biāo)函數(shù)更復(fù)雜的PS形狀.F6是3目標(biāo)函數(shù)，其PF和PS都最為復(fù)雜.圖3展示了MOEA/D-CS算法在這些有代表性的測試函數(shù)上獲得的最終解集.

Fig.3 Final obtained approximations by MOEA/D-CS圖3 MOEA/D-CS算法獲得的最終解集

Fig.3 Final obtained approximations by MOEA/D-CS (Contiuned)圖3 MOEA/D-CS算法獲得的最終解集(續(xù))

通過深入分析圖3，可以發(fā)現(xiàn)如下現(xiàn)象.

1) MOEA/D-CS算法非常適合處理PS相對平滑的多目標(biāo)測試函數(shù).針對F3，F(xiàn)4和ZZF7這3種測試函數(shù)，PS與PF都比較平滑，在這幾個測試函數(shù)上獲得的IGD均值為最小值.MOEA/D-CS算法首先利用分類獲取優(yōu)良解；然后，如果條件滿足，則利用余弦相似性計算每個優(yōu)良解與鄰域個體的相似程度，此時獲得的最近鄰域個體是非常接近的，那么對應(yīng)PF空間的目標(biāo)值也應(yīng)該是非常接近的.算法利用近似目標(biāo)值估計優(yōu)良解的優(yōu)劣，很容易從優(yōu)良解中找出最優(yōu)解.因為MOEA/D-CS算法融合了分類與代理的混合個體選擇機制，所以它提高了獲得最優(yōu)解的概率；

2) MOEA/D-CS算法處理PS非常平滑的多目標(biāo)測試函數(shù)，與其他流行的基于分解多目標(biāo)進(jìn)化算法取得了相同的性能.針對ZZF1測試函數(shù)，其對應(yīng)的PS是非常平滑的，此時，無論利用哪一種多目標(biāo)進(jìn)化算法，只要評價次數(shù)足夠多，最終的IGD均值都是相等的；

3) MOEA/D-CS算法處理PS具有復(fù)雜曲線形狀的多目標(biāo)測試函數(shù)，表現(xiàn)不如其他算法.針對F6與ZZF9測試函數(shù)，越是具有復(fù)雜曲線形狀的多目標(biāo)測試函數(shù)，利用余弦相似性估計每個優(yōu)良解的目標(biāo)值所產(chǎn)生的偏差就越大，所以MOEA/D-CS算法不適合處理PS具有復(fù)雜曲線形狀的多目標(biāo)測試函數(shù).這也是該算法需要進(jìn)一步改進(jìn)的地方.

3.3 收斂性實驗

為了驗證MOEA/D-CS算法的收斂性，本文從F1～F9與ZZF1～ZZ10測試函數(shù)集中選取了F3，F(xiàn)4，ZZF3與ZZF7這4個多目標(biāo)測試函數(shù)，這5種算法利用函數(shù)評價次數(shù)(FES)作為終止條件獲得的平均IGD(log)指標(biāo)值如圖4所示.從圖4中可以發(fā)現(xiàn)，MOEA/D-CS算法在不同運行階段收斂性都是最好的.在迭代優(yōu)化過程中，對應(yīng)相同的函數(shù)評價次數(shù)(FES)，MOEA/D-CS算法的平均IGD(log)指標(biāo)均為最小值，并且MOEA/D-CS算法對應(yīng)的平均IGD(log)曲線始終呈現(xiàn)遞減的趨勢，這說明MOEA/D-CS算法取得了比其他算法更好的收斂性.

Fig.4 Mean IGD(log) values versus numbers of FES obtained by five algorithms over 30 runs圖4 5種算法利用評價次數(shù)作為終止條件獨立運行30次獲得的平均IGD(log)值

3.4 敏感性參數(shù)分析

本文深入分析敏感性參數(shù)對MOEA/D-CS算法性能的影響.在MOEA/D-CS算法中，有兩個敏感性參數(shù):DE算子中的參數(shù)F和種群規(guī)模N.

1) 本文分別設(shè)置了參數(shù)F為單值與組合的形式.如圖5(a)和圖5(b)所示:在隨機選取的測試函數(shù)F4和ZZF7上，F(xiàn)以組合形式選取{0.5，0.7}均取得了最好的效果.這樣選取參數(shù)F可以保證MOEA/D-CS算法具有更好的性能.因此，對于MOEA/D-CS算法來說，選擇合適的參數(shù)F值是非常重要的；

2) 本文設(shè)計了不同種群規(guī)模情況下的參數(shù)實驗，研究不同種群規(guī)模對MOEA/D-CS算法性能的影響.這里，設(shè)置種群規(guī)模N=[50，100，200，300].如圖5(c)所示，種群規(guī)模對平均IGD(log)指標(biāo)值產(chǎn)生重要的影響.隨著種群規(guī)模的不斷增加，平均IGD(log)指標(biāo)值越來越小.因此，PF越來越接近了最優(yōu)邊界PF*.如圖5(d)所示:隨著種群規(guī)模的不斷擴大，MOEA/D-CS算法運行時間也不斷增加.所以必須同時兼顧算法的精度和時間代價，合理地設(shè)置種群規(guī)模以滿足實際問題的需求.

Fig.5 Performances of MOEA/D-CS with setting different parameters圖5 設(shè)置不同參數(shù)情況下MOEA/D-CS的性能

Fig.5 Performances of MOEA/D-CS with setting different parameters (Contiuned)圖5 設(shè)置不同參數(shù)情況下MOEA/D-CS的性能(續(xù))

4 結(jié) 論

本文提出了一種基于混合個體選擇機制的多目標(biāo)進(jìn)化算法，融合有監(jiān)督分類與輕量級代理模型實現(xiàn)后代個體選擇.大量實驗結(jié)果表明:與當(dāng)前流行的基于分解多目標(biāo)進(jìn)化算法相比，在沒有顯著增加時間代價的情況下，本文所提出的MOEA/D-CS算法能取得較好性能.未來工作包括:(1) 設(shè)計適用于處理具有復(fù)雜PS曲線形狀的多目標(biāo)進(jìn)化算法；(2) 將MOEA/D-CS算法應(yīng)用于實際多目標(biāo)優(yōu)化問題.