文章編號：2096-1472（2024）03-0026-04

DOI：10.19644/j.cnki.issn2096-1472.2024.003.006

摘"要：針對NSGA-Ⅱ算法在高維多目標(biāo)優(yōu)化時選擇壓力較小，不適用于高維空間的問題，提出一種基于簡化超體積的NSGA-Ⅱ算法，利用超體積在高維空間中可以準(zhǔn)確評價個體優(yōu)劣的特點(diǎn)，使用簡化超體積代替擁擠距離對種群中的個體進(jìn)行比較，在更新種群時保留收斂性和分布性更好的個體。通過與4個先進(jìn)的、具有代表性的高維多目標(biāo)進(jìn)化算法（NSGA-Ⅲ、MOEA/DD、KnEA、RVEA）的對比實(shí)驗(yàn)表明，基于簡化超體積的NSGA-Ⅱ算法在求解大多數(shù)測試函數(shù)時，獲得了更優(yōu)的解集，證明了該算法處理高維多目標(biāo)優(yōu)化問題的優(yōu)越性能。

關(guān)鍵詞：高維多目標(biāo)優(yōu)化；進(jìn)化算法；超體積

中圖分類號：TP301""文獻(xiàn)標(biāo)志碼：A

NSGA-Ⅱ Algorithm Based on Simplified Hypervolume

JI Hong， ZHAO Jianyin， CHEN Jian， GE Rui

（Naval Aviation University， Yantai 264001， China）

ytjihong@163.com; 13791182798@163.com; 57991949@qq.com; gr33995@126.com

Abstract： Aiming at the problem that the NSGA-Ⅱ algorithm has low selection pressure in many-objective optimization and is not suitable for high-dimensional space， this paper proposes a NSGA-Ⅱ algorithm based on simplified hypervolume. As hypervolume can accurately evaluate the advantages and disadvantages of individuals in high-dimensional space， individuals in the population are compared by simplified hypervolume instead of crowding distance， and individuals with better convergence and distribution are retained when updating the population. The comparative experiment with four many-objective evolutionary algorithms （NSGA-Ⅲ， MOEA/DD， KnEA， RVEA） shows that the proposed NSGA-Ⅱ algorithm based on simplified hypervolume achieves a better solution set when solving most test functions， which proves its excellent performance in handling many-objective optimization problems.

Key words： many-objective optimization; evolutionary algorithm; hypervolume

0""引言（Introduction）

進(jìn)化算法通過模擬生物種群的進(jìn)化迭代過程處理傳統(tǒng)優(yōu)化算法難以解決的復(fù)雜問題，具有魯棒性強(qiáng)、應(yīng)用廣泛等優(yōu)點(diǎn)，自David Schaffer首次提出使用進(jìn)化算法求解多目標(biāo)優(yōu)化問題的矢量評價遺傳算法VEGA^［1］以來，進(jìn)化算法在求解多目標(biāo)優(yōu)化問題上得到了廣泛的應(yīng)用，涌現(xiàn)出了許多經(jīng)典的多目標(biāo)進(jìn)化算法^［2-4］。2002年，SRINIVAS等^［5］改進(jìn)了非支配排序遺傳算法NSGA，提出了使用擁擠距離維持種群分布性和多樣性的快速非支配排序方法——NSGA-Ⅱ^［6］，通過快速非支配排序降低算法的計算復(fù)雜度，并通過擁擠距離維持種群的多樣性，采用的精英保留策略使得父代中優(yōu)秀的個體得以保存，具有速度快、收斂性好的特點(diǎn)，但在面對高維多目標(biāo)優(yōu)化問題時，NSGA-Ⅱ算法的選擇壓力較小，擁擠距離也不適用于高維空間。因此，本文提出了基于簡化超體積的NSGA-Ⅱ算法，使用簡化的超體積代替擁擠距離對種群中的個體進(jìn)行比較，在更新種群時保留收斂性和分布性更優(yōu)的個體，增強(qiáng)NSGA-Ⅱ算法求解高維多目標(biāo)問題的能力。

1""簡化超體積（Simplified hypervolume）

超體積（Hypervolume，HV）^［7］可以評估高維空間中個體的收斂性和分布性，增強(qiáng)算法的選擇壓力，指導(dǎo)搜索過程向Pareto最優(yōu)前沿面（所有Pareto最優(yōu)解的目標(biāo)向量所組成的集合）靠近，但計算復(fù)雜度較高，因此本文采用簡化的超體積^［8］對個體進(jìn)行比較，選擇收斂性和分布性更好的個體保留。

簡化超體積的基本思想是利用空間中的鄰居解信息，對于每一個目標(biāo)函數(shù)，確定兩側(cè)的鄰居解后，選取兩個鄰居解在每個目標(biāo)函數(shù)上的最大值作為參考點(diǎn)，計算該解和參考點(diǎn)之間的體積，依次計算該解在每個目標(biāo)函數(shù)上的體積，其中最小的即該解的超體積值，以此反映周圍空間的稀疏度，降低計算復(fù)雜度。

