基于极值点搜索和非支配排序的高维多目标优化算法

朱春阳，郭晓彤，孙浩然，孙文学

1(南京航空航天大学 计算机科学与技术学院，南京 210016) 2(西安建筑科技大学 管理学院，西安 710055)

1 引 言

在工程技术，经济，管理，军事和系统工程领域大量的存在着这样一类问题，他们往往可以归纳为在某种约束条件下同时使多个目标达到最优，这种含有多个目标的最优化问题被称为多目标优化问题，多目标优化问题中当需要被优化的目标数在4个以及以上的时候被称为高维多目标优化问题.

不失一般性，以最小化问题为例，一个具有n个决策变量，m个目标函数的多目标优化问题(Multi-objective Optimization Problems，MOPs)可表述为：

minimizeF(x)=(f1(x)，.…，fm(x))Tsubject tox∈Ω

(1)

其中，x∈Ω是决策向量，Ω是决策空间，F：Ω→Rm由m个实值目标函数组成，Rm是目标空间，可行目标集被定义为集合{F(x)|x∈Ω}.

使u，v∈Rm，对于任意的i∈{1，…，m}，满足ui≤vi，并且在至少一个目标上满足uj

定义1.理想点(Z*)定义为：

(2)

定义2.Pareto极值点(B)定义为：

(3)

定义3.边界解(PCS)：对于一个具有m个目标的多目标优化问题，对于Pareto最优解集而言，如果一个解能够满足最小化k个目标(k< m)，并且最大化其他目标，那么，这样的解被称为边界解.

Pareto最优解集代表了一种资源的配置状态，在该种状态下，无法通过改变资源的配置状态达到改善某一个目标的同时而不损害其它的目标.

由于Pareto最优解集不是单一解而是一组解集，而另一方面，进化算法是基于群体智能的启发式搜索算法，这就决定了利用进化算法求解多目标优化问题具有天然的优势.因此在过去的十年里，利用进化算法求解多目标优化问题一直被看作是近似Pareto最优解集的一种主要方法.

在进化多目标优化算法中，解的选择对算法的性能有很大的影响，通常我们希望能够得到具有以下性质的一组解集：

1)收敛性：所得到的解集能够尽可能近的靠近Pareto前沿.

2)多样性：所得到的解集能够尽可能均匀的分布在整个Pareto前沿上.

基于对解集收敛性和多样性的综合考量，一批性能优异的多目标优化算法被提出[1-3].这些算法在2，3个目标的优化问题中已经取得了令人满意的表现.但是，当处理高维多目标优化问题时，由于非支配排序的选择压力丧失[4]；所需要的种群规模与计算复杂度的冲突加剧[4];交叉变异效率在高维多目标空间严重降低[5]等原因，使得利用进化算法处理高维多目标优化问题面临很大的挑战.

在过去的几年里，很多研究工作围绕着以上的挑战进行开展并设计出了很多具有很高性能的高维多目标优化算法，比如：

1)直接通过修改非支配关系来加强算法在高维空间的选择压力，这一类算法包括：偏好排序[6]，基于格子的支配[7]，基于模糊的支配[8]等.

2)利用适应度评估机制来改善多目标优化算法的性能，这类算法具体细分为基于度量指标的算法[3]和基于分解的算法[9]，前者往往通过度量指标来指导算法的演化过程从而达到收敛性和多样性的平衡，后者则是将一个多目标优化问题通过聚合函数的方式分解成一组单目标优化子问题，然后子问题之间按照一种基于群体的协作的方式进行优化.

3)将基于分解和基于非支配关系结合起来的混合多目标优化算法[10，11]，这类算法旨在结合基于分解和基于非支配关系的优点来求解高维多目标优化问题.

本文在第二章首先对基于支配的多目标优化算法NSGA-II进行分析，之后详细介绍提出的基于极值点搜索和非支配排序的高维多目标优化算法.第三章介绍了本文中使用的基准测试问题集、评价算法性能指标以及相关实验参数的设置细节.在第四章我们将改进后的算法与6个当前领域主流算法在标准测试问题集上进行比较，并就算法的各个功能模块的有效性进行实验论证.

2 多目标优化算法的设计

2.1 对NSGA-II的分析及改进方案

