IRVEA：一種改進(jìn)角度懲罰距離的RVEA算法

郭華，韋偉，謝承旺,2，潘嘉敏，程文旗，謝子若

IRVEA：一種改進(jìn)角度懲罰距離的RVEA算法

郭華1，韋偉1，謝承旺1,2，潘嘉敏1，程文旗1，謝子若3

（1. 南寧師范大學(xué) 計(jì)算機(jī)與信息工程學(xué)院，廣西 南寧 530000；2. 華南師范大學(xué) 數(shù)據(jù)科學(xué)與工程學(xué)院，廣東 汕尾 516600；3. 華東交通大學(xué) 軟件學(xué)院，江西 南昌 330013）

多目標(biāo)和高維多目標(biāo)進(jìn)化算法致力于平衡收斂性和多樣性。經(jīng)典的RVEA算法利用角度懲罰距離方法平衡收斂性與多樣性，但它仍存在不足，從而對(duì)算法的性能產(chǎn)生不利影響。課題組提出一種改進(jìn)的角度懲罰距離方法IAPD以更好地平衡算法的收斂性和多樣性，并將IAPD策略嵌入RVEA中，以取代原始的APD方法，設(shè)計(jì)了一種改進(jìn)角度懲罰距離的RVEA算法，即IRVEA。IRVEA與其他三種經(jīng)典的高維多目標(biāo)進(jìn)化算法一同在3-、5-、8-和10-目標(biāo)的WFG1～WFG6測(cè)試問題上進(jìn)行IGD性能測(cè)試，結(jié)果表明：該算法在平衡收斂性和多樣性上具有顯著優(yōu)勢(shì)。由此表明IRVEA算法是一種有前途的高維多目標(biāo)進(jìn)化算法。

高維多目標(biāo)優(yōu)化；進(jìn)化算法；改進(jìn)角度懲罰距離；參考向量

1 引言

在科學(xué)計(jì)算與工程實(shí)踐中存在大量需要同時(shí)優(yōu)化多個(gè)目標(biāo)的問題，它們通常被稱為多目標(biāo)優(yōu)化問題[1]（multi-objetive optimization problem，MOP）。MOP各目標(biāo)之間往往相互沖突，改善其中一個(gè)目標(biāo)將導(dǎo)致其他一個(gè)或多個(gè)目標(biāo)性能的惡化。因此MOP一般不存在單個(gè)最優(yōu)化能同時(shí)優(yōu)化所有目標(biāo)，其求解結(jié)果往往是一組折中解，即Pareto解集或非劣解集[2]。

進(jìn)化算法（evolutionary algorithm，EA）是一類基于群體搜索的啟發(fā)式方法，它運(yùn)行一次可獲得一組解，而且它具有內(nèi)在并行性，可顯著地改善算法的搜索性能。自20世紀(jì)80年代以來，研究者基于不同的背景和視角陸續(xù)提出了一些用于求解MOP的進(jìn)化算法，即多目標(biāo)進(jìn)化算法[3–5]（multi-objective evolutionary algorithm，MOEA）。根據(jù)這些MOEA算法的主要特征可將它們粗略地分為基于支配關(guān)系、基于分解和基于指標(biāo)等三種主要的類型，而且，這些算法在求解目標(biāo)數(shù)較少的MOP（即含有2至3個(gè)目標(biāo)）時(shí)具有較好的性能，并取得了令人鼓舞的結(jié)果[6]。

隨著社會(huì)經(jīng)濟(jì)的發(fā)展，現(xiàn)實(shí)中不斷涌現(xiàn)出需要同時(shí)優(yōu)化更多目標(biāo)的問題，即高維多目標(biāo)優(yōu)化問題[7]（many-objective optimization problem，MaOP）。這些MaOP問題的目標(biāo)數(shù)通常不少于4。MaOP的出現(xiàn)給基于Pareto支配的MOEA算法帶來了巨大挑戰(zhàn)，其原因在于：1）Pareto最優(yōu)性無法有效區(qū)分高維目標(biāo)空間中解個(gè)體的優(yōu)劣，使得進(jìn)化算法的選擇壓力驟降，難以驅(qū)使種群逼近Pareto前沿[8]；2）高維目標(biāo)空間中解個(gè)體分布稀疏，它們產(chǎn)生的后代與雙親間的差異較大，使得進(jìn)化算法的變化算子面臨失效的困境[9]；3）在高維目標(biāo)空間中為保持種群的多樣性需評(píng)估解個(gè)體的鄰域擁擠度，而這需要巨大的計(jì)算開銷[10–11]，因此如何有效保持高維目標(biāo)種群的多樣性亦具挑戰(zhàn)性。

