刘中锋，李浩君

（1.宁波广播电视大学网络传播学院，宁波315016；2.浙江工业大学教育科学与技术学院，杭州310023）

0 引言

高维多目标优化问题（MaOPs）具有三个以上冲突目标，广泛存在于现实应用中，例如工程设计[1]、空中交通控制[2]、地下水管理[3]和分子设计[4]等。被用于解决多目标优化问题（MOPs）的多目标进化算法不能很好地优化MaOPs问题[5-9]，主要原因包括两个，第一个原因是收敛压力的损失，在许多MaOPs问题中大多数候选解变得互不支配，从而导致传统多目标进化算法中基于支配的选择策略失效；第二个原因是多样性管理困难，在许多MaOPs问题中，候选解在高维目标空间中分布稀疏，导致多目标进化算法的多样性管理策略失效。为了更好求解MaOPs问题，一些改进方法[10-11]被提出，基本可以分为四类。第一类是基于收敛增强的方法，包括ε支配[12-13]，L最优[14]、模糊支配[15]、偏好次序排序[16]和θ支配[17]等。第二类采用性能指标取代Pareto支配作为选择非支配解的标准[18-21]，相关算法有基于指标的进化算法[22]、基于S度量选择的多目标进化算法[23]和基于超体积的进化算法[24]。第三类是基于分解的方法将MaOPs问题分解为一组简单子问题，然后以协同优化的方式求解。例如，基于稳定匹配模型的MOEA/D[25]和带有自适应权重向量调整方法的MOEA/D[26]。第四类将MaOPs问题转换为一个多目标优化问题，利用已有的多目标进化算法进行求解。例如，基于支配关系保存算法[27-28]。

尽管多目标进化算法已经对MaOPs问题进行了大量研究，但对于多目标优化问题中的大规模决策变量研究较少[29]。Ma等人[30]提出了基于决策变量分析的多目标进化算法（MOEA/DVA），用于求解大规模MOPs问题。该算法中提出了一种基于支配关系的决策变量分析方法，将决策变量分为三类：收敛性相关变量、多样性相关变量和同时与收敛性和多样性相关的变量。这种决策变量分析方法能够有效优化具有两个或三个目标的大规模MOPs问题，但对MaOPs问题没有探究。支配关系并不是区分决策变量进化状态的唯一度量，例如，Cheng等人[31]的研究表明，候选解中决策变量与收敛方向之间的角度同样可以用于测量决策变量的收敛性与多样性。Zhang等人[32]在MOEA/DVA算法基础之上提出了基于决策变量聚类方法的高维多目标进化算法（MLEA），用于求解大规模MaOPs问题。MLEA算法采用K均值方法对样本解中决策变量和收敛方向的夹角进行聚类，具有较小夹角平均值的簇表示对收敛性贡献更大，具有较大夹角平均值的簇对多样性贡献更大，通过这种聚类思路将决策变量分为两类，即收敛性相关变量和多样性相关变量。实验表明MLEA算法在大规模MaOPs问题中具有一定的优势，但是簇的夹角平均值不能直接反映进化状态，因此，并不能有力促进种群的进化过程。

本文针对大规模MaOPs问题，在LMEA算法基础上提出了基于进化角度比较方法的高维多目标进化算法（EACLMEA）。在进化角度比较方法中，首先从种群中随机选择若干样本解，通过比较当前样本解与另外三个随机选择样本解的决策变量与收敛方向形成夹角大小，判断决策变量的多样性和收敛性；如果当前样本解的决策变量夹角小于其中两个或以上，则该决策变量夹角具有属于全部决策变量夹角中较小值高概率，判断该决策变量具有较小夹角值，否则该决策变量具较大夹角值的高概率；较小夹角表示对多样性贡献更大，被判断为多样性相关变量，较大夹角表示对收敛性贡献更大，为收敛性相关变量。

1 LMEA算法

