基于自适应混合非支配个体排序策略的改进型NSGA—Ⅱ算法

耿焕同 李辉健 赵亚光 陈正鹏

摘要：针对经典快速非支配排序遗传算法（NSGAⅡ）中基于拥挤距离的种群多样性保持策略不能客观反映个体间真实拥挤程度的问题，提出了一种基于自适应混合非支配个体排序策略的改进型NSGAⅡ算法（NSGAⅡh）。首先，设计一种新的循环聚类个体排序策略； 然后， 根据Pareto分层信息来对基于经典拥挤距离和循环聚类的两种个体排序策略进行自适应的选择； 最终，实现对进化后期的种群多样性保持机制的改进。通过5个标准测试函数进行算法验证，并与经典的NSGAⅡ、多目标粒子群优化算法（MOPSO）和GDE3等算法进行对比分析，NSGAⅡh算法获得了80%的最优反向世代距离（IGD）值，且显著性水平为5%的双尾t检验结果表明，新算法具有明显统计意义上的性能优势。改进算法不仅能提高进化种群的分布性，而且能增强算法的收敛性，有效提高了优化效果。

关键词：快速非支配排序遗传算法；非支配个体排序；拥挤距离；循环聚类；自适应

中图分类号：TP183 文献标志码：A

Abstract：In order to solve the problem that the population diversity preservation strategy only based on crowding distance of Nondominated Sorting Genetic AlgorithmⅡ （NSGAⅡ） cannot reflect the real crowding degree of individuals， an improved NSGAⅡ algorithm based on the adaptive hybrid nondominated individual sorting strategy （NSGAⅡh） was proposed. First， a novel loopclustering individual sorting strategy was designed. Second， according to the Pareto layersorting information the NSGAⅡh algorithm adaptively chose one from the two individual sorting strategies based on classical crowding distance and loopclustering. Finally， the diversity maintain mechanism could be improved especially during the late period of evolutionary optimization. The NSGAⅡh algorithm was compared with three classical algorithms including NSGAⅡ， MultiObjective Particle Swarm Optimization （MOPSO） and GDE3. The experiments on five multiobjective benchmark functions show that the NSGAⅡh algorithm can acquire 80% of optimal Inverted Generational Distance （IGD） values， and the corresponding twotailed ttest results at a 0.05 level of significance are remarkable. The proposed algorithm can not only improve convergence of the original algorithm， but also enhance the distribution of Pareto optimal set.

Key words：Nondominated Sorting Genetic AlgorithmⅡ （NSGAⅡ）； nondominated individual sorting； crowding distance； loopclustering； adaptive

0 引言

现实生产生活中，复杂的优化问题往往由多个相互冲突的优化目标组成，称为多目标优化问题。进化算法已成为解决这些复杂优化问题的方法之一，特别是对一些传统解析方法难以求解的复杂工程问题，正越来越受到国内外进化算法研究学者的关注。研究表明，进化多目标优化算法是解决多目标优化问题的有效方法并在多项复杂工程优化领域得到成功应用，如航空航天技术——NASA奥德赛火星探测器自动天线设计[1]、大型物流配送系统——DHL公司的货物配送路线规划[2]、大型建筑桁架结构设计——鸟巢、水立方架构优化设计[3]等。

进化多目标优化算法发展至今，大致可分为三个阶段[4]：

第一阶段是基于Pareto个体排序和适应度共享机制保持群体多样性的阶段。如Fonseca等[5]提出的多目标遗传算法（MultiObjective Genetic Algorithm， MOGA），Srinivas等[6]提出的非支配排序遗传算法（NonDominated Sorting Genetic Algorithm， NSGA），Horn等[7]提出的带小生境的Pareto支配遗传算法（Niched Pareto Genetic Algorithm， NPGA）。第二阶段是以精英群体保留机制为特征的阶段。如Zitzler等[8-9]提出的基于Pareto支配强度的多目标进化算法（Strength Pareto Evolutionary Algorithm， SPEA）和对其改进后的SPEA2算法。Deb等通过对NSGA算法的改进，提出了非常经典的快速非支配排序遗传算法（Nondominated Sorting Genetic Algorithm， NSGAⅡ）[10]。第三阶段更关注求解高维目标优化问题，衍生出许多新型Pareto支配机制和新型进化机制。如Brockoff等[11]提出的部分支配机制，Coello等[12]提出的多目标粒子群优化算法（MultiObjective Particle Swarm Optimization， MOPSO）。