鑒于這些困難和挑戰(zhàn)，Deb等[10]利用參考點(diǎn)的方法在高維目標(biāo)空間產(chǎn)生一組均勻分布的參考點(diǎn)以引導(dǎo)種群搜索，期望獲得一組均勻分布的Pareto近似解。在此基礎(chǔ)上，Cheng等[12]提出一種參考向量引導(dǎo)的高維多目標(biāo)進(jìn)化算法RVEA（reference vector guided evolutionary algorithm，RVEA），該算法的關(guān)鍵在于利用角度懲罰距離（angle penalized distance，APD）的標(biāo)量化方法動(dòng)態(tài)平衡高維目標(biāo)優(yōu)化的收斂性和多樣性。然而，APD方法并不能有效地平衡算法的收斂性和多樣性，其原因在于：在進(jìn)化搜索的前期，APD強(qiáng)調(diào)種群的收斂性而犧牲了多樣性；而在搜索的后期，APD為了維護(hù)種群的多樣性而忽視了收斂性?；诖?，為有效平衡高維多目標(biāo)進(jìn)化算法的收斂性和多樣性，這里提出一種改進(jìn)的基于參考向量的高維多目標(biāo)進(jìn)化算法IRVEA（improved reference vector guided evolutionary algorithm，IRVEA）。IRVEA算法的主要?jiǎng)?chuàng)新在于：提出一種改進(jìn)的角度懲罰距離方法IAPD（improved angle penalized distance，IAPD），它能有效地平衡高維目標(biāo)種群的收斂性和多樣性以獲得高質(zhì)量的解集。IRVEA與三種高效的高維多目標(biāo)進(jìn)化算法，即RVEA[12]、NSGA-Ⅲ[10]和MOEA/DD[13]，一同在WFG[14]系列測(cè)試問題上進(jìn)行性能實(shí)驗(yàn)，結(jié)果表明IRVEA算法具有顯著較優(yōu)的收斂性與多樣性之綜合性能。

2 預(yù)備知識(shí)

2.1 多目標(biāo)優(yōu)化問題的定義

為不失一般性，一個(gè)最小化MOP可表示如下：

2.2 角度懲罰距離APD

經(jīng)典的RVEA算法利用角度懲罰距離APD方法動(dòng)態(tài)平衡高維目標(biāo)優(yōu)化的收斂性和多樣性。APD利用解點(diǎn)與理想點(diǎn)之間的歐式距離度量收斂性，用解向量（解點(diǎn)）與參考向量之間的銳角來度量多樣性。相比于基于懲罰的邊界相交法（penalty-based boundary intersection, PBI）采用歐式距離度量多樣性，APD則是利用基于角度的距離度量方法，它一方面更易于進(jìn)行規(guī)范化，另一方面在優(yōu)化目標(biāo)數(shù)上更易于擴(kuò)展[15]，而這對(duì)高維目標(biāo)優(yōu)化顯得尤為重要。

3 改進(jìn)角度擁擠距離的RVEA算法

3.1 APD方法的缺陷

由于APD方法在算法搜索的前期強(qiáng)調(diào)收斂性而忽視多樣性，在后期重視多樣性而忽略了收斂性，因而在有效平衡高維目標(biāo)算法的收斂性和多樣性方面存在不足，下面通過圖1說明存在的問題。

圖1 APD方法存在的不足

如圖1（a）所示，個(gè)體A和B均與參考向量2進(jìn)行了關(guān)聯(lián)，并有A2成立。如果利用APD機(jī)制選擇個(gè)體，由于前期APD機(jī)制強(qiáng)調(diào)收斂性而忽視多樣性，則個(gè)體A將被選中進(jìn)入下一代。但需看到，個(gè)體A和B到原點(diǎn)的距離相差很小，而它們與參考向量的夾角1和2相差卻較大。綜合來看，個(gè)體B更應(yīng)該保留至下一代。當(dāng)算法搜索后期，種群已較穩(wěn)定地逼近于Pareto前沿，此時(shí)各個(gè)體與原點(diǎn)之間的距離（即收斂性）相差不大。如圖1（b）所示，個(gè)體A和B與參考向量2進(jìn)行了關(guān)聯(lián)，并有A2成立。如果利用APD機(jī)制擇優(yōu)個(gè)體，由于搜索后期APD更側(cè)重多樣性，因此個(gè)體B被選中進(jìn)入下一代。但是，個(gè)體A實(shí)際上是支配個(gè)體B的，因此選中個(gè)體A而非個(gè)體B則更能促進(jìn)收斂。換言之，在搜索后期，APD機(jī)制可能會(huì)淘汰Pareto非劣解而選中被支配解，因而算法性能存在下降風(fēng)險(xiǎn)。