快速非支配排序算法(NSGA-II)[1]采用模拟二进制交叉(SBX)和多项式变异(polynomial mutation)来产生新解，并将新解和父代解合并到一起组成混合种群，混合种群根据支配关系被划分到不同的层(F1，F2，…，FL)，分层后的种群将按照由低到高的顺序一层一层的保存到精英种群中，直到Fi层，i≤L，Fi层是所能保存的精英解中的最高的一层，由于种群规模限制，不能将Fi层的所有解都保存到精英种群中，这时，算法采用拥挤度距离这一多样性度量策略，将Fi层中多样性较好的一部分解保存到精英种群中，从而完成算法的一次迭代.NSGA-II正是采用以上策略，通过反复的迭代，直至获得一组近似的Pareto最优解集.

实践证明NSGA-II算法在处理2、3个目标的优化问题时能够表现出较好的性能和鲁棒性，但是在处理高维多目标优化问题时仍存在一些不足.具体表现在以下几个方面：

1.由于在高维空间中解与解之间几乎都是相互非支配的，这导致仅依靠非支配排序作为选择性压力的NSGA-II的收敛效率急速下降.

2.由于在高维空间中，解与解之间的距离很远，生成的新解距离父代解很远，这会导致基于群体智能的生成新解的有效性降低，即交叉和变异操作的效率降低，无法高效的产生优良的子代解供算法选择.

基于此，我们提出了基于极值点搜索和非支配排序的高维多目标优化算法.所谓极值点搜索，即在算法运行的第一阶段，通过极值点搜索算法找到优化问题的近似极值点，从而大幅度的减小目标域的搜索空间.在找到近似的极值点后，算法进入第二阶段，在此阶段通过近似的极值点将目标空间进行划分，空间划分后，只对内部空间的解采用非支配排序和拥挤度距离选择精英解，以此来提升算法的收敛效率.值得注意的是空间划分后，内部空间的解与解之间的距离更近，这使得非支配排序的选择性压力在高维空间上能够得到大幅度的提升，由于解与解之间的距离变近，交叉变异操作的效率能够得到提高.从而提升算法在处理高维多目标问题的性能.

2.2 改进的多目标优化算法

在本节将详细介绍提出的基于极值点搜索和非支配排序的高维多目标优化算法NSGA-II-BS，其中BS表示极值点B和Search.NSGA-II-BS的算法流程如图1所示.

图1 算法流程图Fig.1 Algorithm flow chart

其中gmax表示NSGA-II-BS算法的最大迭代次数，Δg、gmax1作为极值点搜索算法是否终止的判定条件，将在2.2.3小节中详细介绍.

2.2.1 初始化

在初始化阶段，通过在决策空间中随机采样的方法初始化生成含有N个个体的种群P.

1)利用式(2)对理想点进行初始化.

2)利用式(3)对极值点进行初始化.

3)初始化m条参考线：

(4)

对于第i条参考线γi={0，1，…，0}T，其中第i个元素为1其他的元素均为为0.

4)初始化判定条件：Δg=1×106.

2.2.2 极值点搜索算法

在本小节，我们将详细阐述极值点搜索算法.Pareto极值点是由Pareto前沿上的各个目标的最大值所组成的向量，极值点只存在于目标空间.因此不能直接在决策空间中搜索，基于以上原因，我们采用边界解搜索的策略，通过边界解来间接搜索Pareto极值点，从而达到搜索极值点的目的.算法流程如下：

输入：

①初始种群：P.

Step1.生成新解

将初始解集P采用差分进化(Differential Evolution，DE)[9]和多项式变异(Polynomial Mutation)[1]操作生成新解，重复以上步骤直至N个新解全部生成，并与父代解组成混合种群Q.

Step2.划分子种群

根据到相应参考线γi的垂直距离，均匀的划分为m个子种群SubPi，i∈{1，…，m}，每个子种群SubPi包含2×N/m个距离参考线γi垂直距离最近的解.

Step3.选择解

①对于每一个子种群SubPi

1)通过比较非支配关系，将子种群中的非支配解集P1和被支配解集P2分离.

2)如果|P1|≥N/m，那么P1中距离相关联的参考线γi垂直距离最近的前N/m将会被保存下来.

3)如果|P1|

②合并每个子种群中保留下来的解组成精英解集P.

Step4.更新极值点将各个子种群中距离相应参考线γi，i∈{1，…，m}垂直距离最近的非支配解组成解集，并利用式(3)对极值点进行更新.

Step5.终止条件

