基于最小距离和聚合策略的分解多目标进化算法

李二超，李康伟

（兰州理工大学电气工程与信息工程学院，兰州 730050）

0 引言

进化算法是一种基于群体智能的启发式优化算法，它通过对生物进化的繁殖、变异、重组和选择等过程的模拟来达到优化的效果。这种算法对于求解多目标优化问题具有很好的效果，基于进化算法，研究者们相继提出了很多解决不同多目标优化问题（Many-objective Optimization Problem,MOP）［1］的优化算法。

以非支配排序遗传算法（Nondominated Sorting Genetic Algorithm，NSGA）［2］为代表的第一代进化算法，基于Pareto 支配关系以及多样性保留策略对个体进行选择，该算法在选择解之前先将种群根据支配关系进行分层，以便能够有更大的机会选择出更好的个体遗传到下一代，并且在选择解的过程中加入了适应度共享策略，保持了解的多样性。但是，NSGA无法很好地保证高质量的解遗传到下一代，而使一些好的解丢失，并且需要指定共享参数使其依赖于共享的概念。因此，在非支配排序遗传算法（NSGA）、向量评估遗传算法（Vector Evaluated Genetic Algorithm，VEGA）［3］、小生境Pareto 遗传算法（Niched Pareto Genetic Algorithm，NPGA）［4］等基础上引入精英保留策略提出了第二代进化算法，例如强度帕累托进化算法（Strength Pareto Evolutionary Algorithm，SPEA）［5］、改进的强度帕累托进化算法（Strength Pareto Evolutionary Algorithm Two，SPEA2）［6］、基于非支配排序的多目标进化算法（Nondominated Sorting Genetic Algorithm Ⅱ，NSGA-Ⅱ）［7］等。第二代进化算法的代表算法NSGA-Ⅱ与NSGA 类似，首先将整个种群根据Pareto 非支配排序进行分层，其中前一层的解支配后一层的解，而同层的解之间互不支配；在选择解时使用精英解保留策略逐层选择解以保证收敛性，在最后一层采用拥挤距离的选择方法以保证解的多样性。Cai 等［8］为了评估超多目标优化问题的最优前沿逼近真实前沿的程度，提出了一种基于参考向量的多样性指标（Diversity Indicator based on Reference vectors，DIR）。在DIR 中，首先生成一组均匀分布的参考向量，然后根据每个解关联的参考向量数量计算解的覆盖率，最后由所有解的覆盖率的标准差决定解的多样性。DIR 的值越小，多样性越好。将DIR 与NSGA-Ⅱ结合提出了DIR 增强的NSGA-Ⅱ（DIR-enhanced NSGA-Ⅱ，d-NSGA-Ⅱ）。这种第二代多目标进化算法得到的近似解不能均匀地分布在Pareto 最优前沿上。为了提高多样性，Deb 等［9］在NSGA-Ⅱ算法中引入参考点，将每个解关联在相应的参考向量上，提出了基于参考点的多目标遗传算法——NSGA-Ⅲ（Nondominated Sorting Genetic Algorithm Ⅲ），NSGA-Ⅲ为第三代进化算法的代表算法，它结合了非支配排序和基于参考点选择的优点，在保证收敛性的基础上提高了种群的分布性［10-11］。Bi 等［12］在NSGA-Ⅲ的基础上加入了基于消元算子的新的选择机制，提出了基于消元算子的加强NSGA-Ⅲ多目标进化算法——NSGA-Ⅲ-EO（NSGA-Ⅲbased on Elimination Operator），此算法增加了解的选择压力，并且提高了种群的多样性，但是上述这类基于支配的多目标进化算法在解决高维问题时由于各目标之间互不支配［13-14］，从而使选择压力降低。