為了方便說明，以兩目標(biāo)優(yōu)化問題為例。如圖1所示，解a和解b是解x在目標(biāo)函數(shù)f₁方向上兩側(cè)的鄰居解，點(diǎn)R是由它們所確定的參考點(diǎn)，x和R之間的體積V即為所求。分別求得解x在目標(biāo)函數(shù)f₁和f₂方向上的兩個體積，取最小的體積作為該解的超體積值。當(dāng)解x的收斂性更好時，x′與R之間的體積更大，當(dāng)解x的分布性更好時，鄰居解所確定的參考點(diǎn)R′與x之間的體積也更大，因此可以通過超體積值反映解的收斂性和分布性，超體積越大，解的收斂性和分布性越好，從而估計解x的綜合性能。

簡化超體積的計算過程如下。

首先，根據(jù)公式（1）對種群P進(jìn)行歸一化操作，消除量綱影響：

其中：x∈P；f_i（x），i=1，2，…，m是多目標(biāo)優(yōu)化問題的m個目標(biāo)函數(shù)；min f_i和max f_i是種群P中所有解在第i個目標(biāo)函數(shù)的最小值和最大值。

對于邊界點(diǎn)的處理，需要保留部分邊界點(diǎn)用于維持種群的分布性，但是在高維空間中，可能會在多個目標(biāo)函數(shù)方向上有共同的邊界點(diǎn)，從而導(dǎo)致邊界點(diǎn)的超體積很小，因此在計算邊界點(diǎn)的超體積時，需要去掉目標(biāo)函數(shù)值最大的項。綜上所述，解xi與參考點(diǎn)rji之間確定的體積的計算公式如下：

2""基于簡化超體積的NSGA-Ⅱ算法（NSGA-Ⅱ algorithm based on simplified hypervolume）

為提升NSGA-Ⅱ算法求解高維多目標(biāo)優(yōu)化問題的能力，本文提出一種基于簡化超體積的NSGA-Ⅱ算法，在更新種群時使用簡化的超體積替代擁擠距離衡量個體的收斂性和分布性?；诤喕w積的NSGA-Ⅱ算法的具體步驟如下。

3""數(shù)值實(shí)驗(yàn)（Numerical experiment）

為了驗(yàn)證算法的性能，將改進(jìn)的算法與較為先進(jìn)的高維多目標(biāo)進(jìn)化算法NSGA-Ⅲ^［9］、MOEA/DD^［10］、KnEA^［11］和RVEA^［12］進(jìn)行比較，選取CEC2018高維多目標(biāo)優(yōu)化競賽提出的15個多目標(biāo)優(yōu)化問題^［13］作為測試函數(shù)，實(shí)驗(yàn)在基于MATLAB的多目標(biāo)優(yōu)化平臺PlatEMO^［14］上進(jìn)行測試。

實(shí)驗(yàn)選取逆世代距離 （Inverted Generational Distance，IGD）^［15］指標(biāo)衡量算法的性能，如公式（4）所示：

其中：P*為真實(shí)Pareto最優(yōu)前沿面上均勻采樣取得的解集；P是通過算法進(jìn)化得到的解集；d（x*，P）表示解x*與P中距離x*最近的解之間的歐式距離；|P*|是解集P*的規(guī)模，IGD越小，算法的收斂性和分布性越好。

將算法在具有5個目標(biāo)函數(shù)的15個測試函數(shù)上進(jìn)行測試，種群規(guī)模N=200，迭代次數(shù)為1 000，每個測試函數(shù)獨(dú)立運(yùn)行20次，IGD平均值和標(biāo)準(zhǔn)差如表1所示，其中IGD最小的平均值加粗顯示，括號中的數(shù)值是標(biāo)準(zhǔn)差，“+”“=”“-”則分別表示改進(jìn)的算法對比NSGA-Ⅲ、MOEA/DD、KnEA和RVEA更好、一樣、更差。

4""結(jié)果分析（Result analysis）

在15個測試函數(shù)中，本文提出的基于簡化超體積的NSGA-Ⅱ算法在8個測試函數(shù)上比其他4個對比算法的IGD值更小，表現(xiàn)更優(yōu)，證明了本文算法在求解大部分高維多目標(biāo)優(yōu)化問題時有較好的表現(xiàn)。

