原文：

《A Decision Variable Clustering-Based Evolutionary Algorithm for Large-Scale Many-Objective Optimization》

将分为论文摘要、背景介绍、算法原理、实验结果分析和总结五个部分

摘要

当前的进化算法多目标优化文献仅仅集中在目标数量的可伸缩性上，而很少考虑决策变量数量的可伸缩性。然而，许多现实世界的问题可能涉及许多目标和大规模的决策变量。为了解决这类大规模多目标优化问题，本文提出了一种基于决策变量聚类的定制进化算法。首先，决策变量聚类方法将决策变量分为两种类型:1)收敛相关变量和2)多样性相关变量。然后，为了优化这两种类型的决策变量，采用了收敛优化策略和多样性优化策略。此外，为了进一步提高算法的计算效率，提出了一种快速非支配排序方法。

为了评估所提出算法的性能，在具有多达10个目标和5000个决策变量的各种大规模多目标优化问题上进行了实验。实验结果表明，该算法在对多目标优化决策变量的可伸缩性方面，优于现有的几种进化算法。

关键词：聚类进化多目标优化大规模优化多目标优化非支配排序树

背景介绍

先来了解一下目前这个领域的研究背景，现有的多目标优化的研究文献大多数关注目标的规模而很少有文献关注决策变量的规模。而现实中我们大多遇到的是大规模多目标优化问题（MaOPs），MaOPs是涉及三个以上同时要优化的冲突目标的问题，传统的解决方案通常只涉及2-3个目标，在MaOP问题中会出现 收敛压力损失 和 多样性管理失效 的问题。

为了解决上述两类问题，目前已经提出了四类方法，如下：

提高算法的收敛能力
直接采用指标作为选择标准
基于分解的方法，即将MaOP分解为一组简单的子问题，然后以协作的方式解决他们。分解类型有两类：一是将MaOP分解为一组单目标问题（SOP）；二是将MaOP分解为一组简单的MOP
将大规模多目标优化问题转化为多目标问题，即将MaOP转换为MOP，然后采用MOEA解决。该方法有两个分支：一是使用目标约简方法来消除冗余或不相关的目标；二是用两个或三个新定义的目标替换原始目标

代表性MOEA介绍

为了解决大型MOP的这些问题，目前学术界比较成功的策略，目前提出的一些策略，主要为两类：

合作协同进化思想
MOEA/DVA

1.合作协同进化思想介绍

Antonio和Coello提出合作的协同进化框架来解决大规模MOP，主要思想是将大量决策变量随机分为相等大小的几个小子组件，并在预定数量的周期内共同协作演化这些子组件。该思想对2-3个目标的大型MOP有效。

2.MOEA/DAV方法，Ma等人提出基于决策变量的MOEA，称为MOEA/DVA，设计了一种基于优势关系的决策变量分析方法，用于解决大规模MOP。在该方法中，设计了一种基于优势关系的决策变量分析方法，将决策变量分为三类：

1.与收敛相关的变量

2.与多样性相关的变量

3.与收敛和多样性都相关的变量(目前将其单纯视为与多样性相关的变量)

研究表明，该决策变量分析方法对具有两个或三个目标的大型MOP有效，但是未对MaOP进行评估。

而本文想要解决的就是MaOP问题，因此在DAV算法基础上进行了特定的改进。

考虑到将决策变量优化为 收敛相关的变量 还是 多样性相关的变量 的问题，如下例所示：

考虑双目标MOP：

情况1：图1显示了在（1）中公式化的MOP上通过在[0,1]之间扰动一个变量而将另一个变量分别固定为0、0.5和1而获得的采样点。根据MOEA / DVA将x1和x2分别标记为与多样性相关的变量和与收敛性和多样性相关的变量。但是，由于x2对收敛的贡献大于多样性，因此将x2优化为收敛相关的变量而不是多样性相关的变量将更为有益。

即使在DVA中被视为很明显的和多样性相关的变量，实际上为了保证算法的快速收敛有时也需要被考虑成收敛性变量进行优化。

情况2：图2显示了在（2）中公式化的MOP上通过在[0,1]之间扰动一个变量而将另一个变量分别固定为0.2、0.6和1而获得的采样点。根据MOEA / DVA将x1和x2都标记为与多样性相关的变量。不过，在这种情况下，由于优化x2将引导总体趋向帕累托前沿，因此将x2标记为与收敛有关的变量更为有益。

综合上述原因，为了解决大规模超多目标问题（MaOPs），基于MOEA/DVA提出了针对大型MaOP的基于决策变量聚类的MOEA（称为LMEA）在LMEA中，提出了一种决策变量聚类方法，对收敛和多样性变量分类。可以正确地分类上述示例中x2相似的变量。并且分别对这两种不同的变量使用不同的进化方式。另外，提出了一种基于树结构的快速非支配排序方式以提高计算效率。最后，证明了算法的效果相对于当时最先进的算法有显著的提升。

算法原理

本文算法的主要贡献如下：