基于参考点分解的多目标进化算法设置了一组参考向量，将目标空间分成若干个子区域来求解［15-16］。在算法当中每个子区域相当于一个子问题，通过对每个子种群同时进行优化来达到优化的效果。Zhang 等［17］通过将一个多目标优化问题分解成一组单目标优化问题，提出了一种基于分解的多目标进化算法（Multi-Objective Evolutionary Algorithm based on Decomposition，MOEA/D）。MOEA/D 算法在多目标优化问题尤其是高维多目标优化问题的收敛性和分布性等方面表现出了很好的效果，但是这种算法依然存在一些不足，比如在更新邻域子问题时会使其相邻子问题以外表现较好的解丢失，一个解同时出现在多个邻域当中而降低了解的多样性［18］，为此近年来许多学者在此算法上做了更多的研究。Liu 等［19］将均匀分布的参考向量分解成多个子空间，提出将一个多目标优化问题分解为若干个简单多目标子问题的多目标进化算法MOEA/D-M2M（MOEA/D based on decomposing MOP into a number of simple Multi-objective subproblems），其中，每个子空间对应一定大小的子种群，明显增加了解的多样性，而在解的选择过程中加入了Pareto 非支配排序方法使其均匀性有所下降。Li 等［20］将MOEA/D 与NSGA-Ⅱ结合，并且加入了差分进化（Differential Evolution，DE）的策略，另外，为了改善MOEA/D 的收敛性能，将局部搜索的思想融入MOEA/D 算法中，提出了解决复杂Pareto 解集的多目标进化算法——MOEA/D-DE（MOEA/D based on Differential Evolution），此算法使用聚合的方法选择解的过程虽然提高了解的均匀性但是多样性仍有不足。本文针对基于支配的多目标进化算法选择压力不高和均匀性差以及MOEA/D 多样性不足的问题，将均匀分布的参考向量根据角度分解成多个子空间来增加多样性，并且引入分两阶段基于最小距离和聚合方法选择解的策略（Two-stage selection strategy based on minimum Distance and Aggregation method，TDA）来平衡收敛性、多样性以及均匀性，提出了基于最小距离和聚合策略的分解多目标进化算法——MOEATDA。

1 问题描述

1.1 多目标优化

多目标优化问题的各目标之间相互冲突，并且随着目标个数的增加问题的复杂度越高，且越不易求解［21-22］。多目标优化通常用于生产调度和路径规划等实际问题当中，通常情况下优化过程不能使每个目标同时达到最优，而只能找到一组折中解来表示最优解，因此多目标优化的目的是如何用特定的算法来找到一组最优解。一般情况下，将两目标和三目标的问题称为多目标优化问题，将三目标以上的问题称为超多目标优化问题［23］。

多目标优化算法有最大化目标函数值和最小化目标函数值两种［24］，此处以最小化目标函数值为例：

其中：Ω代表决策空间，x=(x1，x2，…，xn)T∈Ω为n维决策变量；Θ代表目标空间，F(x) ∈Θ为M个目标函数；gi(x) ≤0(i=1，2，…，p)为p个不等式约束条件；hi(x)=0(i=1，2，…，q)为q个等式约束条件。以下是几个关于Pareto支配［25-26］的定义。

Pareto 支配对于任意两个解x，y∈Ω，若∀i∈{1，2，…，M} 有fi(x) ≤fi(y)，且∃j∈{1，2，…，M} 满足fj(x) ＜fj(y)，则x支配y（记为x≺y）。

Pareto 最优解 如果x∈Ω，不存在y∈Ω使得y≺x成立，则称x是Pareto最优解。

Pareto 最优解集 所有Pareto 最优解组成的解集，即P={x|x∈Ω∧¬∃y∈Ω，y≺x}。

Pareto 最优前沿 Pareto 最优解对应的目标函数值所组成的解集称为Pareto 最优前沿，即：PF={F(x)=(f1(x)，f2(x)，…，fM(x))T|x∈P}。

1.2 分解方法

在高维多目标优化算法中通常采用分解的方法将一个多目标优化问题分解为一组单目标问题进行求解，在本文中采用常用的基于惩罚的边界交叉法（Penalty-based Boundary Intersection，PBI）作为分解方法。第i个子问题定义如式（2）所示：

其中：θ为惩罚因子；‖ · ‖为L2范数；wi=(w1，w2，…，wm)T为分解后第i个子问题的权重向量。

1.3 权重向量的生成

在多目标优化算法中常用比较成熟的Das 和Dennis 系统方案［27］分解技术，在单位超平面上生成一组均匀分布的参考点，参考点的数目N和每维目标上的划分份数H的关系如式（3）所示：

其中m表示目标的维数，每一个参考向量wi(i=1，2，…，m)中的所有元素之和为1，并且每一维元素都取值于{0/H，1/H，…，H/H}。图1 表示3 目标问题参考点生成的示意图，r1、r2和r3为目标的维数。

图1 权重向量的生成Fig.1 Generation of weight vectors

2 本文算法

2.1 基本思想和主要框架

基于分解的多目标进化算法对于解的分布性有很大的提升，但是在使用聚合方法选择解的过程中降低了解的多样性。本文在基于参考向量分解技术的基础上根据角度将种群分解成一组特定大小的子种群，然后分两阶段在每个子种群内使用最小距离和聚合的方法选择解，这种分解技术可以有效提高种群的多样性。为了提高进化效率，在生成新解的过程中引入邻域，由于邻域中的最优解较为相似，所以在交叉变异的过程中能够促进进化，并且能够降低计算复杂度和提高局部搜索能力。