3.2 改進(jìn)的角度懲罰距離方法

針對(duì)3.1小節(jié)中APD方法存在的不足，這里提出一種改進(jìn)的角度懲罰距離方法（improved angle penalized distance, IAPD）。以下給出IAPD方法的數(shù)學(xué)描述，如公式（6）所示：

3.3 IRVEA算法流程

算法1：IRVEA算法流程

輸入：最大進(jìn)化代數(shù)t，一組均勻分布的單位權(quán)值向量0= {0,1,0,2, …,0,N}。

步驟1：隨機(jī)產(chǎn)生規(guī)模為的初始代種群0；

步驟2：WHILE<t

步驟7：環(huán)境選擇:P+1=Environmental-selection(P，V)；

步驟8：參考向量的自適應(yīng)調(diào)整:V+1= Reference-vector-adaption(，P+1，V，0)；

步驟9：=+1；

步驟10：END WHILE；

算法1的第7步執(zhí)行環(huán)境選擇涉及4個(gè)主要步驟，分別是：1）種群的劃分，即將個(gè)體的目標(biāo)值向量轉(zhuǎn)換后計(jì)算各個(gè)體與參考向量之間的角度，以確定個(gè)體所屬的子種群（關(guān)聯(lián)的參考向量）；2）IAPD選擇策略，即分別計(jì)算個(gè)體的IAPD值，并選擇值最小的個(gè)體進(jìn)入下一代；3）采用角度向量精英保留策略，保持種群規(guī)模不變。需要指出的是，這里的環(huán)境選擇策略與RVEA的環(huán)境選擇策略類似，所不同的是，這里是通過計(jì)算IAPD值而非APD值來擇優(yōu)個(gè)體。考慮篇幅限制，算法1的環(huán)境選擇策略省去，讀者可參閱文獻(xiàn)[12]。

4 實(shí)驗(yàn)與分析

為驗(yàn)證IRVEA算法的性能，這里將它與當(dāng)前主流的高維多目標(biāo)進(jìn)化算法，即RVEA、NSGA-Ⅲ和MOEA/DD一同在3-、5-、8-和10-目標(biāo)的WFG[14]系列測(cè)試問題進(jìn)行IGD[17]性能測(cè)試，各算法在每個(gè)測(cè)試?yán)暇?dú)立執(zhí)行20次獲得IGD指標(biāo)的均值和方差，并利用顯著水平為0.05的Wilcoxon秩和檢驗(yàn)來分析各算法獲得近似解集的性能在統(tǒng)計(jì)意義上的差異，以獲得有說服力的結(jié)論。

4.1 測(cè)試問題

實(shí)驗(yàn)利用WFG1～WFG6測(cè)試問題作為基準(zhǔn)測(cè)試函數(shù)考察算法的性能。采用WFG系列函數(shù)的原因是：1）該系列測(cè)試問題的目標(biāo)數(shù)和決策變量數(shù)是可擴(kuò)展的；2）WFG系列問題的真實(shí)PF是已知的，而且PF具有不同的難度特征，它們對(duì)算法逼近真實(shí)PF構(gòu)成了巨大挑戰(zhàn)。表1列出了WFG系列測(cè)試問題的難度特征。

表1 WFG1～WFFG6測(cè)試問題的難度特征

4.2 性能指標(biāo)

為了綜合評(píng)估算法的收斂性和多樣性，本文采用反轉(zhuǎn)世代距離（inverted generational distance，IGD）。IGD指標(biāo)可以同時(shí)度量近似解集的收斂性和多樣性，原因在于：實(shí)驗(yàn)所采用的測(cè)試問題的真實(shí)PF是已知的，通過在真實(shí)PF上均勻采樣多樣性的點(diǎn)，計(jì)算這些采樣點(diǎn)到近似Pareto解點(diǎn)之間的距離，既能反映解集的收斂性又能反映多樣性。一般而言，IGD指標(biāo)值越小，表示近似解集的收斂性和多樣性越好。假設(shè)P是MOP問題真實(shí)PF的代表解集，IGD性能指標(biāo)可利用公式（7）進(jìn)行計(jì)算：

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