如果满足终止条件，则终止算法并输出P和极值点B；否则，返回Step 1.

2.2.3 极值点搜索算法的终止条件

ΔgNSGA-II-BS首先采用了极值点搜索算法搜索优化问题的极值点.之后采用基于近似极值点的非支配排序算法来获得一组相互非支配的精英解.显然，给极值点搜索算法分配固定的计算资源是不合理的，因为我们无法预知算法要处理的优化问题的极值点的搜索的难易程度，因此，我们提出自适应的切换机制，通过判断是否搜索到近似的极值点来决定是否切终止极值点搜索.Δg表示的是在第g代的判定值，它表示的是极值点与前200代相比的最大相对变化率，即每隔200代计算一次Δg的值，计算公式为：

(5)

当Δg小于一个预先设定的值0.001，这就意味着极值点B的变化率已经非常小，并认定，已经找到了近似的极值点B，此时算法将终止极值点搜索.gmax1表示极值点搜索算法的最大迭代数，作为补充，一旦自适应机制失效，极值点搜索算法最多运行gmax1代后自动切换到算法的下一步.

图2 相关概念在2个目标空间的示意图Fig.2 Schematic diagram for relevant concepts in the two objective space

2.2.4 基于近似极值点的非支配排序算法

本小节将以NSGA-II为算法框架，并结合近似的极值点，提出基于近似极值点的非支配排序算法，算法流程如下：

输入：

①极值点搜索算法所保留的种群：P.

②近似的极值点：B.

Step1.生成新解

从输入种群P中随机选择两个解，然后对这两个解进行模拟二进制交叉(SBX)和多项式变异(polynomial mutation)操作生成新解y，重复以上步骤直至N个新解全部生成，并与父代解组成混合种群Q.

Step2.选择解

①利用近似的极值点B对目标空间进行空间划分，即x，x∈Q，如果∀i，i∈{1，…，m}，满足fi(x)≤Bi，这类解所组成的解集被标记为内部空间解集Qin.对于x，x∈Q，如果∃i，i∈{1，…，m}，使得fi(x)>Bi，那这类解所组成的解集被标记为外部空间解集Qout.

②如果|Qin|≤N，Qin将全部保留进P，在Qout中距离理想点Z*欧几里得距离最近的N-|Qin|个解将会保留进P.

③如果|Qin|>N，对于Qin中的解，将采用NSGA-II的非支配排序和拥挤度选择策略，挑选出排名前N的个体保存进P.

Step3.终止条件

如果满足终止代数条件，则终止算法并输出P；否则，返回Step 1.

3 实验设置

本章将介绍算法对比实验中使用到的基准测试问题，算法性能的度量指标以及相关对比算法的参数设置.

3.1 测试问题

在本文实验中采用目前演化计算领域主流的高维多目标测试问题集DTLZ[12]，该组测试问题的主要特点是可以根据需求拓展不同的优化目标数.

本文实验中我们将目标数设置为5，6， 8.对于决策变量数n，我们将按照n=m+r-1的形式进行设置，其中m∈{5，6，8}，对于DTLZ1我们将r设置为5，对于DTLZ2-6我们将r设置为10，对于DTLZ7我们将r设置为20.

3.2 性能指标

在本文实验中，实验结果的性能度量指标采用反向迭代距离(Inverted Generational Distance，IGD)[13].IGD是指计算真实Pareto前沿上的点到求出的近似Pareto前沿的最小距离的平均值.式(6)中P*是真实Pareto前沿，P是算法近似的Pareto前沿，IGD定义为：

(6)

其中，dist(v，P)表示的是v到P中最近点的欧几里得距离.

通过式(6)可以看出，优化算法得到的近似Pareto前沿越接近真实Pareto前沿，并且在整个前沿上分布越均匀，那么计算出的IGD值就会越小.反之，距离Pareto前沿越远，且分布越不均匀，得到的IGD值就越大.因此，IGD度量指标可以有效地综合评估种群的收敛性和多样性.

3.3 参数设置

实验中将会用到NSGA-II以及另外6种算法：MOEADD[11]，MOEA/D-DE[9]，NSGA-III[10]，MOEA-R&D[14]，MOEA/D-SAS[15]和GrEA[7].