提出的基于k-means的聚类算法将决策变量分类
提出算法LMEA，并且对于多样性和收敛性方法采用了两种不同的算子进行优化。
提出基于树的快速非支配排序算法T-ENS，这是ENS[54]的改进版本。比目前大多数算法的时间复杂度小很多。

算法原理——LMEA

对于多样性和收敛性方法采用了两种不同的算子。对于收敛性变量选择策略是基于和理想点的欧式距离；对于多样性变量选择策略依赖的是和候选解的角度。

N :群体大小；nSel :决策变量聚类的解的数量

nPer :决策变量聚类每个解的扰动数量；nCor :决策变量交互分析的解的数量

算法2 对于收敛性相关的变量采用变量分析的方法将其分组

首先初始化一个相互作用的变量子群的空集子群，然后，基于它们之间的成对相互作用，将CV中与收敛相关的变量分配给不同的子群。

具体来说，如果一个变量与子群中至少一个现有变量有交互作用，那么这两个变量被分配到同一个子群中；否则，它将被分配给一个新的子组。重复该操作，直到每个与收敛相关的变量被分配给一个子组。因此，在极端情况下，子群数与变量数相同，这意味着收敛相关变量是完全可分的；而如果变量是完全不可分的，那么只有一个子群。

算法3 收敛优化策略逐个优化变量的每个子组

非支配排序
计算每个解和理想点之间距离(原点)
进化每个子组中的收敛性变量以获得后代

对于每个子组的变量，从P中挑两个解做父代，只将这个维度变量交叉其余维度不变生成子代，子代父代根据收敛性能优胜劣汰（不同层比较层数，层数越低越好，同层比较离理想点的距离，越近越好！）

算法4 分集优化策略优化多样性相关变量

将所有多样性相关的变量视为一个整体，对这所有的变量进行一次性的交叉，从种群P中生成等量后代，然后将子代种群和父代种群混合，并从中挑选出后代。

算法5 决策变量聚类算法

基于k-means的聚类算法根据采样的解和收敛方向的夹角将决策变量分为收敛性和多样性的变量。更小的夹角意味着变量对收敛的作用更大，更大的夹角意味着变量对多样性的作用更大。举例说明如何在LMEA识别具有四个决策变量的双目标最小化问题的收敛相关变量和多样性相关变量，表示为x1、x2、x3和x4。

DVA中的决策变量分析方法是基于优势关系确定各变量的类别。聚类方法采用k-means方法来确定每个变量的类别，鲁棒性更好。因为其性能与基于优势的关系无关，而基于优势的关系在多目标优化中可能由于优势阻力的问题而无效。

N :群体大小

nSel :决策变量聚类的解的数量

nPer :决策变量聚类每个解的扰动数量

nCor :决策变量交互分析的解的数量

图一显示了这种聚类方法，不同颜色线表示改变调查的不同的变量，相同颜色的条数表示从种群中采样的个体数目，例如，白色的线条有两条就是x2的采样个数是两个个体，而同一条线上点的个数表示对个体上这个变量采取的扰动的数量，例如这里对于单个个体的研究变量的扰动数目为8，所以一条线上的点的个数为8，同时，其他没有考虑的变量此时保持不变。

图二显示了聚类的标准，就是当考虑同一个变量的改变时，两个解构成的线分别与收敛方向构成的夹角，夹角较大表明变量与多样更相关，而夹角越小表明变量与收敛更相关。

图三显示了聚类的操作方法，由于考虑的变量的采样解的个数为二，因此构成的是一个二维的坐标系，通过这个坐标系上点的分布而通过K-means将变量分为两个簇、对于考虑多个采样，角度都比较大的变量划归为多样性相关的变量，而对于考虑多个采样，角度都比较小的变量划归为收敛性相关的变量。这种方式而言，单个变量采样的数量越多，坐标系的维度越大，聚类的效果越好！

这三个图说明了如何针对具有四个决策变量（分别为x1，x2，x3和x4）的双目标最小化问题在LMEA中识别收敛相关变量和多样相关变量。在此示例中，在LMEA中x1和x2被标识为与多样性相关的变量，x3和x4被标识为与收敛相关的变量。图一：由扰动产生的采样解的目标值。图二：拟合线和超平面法线之间的角度。图三：对四个决策变量x1，x2，x3和x4进行聚类结果。

通过这个例子，可以看出决策变量聚类方法的主要思想，其中考虑了具有四个决策变量x1，x2，x3和x4的双目标最小化问题。为了确定决策变量是收敛性相关还是多样性相关性，首先从总体中随机选择多个nSel（在此示例中为两个）候选解决方案。然后，对所选候选解的四个变量中的每个变量执行多个nPer（在此示例中为8）扰动。图一描绘了由扰动产生的采样解的目标值。
然后，通过扰动每个变量的值的采样解被标准化，生成一条线L以拟合每组标准化样品解。使用归一化的样品解和拟合线L，计算每个拟合线L与超平面f1 +··+ fM = 1的法线之间的夹角，其中法线表示收敛方向，M是目标。这样，每个变量都会有几个角度相关联，这个数量和挑选的采样解的数量相关（此处为2）
最后图三中表示的是按照角度进行的聚类方法。