MOEA-TDA 主要分为5 个步骤：1）初始化种群Pop、权重向量集W；2）求解交叉邻域A；3）生成新解；4）根据角度分解子种群；5）根据TDA 策略选择解。MOEA-TDA 总框架伪代码如算法1所示。

算法1 MOEA-TDA总框架。

2.2 基于聚合的交叉邻域

在MOEA/D 中采用均匀分布的权重向量生成了不变的邻域，使得每个子问题都含有很多邻近的子问题，邻域内的子问题具有相似的最优解，所以对子问题的进化有一定的帮助。为了进一步提高算法的进化效率和局部搜索能力，提出基于聚合的邻域选择策略。在MOEA/D 等经典的多目标优化算法中每个子问题的邻域都是根据相邻的权重向量所确定的，这样使得进化前期每个权重向量所对应的子问题都不是离其最近的，所以在差分进化的过程当中局部搜索能力不高，本算法中提出的基于聚合的交叉邻域策略不再是将离权重向量的欧氏距离最近的个体作为邻域解，而是计算出权重向量与每个个体之间的PBI 值，然后选出PBI 值最小的T个解为邻域，这时邻域随着每一代的进化而发生自适应变化，有利于提高种群的局部搜索能力。伪代码如算法2所示。

算法2 基于聚合的交叉邻域。

在进化过程中对于每个权重向量除了原本与其相关联的最优解外，再找出与权重向量的PBI 值最小的两个解来进行差分进化。本文使用MOEA/D-DE 中提出的差分进化和多项式变异来产生子代个体，差分进化中有交叉、变异和选择几个主要的步骤，这种进化算法比较适合解决连续的优化问题，它能引导新解产生的方向。

2.3 基于角度的目标空间分解策略

首先在目标空间中产生N个均匀分布的参考向量，再根据参考向量将目标空间划分为指定数量的子区间，每一个子区间对应唯一的子种群，其中每一代的种群采用基于角度的划分方式将目标空间划分为N个子区间{Ω1，Ω2，…，ΩN} 以提高所求最优解集的多样性，对于每一个子区间：

基于角度的目标空间分解策略原理如图2 所示，如图选出任意两个权重向量wi和wj，在其周围分布着6 个不同的个体。在传统的多目标优化算法当中一般使用基于欧氏距离的计算方法找出与权重向量相关联的个体，例如，在分解过程中根据欧氏距离只会将x2和x4划分到同一区间内，这种分解方法使算法的收敛性有所提高，但是在维持多样性方面有一定的缺陷。而使用基于角度的目标空间的分解策略划分子空间时，在同一子区间内不仅包含x2和x4，而且也包含x6，这样在选择解的过程中会很大程度上维持种群的多样性。

图2 基于角度的目标空间的分解策略Fig.2 Decomposition strategy of target space based on angle

2.4 基于最小距离和聚合策略选择解

根据角度分解目标空间之后会使每个权重向量关联到一个子区间，因此可以在每个子区间内分两阶段基于最小距离和聚合策略单独选择解。由于在分解完子区间后有一些区间内关联不到个体，所以根据此策略选择解时，需要分以下两种情况进行：

1）子区间内有关联个体。

在这种情况下，当进化代数达到临界代数之前基于最小距离选择解，以提高算法的收敛性；当进化代数达到临界代数之后基于PBI 聚合的策略选择解，以提高解的分布性。在本算法中基于距离和基于角度选择解的临界代数是根据多次实验结果测试出来的。这里的距离由式（6）给出，公式当中的各参数与式（2）中相同。

2）子区间内无关联个体。

当子区间内无关联个体时，不能直接选择解，此时需要计算子代和父代组成的混合种群在该区间对应的权重向量下的PBI值，然后选择出混合种群中最小的PBI值所对应的个体作为该区间的最优解。两种情况下的算法流程如图3所示。

图3 基于最小距离和聚合策略的解选择Fig.3 Solution selection based on minimum distance and aggregation strategy

图3 中：gen为当前运行代数，Cgen为临界代数，nC为第i个子种群中的个体数，subpop（i）为第i个子种群，w（i）为第i个子种群相关联的权重向量，Mixpop为子代和父代的混合种群，Pop为最终输出种群。

3 实验和结果分析

为了测试MOEA-TDA 的性能，分别选取了ZDT［28］和DTLZ［29］系列测试问题。其中：ZDT 系列测试问题主要选取具有代表性的ZDT1～ZDT4 和ZDT6；而DTLZ 系列测试问题选取DTLZ1～DTLZ5，主要测试算法在高维情况下的性能。

