非规则帕累托前沿多目标优化问题的进化算法调查外文翻译资料

英语原文共 16 页，剩余内容已隐藏，支付完成后下载完整资料

非规则帕累托前沿多目标优化问题的进化算法调查

摘要--卷积算法在求解多目标优化问题(MOPS)中被证明是非常成功的。然而，当求解具有不规则帕累托前沿的MOPS时，它们的性能往往会恶化。 为了解决这一问题，近年来进行了大量的研究，并提出了许多新的算法。 本文对帕累托不规则锋面MOPS的研究进行了全面的综述。 我们首先简单介绍了基本概念，然后总结了不规则问题的基准测试问题，分析了不规则问题的原因，以及不规则帕累托前沿的现实世界优化问题。 然后，给出了处理不规则问题的现有方法的分类，并对具有代表性的算法进行了回顾，并讨论了它们的优缺点。 最后，指出了面临的挑战，并提出了几个有希望的未来方向。索引项-卷积算法，机器学习，多目标优化问题(MOPS)，不规则帕累托前沿。

大多现实世界多目标优化问题约束、冗余或高度非线性，导致不规则的帕累托前沿，可能是不连续的、退化的或倒置的。用不规则PFs解决MOPS是很有挑战性的，因为对于PFs的形状没有先验的知识，因此设计高效的优化算法特别困难

在过去的几十年里，进化算法在求解MOPS方面取得了巨大的成功，并[1]提出了大量的多目标进化算法(MOEA。一般来说，MOEA可以分为四类。第一类包括基于分解的MOEA，将目标MOP分解为多个子问题，每个子问题的解形成最终的解集。 例如，MOEA/D和RVEA都通过一组预定义的权重或参考向量进行分解，并同时优化子问题。 基于优势的MOEA属于第二类。 在这些算法中，使用非支配排序机制和多样性维护方案来选择候选。例如，NSGA-II使用快速非支配排序方法对候选解进行排序后，在选择中使用拥挤距离作为多样性度量。基于指标的MOEA属于第三类。在这些算法中，如HypE和IBEA，选择了对性能指标贡献更大的候选解。 协同进化MOEAs属于第四类，它使用协同进化算法来处理MOPS。例如，开发了一种使用权重的偏好启发共进化算法(PICEA-w)，将权重与候选解共同进化，从而消除了在优化开始前预先定义适当权重的要求。

然而，已经发现，为常规MOPS设计的MOEA在解决具有不规则PFs[14]的MOPS时很可能无法很好地执行。例如，对于使用一组固定和均匀分布的权重向量的基于分解的MOEA，并非每个权重向量都可以与PFs相交，因为不规则的PFs只分布在目标空间[4]的一部分。因此，许多预定义的权重向量被浪费，使得很难近似整个PF。 显示了一个具有不连续PF（用蓝线表示）的双目标优化问题，其中圆圈表示候选解，箭头线表示传统的基于分解的算法中使用的均匀分布的参考向量。由于PF与参考向量之间只有两个交叉点，因此只能从候选点中选择两个以橙色实心圆表示的个体，因此我们无法逼近完整的PF。同样，基于优势的MOEAs[9]，大多数多样性维护机制假设PF是规则的，因此当PFs是不规则的时，PF不能正常工作。因为它可以显著改善多样性。然而，以这种方式选择的个体并不能很好地代表实际的PF形状。最后，对指标贡献更多的个人将更有可能被选择，这可能有利于一些主导的解决方案，这些解决方案可以对指标做出更多的贡献，而不是非主导的解决方案。例如，对于具有退化PF的MOP，PF只分布在目标空间的一个非常窄的区域。 在这种情况下，分散在目标空间其他区域的许多受支配的个体可能对超体积(HV)指标作出更多的贡献，这可能会误导基于HV指标的环境选择方法。其中个人M对高压指标的贡献大于个人和。因此，M将被选择，这不能有助于实现多样化的帕累托最优解集。

近年来，不规则PFs的MOPS在MOEAs领域引起了越来越多的关注。已经提出了大量的MOEAs来解决不规则的PFs。这些MOEA大致可分为四类。第一类求解不规则MOPS的MOEAs采用辅助选择方法。在第二类中，参考向量在搜索过程中根据总体分布进行调整，目的是生成一组与PF分布匹配的参考向量。第三类，参照点也可用于指导搜索过程处理不规则的PFs。在这种算法中，参考点既用来测量个体的收敛性，又用来保持种群的多样性。第四类处理不规则问题的MOEA打算将人口聚类或使用网格将整个目标空间划分为若干个子区域。因此，可以选择每个子区域中的最佳个体来形成最终的种群。

本文旨在首次对现有的MOEAs进行全面的回顾，以解决具有不规则PFs的MOPS，以深入了解这些算法的优缺点，讨论剩余的挑战，并概述未来的研究方向。 应该指出的是，解决非规则帕累托前沿MOPS的挑战不同于解决多模态多/多目标优化问题的挑战，其中主要动机是促进决策空间和目标空间的多样性。

1)多目标优化问题：在不失去一般性的情况下，多目标问题(MOP)可以表述如下：