在MaF1～MaF15的15個測試函數(shù)中，MaF1、MaF2、MaF4、MaF5、MaF7、MaF8、MaF9和MaF15有局部Pareto最優(yōu)前沿面，即這8個測試函數(shù)的Pareto最優(yōu)前沿面投影不能全部覆蓋單位超平面，在這8個測試函數(shù)中，本文算法的平均IGD分別在5個函數(shù)上比NSGA-Ⅲ、MOEA/DD、KnEA和RVEA的都要小。MaF3、MaF10、MaF11、MaF12、MaF13和MaF14這6個測試函數(shù)的Pareto最優(yōu)前沿面投影能夠完全覆蓋單位超平面，本文算法分別在兩個多目標(biāo)優(yōu)化問題上優(yōu)于NSGA-Ⅲ、MOEA/DD、KnEA和RVEA。對于Pareto最優(yōu)前沿面有退化性的測試函數(shù)MaF6，本文算法優(yōu)于NSGA-Ⅲ、MOEA/DD、KnEA和RVEA。綜上所述，基于簡化超體積的NSGA-Ⅱ算法在大多數(shù)多目標(biāo)優(yōu)化問題上都可以獲得收斂性和分布性更優(yōu)的解集，可以求解具有不同類型Pareto最優(yōu)前沿面的高維多目標(biāo)優(yōu)化問題。

5""結(jié)論（Conclusion）

為了使NSGA-Ⅱ算法在求解高維多目標(biāo)問題時有更好的表現(xiàn)，本文提出一種基于簡化超體積的NSGA-Ⅱ算法，利用簡化超體積在高維空間中可以更好地衡量個體收斂性和分布性的特點(diǎn)，代替NSGA-Ⅱ算法原有的擁擠距離對個體進(jìn)行比較，從而保留種群中性能更優(yōu)的個體。實(shí)驗(yàn)結(jié)果表明，基于簡化超體積的NSGA-Ⅱ算法在求解高維多目標(biāo)優(yōu)化問題時表現(xiàn)較好，可以獲得收斂性和分布更優(yōu)的解集。

參考文獻(xiàn)（References）[HQ]

［1］ SCHAFFER J D. Multiple objective optimization with vector [JP2]evaluated genetic algorithms［C］∥GREFENSTETTE J J. Proceedings of the First International Conference on Genetic Algorithms and Their Applications. Hillsdale：Lawrence Erlbaum Associates，1985：93-100.

［2］ 劉建昌，李飛，王洪海，等. 進(jìn)化高維多目標(biāo)優(yōu)化算法研究綜述［J］. 控制與決策，2018，33（5）：879-887.

［3］ 馮茜，李擎，全威，等. 多目標(biāo)粒子群優(yōu)化算法研究綜述［J］. 工程科學(xué)學(xué)報，2021，43（6）：745-753.

［4］ 呂文鵬，許峰. 基于自適應(yīng)網(wǎng)格方法的免疫多目標(biāo)進(jìn)化算法［J］. 軟件工程，2018，21（6）：25-28.

［5］ SRINIVAS N，DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms［J］. Evolutionary computation，1994，2（3）：221-248.

［6］ DEB K，PRATAP A，AGARWAL S，et al. A fast and elitist multiobjective genetic algorithm：NSGA-Ⅱ［J］. IEEE transactions on evolutionary computation，2002，6（2）：182-197.

［7］ AUGER A，BADER J，BROCKHOFF D，et al. Theory of the hypervolume indicator：optimal μ-distributions and the choice of the reference point［C］∥ACM. Proceedings of the Tenth ACM SIGEVO Workshop on Foundations of Genetic Algorithms. New York：ACM，2009：87-102.

［8］ JI H，DAI C. A simplified hypervolume-based evolutionary algorithm for many-objective optimization［J］. Complexity，2020，2020：1-7.

［9］ DEB K，JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach，part Ⅰ：solving problems with box constraints［J］. IEEE transactions on evolutionary computation，2014，18（4）：577-601.

［10］ LI K，DEB K，ZHANG Q F，et al. An evolutionary many-objective optimization algorithm based on dominance and decomposition［J］. IEEE transactions on evolutionary computation，2015，19（5）：694-716.

［11］ ZHANG X Y，TIAN Y，JIN Y C. A knee point-driven evolutionary algorithm for many-objective optimization［J］. IEEE transactions on evolutionary computation，2015，19（6）：761-776.

［12］ CHENG R，JIN Y C，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］ CHENG R，LI M，TIAN Y，et al. Benchmark functions for CEC’2017 competition on many objective optimization［R］. Birmingham：School of Computer Science，University of Birmingham Edgbaston，2017.

［14］ TIAN Y，CHENG R，ZHANG X Y，et al. PlatEMO：a MATLAB platform for evolutionary multi-objective optimization［J］. IEEE computational intelligence magazine，2017，12（4）：73-87.

［15］ ZITZLER E，THIELE L，LAUMANNS M，et al. Performance assessment of multiobjective optimizers：an analysis and review［J］. IEEE transactions on evolutionary computation，2003，7（2）：117-132.

作者簡介：

紀(jì)"紅（1994-），女，碩士，助教。研究領(lǐng)域：進(jìn)化算法。

趙建?。?976-），男，博士，副教授。研究領(lǐng)域：計算機(jī)仿真。

陳"?。?985-），男，博士，講師。研究領(lǐng)域：計算機(jī)仿真。

葛"睿（1995-），男，碩士，助教。研究領(lǐng)域：進(jìn)化算法。

收稿日期：2023-08-23