ZDT1 和ZDT4 为连续凸型测试函数，但前者的偏约束个数大于后者；ZDT2为连续凹型测试函数；而ZDT3为前沿断续的测试函数；以上均为基因型均匀的测试函数。ZDT6为连续凸型但基因型非均匀的测试函数。对于DTLZ1，目标函数值位于一个线性超平面上，并且难以收敛到最优解；DTLZ2 的Pareto 最优解集位于单位球的第一象限，它可用于探测一个MOEA 对高维目标的进化搜索能力；DTLZ3 不仅包含局部Pareto 最优解集还包含一个全局Pareto 最优解集，可测试全局收敛能力；DTLZ4 测试MOEA 维持一个良好的分布解集的能力［30］；DTLZ5 的Pareto 最优解集聚集于一条曲线上，用于测试MOEA 收敛到一条曲线的能力。本文主要研究收敛性和多样性问题，因此使用以上测试函数进行实验。

为了验证可行性，本算法与4 种经典的算法MOEA/D、MOEA/D-DE、NSGA-Ⅲ和基于网格的多目标进化算法GrEA［31］进行了比较。

3.1 参数设置

为了公平比较，所有算法的种群规模和运行代数均保持一致，对于GrEA算法，由于自身的机制限制，将种群规模设置为4的倍数。各测试问题的参数设置如表1所示。

表1 DTLZ测试问题的参数设置Tab.1 Parameter setting of DTLZ test problem

对于3、6、8 以及10 维问题，所有算法的种群规模分别设置为300、252、120 以及220；而对于5 维问题，GrEA 算法的种群规模设置为212，其他算法设置为210，GrEA算法的div设为10。ZDT 系列测试问题的迭代次数设为100，DTLZ 系列测试问题的迭代次数设为1 000，交叉指数mu=30，变异指数mum=20，变异概率Pm=1/D，交叉概率CR=1.0，惩罚因子θ=5，差分进化参数F=0.5，所有算法在每个测试函数上独立运行20次。

3.2 性能指标

为了能够更精确地比较算法的性能优劣，通常需要做定量的对比，在本文中使用较为广泛的综合性能指标反世代距离（Inverted Generational Distance，IGD）［32-33］和超体积（HyperVolume，HV）［34］作为评估指标。

反世代距离（IGD）兼顾了近似解集的收敛性和多样性，其通过真实前沿上均匀采样的一组参考点与求得的近似最优解集之间的平均距离来计算。P*为Pareto 真实前沿上均匀采样得到的一组参考点，P为使用优化算法求出的一组近似最优解集。则IGD指标的计算如式（7）所示：

其中：|P*|表示P*的基数，即解集P*中解的个数；dist(v，P)表示v∈P*到其最近解的欧氏距离。若IGD 值越小，则所求得的近似最优解集的性能越好，即更接近于真实前沿PF。

另一个指标超体积HV 也用来同时评估所得近似最优解集的收敛性和多样性，其不需要真实Pareto 真实前沿而通过在目标空间设定一个参考点来求得。假设ur=为目标空间中被所有的Pareto 最优解支配的一个参考点，则超体积表示目标空间中以ur为边界被最优解集P中的解所支配的区域的大小，HV 指标的计算如式（8）所示：

其中，VOL(·)表示勒贝格计量。HV 越大说明最优前沿P的性能越好。

3.3 实验结果分析

为了更客观地显示出所提算法的优越性，分别对所有算法的IGD 和HV 指标独立计算20 次，所有算法在ZDT 测试问题下的IGD 和HV 指标的均值和标准差如表2 所示，在DTLZ测试问题下的IGD 和HV 指标均值和标准差分别如表3～4 所示，并且在表中用粗体标出了最好的值。

表2 5种算法在ZDT测试集上的平均IGD和HV均值以及标准差Tab.2 Average IGD，average HV mean and standard deviation of five algorithms on DTLZ test set

表3 5种算法在DTLZ测试集上的平均IGD均值及标准差Tab.3 Average IGD mean and standard deviation of five algorithms on DTLZ test set