其中是决策变量的向量，是决策空间。是目标的数量，是目标的目标向量。是客观的空间。

2）帕累托优势：如果是两个决策向量，则支配（表示为），当且仅当被称为非主导解和主导解。 如果不存在支配它的任何其他可行解，则称为帕累托最优解。

3)帕累托集和帕累托前沿：所有帕累托最优解的结合称为帕累托集。

4)理想点、纳迪尔点和最坏点：理想点由真实PF的每个目标的最小值组成，最低点由真实PF的每个目标的最大值组成最差点由每个目标的最大值组成，其中，在上述所有表达式中。注意，现有文献中提到的理想点，最低点和最坏点多为当前总体，而不是问题理论中的三点。 无花果。 给出了一个两目标优化问题的例子，其中阴影区域是目标空间的可行区域，是理想点，是最低点，是最坏点。

5）Das和Dennis的参考点和参考向量：在基于分解的MOEAs中，经常使用一组均匀分布的权重或参考点，这通常是由Das和Dennis提出的晶格方法生成的。参考点的数目是由，其中是目标的数目，H是每个边缘上的段数。参考点分布在单位超平面上，其中是目标数，是目标值。每相邻两个参考点之间的欧氏距离相等。可以从均匀分布的参考点和原点构造均匀分布的参考向量。

6）定义：极限点被定义为超平面的截距由中变换的目标值和不同的目标轴构造（表示原始目标值，表示理想点）。正如他们的名字所暗示的，边界点是沿着PFs边界的解。 注意极值点的个数是（是目标的个数），而边界点的个数是无限的。

具有不规则PFsA的MOPS。不规则问题的定义规则PF表示PF具有单形形状，其中所有具有正方向的向量都与它相交当它的理想点是原点时，如[33]所述。 所有其他形状的PF被称为不规则PF。特别是，设为向量，其中，可以是第一象限中的任何向量。意味着不存在任何与规则PF不相交的方程。换句话说，所有具有正方向的向量都与规则PF相交。在（6）中，我们将符号替换为，这意味着如果一个帕累托前沿是不规则的，那么一定有一个与帕累托前沿不相交。显示四个规则PF，黑色表面表示PF，蓝色箭头线表示正方向矢量，矢量与PF的交点用红色实心圆表示。我们可以看到，无论PF是线性的、凸的、凹的还是非凸的，只要（5）成立，PF是规则的。

然而，现实世界中的PF并不总是规律的。 在现实中，PFs的形状可能是不连续的、退化的或倒置的。显示了三个目标问题的(A)正则、(B)不连续、(C)退化和(D)倒置PF，其中黑色表面表示PF，蓝色箭头线表示正方向矢量，矢量和PF的交点用红色实心圆表示。 三个坐标轴表示三个目标的目标值。显示了(A)正则、(B)不连续、(C)退化和(D)5目标问题的倒PF的平行坐标图。x轴表示目标数，y轴表示目标值。 我们可以看到不规则PF是规则PF的一部分。因此，如（6）中所述，将有与不规则PF不相交的正方向向量。

在下面，我们根据不规则的类型讨论了帕累托锋变得不规则的原因。

1)退化PF：退化问题是那些有非必要目标的问题。在这里，基本目标意味着实际决定PFs形状的目标。简并问题可分为三类：显式简并，隐式简并和部分简并。显式退化问题通常是由非本质目标产生的，这些目标是由本质目标的线性组合来制定的。但是，如果不是本质目标是由非线性组合或变换的本质目标的组合形成的，那么这种MOPS就是隐式退化问题。要解决隐式退化问题，算法必须能够提取本质目标，使其更难解决。部分退化问题的原因是客观空间的某些部分相互冲突，而其他部分则不是。 当决策空间不同区域对应的目标函数不同时，可能会发生这种情况。除上述外，还有一种特殊的简并问题，称为多点或多线距离最小化问题。这类问题的性质是决策变量的流形总是二维的。从它们在决策空间上的分布可以直接观察到观测到的解在目标空间中的分布。

2)不连续PF：通过不连续问题，我们通常意味着帕累托最优前沿是不连续的，而决策空间中的帕累托最优集是连续的。 一个不连续的PF通常是由于一些区域被其他区域所支配。 例如，不连续段可能是由于在设计基准函数时改变PF的形状函数，由Inv-DTLZ2和MaF1的倒置PFs以类似的方式形。DTLZ1-1-DTLZ4-1[15]和WFG1-1-WFG9-1将DTLZ和WFG[38]问题的目标函数值乘以-1来构造倒置PF。 此外，约束是导致倒PFS的另一个原因。 例如，C-DTLZ1[36]是通过添加一个超缸（其中心轴通过原点并同样倾斜到所有目标轴）作为约束来创建的，这样只有超缸内的区域是可行的。同时，一些倒置PFs是由函数本身引起的。功能本身的构建使倒P F区以外的区域占主导地位，如MaF4[37]。不规则PFs的其他形状：IMOP4-IMOP8[33]的不规则PFs是由功能本身引起的。功能本身的构建使得不规则PF区域以外的区域占主导地位。同时，约束是导致各种形状不规则PF的另一个原因。表一总结了应用广泛的具有不规则帕累托前沿的多目标测试问题。不规则PF的真实世界问题，许多不规则PF的真实世界MOPS已经被报道。无规则PFs是由目标函数[4]的约束[2]、冗余[3]或高非线性引起的。例如，三杆桁架优化问题[57]旨在使桁架的体积和组合节点位移在区域约束下最小化，并允许每个单元的应力。双目标优化问题的PF由两条独立的线性曲线组成。选矿生产计划问题[58]是一个具有五个目标的非线性MOP，即精矿品位最大化、总选矿比最小化、金属回收率最大化和精矿成本最小化。这个选矿生产计划问题的PF也是不连续的。车辆设计中的碰撞价值是一个三目标无约束优化问题，该问题的PF分布在两个独立的区域。其他具有不连续PFs的实际优化问题包括双目标碳纤维拉伸问题[14]和汽车侧冲击问题[2]。

