多目标优化问题的景观可视化方法 崔志集， 梁子敏， 李密清

《Mathematical and Computational Applications》：A Problem Landscape Visualisation Method for Multi-Objective Optimisation Zhiji Cui, Zimin Liang and Miqing Li

　　摘要 理解多目标优化问题（MOPs）的结构对于分析搜索难度和支持明智的决策至关重要。在单目标优化中，适应度景观提供了问题的空间视图，但由于目标的向量值特性，将这种可视化扩展到MOPs具有挑战性。在这项工作中，我们引入了帕累托景观（Pareto landscape），这是一种基于帕累托优势关系（Pareto dominance relation）的多目标优化适应度景观可视化技术。我们阐述了帕累托景观的主要特征，将其与经典的适应度景观进行了比较，并研究了其在基准测试套件、受限问题、多模态问题和实际案例中的表现。我们还展示了它如何捕捉与优化难度相关的问题景观结构。与梯度场热图（gradient field heatmaps）、PLOT、成本景观（cost landscape）和受限成本景观（constrained cost landscape）的比较进一步表明，帕累托景观通过突出现有可视化方法无法看到的结构模式，提供了互补的洞察力。总体而言，结果表明，帕累托景观为观察不同类别的多目标优化问题的结构提供了一种一致的方法。 1. 引言可视化长期以来一直是理解优化问题的核心，使决策者能够形成更加自信和明智的判断[1]。这在多目标优化（MOO）中尤为突出，因为结果很少是单一的最佳解决方案。相反，决策者必须从潜在的大量帕累托最优解中选择（即帕累托前沿），每个解都代表了不同目标之间的权衡。如果没有适当的可视化支持，这样的决策可能严重依赖于主观解释和个人偏好，从而难以完全理解每个选择的影响[2]。在多目标优化中，可视化方法可以大致分为两个互补的领域：目标空间可视化（objective space visualisation）和问题景观可视化（problem landscape visualisation），如[3]中所调查的，并在图1中进行了说明。目标空间方法根据目标向量绘制解决方案，已经开发了多种方法，包括散点图和基于矩阵的图表、热图以及基于平行坐标的图表、层次布局和基于投影的方法；例如，参见参考文献[4,5,6,7,8]以获取概述。这些方法在揭示权衡和优势关系方面非常有效，但它们对底层搜索空间的结构属性（如多模态性、吸引盆或（局部）最优区域的连通性）的洞察非常有限[9,10]。图1. 多目标优化中可视化方法的高层次分类。受限成本景观（Constrained cost landscape）指的是在[11]中提出的成本景观的受限扩展。问题景观可视化方法通过揭示解决方案在搜索空间（也称为决策空间）中的分布来解决这一限制。这些方法可以大致分为抽象方法（abstract methods）和原生方法（native methods）。抽象方法将问题景观结构压缩成网络抽象，例如局部最优解网络及其多目标变体[12,13,14,15]。这些方法在连通性和搜索动态方面提供了宝贵的洞察，特别是在组合设置中，但它们不保留决策空间的空间结构。相比之下，原生决策空间方法根据决策变量显示解决方案，并使用高度或颜色刻度来分配解决方案质量。在这些方法中，基于搜索的方法（如梯度场热图[16]、PLOT[17]和局部优势景观[18]）可以揭示局部结构，但取决于所考虑的搜索算法的行为。非基于搜索的方法通过独立于搜索算法来分配质量来避免这种伪影。例如，多轮廓图[19]通过叠加各个目标的等高线信息来推断结构，但当目标交互复杂时可能难以解释；成本景观[20]测量支配解决方案的数量，但可能无法准确反映优化问题的底层结构；及其受限扩展[11]通过违反约束来表示不可行区域。在本文中，我们介绍了帕累托景观，这是一种非基于搜索的景观可视化方法，它使用帕累托非支配级别（Pareto non-domination levels）来分配解决方案质量。我们展示了帕累托景观保持了与优势一致的颜色顺序，并捕捉了由优势级别拓扑隐含的全局结构特征和某些局部结构模式，例如相邻解决方案之间的高度差异、孤立的局部优势区域和中性区域，尽管它没有明确标识局部高效解决方案或盆地结构。这项工作的初步版本曾在PPSN 2024[21]上进行了展示。目前的期刊版本在以下方面对该研究进行了重大扩展：它提供了对所提出可视化的深入分析和讨论，包括其在领域中的位置以及与现有方法的比较及其特点和特性。它考虑了更多问题类别，包括受限问题、多模态问题和实际问题，并展示了可视化如何揭示它们的结构特征和相关优化挑战。本文的其余部分组织如下。第2节提供了必要的背景信息，包括多目标优化和景观可视化的关键术语，然后回顾了现有的MOPs可视化方法。第3节介绍了帕累托景观并讨论了其基本属性和特性。第4节将帕累托景观应用于成熟的基准测试套件（ZDT [22]、DTLZ [23]、WFG [24]和BBOB [25]），以揭示它们的结构特征。第5节探讨了特定问题类型，包括受限问题、多模态问题和实际问题。第6节将帕累托景观与现有的景观可视化方法进行了比较，特别是梯度场热图[16]、PLOT [17]、成本景观[20]及其受限扩展[11]。第7节讨论了所提出方法的局限性。最后，第8节总结了不同问题类型揭示的特征，并讨论了未来的研究方向。2. 前置知识在本节中，我们首先给出了多目标优化和我们的可视化方法中使用的术语，然后简要回顾了代表性的MOPs可视化方法。2.1. 术语理解MOPs的结构属性，如全局和局部高效区域的分布，是设计有意义的问题景观可视化方法的前提。在这一小节中，我们介绍了本工作中考虑的景观表示所依赖的关键概念。多目标优化问题（MOP）涉及多个冲突目标的同时优化。不失一般性，假设所有目标都被最小化：(1) 其中 表示可行的决策空间， 是决策向量。每个可行解映射到一个目标向量 ，其中 是可行的目标空间。由于目标通常存在冲突，解决方案通常不能完全排序。相反，比较基于帕累托优势。给定两个目标向量 ，如果 则写为 (2) 这种关系扩展到决策空间为 当且仅当 。一个可行解是帕累托最优的（也称为全局高效的），如果没有其他可行解支配它：(3) 所有这样的解构成了帕累托最优集：(4) 它们对应的对象向量构成了帕累托前沿：(5) 除了全局效率之外，决策空间可能包含多个没有局部改进可能的区域。如果存在一个邻域半径 ，以至于开放球体内的任何解决方案都不支配它，则称解为局部高效的：(6) 鉴于此，所有局部高效解决方案的集合是 (7) 它们对应的目标向量形式是 (8) 如果一个多目标优化问题除了全局高效区域外还包含至少一个局部高效区域，或者如果两个或多个不同的全局高效解决方案映射到帕累托前沿上的同一点，则称该问题为多模态的（MMOP）[19,26,27,28,29]。在连续的多目标优化中，多目标梯度（MOG）[30]与局部效率密切相关。它指示了所有目标同时下降的最陡方向，并且当且仅当 是局部高效时满足 (9) 其中系数 解决了 (10) 因此MOG表征了决策空间中的吸引盆。在MOP中另一个广泛使用的概念是非支配级别[31]。给定一个有限集，第一个非支配集是 (11) 随后层次通过递归获得：(12) 每个解被分配一个级别 (13) 在这项工作中，集合S不是优化器的中间种群，而是从决策空间或所有可行解中抽取的样本。根据这种解释，第一个非支配集对应于问题的帕累托最优解（或它们的抽样代表），更高的级别反映了决策空间中越来越被支配的区域。这些基于问题的非支配级别构成了帕累托景观中使用的适应度。2.2. 相关工作多目标优化中的可视化已经从几个角度进行了研究，方法大致分为目标空间可视化（objective space visualisation）和问题景观可视化（problem landscape visualisation）[3,32]，如图1所总结的。在这一节中，我们回顾了现有的主要方法家族，特别强调了与本工作最相关的问题景观可视化方法。2.2.1. 目标空间可视化目标空间方法根据目标向量绘制解决方案，已经开发了多种方法[4,5,6,7,8]。直接显示目标值的常见方法包括散点图和散点图矩阵[33,34]、值路径[35,36]、热图[37]以及基于平行坐标的图表（PCP）[38]。在这些通用方法的基础上，提出了一些扩展以改善多目标设置中的可解释性。例如，热图通过基于优势的分组和排序[39]和排序[40]在高维问题中更清晰地揭示了结构，PCP通过解释性指导和目标重排序[41,42]得到了改进。其他家族包括基于圆形和多边形的方法，如星形图[43,44]和雷达图[45]；基于图标的方法，如切尔诺夫面（Chernoff faces）[46]；以及层次方法，如层次树[44,47]。在这个更广泛的层次结构家族中，基于树的可视化方法包括空间填充布局，如树图[48]和太阳爆炸图[49]，这些方法已被应用于多目标优化来可视化优势层次[50,51]。基于投影的方法也被广泛使用，包括PCA[52]、MDS[53]、自组织映射[54]和RadVis[55]。还提出了一些针对多目标优化的特定投影方法，如目标降维投影[56]和基于切片的视图，包括剖面图[57,58]。这些基于投影的工具也常用于通过在整个进化过程中嵌入种群轨迹来可视化算法行为[59,60,61,62]。最后，还提出了几个面向可视化的测试问题，以促进对多目标优化中的目标空间视图、多模态性和结构模式的系统检查[63,64,65]。尽管目标空间方法丰富，但问题景观可视化受到的关注相对较少，很长一段时间以来，成本景观[20]是唯一广泛使用的方法。然而，理解结构属性对于算法设计和有效决策至关重要，因为这些属性强烈影响优化难度和替代解的解释。2.2.2. 问题景观可视化问题景观可视化方法旨在揭示优化问题的结构属性，特别是相对于决策空间中的解决方案质量。抽象方法将景观信息压缩成基于图的表示，其中节点通常代表局部最优解或局部高效集，边表示可能的转换。代表性方法包括局部最优解网络和几种多目标变体，如PLOSNet[13]、CPLOSNet[14]、PLON、DNON[66]和最近盆地网络（NBN）[15]。这些方法在组合设置中提供了对连通性和搜索动态的洞察，但它们不保留几何邻接性，因此不传达决策空间的空间结构。原生决策空间方法根据决策变量直接绘制解决方案，并使用高度或颜色刻度来编码解决方案质量。这些方法可以大致分为基于搜索的方法，如局部优势景观[18]、梯度场热图（GFH）[16]和带有最优权衡的景观图（PLOT）[17]，它们通过局部搜索或多目标梯度来推导解决方案质量；以及非基于搜索的方法，包括多轮廓图[19]、线切割[25,67]、成本景观[20]，以及Tu?ar等人提出的受限成本景观的受限变体[11]。为了简洁起见，我们将这种受限变体称为受限成本景观。在这些方法中，GFH、PLOT、成本景观和受限成本景观与本文最为相关，因为它们为每个解决方案分配了一个标量适应度值，从而引入了可以直接与帕累托景观中使用的非支配级别进行比较的基于高度或颜色的决策空间表示。相比之下，如多轮廓图[19]（它可视化目标等高线）和局部优势景观[18]（它突出吸引盆而不是定义所有解决方案的全局适应度）等方法，关注了景观结构的不同方面，因此不是我们比较的主要焦点。在这里，我们仅简要描述GFH、PLOT、成本景观（cost landscape）和受限成本景观（constrained cost landscape）；它们的特点和潜在限制将在第6节中进行详细分析。成本景观（cost landscape）[20]最初在Fonseca的博士论文中被提出。该方法提供了多目标问题结构的全局视图。在成本景观中，每个解决方案的适应度值（通过颜色或高度表示）对应于支配它的其他解决方案的数量，这通常被称为其帕累托排名（Pareto rank）[3,17,20,26]。在一些研究和可视化平台[11,26,68]中，还使用了一个标准化版本，称为支配排名比率（domination rank ratio）。受限成本景观（constrained cost landscape）[11]将成本景观扩展到受限的多目标优化问题。对于可行的解决方案，它保留了成本景观的支配排名比率编码；对于不可行的解决方案，它编码了违反约束的程度。这种双色方案允许在单一可视化中同时传达可行解决方案的质量和不可行解决方案的邻近性。