其中MOEA/D-DE和MOEA/D-SAS采用切比雪夫聚合函数，其他对比算法参数均按照相应的参考文献进行设置.所有的对比算法的种群规模设置在5个目标时为210，在6个目标时GrEA、MOEA-R&D和NSGA-II-BS为180，其他对比算法的种群规模设置为182.在8个目标时MOEA-R&D和NSGA-II-BS的种群规模设置为160，其他对比算法的种群规模设置为156.所有算法每次运行都将进行300000次的函数评估，并独立运行30次.对于NSGA-II-BS，交叉分布指数和多项式变异分布指数均为1，最大变异概率为0.1，Pm=1/n(n为决策变量个数)，gmax1=gmax-50.

4 实验结果与分析

本章第一小节将进行一组算法对比实验，以探究NSGA-II-BS的算法性能.接下来两个小节将通过实验来论证算法的各个功能模块的有效性.

4.1 与当前主流的的高维多目标优化算法的比较

NSGA-II-BS与NSGA-II 以及6个当前主流的高维多目标优化算法进行比较，这些算法涵盖了基于非支配排序策略，基于分解的策略，基于格子支配的策略，基于非支配排序和分解混合的策略等.我们将算法运行30次所取得的IGD平均值进行统计，实验结果如表1所示，通过实验我们发现MOEA/DD在处理DTLZ1，DTLZ2，DTLZ3和DTLZ4这类Pareto前沿是规则流型的优化问题时表现出了较高的性能，本文采用Wilcoxon秩和检验对所得数据进行显著性测试.+和-分别表示在相应测试问题上NSGA-II-BS显著优于或劣于该算法，如无则表示该算法与NSGA-II-BS相比无显著性差异,粗体表示在相应测试问题上该算法IGD均值最小.

表1 NSGA-II-BS与6个主流高维多目标优化算法在IGD均值指标上的对比结果Table 1 Comparison results of NSGA-II-BS with six classical algorithms for IGD mean values

但是，这类基于在目标空间均匀分布权重向量(参考线)来保证收敛性和多样性的优化算法在处理Pareto前沿是不规则的流型的优化问题时还能保持这样的高性能吗？通过进一步的实验我们发现，NSGA-II-BS在7个问题上对比其他的算法具有显著性的优势，值得注意的是，DTLZ5，DTLZ6和DTLZ7具有不规则的Pareto前沿，这也就意味着基于在目标空间均匀分布权重向量(参考线)来保证收敛性和多样性的算法在处理这类问题上的性能大大降低[16]，与此同时，我们通过实验结果发现，我们的NSGA-II-BS在处理这类不规则的优化问题上仍然具有很好的性能，并优于对比的其他算法，这表明，NSGA-II-BS在处理不同类型的高维多目标优化问题时具有很好的算法鲁棒性.

4.2 极值点搜索算法终止条件的有效性验证

在2.2.3节中提出极值点搜索算法的终止条件，在本节将通过实验来论证极值点搜索算法终止的有效性，图3展示了算法在5个目标的DTLZ测试问题的计算资源的分配，其中黑色柱体表示极值点搜索算法的计算资源，白色柱体表示基于近似极值点的非支配排序算法的计算资源，从图中可以观察到，计算资源的分配在不同的测试问题上表现出不同的偏好，从图中观察可知，对于DTLZ1和DTLZ3测试问题，NSGA-II-BS分配更多的计算资源用于极值点的搜索，根据文献[12]可知，DTLZ1和DTLZ3属于收敛非常困难的测试问题，这表明，终止条件能够有效的根据测试问题的收敛难易程度来自适应的控制极值点搜索算法的终止.

图3 计算资源分配示意图Fig.3 Distribution of computing resources

4.3 极值点搜索算法的有效性验证

在NSGA-II-BS中，极值点搜索算法具有很重要的作用，如果极值点不能有效的被搜索到，对算法的性能将会产生一定的影响.本小节将通过实验来验证极值点搜索算法的有效性，我们将NSGAII-BS算法在4个目标DTLZ测试问题上搜索到的极值点与真实的Pareto前沿的极值点进行比较，对比结果如表2所示，比较发现，我们的极值点搜索算法能够有效的近似出真实的极值点，值得注意的是DTLZ5，DTLZ6属于退化类型的测试问题，具有不规则的Pareto前沿，实验发现，我们的算法能够有效的搜索到这类优化问题的极值点，这也证明我们的极值点搜索算法具有很好的鲁棒性.

表2 极值点对比Table 2 Comparison for nadir points