三目标多速度变速箱设计优化问题旨在最小化所用齿轮材料的整体体积，这直接关系到变速箱的重量和成本，最大限度地提高变速箱交付的功率，最大限度地减少输入和输出轴之间的中心距离。 使用的齿轮材料的整体体积的最小化和输入输出轴之间的中心距离的最小化是不冲突的，而它们中的每一个都与变速箱交付的功率的最大化相冲突。 因此，这个问题的PF是退化的。 最后，多目标旅行商问题[59]是一个具有倒PF的三目标优化问题。

在本节中，我们将概述现有的MOEAs，致力于解决具有不规则PFs的MOPS。 从提交时可以找到的文献中，我们选择一个或两个算法来说明每个算法不同的想法。 因此，我们不能保证由于空间限制而涵盖所有相关参考资料。 在此，MOPS根据其处理PF中不规则性的主要机制分为四组。

基于固定向量的MOEAs与辅助方法，DAS和Dennis的系统方法产生的固定向量被广泛应用于基于分解的MOEAs[4]，[60]。 个体被分配到最接近的向量，使得问题被划分为几个子问题。 然后从每个子问题中选择最佳解决方案来构造最终的总体。 然而，在处理不规则PF时，有一些向量与PF不相交，因此，剩余的活动向量不能选择足够的个体来近似完整的PF。 因此，增加了辅助方法来提高基于固定向量的MOEAs在处理不规则PFs方面的性能。

在传统的基于分解的MOEA中，每个子问题都与一个且只有一个解决方案相关联。 基本假设是，每个子问题都有一个不同的帕累托最优解，对于不规则的PF可能无法保持。 这就是为什么MOEA/D或其变体在不规则问题上表现不佳的原因之一。 因此，另一个想法是允许不同的解决方案与相同的子问题相关联，并允许某些子问题没有关联的解决方案。例如，在MOEA/D-SAS[17]中，允许一些个体与相同的活动参考向量相关联。每个子问题中的个体首先根据其适应度值进行排序，然后根据其他个体之间的角度进行排序。同样，在ASEA[63]中，与同一主动向量相关的个体首先通过收敛进行排序，然后使用基于角度的拥挤度评估方法进一步筛选收敛排序较低的个体。这使得即使只有一组固定的参考向量也可以解决不规则问题。一些研究人员还提出利用两组固定的参考向量来解决不规则问题，一组从理想点出发，另一组从最低点出发。图中给出了一个例子。可以看出，只有一组均匀分布的参考向量的一部分覆盖了倒置的PF。相反，一组从最低点开始的参考向量可以覆盖整个倒置PF。在这方面做了一些工作。在PAEA[64]、MOEA/AD[65]和MOEA/D-MR[20]中，采用两组固定参考向量来处理倒置PFs问题。基于这两组参考向量（分别从理想点和最低点开始）的PBI和倒PBI标量化函数同时用于PAEA[64]，以评估搜索过程中种群中的解。每组参考向量的标量化函数可以是不同的，也可以是相同的。对MOEA/AD[65]中的每组参考向量采用PBI和增广成果标量函数(AAS F)，分别考虑收敛性和多样性。此外，基于理想点和最低点的信息也涉及MOEA/AD[65]中的配偶选择。与PAEA[64]、MOEA/AD[65]不同，MOEA/D-TPN[54]在搜索过程的两个阶段分别采用了基于理想点和最低点的两个标量化函数。在第一阶段，只使用基于理想点的Tchebycheff方法来指导搜索，其中参考向量分别被划分为中间子集和极端子集。 如果在第一阶段结束时找到的解表示中间子集和极端子集参考向量发现的种群的拥挤程度不平衡，则将采用基于最低点的Tchebycheff方法指导的第二搜索阶段。 在DBEA-DS[66]中，每一代得到两组具有两组参考方向的解。 即使同时使用两组参考向量，只有一组适应度值最小的解将存活。 在MOEA/D-MR[20]中，采用理想点和最低点作为原点的两个

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[605810]，资料为PDF文档或Word文档，PDF文档可免费转换为Word