梯度场热图（GFH）[16]是第一个明确使用梯度信息来可视化多目标问题景观的方法。对于每个解决方案，GFH定义了一个适应度值（通过颜色显示），即沿着通往局部有效解决方案的路径的多目标梯度的累积长度，即归一化后的单目标梯度之和。从一个初始解决方案开始，该解决方案的累加器初始化为零，该方法反复移动到MOG指示的八个相邻解决方案之一，并在每一步添加归一化的MOG长度。一旦到达局部有效解决方案，累积的长度就被分配为起始解决方案的适应度值。通过这种方式，GFH提供了基于梯度的局部盆地结构视图，并被公认为是分析局部景观属性的有用工具[3]。

具有最优权衡的景观图（PLOT）[17]结合了GFH和成本景观的思想，提供了盆地结构和效率的联合视图。与GFH一样，每个解决方案的适应度值由累积的MOG长度给出，但PLOT使用灰度颜色方案，根据帕累托排名强调全局和局部有效解决方案。这种集成使得可以在一个图中同时检查吸引盆地的组织和全局/局部最优结构。

帕累托景观（Pareto Landscape）[69]首次由Wright提出，将优化描述为在三维“山脉”中导航，其中水平轴代表决策变量，垂直维度表示解决方案的适应度。这一视觉隐喻在进化计算和景观分析[70,71]中被广泛采用，因为它能够直观地描绘单目标问题的关键结构特征，包括峰值和谷值、山脊、高原、漏斗以及多模态性、崎岖度以及局部最优解的空间排列等特性。将这一概念扩展到多目标优化（MOO）并非易事，因为解决方案的质量是根据多个相互冲突的目标函数而不是单一标量来评估的。一种保留关键权衡信息的自然方法是利用帕累托支配关系引起的排序。基于这种关系，可以根据解决方案的非支配级别将它们分组到不同的层次中，这些层次可以作为景观表示的垂直坐标。从这个角度来看，一个点的“高度”反映了它的非支配级别，而不是原始的目标值（详见第2.1节中的非支配级别定义）。