NSGAⅡ算法作为进化计算领域最为经典的算法之一。虽然常作为对比算法验证改进后算法的优劣，但是其自身还存在一定的缺陷，即单一采用拥挤距离大小进行同层群体多样性保持并不能客观反映个体间的真实拥挤程度，特别是种群进化后期，随着非支配解集的增大，该缺陷愈加明显。这就直接影响到了种群的多样性，最终影响到寻得Pareto解集的优劣。近年来，进化计算领域针对非支配个体排序的研究已经取得了一些成果，如罗辞勇等[13]提出了采用循环拥挤排序策略的改进NSGAⅡ算法，该算法虽然在一定程度上提高了种群多样性，但算法执行效率偏低，尤其是在种群进化后期，随着非支配解的不断增多，计算复杂度迅速增加。Fortin等[14]针对拥挤距离策略对非支配个体密度估计不准确这一问题，提出了新的个体排序策略，即采用新的个体适应度算子代替拥挤距离算子对非支配解进行排序，该算法在不增加时间复杂度的情况下，提高了算法的收敛性和分布性；但算法在解决高维目标优化问题时还需要进一步优化验证。Mohapatra等[15]先通过挖掘同层非支配个体信息产生一组分布均匀的虚拟均值个体；然后依据原非支配个体的拥挤程度，用虚拟个体对原个体进行有选择的替换；进而计算个体的适应度值，对个体进行排序选择；最后将该策略代替NSGAⅡ中的拥挤距离策略，提出了基于均值个体的改进NSGAⅡ算法，该算法有效地提高了种群的分布性。

本文针对经典NSGAⅡ算法中的基于拥挤距离策略不能客观反映个体间的真实拥挤程度的不足，提出一种基于自适应混合非支配个体排序策略的改进型NSGAⅡ算法。其思想是首先设计一种新的循环聚类个体排序策略，然后根据Pareto分层信息来对基于经典拥挤距离和循环聚类的两种个体排序策略进行自适应的选择，改进进化后期的多样性保持机制，以增强改进型NSGAⅡ算法的优化效果。

2 经典NSGAⅡ算法存在的问题

2.1 NSGAⅡ算法回顾

2002年Deb等在NSGA基础上提出了快速带精英策略的NSGAⅡ算法。主要改进之处有：首先，设计了基于合并父代种群和子代种群的精英保留策略；其次，通过快速非支配排序策略降低算法计算复杂度；再者，采用拥挤距离策略代替适应度共享策略来实现更具可操作性的非支配个体排序方法。NSGAⅡ算法流程如下：

步骤1 群体初始化。随机产生包含N个个体的初始种群Pt（t=0），Qt=。

步骤2 适应度计算。合并Pt和Qt种群得Rt={Pt∪Qt}，依据评估函数对种群Rt进行个体适应度计算。

步骤3 Pareto分层非支配排序与个体拥挤距离计算。

3.1） k=1，R′t=Rt；

3.2）从种群R′t提取出Pareto最优解集PSk，R′t=R′t-PSk，k=k+1；

3.3）若R′t≠，则转3.2）；

3.4） 计算种群Rt中每个个体的拥挤距离。

步骤4 进化操作。

4.1）依据每一个个体的Pareto分层数和拥挤距离，从Rt选出前N个个体作为下一代种群Pt+1；

4.2）对种群Pt+1进行交叉操作生成群体Qt+1，并对Qt+1进行变异操作。