对于二维多目标优化问题，由表2中的反世代距离（IGD）和超体积（HV）可以看出，MOEA-TDA 与其他4 种经典算法相比在收敛性和多样性方面有很大的提升，尤其对于ZDT4测试问题，其效果较为显著，但是对于ZDT1 测试问题效果没有ZDT4 效果明显，这说明MOEA-TDA 对于解决偏约束个数较小的优化问题性能有很大的提升，这是由于第一阶段基于最小距离的选择策略能够有效提高解集的收敛能力。对于ZDT2，所提算法的效果优于其他算法，因此该算法对连续凹型测试问题也同样适用。对于非均匀的ZDT6，该算法也均优于其他对比算法，说明该算法能够有效地解决非均匀系列的测试函数。但是对于ZDT3这类不连续的测试问题而言，尽管该算法能够提高收敛性和多样性，但是它不能完全收敛到真实前沿上。因为在该算法中生成的权重向量都是均匀分布的，在利用角度分解目标空间的过程中会使前沿断续地方的权重向量也会参与到分解目标空间的过程中，从而使这些权重向量也匹配到解，因此对于前沿断续的问题效果并不好。从标准差可以看出，算法的鲁棒性也有所提高，所以算法MOEA-TDA在ZDT测试集上明显优于其他4类经典算法。

对于DTLZ 系列测试函数，使用性能指标反世代距离IGD和超体积HV 表示其结果如表3 和表4。同样，由表3 可以看出，算法MOEA-TDA 在高维问题上也有较大的优势，对于DTLZ1 测试问题而言，虽然收敛性提升较小，而且相对于NSGA-Ⅲ和GrEA 最优解集分布更加均匀，但是MOEA/D-DE对DTLZ1 的8、10 目标效果比MOEA-TDA 好。说明该算法对难以收敛到最优解集的测试问题性能有一定的提升，但是此策略对于DTLZ1 问题随着目标维数的增加效果逐渐减弱。由表3～4 可以看出，对于DTLZ2，不管是高维问题还是低维问题MOEA-TDA 的优化效果均优于其他算法，说明基于最小距离和聚合策略的选择方法对于高维目标的进化搜索能力有较大的提升。对于同时包含局部Pareto 最优解集和全局Pareto最优解集的DTLZ3 测试函数，从性能指标可以看出，维数较低时优化效果明显，但是维数增加到10 维时优化效果显著降低，而MOEA/D-DE 效果较好，说明当维数较低时MOEA-TDA能有效提高全局搜索能力，维数较高时MOEA/D-DE的全局搜索能力较强。DTLZ4 主要测试解集的分布能力，在此算法中基于角度的目标空间分解策略主要用于提高最优解集的分布性，从实验结果看出该算法在目标数较低时效果较好，此外GrEA 算法也能够很好地保持解集的分布性，因为在GrEA 算法中使用到了基于网格的策略，对分布性也有较大的提升。而对于DTLZ5 而言实验MOEA-TDA 结果较差，这是由于使用了基于角度分解目标空间的策略，使其在高维空间中很难保证前沿退化问题的最优解集聚集到真实前沿上。

表4 5种算法在DTLZ测试集上的平均HV及标准差Tab.4 Average HV and standard deviation of five algorithms on DTLZ test set

NSGA-Ⅲ为非常经典的多目标优化算法，它结合了非支配排序和基于参考点选择的优点，在保证收敛性的基础上提高了种群的多样性，MOEA/D 和MOEA/D-DE 通常使用加权和法、Tchebycheff 法和PBI 的聚合方法，PBI 的聚合方法比Tchebycheff 法得到的最优解集更加均匀，主要用来求解非凸优化问题，在本文中为了与提出的算法保持一致采用PBI 的聚合方法。从实验结果来看，与其他几个对比算法相比，MOEA/D-DE 的结果较优，这是由于加入差分进化的原因。而基于网格的多目标优化算法GrEA 在收敛性和多样性上表现也较为突出，不仅更加适合处理复杂的优化问题，而且对Pareto 前沿的形状有很强的鲁棒性。MOEA-TDA 在基于权重向量分解的基础上加入了基于角度的分解策略，进一步提高了种群的多样性并且保证了分布性；为了提高收敛性，在算法的前期使用基于最小距离的选择策略。综上，根据实验结果得出，提出的MOEA-TDA 不仅能够提高收敛性和多样性，并且能够提高维持一个良好分布解集的能力。

4 结语

本文提出了一种分两阶段基于最小距离和聚合策略选择解的多目标进化算法——MOEA-TDA。首先，使用根据角度分解子空间的策略，有效地提高了解的多样性；其次，使用基于聚合的交叉邻域，提高了局部搜索能力；最后，分两阶段在每个子种群中分别根据最小距离和PBI 聚合策略选择解，提高了解的收敛性。从实验结果可以得出，所提出的MOEATDA 与其他4 种经典的多目标优化算法相比在本文中的测试问题上综合性能都有明显的提高。