图2提供了一个基于四目标多点距离最小化问题（MP-DMP）[72,73]的示例。（除非另有说明，本文中显示的帕累托景观是使用均匀采样网格生成的。）在这个问题中，每个目标被定义为到正多边形一个顶点的欧几里得距离。因此，帕累托最优解集恰好对应于多边形的边界（图2a）。相应的帕累托景观（图2b）将这些解集突出显示为最高的平台。此外，随着远离多边形，支配排序导致级别逐渐降低，域的边界达到最低位置。这展示了帕累托景观如何直接捕捉问题景观的全局结构。图2. 四目标MP-DMP[72,73]实例的示意图。决策空间（a）包含一个完全映射到帕累托前沿的正方形区域。相应的帕累托景观（b）将所有帕累托最优点放在最高级别，揭示了一个对称的由支配关系驱动的分层结构。

图3展示了一个由十个解决方案组成的简单示例——每个解决方案都由一个决策变量和两个最小化目标特征化。它们的目标向量产生了四个非支配级别：在级别1中，，在级别2中，在级别3中，而在级别4中出现。如图3a所示，这种排名直接决定了每个解决方案在帕累托景观中的垂直坐标。图3. 由一个决策变量和两个最小化目标特征化的十个解决方案的示例。左侧图中的高度反映了非支配级别。从这个示例中，可以识别出帕累托景观和经典适应度景观之间的几个相似之处：帕累托最优解总是出现在表面的最高峰上，如图3中的和。局部结构模式，如孤立的优势区域和高效区域之间的空间分离，在景观拓扑中可见（例如，形成了一个局部优势区域，而与和在空间上分离）。注意，帕累托景观并不明确标识局部有效解决方案；相反，这些结构是从支配级别表面的形状和连通性中推断出来的。支配关系严格通过高度来反映：每当时，被放置在一个更高的级别。例如，支配，而支配。具有相同目标向量的解决方案总是位于相同的高度（例如，和）。相邻点之间的斜率表明了支配变化的程度。例如，从到的下降比从到的下降更陡峭，这与非支配级别的较大差异（2对比1）一致。然而，帕累托景观也有一些与传统适应度景观不同的特点：较高的高度普遍表明解决方案质量更好，无论目标是被定义为最小化还是最大化。相互非支配的解决方案可能落在同一级别或不同级别，这取决于集合中其他解决方案引入的支配关系。例如，和共享同一个级别，因为没有一个支配另一个。尽管和也是相互非支配的，但由于被支配，所以位于较低的位置。如果没有任何解决方案支配另一个，则具有显著不同目标值的解决方案可能被映射到同一级别（例如，和）。这些观察结果源于帕累托景观是由支配关系而不是原始目标值决定的。由于支配关系只在评估的集合内引入部分顺序，因此相互非支配的解决方案即使目标值差异很大也可能占据相同的级别。相反，全局上都非支配的解决方案可能在有其他解决方案支配其中一个但不支配另一个时被分配到不同的级别。

在第2.2节中回顾的现有可视化方法中，成本景观[20]与帕累托景观最为相似。这两种方法有几个共同点：它们都为每个解决方案分配基于支配关系的标量适应度值，将全局最优解决方案放在最高级别，并揭示决策空间的全局结构特征。然而，上述一些特点并不适用于成本景观。首先，帕累托景观基于非支配级别，因此相邻点之间的斜率反映了离散的级别差异，而在成本景观中，适应度对应于支配解决方案的数量，而不是非支配级别。其次，成本景观中相互非支配的解决方案不太可能具有相同的高度，因为它们的支配计数受到采样集合组成的影响。同样，具有显著不同目标值的解决方案也不太可能映射到相同的高度，因为即使是很小的目标差异也可能显著改变支配解决方案的数量。这些区别在第6节中进一步分析。

MP-DMP问题家族在进化多目标算法的研究中被广泛使用[74,75,76,77]，因为它允许控制性地包含各种结构特征[73]，包括多模态性[72]和中立性[18]。我们下面将展示这些特征可以在帕累托景观中看到。在多模态MP-DMP实例中，使用多个一致的多边形而不是一个多边形，每个多边形定义一个全局有效解决方案的单独区域。每个区域都映射到整个帕累托前沿。如图4所示，这些区域在帕累托景观中表现为不同的平台，使得多个吸引盆地的存在变得直观可见。