步骤5 算法终止判断。t=t+1，判断t是否大于最大迭代次数MaxGen，若是则输出Pt中的非支配个体作为Pareto最优解集，且算法结束；否则，转到步骤2。

基于群体的进化多目标优化算法的关键所在是寻找一种合理的个体排序方法，将个体间的偏序关系转换成利于搜索的全序关系；而NSGAⅡ算法采用Pareto分层及拥挤距离的方法来对个体排序，进化后期个体拥挤距离成为个体排序的决定因素，因此对个体拥挤距离策略的深入分析是非常必要的。

2.2 拥挤距离策略存在的不足分析

回顾NSGAⅡ算法中个体拥挤距离的计算过程可知：根据群体中不同个体在同一个目标函数上的数值大小，进行从小到大个体排序，排序后除首、尾两个体拥挤距离为∞外，其他个体的拥挤距离为前、后两个体在此目标值的差值除以该目标上的最大值与最小值的差值；对每一个个体在每一个目标函数上的拥挤距离进行相加求和，就得到每个体的拥挤距离值。通过实验分析，发现基于拥挤距离策略的个体排序方法存在着不足，即单一采用拥挤距离大小进行群体多样性保持并不能客观反映个体间的真实拥挤程度。

为更好地分析该策略存在的不足，以NSGAⅡ算法求解多目标优化标准测试函数ZDT1问题为例，选取进化过程中某一代的首层Pareto最优个体集（见2.1节步骤3中种群Rt分层排序得到的首层Pareto最优解集PS1）为分析对象，共有18个非支配个体，个体的分布情况见图1（a）所示，所有个体的两目标函数值及拥挤距离值见表1所示。

按照基于拥挤距离策略的个体排序方法进行选择，现假设需从中选择9个非支配个体进入下一代群体，将得到图1（b）中的个体，其余个体将被淘汰。从图1（b）可看出，由于拥挤距离策略存在的不足导致个体f和p之间出现了搜索盲区，致使多样性保持缺乏，势必影响算法搜索效率和解集的均匀分布性。

从上述分析可知，当NSGAⅡ算法采用基于拥挤距离策略的个体排序方法进行筛选个体时，当拥挤距离较小和较大的个体分布都较为聚集时，筛选后的解集分布性不够理想，即单一采用拥挤距离大小进行群体多样性保持并不能客观反映个体间的真实拥挤程度。究其原因是个体的拥挤距离计算仅依赖于其相邻两个体的位置信息，没有考虑种群中其他个体的位置信息。

3 NSGAⅡh算法

为改进基于拥挤距离策略的个体排序方法存在的不足，文中将增加基于聚类分析的个体选择方法；在进化过程中，根据每代首层Pareto最优个体集的规模大小来自适应确定采用拥挤距离策略还是聚类选择策略。

3.1 新型个体聚类选择策略

为克服NSGAⅡ算法中拥挤距离在保持种群多样性上的不足，本文增加聚类排序策略来进行个体选择，简称为个体聚类选择策略。聚类分析属于数据挖掘技术，旨在将一组同类样本划分为多个类簇，力求类间相异、类内相似。常见的聚类算法有KMedoids和KMeans算法，为选择能保持具有更好多样性的个体以及不同聚类算法的特点，文中选用KMedoids算法作为同一层个体的聚类算法，结合Pareto非支配个体集的选择好坏对种群多样性保持的重要影响。为方便叙述，不妨以2目标优化问题为例，聚类数设为c，要求从规模为Np的非支配群体P中选择Nc个个体作为下一代进化群体，主要步骤具体如下。