LMEA算法被设计用于求解大规模MaOPs问题，采用决策变量聚类方法将决策变量分为收敛性相关变量和多样性相关变量。收敛性相关变量根据交互分析方法可以进一步划分为若干收敛性相关变量子组，然后利用收敛性优化策略优化收敛性相关变量子组；多样性相关变量则采用多样性优化策略进行优化。

1.1 决策变量聚类方法

通过一个具有四个决策变量x1,x2,x3和x4的两目标最小化问题来说明决策变量聚类方法。为了说明决策变量与收敛性相关还是与多样性相关，首先从种群中随机选择nSel（本例中nSel为2）个候选解，所选择候选解的每个决策变量都被执行nPer（本例中nPer为8）次扰动。

将扰动每个决策变量产生的样本解归一化，拟合归一化样本解以生成一条线L。所有样本解组成超平面的法线与拟合线L的之间的角度被计算为f1+…+fm=1，其中M是目标数，法线代表了收敛方向。每一个决策变量都关联了一些角度，角度的数量取决于用于决策变量聚类所选择候选解的数量。因为本例中有两个候选解被选择用于决策变量聚类，因此每个决策变量xi，1≤i≤4，与两个角度相关联。决策变量聚类方法中，与决策变量关联的角度用于测量决策变量对于收敛性和多样性的贡献，即较大的角度意味着该决策变量对多样性贡献更大，一个更小的角度对收敛性贡献更大，更多的解被用于决策变量聚类，则会有更多的角度与每一个决策变量关联，则对于决策变量的度量更加准确。

采用k均值聚类方法将决策变量分为两簇，其中较小夹角平均值簇中的决策变量为收敛性相关变量，在另一个簇中的决策变量为多样性相关变量。

1.2 交互分析方法

算法1用于说明决策变量交互分析过程。首先初始化交互作用的变量子组的空集合subCVs，然后根据决策变量之间的交互作用，将收敛性相关变量集合CV中的变量分配给不同的收敛性相关变量子组，其中交互关系被定义如下：给定一个MOP问题，min f=min(f1,f2,…,fm)，如果存在x,a1,a2,b1,b2和至少一个 fk,1≤k≤m，满 足 fk(x)|xi=a2,xj=b1fk(x)|xi=a1,xj=b2，其中fk(x)|xi=a2,xj=b1=fk(x1,…,xi-1,a2,…,xj-1,b1,…,xn)，则决策变量xi和xj存在交互作用。具体来说就是，如果一个变量与subCVs中至少一个现有变量交互，那么这两个变量被分配到同一个子组，否则，该变量被分配到一个新的子组。重复此操作，直到每个与收敛性相关的变量都分配给一个子组。因此在极端情况下，最多会有|CV|个子群，即收敛性相关变量是完全分离的，相反，如果收敛性相关变量是完全不可分的，则只有一个子群。

算法1：InteractionAnalysis（P，CV，nCor）

输入：P（当前种群），CV（收敛性相关变量集合），nCor（被选取用于决策变量交互分析的解的数量）

输出：subCVs（CV中的交互决策变量子组集合）

1:subCVs←∅;

2:forall th ev∈CVdo;

3:CorSet←∅;

4:forall th e Group∈subCVsdo

5: forall th eu∈Groupdo

6: flag←false;

7: for i=1tonCor do

8: Randomly selecta solution p from P;

9:if v isinteracted with u in p then

10: flag←true;

11:CorSet←CorSet∪{Group};

12:break;

13:if flagthen

14: break;

15:if CorSet==∅th en

16: subCVs←subCVs∪{{v}};

17:else

18: subCVs←subCVs/CorSet;

19:Group←all var iablesin CorSet and v;

20:subCVs←subCVs∪{Group};

1.3 基于树快速非支配排序方法（T-ENS）

T-ENS核心思想是利用一棵树来表示每一个非支配前沿的解，树中节点用于存储解，同时也存储决定解之间支配关系的目标信息，可以从分配给非支配前沿的解（即树中的解）推断出很多非支配关系，从而可以减少同一前沿解之间的比较次数，因此，提高了快速非支配排序的计算效率，该方法的具体过程如算法2所示。