ZDT [22]：一组具有不同搜索难度的两目标问题，包括局部最优解和不连续性。DTLZ [23]：旨在实现可扩展的多目标优化（MOO），支持任意数量的目标，同时保持多模态性和不连续效率区域等受控特征。WFG [24]：针对现实世界的特性，如可分离性、模态性、参数偏移和偏差，同时允许对问题难度进行精细控制。BBOB（bbob-biobj）[25]：结合了经过良好研究的单目标函数，导致景观不规则且变化多样，且先验信息有限。对于每个BBOB问题，存在多个实例；这里我们考虑第一个实例。请注意，我们关注上述问题集中的代表性问题，而不是遍历所有实例。为了可视化，所有问题都设置在具有两个目标的二维决策空间中。

图7a,b显示了ZDT3和ZDT4的帕累托景观。ZDT套件的一个特点是帕累托最优解位于所有决策变量（除了）都为零的区域[22]，这可以在两个面板中看到。ZDT3展示了五个不连续的帕累托最优区域，它们对应于目标空间中帕累托前沿的不同部分，这与现有可视化报告一致。此外，在可行域的边界处还可以观察到一个局部有效区域，这也是与现有可视化一致的结果。ZDT4更具挑战性：从图7b可以看出，存在许多局部最优解，如果搜索步长不适当（例如过小），这些局部最优解可能会困住算法。这种结构也可以通过moPLOT平台观察到[79,80]。然而，值得注意的是，对于ZDT3和ZDT4，现有的可视化方法（特别是基于原始决策空间表示的方法）[3,79,80]认为在某个区域的解质量较高，但这与帕累托景观产生的表示结果不同。图7显示了ZDT3、ZDT4、DTLZ1和DTLZ7的帕累托景观。DTLZ系列[23]与ZDT具有相似的特征。图7c和d展示了DTLZ1和DTLZ7，DTLZ1与ZDT4类似，呈现出多个等间距的局部最优解区域（尽管 valleys更深），这与[3,17,26]中的可视化结果一致，也可以通过moPLOT平台观察到[79,80]。DTLZ7与ZDT3的不同之处在于，当某些条件满足时，它具有不连续的帕累托最优区域（见图7d）；然而，最优区域之间的间隙较大，这使得算法在找到一个最优解后很难转移到另一个区域。DTLZ7的结构也可以通过moPLOT平台观察到[79,80]。同样值得注意的是，基于原始决策空间表示的现有结果[3,17,26,79,80]认为在某些区域的解质量较高，这与帕累托景观产生的表示结果不同。

4.2. WFG
图8展示了WFG1、WFG4、WFG7和WFG8。与之前的基准测试套件相比，WFG问题展现出更为精心构建的决策空间模式，反映了WFG工具包[24]中对可分性、模态和参数依赖性的精细控制。图8显示了几个WFG问题的帕累托景观。在图8a中，WFG1呈现出相对平滑且规则的结构，具有一条单一的帕累托最优脊线，这与WFG1被设计为可分且单模态的特性一致[24]。相比之下，图8b中的WFG4展现出明显崎岖的多模态结构，表面有反复的振荡变化，这与WFG4的多模态特性相符[24]。此外，Huband等人[24]指出，WFG4的山丘比其他一些多模态WFG问题更大，这使得搜索算法更容易陷入困境。图8c和d显示WFG7和WFG8的帕累托最优区域形状不同。WFG7呈现一条单一的帕累托最优脊线，其他部分结构规则。而WFG8则呈现出弯曲的帕累托最优脊线以及更加不对称的周围景观，这与WFG8中引入的额外参数依赖性有关，其中与位置相关的参数依赖于距离相关的参数，使得问题变得不可分[24]。

4.3. BBOB
ZDT、DTLZ和WFG的一个共同特点是存在“人工制造的模式”（例如，当某些变量固定时会出现聚集的最优解，或者等间距的局部最优解）。这些规律性可以被搜索算法利用——例如，通过解耦变量或调整步长。而在BBOB（bbob-biobj）套件中并非如此，其中每个目标都是由研究较为成熟的单目标函数组成的；因此，帕累托最优区域既不可知也无法直接控制[3,25]。图9展示了八个bbob-biobj问题，它们的景观表现出很大的多样性：包括单模态（BBOB1、BBOB29）、高崎岖度（BBOB10、BBOB47、BBOB55）、全局结构（BBOB47）、大的局部最优解区域（BBOB10、BBOB55）以及小尖刺状的局部最优解（BBOB18、BBOB39、BBOB53）。帕累托最优区域也不规则，包括一条直线（BBOB1）、一条折线（BBOB29）、几条独立的线（BBOB10、BBOB55）、不连续的点（BBOB47）以及线和点的混合（BBOB18、BBOB39、BBOB53）。这些结构观察结果与[3,17,25,26]中的报告一致。许多BBOB问题的帕累托最优区域的不连续性是一个重大挑战[26]。为了近似整个帕累托最优区域，算法在搜索过程中必须保持多样性；它们不能简单地沿着一个方向搜索到一个最优解然后进行局部探索。相比之下，ZDT、DTLZ和WFG中的大多数问题缺乏这种程度的不连续性，这使得算法相对容易恢复整个帕累托最优区域。

5. 某些类型问题上的帕累托景观
5.1. 受限问题
在多目标优化中，约束将决策空间划分为可行区域和不可行区域。可行区域可能面积较小、不连续或形状不规则，因此受限的帕累托集和帕累托前沿可能与无约束的情况有很大不同。这些结构效应使得受限的多目标优化（MOPs）特别具有挑战性，因为算法必须在收敛到帕累托前沿的同时有效探索并保持可行性。为了系统研究这些效应，已经提出了一些受限基准测试套件[81]。区分受限问题和大多数现有景观可视化方法考虑的盒约束设置是有帮助的，在那种设置中，决策空间仅受变量界限的限制，没有施加额外的可行性约束，如前文讨论的ZDT和DTLZ问题。与帕累托景观最相关的原始决策空间可视化方法——GFH[16]、PLOT[17]和成本景观[20]——都是为这种盒约束设置开发的。针对受限问题，Tu?ar等人[11]提出了一个受限的成本景观变体，通过根据支配度排名对可行点着色和对违规点根据违规值着色来扩展成本景观。第6节提供了帕累托景观与这些现有方法之间的比较。