由于空间限制，以上数据只保留到小数点后一位

本文采用Wilcoxon秩和检验对所得数据进行显著性测试.+和-分别表示在相应测试问题上NSGA-II-BS显著优于或劣于该算法，如无则表示该算法与NSGA-II-BS相比无显著性差异，粗体表示在相应测试问题上该算法IGD均值最小由于空间限制，以上数据只保留到小数点后一位

5 结束语

本文所设计的基于极值点搜索和非支配排序的高维多目标优化算法充分继承了原始NSGA-II算法优良的鲁棒性的优点，并通过提出的极值点搜索算法来大大的缩小了目标搜索空间，提升了非支配排序的选择性压力，并通过缩小的搜索空间，在一定程度上缓解了原始NSGA-II在处理高维多目标优化问题时由于解与解之间距离很远而导致的模拟二进制交叉和多项式变异效率降低的缺点.算法对比实验中，NSGA-II-BS显示出了较好的性能，尤其是处理Pareto前沿不规则的测试问题时更是展现了其优异的算法鲁棒性.在接下来的工作中，我们将考虑对NSGA-II-BS进行扩展以探究其在处理高维含有约束的优化问题和高维离散优化问题上的性能.

[1] Deb K，Pratap A，Agarwal S，et al.A fast and elitist mul-tiobjective genetic algorithm：NSGA-II[J].Evolutionary Computation，IEEE Transactions on，2002，6(2)：182-197.

[2] Zitzler E，Laumanns M，Thiele L.SPEA2：improving the strength pareto evolutionary algorithm for multiobjective optimization[C].Evolutionary Methods for Design，Optimization and Control with Applications To Industrial Problems，Proceedings of the Eurogen'2001，Athens，Greece，September，2001.

[3] Bader J，Zitzler E.HypE：an algorithm for fast hypervolume-based many-objective optimization[J].Evolutionary Computation，2011，19(1)：45-76.

[4] Li B，Li J，Tang K，et al.Many-objective evolutionary algorithms：a survey[J].Acm Computing Surveys，2015，48(1)：1-35.

[5] Deb K，Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach，Part I：solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation，2014，18(4)：577-601.

[6] Pierro F D，Khu S T，Savic D A.An investigation on preference order ranking scheme for multiobjective evolutionary optimization[J].Evolutionary Computation IEEE Transactions on，2007，11(1)：17-45.

[7] Yang S，Li M，Liu X，et al.A grid-based evolutionary algorithm for many-objective optimization[J].IEEE Transactions on Evolutionary Computation，2013，17(5)：721-736.

[8] He Z，Yen G G，Zhang J.Fuzzy-based pareto optimality for many-objective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation，2014，18(2)：269-285.

[9] Li H，Zhang Q.Multiobjective optimization problems with complicated pareto sets，MOEA/D and NSGA-II[J].IEEE Transactions on Evolutionary Computation，2009，13(2)：284-302.

[10] Deb K，Jain H.An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach，Part I：solving problems with box constraints[J].IEEE Transactions on Evolutionary Computation，2014，18(4)：577-601.

[11] Li K，Deb K，Zhang Q，et al.An evolutionary many-objective optimization algorithm based on dominance and decomposition[J].Evolutionary Computation IEEE Transactions on，2015，19(5)：694-716.

[12] Kalyanmoy Deb，Lothar Thiele，Marco Laumanns，et al.Scalable test problems for evolutionary multiobjective optimization[M].Evolutionary Multiobjective Optimization，2006：105-145.

[13] Bosman P A N，Thierens D.The balance between proximity and diversity in multiobjective evolutionary algorithms[J].IEEE Transactions on Evolutionary Computation，2003，7(2)：174-188.

[14] He Z，Yen G G.Many-objective evolutionary algorithm：objective space reduction+diversity improvement[J].IEEE Transactions on Evolutionary Computation，2015，20(1)：145-160.

[15] Cai X，Yang Z，Fan Z，et al.Decomposition-based-sorting and angle-based-selection for evolutionary multiobjective and many-objective optimization[J].IEEE Transactions on Cybernetics，2016,47(9)：2824-2837.

[16] Ishibuchi H，Yu S，Masuda H，et al.Performance of decomposition-based many-objective algorithms strongly depends on pareto front shapes[J].IEEE Transaction on Evolutionary Computation,2017,21(2)：169-190.