第一步 设计一种新的聚类初始点选取策略来确定聚类初始点。已有文献[16-17]表明聚类效果依赖于聚类初始点的选取，同时考虑到非支配个体选择对群体多样性保持的影响，本文专门设计了一种基于各聚类大小分布均匀新的聚类初始点选取策略。具体为在已知聚类数的情况下，首先选取每一个目标函数的最大值与最小值个体直接进入下一代进化群体；然后依次以每个目标的最大和最小值为边界，将中间区域划分为c-2等份，统计每等分区间中非支配个体的数目；接着依次按式（2）计算每个目标上不同区间的均匀分布方差D（fi），以D（fi）最小的目标函数作为划分；最后从选定的划分区域中随机挑选一个作为聚类初始个体。图2是采用基于各聚类大小分布均匀的聚类初始点选取策略，从20个非支配个体选取3个初始聚类个体的实现过程。

其中：N为种群规模，t当前进化代数，MaxGen为进化过程的最大迭代次数。在进化前期，待聚类的首层Pareto最优解集中规模相对较少，选取较小的聚类数目c将提高算法的探索能力，增强算法的收敛性能；而在进化的后期，通过逐渐增加聚类数，将提高算法的探究能力，以便更好地保持群体分布性。

3.3 自适应混合非支配个体排序的改进型NSGAⅡ算法

通过引入新的混合个体排序策略来改进NSGAⅡ算法中的拥挤距离策略，本文提出了基于自适应混合个体排序策略的改进型NSGAⅡ算法（NSGAⅡ based on Adaptive Hybrid Individual Sorting， NSGAⅡh）。除步骤4外，该算法的主要流程与2.1节中NSGAⅡ类似，不再赘述。下面仅给出步骤4的具体实现过程。

步骤4 进化操作。

4.1）判断Pareto首层的规模是否小于种群规模N，若是则采用Pareto分层和拥挤距离策略，Rt选出前N个个体作为下一代种群Pt+1；否则，依据式（3）计算聚类数c，采用基于自适应混合非支配个体排序策略，Rt选出前N个个体作为下一代种群Pt+1。

4.2）对种群Pt+1进行交叉操作生成群体Qt+1，并对Qt+1 进行变异操作。

由于3.1节中对新型个体聚类选择策略进行了时间复杂度的分析，当优化的目标数远小于进化群体的规模时，其时间复杂度与经典NSGAⅡ中非支配个体Pareto分层的时间复杂度O（N2）相同。因此，基于自适应混合非支配个体排序策略的改进型NSGAⅡ算法的时间复杂度与经典的NSGAⅡ算法也相同。

4 实验及结果分析

4.1 测试函数

实验时，选取当前进化多目标优化领域普遍使用的标准测试函数ZDT（ZitzlerDebThiele）[18]系列和SCH[19]来检验算法的优化效果，具体的函数描述见表2。这些函数包含了连续函数、非连续函数、凹函数、凸函数等多种复杂类型。

4.2 实验设计与主要参数设置

为了测试NSGAⅡh算法的优化性能，分别与经典的NSGAⅡ算法、MOPSO算法、GDE3算法[20]进行对比，检验算法的改进效果。算法均采用相同的参数设置：种群规模N=100，运行代数MaxGen=300；交叉概率设置为Pm=0.9，变异概率设置为Pc=0.1；每个算法对每个问题独立运行30次。

4.3 评价指标IGD

为更科学地比较不同算法得到的Pareto解集的收敛性和多样性，文中采用多目标优化领域普遍使用的综合性指标反向世代距离（Inverted Generational Distance， IGD）来进行比较算法，此指标是度量真实Pareto前沿到算法得到的近似Pareto前沿之间距离，指标值越小，说明算法得到的Pareto解集的收敛性和多样性越好，越接近真实Pareto前沿。IGD计算公式如下：

4.4 实验结果及分析

为了对比NSGAⅡh和各对比算法的优劣，图3～图7分别是两个算法在各个测试函数上获得的最优解集，算法设置相同参数和相同初始种群。