在本节中，我们采用了六个具有代表性的受限基准测试套件——SRN[82]、TNK[83]、CTP[84]、CF[85]、C-DTLZ[86]和CMOP[87]，每个套件都针对不同的结构特性：
- SRN[82]：一个早期的双目标问题，具有非线性目标和非线性不等式约束，展示了陡峭的可行性边界如何塑造受限的帕累托前沿（PF）。
- TNK[83]：一个双目标问题，其三角和圆形约束产生了由不连续部分组成的可行区域，常用于评估当可行解出现在孤立子集中时的多样性保持情况。
- CTP[84]：通过在无约束函数上施加三角约束来产生受控的可行区域，CTP1–CTP7改变了可行比率、不连续性和PF形状。
- CF[85]：为CEC 2009引入，结合了DTLZ/WFG类型的目标准与各种非线性约束，CF1–CF10具有不规则的可行区域和误导性的可行性边界。
- C-DTLZ[86]：为扩展到多个目标而设计的DTLZ的受限变体；约束可以去除搜索空间的大部分，导致非常低的可行体积并重塑PF。
- CMOP[87]：一个构建CMOP1–CMOP8的工具包，具有可控的可行比率和维度；约束按主要影响PF几何形状、可行比率还是两者来分类。

因为许多受限问题在两个维度上展示出相似的结构模式，所以我们只展示了一部分代表性案例。除非另有说明，后续分析中始终使用相同的可视化设置。

5.1.1. SRN和TNK
图10a和b展示了SRN和TNK。在SRN中，两个二次约束只留下了一条狭窄的帕累托最优解带（用绿色显示），而不可行域形成了一个平坦的高原。这表明了一个平滑的无约束结构如何被可行性截断，只剩下少量的解有效。图10显示了几个受限测试问题的帕累托景观：(a) SRN，(b) TNK，(c,d) CTP4和CTP6，(e,f) CF5和CF6，(g) C-DTLZ1，以及(h,i) CMOP2和CMOP7。注意，对于C-DTLZ1，由于其不可行区域极小，因此在可视化中突出显示为青色。TNK更具挑战性：一个三角约束与一个圆形不等式结合，产生了几个不连续的帕累托最优解簇，这些解簇被不可行空间分隔开，这使得维持多样性变得复杂，因为一个可行组件中的解无法直接指引到另一个解。

5.1.2. CTP
图10c和d展示了CTP4和CTP6。CTP4没有产生一个大的不可行盆地；相反，许多小的不可行口袋围绕着全局帕累托区域，形成了分散的局部最优解，这些局部最优解在景观中表现为凹坑。接近真实PF的进展很微妙：小步长可能会陷入附近的局部帕累托解，而大步长可能会超出狭窄的全局最优区域。这需要仔细控制步长，以穿越碎片化的可行邻域而不丢失全局最优性。

5.1.3. CFF
图10e和f展示了CF5和CF6。CF5的特征是在决策空间中有两条弯曲的走廊——一个较好的左走廊和一个较差的右走廊。不可行区域阻挡了左走廊的部分部分，使得一些右走廊的解成为帕累托最优解。这使帕累托前沿分成两个不连续的部分，阻碍了算法在两部分之间保持多样性。与CF5不同，CF6中的不可行区域只是重塑了帕累托前沿，而不是将其分割。虽然帕累托前沿保持连接，但陡峭的可行边界要求高精度——小的扰动很容易导致违规。

5.1.4. C-DTLZ
图10g展示了C-DTLZ1。无约束的DTLZ1模式（类似于第4.1节中的ZDT4）展示了等间距的局部最优解。新增的约束改变了帕累托前沿周围的可行性，将其分割成几个不连续的部分。这增加了难度：一旦收敛到一个帕累托前沿，穿越不可行区域发现其他前沿就变得困难。

5.1.5. CMOP
图10h和i展示了CMOP2和CMOP7。在CMOP2中，周期性约束将可行性切分成几条带状区域，产生了多个等间距的帕累托前沿；算法必须穿越不可行的间隙来发现所有这些前沿。CMOP7的特点是大的不可行块将远距离的帕累托前沿分开，并引入了几个局部帕累托前沿，增加了过早收敛的风险。

5.2. 多模态问题
在多目标优化（MOO）中，多模态性指的是存在多个映射到相同（或几乎相同）帕累托前沿（PF）的帕累托解，以及/或存在局部帕累托前沿[19,27,28]。这种情况在应用中很常见，例如[88]。之前的研究[27,29,89]表明，仅在目标空间中保持多样性是不够的：未能识别多个帕累托前沿会限制决策者的选择范围，并可能降低决策质量。我们考虑了六个代表性的多模态问题套件：Omni-test、SYM、Two-On-One、SS-UF、MMF套件和IDMP/IDMP_e，涵盖了对称/不对称结构以及局部帕累托前沿的存在。
- Omni-test[90]：由正弦/余弦构建的目标产生高度重复的帕累托前沿结构；真正的帕累托前沿/PF可以通过分析来表征。
- SYM-PART[91]：几何对称性（例如，“简单”和“旋转”变体）生成等效帕累托解的簇，有助于测试对称集合的平衡覆盖。
- Two-On-One[92]：具有一个或两个最优解的双目标家族；通过移动/提升最小值，可以检查帕累托前沿（PF）与解之间的联系。
- SS-UF[27]：通过对称/移位变换，多个帕累托前沿映射到同一个PF的问题；这些函数引入了对称/不对称的多模态性和决策空间的冗余（后来由MMF推广）。
- MMF[89]：一个系统性的套件，区分了帕累托前沿的重叠、PF的凸性以及帕累托前沿的数量/几何形状。
- IDMP/IDMP_e[28]：引入局部帕累托前沿来模拟目标几乎相同但决策变量差异较大的情况；IDMP_e强调了全局/局部帕累托前沿之间的层次排名。