算法2：T-ENS的主要步骤

输入：P（种群），M（目标数）

输出：F（前沿集合，每个前沿被一棵树表示）

1:根据第一个目标升序排列P;

2:F←∅;

3:k←0;

4:whilenot_empty(P) do;

5:k←k+1;

6:for all th ep∈Pdo

8:update_tree(p,F[]k,objSeq);

9:return F;

1.4 收敛性优化策略与多样性优化策略

在算法1完成交互分析后，LMEA算法开始使用收敛性优化策略逐个优化每一个收敛性相关变量子组，过程如算法3。在收敛性优化策略中，利用T-ENS对父代种群进行非支配排序，计算出每一个候选解到理想点的欧氏距离。每个子组中的变量，使用二元竞赛法则从种群P中随机选择两个候选解，然后利用重组算子生成的变量替代同一子组中的决策变量值，保持剩余决策变量不变，以生成子代候选解。当且仅当子代候选解在非支配排序中具有较小的非支配前沿数，或者它具有与父代相同的非支配前沿数，但与理想点之间的欧氏距离较小时，子代候选解被认为具有比其父代解具有更好的收敛性。那么如果子代候选解比其父代具有更好的收敛性，则选择将其作为下一代，否则子代候选解被丢弃，父代候选解作为下一代。

算法3：ConvergenceOptimization（P，subCVs）

输入：P（当前种群），subCVs（收敛性相关变量子组的集合）

输出：P（下代种群）

1:Front←Nondo min atedSort(P);

2:计算P中每个解和原始点在目标空间中的距离

3:forall th eGroup∈subCVsdo

4:nEvaluated←0;

5:whilenEvaluated< ||P do

6: S←∅;

7: for i=1to ||P do

8: if rand()

9: S←S∪{i};

10:O←∅

11:for s∈Sdo

12:通过二元竞赛从P中选择p1和p2，其中每个解的前沿数和距离被用于作为第一和第二标准;

s'(G roup)表示在组Group中决策变量以上的组成s'值的一个向量*/

14:s''←s;

15:s''(Group)←s'(Group);

16:O←O∪{s''}

17:nEvaluated←nEvaluated+|O|;

18:Front←Nondo min atedSort(P∪O);

19:计算目标空间中O中的所有解和原始点之间的距离;

20：根据前沿数和距离，用O中每个解替代P中相应的解;

在多样性优化策略中，通过将所有多样性相关变量作为一个整体进行优化，以从P种群中生成|P|子代；然后，子代与父代进行组合，组合种群通过两阶段进行环境选择。首先，从k-1个前沿中选择候选解，k是满足|F1∪F2∪…∪Fk|>|P|的最小值；来自前沿Fk的最好多样性的剩余候选解被一个一个地选择直到种群规模|P|被达到，多样性通过目标空间中候选解之间的角度进行测量。多样性优化策略如算法4所示。重复算法3和算法4直到终止条件满足。

算法4：DiversityOptimization（P，DV）

输入：P（当前种群），DV（多样性相关变量）输出：Q（下代种群）

1:O←∅;

2:forall thep∈Pdo

3:随机从P中选择p1和p2;

4: p'(DV)←recombination(p1(DV),p2(DV));

5: p''←p;

6: p''(DV)←p'(DV);

7:O←O∪{p''};

8:F←Nondo min ateSort(P∪O);

9:Q←F1∪F2∪…∪Fk-1，其 中 k是 满 足|F1∪F2∪…∪Fk|>|P|的最小值;

10:if Q=∅th en

11:Q←在Fk中的所有极值;

12:Fk←Fk/Q;

13:计算所有目标空间中Q∪Fk内任意两个解之间的角度;

14:while ||Q< ||P do

15: p←argmaxx∈Fkminy∈QAngle[]x[y];

16:Q←Q∪{p};