从图3～图7可以直观地看出，NSGAⅡh算法无论在分布性还是收敛性上都取得了更为理想的结果，而MOPSO的分布性和收敛性均表现最差。例如，对于ZDT1测试问题，NSGAⅡh和GDE3算法具有最好的分布性和收敛性，NSGAⅡ具有较好的收敛性，但是部分区域没有被Pareto最优解覆盖，分布性方面出现了不均匀现象，而MOPSO算法并没有收敛，分布性也不够理想。再如，对于ZDT2测试问题，GDE3算法具有最好收敛性和分布性，虽然本算法在个别点上分布性稍有逊色，但同样具有良好的收敛性。而NSGAⅡ算法虽然收敛性较好，但分布性略显不够；而MOPSO收敛性和分布性均最差。因此从实验结果来看NSGAⅡh不仅具有较强的寻优能力，而且能保持较好的最优前沿分布性。

为更细致地定量分析算法优劣，表3列出了NSGAⅡh和对比算法在各个测试问题上的IGD性能指标值，同时参考文献[21]做法给出ttest指标值，其中，IGD的平均值（mean）和方差值（std）是同一算法在同一测试问题上独立运行30次的统计结果，同时ttest值是本文算法与3种对比算法在同一测试问题上进行t检验时的t值（“+”“=”和“-”表示本文算法获得的IGD 值在显著性水平为5%的双尾t检验中分别优于、等于和劣于对应列的对比算法在对应行的测试问题上的显著性区分结果）。

分析表3的IGD指标数据可知，NSGAⅡh算法在5个测试函数上获得了4个最优IGD值，GDE3获得了1个最优IGD值，NSGAⅡ与MOPSO算法均未获得最优IGD值。同时，对t检验结果分析可知，NSGAⅡh算法在上述测试函数上具有明显统计意义上的性能优势。综上分析可知，与NSGAⅡ、MOPSO和GDE3算法相比，NSGAⅡh算法获得的解集具有更好的收敛性和分布性。这说明通过本文提出的混合个体排序策略不仅能提高种群分布性，而且能提高算法的收敛性。

5 结语

通过对NSGAⅡ算法中基于拥挤距离个体排序策略在进化后期多样性保持不足的分析，设计并提出了一种基于自适应混合非支配个体排序策略的改进型NSGAⅡ算法。算法实现上提出了新型个体聚类选择策略和自适应混合非支配个体排序策略等，以实现对进化后期的多样性保持机制的改进。在实验部分，选取了5个标准测试函数进行测试，并与NSGAⅡ、MOPSO、GDE3算法进行对比，NSGAⅡh算法获得了80%的最优IGD值；并从显著性水平为5%的双尾t检验结果可知，NSGAⅡh算法具有明显统计意义上的性能优势。NSGAⅡh算法在不提高算法时间复杂度的情况下，不仅有效提高了解集的分布性，而且具有更好的收敛性；与此同时，文中提出的自适应混合非支配个体排序策略由于不受优化目标维数影响，因此可用于高维目标优化问题求解中，实现对进化高维目标优化算法中的非支配个体排序进行有益的探索。

参考文献：

[1]HORNBY G S， GLOBUS A， LINDEN D S， et al. Automated antenna design with evolutionary algorithms[C]// SPACE Conferences and Exposition. San Jose： AIAA， 2006： 19-21.

[2]WEISE T， PODLICH A， REINHARD K， et al. Evolutionary Freight Transportation Planning[M]. Berlin： Springer， 2009： 768-777.

[3]HOVESTADT L， DANAHER T. Beyond the Grid： Architecture and Information Technology Applications of a Digital Architectonic[M]. Boston： Birkhauser， 2010：273-274.

[4]公茂果， 焦李成， 杨咚咚， 等. 进化多目标优化算法研究[J]. 软件学报， 2009， 20（2）：271-289.（GONG M G， JIAO L C， YANG D D， et al. Research on evolutionary multiobjective optimization algorithms[J]. Journal of Software， 2009， 20（2）：271-289.）

[5]FONSECA C M， FLEMING P J. Genetic algorithms for multiobjective optimization： formulation discussion and generalization[C]// Proceedings of the 5th International Conference on Genetic Algorithms. San Francisco， CA： Morgan Kaufmann Publishers Inc.， 1993： 416-423.