为了可视化这些多模态问题，我们采用了一个修改过的图例，突出显示决策空间结构与帕累托前沿之间的关系。具体来说，共享相同颜色的解对应于帕累托前沿上的同一点。如图11所示，这种编码通过将帕累托景观与其对应的对象空间视图配对来说明。颜色在两种表示中是一致的，允许在决策空间中直接识别映射到相同帕累托前沿点的多模态解。图11显示了SS-UF1的目标空间（a）和帕累托景观（b）。决策空间中的相同颜色解决方案映射到帕累托前沿上的同一点。对于具有单一全局最优解的问题，局部高效解决方案用青色突出显示，而全局高效解决方案用绿色突出显示。与基于梯度的可视化方法（如GFH或PLOT）不同，帕累托景观不通过梯度下降来显式识别局部最优解。因此，为了在可视化中突出显示局部高效区域，我们直接从采样网格中近似局部最优解。具体来说，如果一个解决方案在其直接的网格邻域内是非支配的（即没有被其他解决方案所支配），那么它就被认为是局部有效的，但这不包括全局有效的解决方案。由于采样分辨率是有限的，当解决方案的目标向量在相对意义上足够接近时，我们将其视为等效的。具体而言，如果对于每一个目标k，其中 和 分别是目标k观察到的最大值和最小值，而 是一个相对容忍度，那么两个解决方案被认为是等效的。在所有实验中，我们都设置 。5.2.1. Omni-Test和SYM 图12a,b展示了Omni-test和SYM。Omni-test在一个规则网格上显示出多个全局最优解[90]。每个帕累托前沿（PF）映射到相同的PF，从而产生许多等效的帕累托前沿区域；仅识别一个帕累托前沿区域是不够的，而且域边界处的周期性结构可能会引入额外的局部帕累托前沿区域。SYM问题与此相关，但配置更简单；它产生多个映射到相同PF的帕累托前沿区域，且几何结构较为简单，因此是一个用于平衡维护等效集合的轻量级测试。图12展示了几个多模态测试问题的帕累托景观：(a) Omni-test，(b) SYM-PART1，(c) Two-On-One情况1，(d,e) SS-UF1和SS-UF3，(f,g) MMF4和MMF6，(h) IDMPM2T2，以及(i) IDMPM2T2_e。5.2.2. Two-On-One 图12c描述了Two-On-One问题中的情况1。该构造结合了一个双峰四次函数和一个单峰球体。在这种情况下，两个四次最优解是对称的，并且它们映射到相同的目标值，而球体的最优解位于连接两个四次最优解的直线的中点。因此，形成了一个连续的帕累托集合，在景观中表现出对称性。这对应于一种基本的多模态性，其中由于决策空间的对称性，多个决策向量共享相同的目标值。5.2.3. SSU 图12d,e展示了SS-UF1和SS-UF3。在SS-UF1中，（几乎）连续的帕累托前沿是对称的，带有轻微的周期性波动，这些波动在全局集合附近形成了局部帕累托前沿。 Meanwhile，SS-UF3表现出明显的多模态结构。全局帕累托最优集合由两个不连续的连续分支组成，每个分支在景观中形成一个平滑的山脊。这些分支被表现出强烈振荡的区域所分隔，从而导致一个高度崎岖的景观。这导致了与不同全局/局部最优解相关的多个吸引盆。5.2.4. MMF 图12f,g展示了MMF4和MMF6。MMF4产生两个对称但完全分离的全局帕累托前沿；如果只收敛到一个最优解，则会遗漏一半的全局结构。MMF6引入了更大的周期性扰动，将帕累托前沿分割成许多较小的片段，并增加了虚假的局部帕累托前沿，使得遍历变得更加困难。5.2.5. IDMP 图12h,i分别展示了IDMPM2T2和IDMPM2T2_e。在IDMPM2T2中，多个解决方案对应于相同的目标值，从而产生了多模态性，并且有几个等效的全局帕累托前沿。相比之下，IDMPM2T2_e引入了一个额外的参数来控制全局和局部PF之间的分离，从而打破了这种对称性。除了创建全局-局部多模态结构之外，引入的参数还改变了局部景观的特征，导致局部最优解周围的区域趋于平坦。这表明扩展的公式不仅影响了PF/PS结构，还影响了问题的局部几何形状，对于更复杂的问题实例，这种影响可能变得越来越难以预测。5.3. 真实世界问题 除了合成基准测试之外，还有几个真实世界问题集[93,94,95,96,97]在实际条件下评估了算法行为。这些问题集成了受领域启发的结构、不规则的可行区域以及标准测试无法完全捕捉到的非线性约束。由于我们的可视化方法仅限于两个决策变量，因此只能分析其中的一部分问题。因此，我们专注于来自RWCMOP [95]和RE [93]的代表性案例（例如，RWCMOP10、RWCMOP16和RE2-2-4），并且还包括来自[98]的一个基于地图的问题。基于地图的问题[98]：在地理地图上放置设施，具有基于距离的目标，捕捉空间权衡（例如，可访问性与覆盖范围），并产生高度不规则的景观结构。RWCMOP套件[95]：难度可控的受约束的多模态优化（MOP），模仿真实应用；约束调整了可行比例和断开性，而目标反映了典型的冲突（例如，成本与性能）。RE问题[93]：源自实际工程公式（例如，焊接梁设计、舱口-盖板优化和水资源管理），具有反映物理要求的非线性目标/约束。我们现在对其中一些真实世界问题进行可视化。可视化设置保持不变。5.3.1. 基于地图的问题 图13a展示了一个基于地图的设施放置问题，具有基于距离的目标。景观高度不规则，显示出孤立的全局解决方案以及由地理特征塑造的多个局部有效区域。图13. 典型真实世界问题的帕累托景观：(a) 基于地图的问题，(b,c) 来自RWCMOP套件的两个实例，以及(d) RE2-2-4。5.3.2. RWCMOP 相比之下，RWCMOP10和RWCMOP16（每个只定义了两个决策变量）产生的结构相对简单。低维模型通常具有较低的非线性耦合，使得它们的景观在视觉上不那么复杂。RWCMOP10（图13b）特征是一个狭窄的类似山脊的全局帕累托前沿；RWCMOP16（图13c）引入了大的不可行区域，同时保持了一个连续的全局帕累托前沿。5.3.3. RE 图13d展示了RE2-2-4问题的帕累托景观。尽管整体景观是平滑的，但帕累托前沿显示出明显的转折点。这个转折点与[93]中报告的观察结果一致，即PF形状的变化。6. 与现有方法的比较 在本节中，我们将帕累托景观与四种代表性的问题景观可视化方法进行比较：梯度场热图（GFH）[16]、PLOT [17]、成本景观[20]以及Tu?ar等人的受限成本景观[11]。如2.2节所述，GFH和PLOT是基于搜索的方法，依赖于多目标梯度（MOG）下降，而成本景观和受限成本景观是非基于搜索的。前三种方法是为盒型受限问题开发的，其中决策空间仅受决策变量的上下界限制，而最后一种方法明确解决了受限问题。对于本节中使用的可视化，GFH和PLOT是从moPLOT平台[79,80]中复制的。由于这两种方法以2D形式显示，帕累托景观也在2D形式中展示，省略了高度维度，以便在第6.1节中进行比较。对于其余的比较，成本景观采用了与帕累托景观相同的颜色尺度。在第6.3节中讨论的受限成本景观遵循了原始工作[11]的颜色设置，使用帕累托排名而不是支配排名比，并以3D形式呈现。表1总结了本节中考虑的所有五种方法的主要特征。接下来我们将依次讨论每个比较，从基于搜索的方法开始。表1. 第6节中考虑的方法的总结比较。?：是；△：部分；?：否。6.1. 与基于搜索的可视化方法的比较 GFH [16]和PLOT [17]从规则网格（例如，点数）开始，并迭代地跟随最陡的MOG下降方向，直到达到一个点，其中阈值默认设置为。然而，在实践中，MOG值非常小的点可能不一定具有局部效率，从而导致可能错误地识别帕累托最优区域。图14为BBOB11测试问题[25]说明了这个问题。真实的帕累托最优区域是决策空间中心的一个矩形带。GFH和PLOT未能正确标记该区域，而成本景观和帕累托景观准确地突出了它。图14. 在BBOB11上比较GFH、PLOT、成本景观和帕累托景观。来自[21]。此外，GFH和PLOT中的搜索仅限于八个网格相邻的方向。这可能会偏离MOG的真实最陡下降路径。另外，它们使用累积路径长度作为适应度代理，这意味着具有相同目标质量的点可能因为不同的遍历路径而具有不同的适应度值。图15在ZDT1[22]上提供了这样一个例子。在GFH和PLOT中，对角线区域在视觉上显得较差，并不是因为这些解决方案更糟糕，而是因为下降路径更长。因此，基于梯度的搜索可视化可能会错误地表示支配关系。图15. 在ZDT1上比较GFH、PLOT、成本景观和帕累托景观。来自[21]。应该注意的是，GFH和POLT具有帕累托景观或成本景观所不具备的能力，即可以通过梯度下降来识别局部有效的解决方案。这允许明确揭示盆地结构和局部最优解。因此，方法的选择取决于分析目标。当需要识别局部最优解时，GFH或PLOT是合适的，而帕累托景观提供了与全局结构一致的支配视图。除了与基于搜索的方法的比较之外，图15中还可以看到成本景观和帕累托景观之间的差异。与图14不同，成本景观和帕累托景观不再完全吻合。例如，成本景观将左上区域标记为最差，而帕累托景观则标记为顶部区域。我们将在下一小节分析这种区别。6.2. 与成本景观的比较 成本景观[20]为每个点分配了支配它的样本点的数量。像帕累托景观一样，它提供了样本集上的相对适应度；然而，它通常对采样变化更加敏感。每当添加一个新的支配给定解决方案的点时，该解决方案的帕累托排名就会增加。相比之下，帕累托景观使用非支配级别（前沿索引）来自非支配排序；只有当前沿边界改变时，级别才会改变，使得在不改变前沿结构的插入下表示更加稳定。例如，在图3中，在和之间插入额外的非支配点不会影响任何解决方案的非支配级别。然而，在成本景观中，这样的插入会增加像、和这样的解决方案的支配计数（它们被新点支配），从而改变它们的显示适应度。这说明了帕累托景观对保持前沿结构的样本扰动的更强鲁棒性。同样值得注意的是，虽然帕累托景观在保持前沿结构的插入下更加稳定，但改变前沿的插入可能会更显著地影响其表示。在这种情况下，成本景观提供的支配计数信息可能更好地反映了支配关系的不对称性。在图16的另一个方面，提供了ZDT1上的具体比较。通过两个变量和，可以验证以下内容：(i) 固定并增加始终会产生一个由原始解决方案支配的解决方案；(ii) 固定并改变会产生相互非支配的解决方案。在成本景观（图16a）中，点A和B几乎具有相同的高度，尽管A支配B；相反，C和D（相互非支配）出现在显著不同的高度。图16. ZDT1的3D成本景观（a）和帕累托景观（b）。点A–D：A（0,0.2），B（0,0.4），C（0.2,1），D（0.4,1）。对于DTLZ2也观察到了类似的不一致性。在图17a中，成本景观几乎为解决方案A和B分配了相同的高度，尽管A支配B，而解决方案C和D（相互非支配）则出现在明显不同的高度。相反，帕累托景观（图17b）严格符合这些支配属性：A位于B之上，而C和D处于同一水平。图17. ZDT1的3D成本景观（a）和帕累托景观（b）。点A–D：A（0,0.6），B（0,0.8），C（0.2,1），D（0.4,1）。6.3. 与受限成本景观的比较 图18比较了CMOP8 [87]上的受限成本景观[11]和帕累托景观。在可行区域内，受限成本景观基于帕累托排名（或支配排名比），而帕累托景观基于非支配级别。因此，即使在相同的可行区域内，这两种可视化也表现出不同的结构模式。在帕累托景观中，每个断开的可行区域内，表面随着远离帕累托最优区域而逐渐恶化，高度变化大致呈线性。相比之下，在受限成本景观中，恶化起初较温和，然后变得更加陡峭。图18. 在CMOP8上比较受限成本景观（a）和帕累托景观（b）。在这两种情况下，不可行区域在最低层被渲染为平坦表面。在(a)中，可行区域根据帕累托排名着色，而不可行区域根据约束违反的程度用红色着色。在(b)中，可行解决方案根据非支配级别着色，而不可行区域统一显示为灰色。这是因为在远离帕累托最优区域的大多数方向上，占主导地位的解决方案数量会逐渐累积，并且当点进一步进入决策空间的劣质部分时，这一数量往往增长得更快。这种解释也与第3节中的观察结果一致，即即使是很小的目标差异也可能显著改变占主导地位的解决方案数量，这也在图16和图17中得到了体现，尽管在ZDT1中的某些特殊方向或DTLZ2中的某些方向上存在例外，因为在这些方向上，一个目标不会进一步恶化。对于图18中的不可行区域，两种可视化方法具有相同的几何形状。然而，受限成本景观通过根据违规程度对这一表面进行着色，提供了额外的信息。更具体地说，在整个决策空间中，随着点接近某个值，违规情况会变得更加严重。此外，在两个平行可行区域之间的每个不可行带内，违规情况在带的中间部分最高。在这方面，受限成本景观可能有助于了解算法在可行性边界附近的行为[11]，并可能帮助指示不可行区域的哪些部分更接近可行性，哪些部分可能构成了更强的约束障碍。