算法6 基于树的快速非支配排序算法T-ENS

用于识别非支配关系的信息被记录在树的节点中，由此可以推断出解之间大量的非支配关系。最终，只需要比较非支配前沿支配的解的子集得到结果。算法有很大的时间复杂度优化。

多目标优化问题与单目标优化问题有很大差异。存在多个目标时, 很难找到一个解使得所有的目标函数同时最优。因此,对于多目标优化问题,通常存在一个解集,这些解之间就全体目标函数而言是无法比较优劣的,其特点是:无法在改进任何目标函数的同时不削弱至少一个其他目标函数。这种解称作非支配解(nondominated soluitons)或Pareto最优解(Pareto optimal Soluitons)

在LMEA中优化与收敛有关的变量和与多样性有关的变量时都采用非支配排序。非支配排序选取的方法将极大影响LMEA的计算效率。传统多目标优化中用来降低非支配排序的复杂性的方法大多数不适用于MaOPs。本文提出了一种计算效率高的基于树的非支配排序方法，称为T-ENS。基于快速树的非支配排序主要思想是用一棵树来表示每个非支配前沿的解，是在ENS算法的基础上提出的，该框架允许在不调整树的结构的情况下将候选解逐一插入树中。受益于ENS的框架，T-ENS的计算复杂度大大降低。其中关于确定解之间非支配关系的目标的信息由存储解的树中节点的位置来记录。因此，可以从已经被分配到前沿(存储在树中)的解中推断出解之间的许多非支配关系，从而大大减少了属于同一前沿的解之间的比较次数。带来了计算效率的显著提高，时间复杂度为O(MNlogN/logM)，用于大多数候选解之间不具有优势的种群。

非支配排序

该算法需要计算种群P中每个个体i 的两个参数ni（种群中支配个体i的个体数目）和si（种群中被个体I 支配的个体集合）。

1、找出种群中所有ni=0的个体，保存在集合F1中（也就是第一层）。

2、对F1中的每个个体i，其所支配的个体集合为si，遍历si中每个个体L，nL=nL-1,若nL=0，将L保存在集合H中（第二层）。

3、以H为当前集合，重复2，直到整个种群被分层.

在T-ENS中，用于识别非支配关系的信息被记录在树的节点中，由此可以推断出解之间大量的非支配关系。最终，只需要比较非支配前沿支配的解的子集，而不是全部。理论分析表明，所提出的T-ENS的时间复杂度为O（MNlogN / logM），其中N表示人口规模，M表示目标数量，这要比目前大多数算法O（MN^2）的时间复杂度小很多。

表示第i个解决方案，第j个的值。

T-ENS开始为所有非支配前沿（F）构造树：

①采用作为第一个非支配前向的根结点，所有属于的其他解决方案将被作为的后代存储。

②第i个解决方案在树中的位置由满足下公式的最小 j 决定

（其中是为解决方案随机从2到M生成的序列的第j个元素，即满足上述条件，将被存储为根的第j个孩子节点。）

③如果有多个解满足上述条件，多出的将存储为孩子，也就是的孙子节点，依此类推。

④重复上述过程，直到所有的解决方案都被检查。

⑤当第一个非支配前向的树构造完成后，依次构造的树，直到所有的解决方案都被放进树中。

算法6–8以伪代码的形式展示了T-ENS的详细步骤。

T-ENS开始为每个非支配的前沿构造一棵树。 T-ENS将第一个解p1作为第一个非主导前沿F1的树的根，并且属于F1的总体中的所有其他解将作为p1的后代存储。解pi，2≤i≤N的位置在树中，由满足j的最小值j（j> 1）确定，fiobjSeq[1][ j] < f1 objSeq[1][ j]，其中objSeq [1] [j]是序列的第j个元素。更精确地，具有满足上述条件的第objSeq [1] [j]个目标的解决方案pi将被存储为根的第j个子级。如果有多个满足上述条件的解决方案，则下一个解决方案将存储为pi的子代，即p1的孙代。重复此过程，直到检查总体中的所有解决方案为止。

在完成第一个非主导前沿F1的树的构造后，T-ENS开始为第二个前沿F2构造一棵树，直到总体中的所有解都分配给树为止。

使用上面的树来表示前面的解时，如果要分配给前面的解p不被树中的解q所支配，则p的值小于objSeq [q] [j 第]个目标（由于在排序的总体中q排在p之前，因此p在第一个目标上具有大于q的值），则p与存储为节点q的第k（k> j）个子项的解之间的非优势关系可以从q和p之间的非支配关系推断出该孩子的所有后代，因为对于每个这些解s，我们有fp objSeq [q] [j] <fq objSeq [q] [j] <fs可以与这些进行比较确定前objSeq [q] [j]，j∈{1，2，...，M-1}的解。因此，在确定p的前部时，无需与这些进行比较，这使得T-ENS对于MaOP非常有效。时间复杂度：O(MNlogN/logM)。