[6]SRINIVAS N， DEB K. Multiobjective optimization using nondominated sorting in genetic algorithms[J]. Evolutionary Computation， 1994， 2（3）： 221-248.

[7]HORN J， NAFPLIOTIS N， GOLDBERG D E. A niched Pareto genetic algorithm for multiobjective optimization[C]// Proceedings of the 1st IEEE Conference on Evolutionary Computation. Piscataway， NJ： IEEE， 1994： 82-87.

[8]ZITZLER E， THIELE L. Multiobjective evolutionary algorithms： a comparative case study and the strength Pareto approach [J]. IEEE Transactions on Evolutionary Computation， 1999， 3（4）： 257-271.

[9]ZITZLER E， LAUMANNS M， THIELE L. SPEA2： improving the strength Pareto evolutionary algorithm[C]// Evolutionary Methods for Design， Optimization and Control with Applications to Industrial Problems. Berlin： SpringerVerlag， 2002： 95-100.

[10]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.

[11]BROCKHOFF D， ZITZLER E. Are All Objectives Necessary on Dimensionality Reduction in Evolutionary Multiobjective Optimization[M]. Berlin： Springer， 2006， 4193：533-542.

[12]COELLO C A C， PULIDO G T， LECHUGA M S. Handling multiple objectives with particle swarm optimization [J]. IEEE Transactions on Evolutionary Computation， 2004， 8（3）： 256-279.

[13]罗辞勇，陈民铀，张聪誉. 采用循环拥挤排序策略的改进NSGAⅡ算法[J]. 控制与决策，2010，25（2）：227-231.（LUO C Y， CHEN M Y， ZHANG C Y. Improved NSGAⅡ algorithm with circular crowded sorting[J]. Control and Decision， 2010， 25（2）： 227-231.）

[14]FORTIN F A， PARIZEAU M. Revisiting the NSGAⅡ crowdingdistance computation[C]// Proceedings of the 15th Annual Conference on Genetic and Evolutionary Computation. New York： ACM， 2013： 623-630.

[15]MOHAPATRA P， ROY S. APNSGAⅡ： an evolutionary multiobjective optimization algorithm using averagepointbased NSGAⅡ[C]// Proceedings of 4th International Conference on Soft Computing for Problem Solving. Berlin： Springer， 2015： 565-575.

[16]PATEL G K， DABHI V K， PRAJAPATI H B. Study and analysis of particle swarm optimization for improving partition clustering[C]// Proceedings of the 2015 IEEE International Conference on Advances in Computer Engineering and Applications. Piscataway， NJ： IEEE， 2015： 218-225.

[17]LI Q， LIU X. A Kmedoids Clustering Algorithm with Initial Centers Optimized by a P System[M]. Berlin： Springer International Publishing， 2015： 488-500.

[18]ZITZLER E， DEB K， THIELE L. Comparison of multiobjective evolutionary algorithms： empirical results[J]. IEEE Transactions on Evolutionary Computation， 2000， 8（2）： 173-195.

[19]SCHAFER J D. Multiobjective optimization with vector evaluated genetic algorithm[C]// Proceedings of the 1st International Conference on Genetic Algorithms. Hillsdale， NJ： L. Erlbaum Associates Inc.， 1985： 93-100.

[20]KUKKONEN S， LAMPINEN J. Performance assessment of generalized differential evolution 3 with a given set of constrained multiobjective test problems[C]// Proceedings of the 11th Conference on Congress on Evolutionary Computation. Piscataway， NJ： IEEE， 2009：1943-1950.

[21]胡旺，YEN G G，张鑫. 基于Pareto熵的多目标粒子群优化算法[J]. 软件学报，2014，25（5）：1025-1050.（HU W， YEN G G， ZHANG X. Multiobjective particle swarm optimization based on Pareto entropy[J].Journal of Software， 2014， 25（5）： 1025-1050.）