7. 局限性
尽管帕累托景观提供了许多见解，但应该承认所提出方法的几个局限性。首先，帕累托景观是一种基于决策空间几何结构的本地化可视化方法，因此其适用性主要局限于决策变量数量较少的连续优化问题。对于离散或组合问题，由于邻域关系是通过组合运算符而非几何邻接来定义的，帕累托景观所基于的空间解释变得不那么有意义，因为决策空间缺乏自然的几何嵌入。在这种设置下，抽象的景观表示方法，如局部最优解网络及其多目标扩展[12,13,14,15]，可能更适合分析结构特性。对于具有有序离散变量的低维问题（例如整数值决策空间），情况略有不同，因为常规网格采样仍然可行，并且帕累托景观的空间解释得以保留。

其次，这种可视化方法依赖于对决策空间的采样近似。在这项工作中，帕累托景观是在一个规则网格上构建的，因此其可解释性取决于采样分辨率。特别是当网格足够细时，通常可以观察到主要的结构模式；而在非常粗糙的采样下，这些模式可能会变得模糊或无法显现。

第三，帕累托景观并不明确标识局部有效解决方案。相反，必须从支配级表面的拓扑结构中推断出局部结构特征。相比之下，基于搜索的可视化方法，如梯度场热图和PLOT，可以通过梯度下降机制明确揭示吸引盆和局部有效解决方案[16,17]。因此，帕累托景观更适合提供全局结构概览，而不是对局部最优结构的精确描述。

