基于簡(jiǎn)化超體積的NSGA-Ⅱ算法

文章編號(hào)：2096-1472（2024）03-0026-04

DOI：10.19644/j.cnki.issn2096-1472.2024.003.006

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

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

中圖分類號(hào)：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)化問題的矢量評(píng)價(jià)遺傳算法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］，通過快速非支配排序降低算法的計(jì)算復(fù)雜度，并通過擁擠距離維持種群的多樣性，采用的精英保留策略使得父代中優(yōu)秀的個(gè)體得以保存，具有速度快、收斂性好的特點(diǎn)，但在面對(duì)高維多目標(biāo)優(yōu)化問題時(shí)，NSGA-Ⅱ算法的選擇壓力較小，擁擠距離也不適用于高維空間。因此，本文提出了基于簡(jiǎn)化超體積的NSGA-Ⅱ算法，使用簡(jiǎn)化的超體積代替擁擠距離對(duì)種群中的個(gè)體進(jìn)行比較，在更新種群時(shí)保留收斂性和分布性更優(yōu)的個(gè)體，增強(qiáng)NSGA-Ⅱ算法求解高維多目標(biāo)問題的能力。

1""簡(jiǎn)化超體積（Simplified hypervolume）

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

簡(jiǎn)化超體積的基本思想是利用空間中的鄰居解信息，對(duì)于每一個(gè)目標(biāo)函數(shù)，確定兩側(cè)的鄰居解后，選取兩個(gè)鄰居解在每個(gè)目標(biāo)函數(shù)上的最大值作為參考點(diǎn)，計(jì)算該解和參考點(diǎn)之間的體積，依次計(jì)算該解在每個(gè)目標(biāo)函數(shù)上的體積，其中最小的即該解的超體積值，以此反映周圍空間的稀疏度，降低計(jì)算復(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₂方向上的兩個(gè)體積，取最小的體積作為該解的超體積值。當(dāng)解x的收斂性更好時(shí)，x′與R之間的體積更大，當(dāng)解x的分布性更好時(shí)，鄰居解所確定的參考點(diǎn)R′與x之間的體積也更大，因此可以通過超體積值反映解的收斂性和分布性，超體積越大，解的收斂性和分布性越好，從而估計(jì)解x的綜合性能。

簡(jiǎn)化超體積的計(jì)算過程如下。

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

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

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

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

為提升NSGA-Ⅱ算法求解高維多目標(biāo)優(yōu)化問題的能力，本文提出一種基于簡(jiǎn)化超體積的NSGA-Ⅱ算法，在更新種群時(shí)使用簡(jiǎn)化的超體積替代擁擠距離衡量個(gè)體的收斂性和分布性。基于簡(jiǎn)化超體積的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)化競(jìng)賽提出的15個(gè)多目標(biāo)優(yōu)化問題^［13］作為測(cè)試函數(shù)，實(shí)驗(yàn)在基于MATLAB的多目標(biāo)優(yōu)化平臺(tái)PlatEMO^［14］上進(jìn)行測(cè)試。

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

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

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

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

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

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

作者簡(jiǎn)介：

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

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

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

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

收稿日期：2023-08-23