2 EACLMEA算法

EACLMEA算法采用了LMEA算法的基本结构，同时在EACLMEA算法中引入了进化角度比较方法替代LMEA算法中的决策变量聚类方法。

2.1 EACLMEA算法的主要框架

EACLMEA算法如算法5，由五部分组成。第一部分随机初始化包括n个候选解的种群；第二部分采用进化角度比较方法将这些变量分为两组，即收敛性相关变量和多样性相关变量；第三部分依据交互分析方法，如算法1，将收敛性相关变量进一步划分为若干收敛性相关变量子组，同一子组内变量间存在交互作用，不同子组间的变量不存在交互作用关系。第四部分采用收敛性优化策略，如算法3，优化收敛性相关变量子组；第五部分采用多样性优化策略，如算法4，优化多样性相关变量。

算法5：EACLMEA算法的主要框架

输入：N（种群大小），nSel（被选取用于决策变量进化角度比较的解的数量），nPer（决策变量进化角度比较中每个解被扰动的数量），nCor（被选取用于决策变量交互分析的解的数量）

输出：P（最终种群）

1:PßInitialize（N）;

2:[DV，CV]ßVarialbleEvolutionAngleCompare（P，nSel，nPer）;

3:subCVsßInteractionAnalysis（P，CV，nCor）;4:while termination criterion not fulfilled do

5:PßConvergenceOptimization（P，subCVs）;6:PßDiversityOptimization（P，DV）;

7:end while

2.2 进化角度比较方法

进化角度即决策变量与收敛方向之间的夹角，计算方法为从种群中选择nSel个样本解，每个样本解的决策变量被扰动nPer次，以生成扰动样本解，然后将扰动样本解归一化，生成归一化样本解。并通过线L拟合归一化样本解中的决策变量。线L与归一化样本解组成超平面的法线形成夹角，即为归一化样本解中决策变量的进化角度，法线代表收敛方向，因此进化角度也可以表述为决策变量与收敛方向之间的夹角。进化角度比较方法，如算法6所示，核心思想是通过进化角度大小判断决策变量属于收敛性相关变量还是多样性相关变量。对于某一决策变量i，如步骤2，为了判断决策变量i是多样性相关还是收敛性相关，随机从种群P选择nSel个样本解，如步骤3，通过比较当前样本解，与另外三个随机选择样本解中决策变量夹角的大小，得出决策变量是否具有所有决策变量中较小值的高概率，如果具有较小值高概率，判断决策变量i为多样性相关变量，否则为收敛性相关变量。

算 法6：VarialbleEvolutionAngleCompare（P，nSel，nPer）

输入：P（当前种群），nSel（被选择用于决策变量进化角度比较的解的数量），nPer（被选择用于决策变量进化角度比较的每个解的扰动数）

输出：DV（多样性相关变量），CV（收敛性相关变量）

1:D←决策变量的长度;

2:for i=1 to Ddo

3:S←从P中随机选择nSel个解;

4: for j=1 nSel todo

5: 扰动S[]j的第i个决策变量nPer次以生成一个种群SP;

6: 归一化SP;

7:为SP拟合一个线L;

8: Angle[i][j]←计算L和超平面的法线之间的角度，f1+…fM=1，M是目标数;

9:K←randsample(nSel,3);

10:if Angle[i][j]小于Angle[i][ K(1)]、Angle[i][ K(2)]和Angle[i][K (3)]中两个或三个值

11:JudgeAngle[i][j]←0;

12:elseif Angle[i][j]小于Angle[i][ K(1)]、Angle[i][K (1)]和Angle[i][K (1)]中两个或三个值

13:JudgeAngle[i][j]←1;

14: else JudgeAngle[i][j]←1

15:CV←{i=1,…,D|mean( MSE[i])<1e-2};

16: if any( JudgeAngle(C V)==1)≠∅and any(JudgeAngle(C V)==0)≠∅

17:if JudgeAngle(C V,:)==1