最后，虽然当整体前沿结构得以保持时，基于支配的度量（如非支配级别）通常比基于支配计数的度量更稳定，但关于采样密度和替代采样策略的系统敏感性分析仍然是未来工作的一个重要方向。正如第6节所讨论的，帕累托景观不应被视为取代现有的景观可视化方法。相反，它提供了互补的观点。成本景观、受限成本景观、梯度场热图和PLOT等方法捕捉了支配关系、不可行性和局部最优结构的不同方面。特别是对于受限问题，帕累托景观不像受限成本景观那样直接显示决策空间中不可行性的变化。因此，方法的选择取决于分析目标。

8. 结论
在这项工作中，我们引入了帕累托景观，这是一种基于非搜索的问题景观可视化方法，它通过非支配级别来评估解决方案的质量。这为多目标优化提供了对经典适应度景观的自然扩展。我们讨论了它们之间的相似性和差异。帕累托景观的不同之处在于，它在所考虑的集合内提供了一个“相对”的解决方案质量度量。然而，像适应度景观一样，它能够有效捕捉一系列问题特征（例如，最优性、多模态性、中性度、粗糙度水平以及决策空间的空间特征（例如，峰值、山谷、高原、山脊和漏斗）。

我们使用帕累托景观可视化了各种多目标优化问题，包括成熟的基准测试、受限和多模态函数以及现实世界问题。我们的发现如下：
许多成熟的基准测试套件（例如ZDT [22]、DTLZ [23]和WFG [24]）展示了可以通过搜索配置加以利用的人造特征，例如，通过在不同变量上分别搜索最优解或在搜索过程中使用特定的搜索步长。BBOB套件可能更适合表示具有多样化、不规则景观的具有挑战性的现实世界优化场景。
对于受限的多目标优化（MOPs），不可行的规模和模式差异巨大——从CTP4中的小范围散布到CTP6 [84]中的大阻塞区域，以及从CMOP2 [87]中的规则周期性条带到CF5 [85]中的不规则走廊。这些不同的约束将决策空间分割成不连续的可行区域，导致不同的结构后果：多个孤立的帕累托最优区域（TNK [83]、CF5 [85]、C-DTLZ1 [86]）在景观中表现为单独的峰值，可行性边界处的额外局部帕累托最优区域（CTP6 [84]、CMOP7 [87]），以及帕累托最优区域附近的狭窄可行带（SRN [82]、CF6 [85]）。

大多数多模态基准测试关注全局最优性（例如Omni-test [90]、SYM-PART [91]和SS-UF [27]），用于测试搜索算法以找出多个相同的全局最优区域。很少有测试关注局部最优性，即测试算法不会陷入局部最优区域。然而，在现实世界中，后者可能更为常见。
许多低维的现实世界问题（例如RWCMOP [95]和RE [93]）由于其公式中的非线性耦合减少，通常表现出相对简单的结构。然而，基于地图的问题[98]可能具有强烈的不规则性，特点是被孤立的全局解和多个局部有效区域。
与梯度场热图（GFH）[16]、PLOT [17]、成本景观[20]和受限成本景观[11]的比较进一步表明，帕累托景观提供了互补的见解：它提供了不同类别的多目标优化问题的全局视图，而这些方法在需要关于不可行性变化、局部有效解决方案或局部盆地结构的信息时更为合适。
最后，值得指出的是，一个与所有本地化决策空间可视化方法共有的关键限制是，它仅适用于具有两个或三个决策变量的问题。将这种方法扩展到更高维度的决策空间，或将帕累托支配与适当的降维技术结合，是未来研究的重要方向。