為了驗(yàn)證IRVEA算法的有效性，這里將本文算法與3種具有代表性的高維多目標(biāo)進(jìn)化算法，即NSGA-Ⅲ，RVEA，MOEA/DD一同在WFG1～WFG6測(cè)試函數(shù)上進(jìn)行了IGD指標(biāo)性能比較。實(shí)驗(yàn)中考察的目標(biāo)數(shù)目分別為3、5、8和10個(gè)目標(biāo)，其分別對(duì)應(yīng)的種群規(guī)模設(shè)為92、212、156和276。

表2給出了IRVEA、RVEA、NSGA-Ⅲ和MOEA/DD四種算法在WFG1～WFG6共24個(gè)測(cè)試實(shí)例上的IGD均值與方差，以及它們的優(yōu)劣對(duì)比。表現(xiàn)最優(yōu)的IGD值用粗體標(biāo)注。從表2可以看出，IRVEA、RVEA、NSGA-III和MOEA/DD分別獲得了11、6、7和0個(gè)最優(yōu)的IGD均值。從表2的Wilcoxon秩和檢驗(yàn)的結(jié)果可知，IRVEA算法的凈勝得分（劣于的數(shù)目減去優(yōu)于的數(shù)目即為凈勝得分）相比于RVEA、NSGA-Ⅲ、MOEA/DD算法，分別為7、9和20。由此可見，IRVEA相比其他三種對(duì)比算法，它在求解WFG系列測(cè)試函數(shù)具有顯著較優(yōu)的性能。究其原因，IRVEA中的改進(jìn)的角度懲罰距離能夠更好地平衡收斂性與多樣性，因而能夠獲得相對(duì)較好的解題性能。

表2 四種算法在WFG系列測(cè)試函數(shù)上的IGD均值與方差

表2 四種算法在WFG系列測(cè)試函數(shù)上的IGD均值與方差（續(xù)）

注：‘+’、‘-’和‘=’分別表示該結(jié)果顯著地優(yōu)于、劣于和統(tǒng)計(jì)上無差別于IRVEA算法

4 結(jié)論

課題組針對(duì)經(jīng)典RVEA算法中基于APD的不足，提出一種改進(jìn)APD的方法，即IAPD。隨后將該算子嵌入到RVEA算法中以替代原有的APD方法，并由此構(gòu)造一種改進(jìn)的RVEA算法，即IRVEA。新算法與三種經(jīng)典的高維多目標(biāo)進(jìn)化算法一同在WFG1～WFG6測(cè)試問題上進(jìn)行IGD性能指標(biāo)測(cè)試，結(jié)果表明，本文算法能夠更好地平衡高維目標(biāo)空間中解群的收斂性與多樣性，它將是一種有前途的高維多目標(biāo)優(yōu)化器。未來將利用一些更加復(fù)雜的MaOP檢驗(yàn)本文算法的性能,并利用該算法求解現(xiàn)實(shí)應(yīng)用中的一些MaOP。

[1] DEB K. Multi-objective optimization using evolutionary algorithms: an introduction[M]// Multi-objective evolutionary optimization for product design and manufacturing. Springer, London, 2011: 3–34.

[2] ZHOU A, QU B Y, LI H, et al. Multiobjective evolutionary algorithms: A survey of the state of the art[J]. Swarm and evolutionary computation, 2011, 1(1): 32–49.

[3] 謝承旺, 王志杰, 夏學(xué)文.應(yīng)用檔案精英學(xué)習(xí)和反向?qū)W習(xí)的多目標(biāo)進(jìn)化算法[J]. 計(jì)算機(jī)學(xué)報(bào), 2017, 40(3):757–772.

[4] MA H, SHEN S, YU M, et al. Multi-population techniques in nature inspired optimization algorithms: A comprehensive survey[J]. Swarm and evolutionary computation, 2019, 44: 365–387.

[5] Falcón-Cardona J G, Coello C A C. Indicator-based multi-objective evolutionary algorithms: A comprehensive survey[J]. ACM computing surveys (CSUR), 2020, 53(2): 1–35.

