| 标题 | A Diversity-Enhanced Tri-Stage Framework for Constrained Multi-objective Optimization |
|---|---|
| 作者 | Yubo Wang, Chengyu Hu, Fei Ming, Yanchi Li, Wenyin Gong, Liang Gao |
| 机构 | School of Computer Science, China University of Geosciences |
| 邮箱 | huchengyu@cug.edu.cn) |
| 论文 | https://ieeexplore.ieee.org/document/10680148 |
摘要
实现收敛性、可行性和多样性之间的权衡对于解决约束多目标优化问题（CMOP）至关重要。现有的约束多目标进化算法（CMOEA）主要侧重于约束处理技术，以平衡约束满足和目标优化。然而，人们普遍认为个体多样性较低。由于多样性增强不足，在处理具有复杂约束的CMOP时，CMOEA无法在目标空间中很好地分散，以增强对约束帕累托前沿（CPF）的搜索。为了解决这一局限性，本研究开发了一个具有三个不同进化阶段的多样性增强三阶段框架。首先，实现了足够的收敛，使种群能够在不可行的区域流动。然后，设计了一种角度控制策略，旨在在保持已实现收敛的同时，将种群均匀地分布在目标空间中。第三，我们提出了一种基于最小邻域的支配策略，以确保种群通过在目标空间中追求均匀分布来搜索CPF。此外，提出了一种权重向量预选策略，通过避免在不包括CPF的区域中进行无效搜索来减少计算开销。通过48个基准实例和25个真实世界实例的广泛实验，验证了我们的方法对9种最先进方法的有效性。
简介
与无约束多目标优化问题（MOP）相反，求解CMOP除了具有良好的收敛性和分布性外，还必须同时满足约束。各种约束多目标进化算法（CMOEAs）将不同的约束处理技术（CHTs）与MOEA相结合，以应对这一挑战，例如目标和约束的分离方法、惩罚函数方法、将CMOP转化为其他问题的方法以及混合方法。尽管现有的CMOEA可以在某些具有简单约束的CMOP上实现良好的性能，但在处理具有复杂约束的问题时表现不佳。不同的约束导致可行区域的结构性转变。翻译：
与无约束多目标优化问题（MOP）相反，求解CMOP除了具有良好的收敛性和分布性外，还必须同时满足约束。各种约束多目标进化算法（CMOEAs）将不同的约束处理技术（CHTs）与MOEA相结合，以应对这一挑战，例如目标和约束的分离方法、惩罚函数方法、将CMOP转化为其他问题的方法以及混合方法。尽管现有的CMOEA可以在某些具有简单约束的CMOP上实现良好的性能，但在处理具有复杂约束的问题时表现不佳。不同的约束导致可行区域的结构性转变。例如，由于复杂的约束，LIR CMOP的约束PF（CPF）受到大的不可行区域的阻碍，使可行区域变小或断开连接。这些算法在此类问题上表现不佳。
表现不佳的原因可归因于对多样性的考虑不足。良好的多样性是保持全局搜索能力的基础。尽管这些CMOEA在设计不同的CHT以处理约束方面付出了相当大的努力，但他们因此低估了多样性的重要性。例如，一些算法会在违反约束规则时，更倾向于收敛性而不是多样性。
然而，尽管这种偏好策略确保了快速收敛到可行区域，但整个群体在目标空间中以聚类状态搜索CPF。相应地，在探索中央公积金的一部分时，整个人口将位于这部分附近。在这种情况下，尽管CMOEA配备了不同的CHT，但它们无法搜索整个CPF，特别是在面对具有非常窄或离散可行区域的CMOP（例如LIR-CMOP1）时。
这是因为当种群迅速收敛到CMOP的局部CPF或UPF时，很难充分探索目标空间的其他区域。换句话说，这可能会导致无法找到部分甚至全部CPF片段，特别是当个体容易受到支配CPF片段的局部最优不可行区域的影响时。因此，将多样性视为处理具有不同特征的CMOP的最不重要因素是不合理的；相比之下，多样性的优先级应该提高。在确保种群多样性（全局搜索能力）的基础上搜索CPF更有可能搜索所有CPF，并更好地平衡收敛性、可行性和多样性。
为了更好地平衡上述三个特征，可以将整个进化过程分为三个阶段，分别根据不同的偏好指导种群搜索。更具体地说，在第一阶段必须保证收敛，以确保种群跨越不可行区域。第二阶段有利于多样性，以提高全局搜索能力。在优化了上述两个指标后，种群已经越过了不可行区域，并在目标空间中很好地传播。在最后阶段，我们更倾向于可行性，引导种群均匀地寻找CPF。这样，经过三个阶段，收敛性、可行性和多样性得到了平衡，实现了对CPF的统一搜索。换句话说，该框架克服了上述算法遇到的困难，即群体在聚合状态下搜索CPF，很容易陷入局部最优。
基于上述考虑，本研究提出了一种多样性增强的三阶段框架，以平衡收敛性、可行性和多样性，解决具有不同特征的CMOP问题。具体而言，本研究的主要贡献如下：
1） 我们提出了一种多样性增强的三阶段（DEST）框架，以更好地平衡收敛性、可行性和多样性。所提出的框架将进化过程分为三个阶段。收敛性、可行性和多样性在不同阶段被分配了不同的优先级。在第一阶段，我们更倾向于收敛，将种群转移到不可行的区域。在第二阶段，我们更倾向多样性而不损失收敛性，从而提高了全局搜索能力。在第三阶段，依次考虑多样性、可行性和收敛性，引导种群在保持良好分布的同时搜索CPF。
2） 为了使种群在目标空间中均匀分布在有希望的区域，同时保持收敛，我们设计了一种在第二阶段应用的角度支配策略。同样，我们在第三阶段提出了一种基于最小邻域的支配策略。基于该策略，每个个体更倾向于在其相应权重向量的最小邻域内搜索CPF。换句话说，在这种策略下，具有良好多样性和收敛性的人群可以均匀地搜索所有CPF。
3） 我们提出了一种权重向量预选策略，以减少目标空间中的无效搜索。该策略确定CPF是否可能存在于每个权重向量的最小邻域中。在不影响种群遗传多样性的情况下，我们使用这种策略来删除无用的权重向量，这些向量可能附近没有CPF。基于这种策略，许多计算资源都是可以减少的开销。
提出的三阶段框架和三种策略是本文的主要贡献，也是本文的主要创新点。在进化算法中，多阶段策略是常用的改进方法，比如在一些搜索空间较大的问题上或者容易陷入局部最优解的问题上，研究人员通常会设置两个阶段，在第一个阶段增加随机性以扩大范围，在第二阶段减小随机性以此来实现收敛。在不同阶段的策略也需要研究人员仔细设计，不然可能会适得其反。
相关工作和背景
现有CMOEA
1） 目标与约束分离方法
i） 约束支配原则（CDP） ii）ε约束松弛技术
2） 惩罚函数方法
3） 将CMOP转化为其他问题方法
i） 多群体方法 ii）多阶段方法
4） 混合方法
动机
大多数现有的CMOEA可以被视为MOEA和CHTs的组合。然而，在某些情况下，它们在平衡可行性、多样性和收敛性方面并不成功。无论基于支配、基于分解或基于指标的CMOEA使用何种CHT，它们在评估解决方案时通常更倾向于可行性或收敛性；相比之下，多样性通常较少被考虑。
对于具有简单约束的CMOP，当搜索了大多数可行区域时，上述平衡策略可以进一步对CPF进行局部搜索。然而，当面临以复杂约束为特征的问题时，当前的CMOEA表现出有限的性能。由于对可行性或收敛性的偏好，种群无法在目标空间中保持良好的分布，从而一次搜索所有CPF。相应地，一旦找到部分CPF，种群就会根据这种偏好策略陷入局部最优。此时，CMOEA试图使用CHT跳出局部可行区域。虽然一些CHT放宽了约束，如ε约束松弛技术，但首先优化了目标函数。因此，为了探索所有有前景的区域，在目标空间中均匀分布全局多样性并不容易。换句话说，由于多样性不足，现有的CMOEA无法确保有足够的全局搜索能力来探索所有CPF。
为了更清楚地说明这些局限性，下图显示了来自PPS、MOEA/D-FCHT、C3M和ICMA的人群，
LIR-CMOP1的可行域极小，其CPF距离UPF很远。PPS是一种基于分解的CMOEA，它使用多级约束松弛技术的CHT。MOEA/D-FCHT是一种基于分解的CMOEA，具有模糊CHT。CMOEAMS是一种基于优势的多阶段CMOEA。ICMA是一种基于指标的CMOEA，采用均匀搜索的CHT。这些CMOEA使用不同的MOEA和CHT，只能找到CPF的一小部分。
为了克服现有CMOEA的局限性，拟议的多样性增强三阶段框架引导种群在保持均匀分布的同时寻找CPF，旨在实现对CPF的均匀探索，避免遗漏CPF的某些部分。下图（a）、图（b）和图（c）显示了所提出框架的三个阶段。
在第一阶段，最好有足够的收敛来跨越不可行区域，这可以防止种群落入局部可行区域。
在第二阶段，与现有的CMOEA不同，首先需要种群多样性，而不会失去已实现的收敛性。该阶段确保种群在目标空间中均匀分布，以提高全局搜索能力。图（c）中两条相邻虚线之间的间距表示它们之间的权重向量的最小邻域。在寻找CPF的第三阶段，与通常最后考虑多样性的现有CMOEA不同，我们更偏向先考虑多样性然后是可行性和收敛性。
这将指导每个个体在其最小的邻近区域探索CPF。也就是说，种群在目标空间中基于均匀分布搜索整个CPF，避免了种群在聚合状态下搜索CPF。
通过将不同个体的搜索范围限制在均匀分布的整个CPF上，由此来增强多样性。确实是个简单而且有效的想法。
提出的方法
算法整体框架
所提出算法的总体流程图如图所示。首先，我们初始化总体、权重向量和存档。接下来，根据进化的当前阶段，算法进入主循环。在第一阶段，种群不考虑任何约束来实现足够的收敛。在第二阶段，在不损失收敛性的情况下获得足够的多样性。在第三阶段，种群探索CPF，同时在目标空间中保持良好的分布。最终，当计算资源耗尽时，主循环结束并输出存档。
算法1中给出了相应的伪码。
在第一阶段，作者选择了使用SPEA2的适应度评估策略，作者还指出任何能够实现良好收敛的MOEA都可以在第一阶段使用。然后在达到0.4倍最大评估次数时进入第二阶段，最后在符合条件的个体达到一定数量或者达到0.7倍评估次数的时候进入第三阶段。
所提出算法的第二阶段
在第二阶段，我们倾向多样性，而不会失去第一阶段实现的收敛性。算法2显示了伪代码。
首先，我们为每个权重向量初始化一组邻域向量B，并初始化几个与其他基于分解的CMOEA中相同的参数（第1行）。然后，我们对每个权重向量进行迭代。使用常见的基于分解的方法生成新的解决方案（第3-19行）。为了在目标空间中均匀分布种群，我们提出了一种在环境选择中执行的角度支配策略（第11-17行）。该战略概述如下。对于任何两个解，x和y，如果以下条件成立，则x被称为角度支配y。
条件：x不被y帕累托支配，x和λ（i）之间的角度小于y和λ（i）之间的夹角。
之所以要求x不被y支配，是为了在第一阶段保持已实现的收敛。然而，每个解都保持其收敛性，并倾向于探索其相应权重向量的邻近区域。整个种群在目标空间中均匀分布。因此，基于这种角度支配策略更新了种群P，与第一阶段相比提高了多样性。
所提出算法的第三阶段
经过前两个阶段的进化，种群P实现了优越的收敛性和多样性。因此，在第三阶段，有必要提高寻找CPF的可行性。我们应该确保种群以分布良好的方式搜索CPF，以避免遗漏CPF的部分。为了解决这个问题，我们提出了一种基于最小邻域的统治策略。相应的伪码如算法3所示。
算法2和3之间的主要区别在于环境选择（第13-38行）。在第三阶段，使用基于最小邻域的支配策略进行环境选择。该策略定义如下。在基于第i个权重向量的标准下，如果以下任何条件为真，则解x被称为最小邻域解，并支配解y。
1） x和y都∈Ui，且x≺Cy。
2） x∈Ui且y∉Ui。
3） x和y都∉Ui，且y⊀C x，x与第i个权重向量之间的角度小于y与第i个中的角度。
下图显示了基于最小邻域的统治策略的第一规则的效果（第17-19行），这反映了可行性的提高。x和y都位于第i个权重向量的最小区域。然而，x具有更大的潜力来探索CPF，因为x≺C y。具体来说，在图（a）中，x的约束违反程度小于y。在图（b）中，x和y都是可行的，x表现出增强的收敛性。因此，x支配y，这有助于提高可行性并确保Ui内的收敛。
权重向量的预选
由于约束，可行区域非常复杂。可行区域可以是离散的或非常窄的。因此，CPF可能不存在于某些权重向量的最小邻域中。基于上述考虑，我们提出了一种权重向量预选策略，以去除无用的权重向量及其相应的解决方案。
伪码如算法4，最初，我们保留与非支配可行解相关的权重向量（第5-7行）。如图（a）所示，W1、W2、W5、W6和W8将保持不变。丢弃剩余的权重向量（W3、W4和W7）和相应的解。剩余的权重向量被丢弃，因为在这些权重向量的最小邻域中没有CPF。
然而，CPF存在于某些权重向量的最小邻域中，但尚未被搜索到。权重向量将被错误地删除。为了解决这个问题，我们必须在确定权重向量是否被保留时提供多样性（第8-25行）。对于要删除的每个权重向量，我们分别找到其左侧和右侧最接近的三个权重向量。如果对应于最近权重向量的解中至少存在一个可行的非支配解，那么我们认为这个选定的权重向量是有希望的并保留它。
实验结果
实验设置
1） 基准问题：我们对三个广泛使用的基准套件进行了广泛的实验，共有37个实例，以衡量DEST的性能。它们是DASCMOP、LIR-CMOP和MW测试套件。此外，还选择了两个特殊的基准套件来验证DEST处理具有不同约束特征的CMOP的能力。
2） 比较算法：我们将DEST与九种最先进的算法进行了比较：MOEA/D-D-AE、MOEA/D-FCHT、PPS、CMOEMT、CMOEAMS、DSPCMDE、C3M、ICMA和TSTI。
3） 性能指标：为了衡量CMOEA的性能，我们在实验中使用了两个流行的指标，即反向世代加（IGD+）和超体积（HV）作为性能指标。
结果展示
消融实验
这篇文章总体上的解决思路是比较简单的，可以说是将进化过程分解为多个阶段，以此来解决之前算法的局限，策略的制定上也是通过考虑不同情况来解决多个问题，虽然总体上构思并不算特别巧妙，但是能解决问题就是好方法。