18: CV=CV&JudgeAngle==1

19:else CV=CV&JudgeAngle==0

20:DV←{j=1,…,D|j∉CV};

3 实验与分析

为了验证EACLMEA算法在大规模MaOPs问题中的性能，对比了三种最新的多目标进化算法，即MOEA/DVA算法[30]、NSGA-III[33]算法和LMEA算法[32]。

使用被广泛使用的测试集LSMOP[34]作为实验问题，LSMOP测试集用于研究者开发多变量和高维多目标问题，允许创建带有任何数量决策变量和目标数的函数。LSMOP包括9个测试问题，LSMOP1-LSMOP9，在本研究中所有测试问题的目标数均为5个，决策变量分别考虑100个和1000个，所有测试问题均为大规模MaOPs问题。

3.1 实验设置

为了进行公正比较，用于比较的算法参数均采用原文献推荐值以获得最佳性能，其他公用参数具体设置如下：

（1）种群规模、最大评估次数和运行次数：所有算法种群规模均为10，最大评估次数为1000，在每个测试问题上，每个算法独立执行20次，以获得统计结果；

（2）本文提出的EACLMEA算法相关参数：进化角度比较方法中，种群中被选择用于进化角度比较的样本解的数量nSel=5，每个样本解被扰动数为nPer=50，用于交互分析方法中的解的数量为nCor=5。

（3）性能指标：采用被广泛使用性能指标，翻转世代距离（IGD）作为评价算法的性能指标，IGD值越小，解集质量越好。

3.2 结果与讨论

表1给出了四种算法在具有100和1000个决策变量的9个测试问题LSMOP1-LSMOP9上，20次独立运行获得的IGD值的统计结果，最佳结果显示为灰色背景。其中符号“+”、“-”和“≈”分别表示在0.05显著水平的Wilcoxon轶和检验上，相比EACLMEA算法的IGD值，显著更好、更差和统计学没有差异。

表1四种算法在测试问题LSMOP1-LSMOP9上获得的IGD值

从表1中可以得出两个观察结果，首先LMEA和EACLMEA总体获得更好的IGD值，且EACLMEA获得更多的最优IGD值。EACLMEA在LSMOP5-LSMOP9和具有100个决策变量的LSMOP3上具有更好的结果；LMEA在LSMOP1、具有100个决策变量的LSMOP2、具有1000个决策变量的LSMOP3和具有100个决策变量的LSMOP4上具有更好的IGD值。在Wilcoxon轶和检验结果中，在LSMOP9、具有100个决策变量的LSMOP2、具有1000个决策变量的LSMOP4和具有1000个决策变量的LSMOP6上，LMEA和EA⁃CLMEA在统计学上没有差异。EACLMEA算法获得更多最优IGD值原因是，进化角度比较方法能够将决策变量准确区分为多样性相关变量和收敛性相关变量，通过相关优化策略获得较好的IGD值；EACLMEA算法整体上比LMEA算法具有更优的性能，原因是EA⁃CLMEA算法将具有较小夹角的决策变量判断为多样性相关变量，从而使更加偏向收敛方向决策变量的多样性得到充分利用。其次，随着决策变量从100变为1000，EACLMEA算法都能获得较好的IGD值，说明该算法能够适应高维度多目标优化问题中，大规模决策变量的优化需求。

4 结语

本文提出基于进化角度比较方法的高维多目标进化算法（EACLMEA），进化角度比较方法根据当前样本解与随机选择样本解的决策变量与收敛方向形成夹角的大小比较，判断当前样本解的决策变量为收敛性相关变量或多样性相关变量，如果当前样本解的决策变量小于大多数随机选择样本解决策变量夹角，则判断决策变量为多样性相关变量，采用多样性优化策略进行优化；否则采用收敛性优化策略优化该决策变量。结果表明EACLMEA算法在大多数LSMOP问题中取得更好的IGD值，即进化角度比较方法能够有效解决大规模高维多目标优化问题。