[6] TIAN Y, CHENG R, ZHANG X, et al. A strengthened dominance relation considering convergence and diversity for evolutionary many-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2018, 23(2): 331–345.

[7] ISHIBUCHI H, AKEDO N, NOJIMA Y. Behavior of multi-objective evolutionary algorithms on many-objective knapsack problems[J]. IEEE Transactions on Evolutionary Computation, 2014, 19(2): 264–283.

[8] TIAN Y, WANG H, ZHANG X, et al. Effectiveness and efficiency of non-dominated sorting for evolutionary multi-and many-objective optimization[J]. Complex & Intelligent Systems, 2017, 3(4): 247–263.

[9] Purshouse R C, FLEMING P J. On the evolutionary optimization of many conflicting objectives[J]. IEEE transactions on evolutionary computation, 2007, 11(6): 770–784.

[10] DEB K, Jain H. An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, part I: solving problems with box constraints[J]. IEEE transactions on evolutionary computation, 2013, 18(4): 577–601.

[11] JAIN H, DEB K. An evolutionary many-objective optimization algorithm using reference-point based non-dominated sorting approach, part II: Handling constraints and extending to an adaptive approach[J]. IEEE Transactions on evolutionary computation, 2013, 18(4): 602–622.

[12] CHENG R, JIN Y, OLHOFER M, et al. A reference vector guided evolutionary algorithm for many-objective optimization[J]. IEEE transactions on evolutionary Computation, 2016, 20(5): 773–791.

[13] 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, 2014, 19(5): 694–716.

[14] HUBAND S, HINGSTON P, BARONE L, et al. A review of multi-objective test problems and a scalable test problem toolkit[J]. IEEE transactions on evolutionary computation, 2006, 10(5): 477-506.

[15] 謝承旺, 李凱, 廖國(guó)勇.一種帶差分局部搜索的改進(jìn)型NSGA2算法[J]. 計(jì)算機(jī)科學(xué), 2013, 40(10):235–238+273.

[16] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multi-objective genetic algorithm: NSGA-II[J]. IEEE transactions on evolutionary computation, 2002, 6(2): 182–197.

[17] ZITZLER E, THIELE L, LAUMANNS M, et al. Performance assessment of multi-objective optimizers: An analysis and review[J]. IEEE Transactions on evolutionary computation, 2003, 7(2): 117–132.

IRVEA: A New RVEA Approach with Improved Angle Penalty Distance

GUO Hua1,WEI Wei1, XIE Cheng-wang1,2, PAN Jia-min1,CHENG Wen-qi1, XIE Zi-ruo3

（1. School of Computer and Information Engineering, Nanning Normal University, Nanning Guangxi 530000; 2.School of Data Science and Engineering, South China Normal University, Shanwei, Guangdong 516600; 3. School of Software, East China Jiaotong University, Nanchang, Jiangxi 330013, China）

Multi-objective and many-objective evolutionary algorithms are devoted to balance convergence and diversity. The classical RVEA approach uses the angle penalty distance method to balance the convergence and diversity, but it still has shortcomings, which results in the adverse impact on the performance. An improved angle penalty distance method, that is IAPD, is proposed to better balance the convergence and diversity, and the IAPD strategy is embedded in the original RVEA to replace APD method, then the improved RVEA, that is IRVEA, is designed to solve MaOPs effectively. The IRVEA is compared with the other three typical many-objective evolutionary algorithms based on IGD indicator on WFG1 to WFG6 with 3-, 5-, 8-, and 10- objectives, respectively. The empirical results show that the proposed IRVEA has significantly advantageous over the peer algorithms in terms of convergence and diversity. Therefore, the IRVEA is a promising solution for MaOPs.

many-objective optimization problems; evolutionary algorithm; improved angle penalty distance; many-objective evolutionary algorithm; reference vector

TP181

A

2095-9249（2021）06-0062-06

2021-10-10

國(guó)家自然科學(xué)基金（61763010）；廣西自然科學(xué)基金（2021GXNSFAA075011）；廣西研究生教育創(chuàng)新計(jì)劃項(xiàng)目（YCSW2020194）

郭華（1996—），女，甘肅隴南人，碩士研究生，研究方向：智能計(jì)算和多目標(biāo)優(yōu)化。

謝承旺（1974—），男，湖北武漢人，教授，博士，研究方向：智能計(jì)算，E-mail: chengwangxie@m.scnu.edu.cn

〔責(zé)任編校：陳楠楠〕