基于多种群分区辅助的用于解决约束多目标优化问题的协同进化算法

A Cooperative Evolutionary Algorithm for Solving Constrained Multi-Objective Optimization Problems Based on Multi-Population Partition Assistance

摘要: 在解决约束多目标优化问题时，需要同时考虑多个优化目标以及问题的约束条件，这给问题的解决带来了很大的挑战，主要体现在解的可行性、收敛性和多样性三个方面。为了应对这些挑战，本文提出了一种新的约束多目标进化优化算法，该算法采用了三个阶段和多个辅助种群的设计。具体来说，第一阶段中，算法首先利用不受约束的种群引领其他种群进行搜索，在第二阶段，每个辅助种群致力于解决单个约束条件下的多目标优化问题。最后，本文设计了一种分区辅助策略，根据不同种群在每个分区的表现来调整辅助种群的参与度。为了评估算法的表现和有效性，我们将其与当前较为优秀的四个算法在DASCMOPs测试基上进行了比较。实验结果表明，我们的算法具有出色的表现。

Abstract: In tackling constrained multi-objective optimization problems, it is necessary to consider multiple optimization objectives as well as the constraints of the problem, which poses significant challenges to finding solutions. These challenges are mainly reflected in the feasibility, convergence, and diversity of solutions. To address these challenges, this paper proposes a novel constrained multi-objective evolutionary optimization algorithm, which employs a three-stage approach and multiple auxiliary populations. Specifically, in the first stage, the algorithm utilizes an unconstrained population to guide the search of other populations. In the second stage, each auxiliary population focuses on solving the multi-objective optimization problem under a single constraint. Finally, a partition-driven strategy is designed to adjust the participation of auxiliary populations in each partition based on their performance, thereby enhancing the efficiency of the main population in obtaining superior solutions. To evaluate the performance and effectiveness of the algorithm, we compare it with four currently classic and outstanding algorithms on the DASCMOPs test suite. The experimental results demonstrate the excellent performance of our algorithm.

1. 引言

现实应用中有很多优化问题包含了几个相互冲突的目标和多个复杂的约束条件，如机电力配送系统规划 [1] 、组合经济排放调度问题 [2] 、车辆路径规划 [3] 。这类问题被称为受约束的多目标优化问题。其数学模型可以用下面的公式表达：

$\begin{array}{cc}{\min }_x& f\left(x\right)=\left(f_1\left(x\right),\cdots ,f_M\left(x\right)\right)\\ \text{s}\text{.t}\text{.}& x\in \Omega \\ & g_i\left(x\right)\le 0,i=1,\cdots ,p\\ & h_j\left(x\right)=0,j=1,\cdots ,q\end{array}$ (1)

其中， $x=\left(x_1,x_2,\cdots ,x_D\right)\in \text{Ω}$ 表示的是决策空间维度为D维的决策解； $\text{Ω}\subseteq {ℝ}^D$ 代表的是决策空间； $f:\text{Ω}\to {ℝ}^M$ 表示的是维度为M的目标解；其中还包括了q个等式约束 $h_j\left(x\right)$ 和p个不等式约束 $g_j\left(x\right)$ 。

从上述数学模型可以看出，约束多目标优化问题涉及多个优化目标，因此并非具有唯一解，而是通过一组解集展示各个优化目标之间的最优权衡。多目标进化算法，如基于非支配排序 [4] 、指标 [5] 、分解 [6] 等方法，是一种随机启发式算法，能够在一次运行中生成一组解集。受遗传进化的启发，该算法通过不断迭代更新朝向更优的进化方向搜索，最终产生一组较优的解集。然而，由于约束条件的存在，这些条件会改变目标空间的搜索景观，导致不可行解域的出现。在这种情况下，单纯使用多目标进化算法就不再有效，因此需要各种约束处理机制来应对这一挑战。

目前，约束处理机制主要分为六类。第一类是基于罚函数的方法，这些方法主要依据约束违反程度来构建惩罚项。将惩罚项融入目标函数中，将约束多目标优化问题转化为无约束的形式。文献 [7] 提出了一种新的方法，将非支配排序遗传算法与无参数惩罚方法相结合，以持续搜索更优解集。第二类是基于目标与约束分离的方法。文献 [4] 提出了一个非支配排序方法，该方法在比较两个不同个体时优先考虑可行解，若两个个体都是可行解则选择非支配解，若两个个体都是不可行解则选择约束违反度小的个体。第三类是基于多目标的方法，将约束条件也视为优化目标处理，从而将约束多目标优化问题转化为无约束的多目标优化问题。第四类方法是混合方法，将进化算法与数学规划相结合，特别是在处理等式约束时，这种方法可以减少空间搜索的成本。文献 [8] 提出了一种混合优化技术，将遗传算法与基于内点方法的局部搜索策略相结合。第五类是基于改变繁殖算子的方法 [9] ，该类方法专注于设计高效且特定的算子来处理繁殖过程。第六类是将约束多目标优化问题转化为其他问题，这是处理约束多目标优化问题的主要流行方法。这类方法可以有效利用不同优化问题或不同进化阶段的信息为其余问题和进化阶段提供参考信息，又可以细分为以下两类：

第一类，基于将优化问题转化为多个阶段的优化问题的方法，文献 [10] 提出了一种双阶段的算法框架，该框架分为推和拉两个阶段，在推的阶段，算法旨在使种群穿过不可行区域到达非约束帕累托前沿；而拉的阶段，采用改进的ε约束方法来往回搜索约束帕累托前沿。第二类方法是将约束多目标优化问题转化为协同优化问题，核心思想是使用不同的种群处理不同的优化问题，并相互分享经验。文献 [11] 提出了一个协同进化框架，来解决约束多目标优化问题，其中一个种群搜索约束帕累托前沿，另一个种群忽略约束条件寻找非约束帕累托前沿，并且这两个种群相互协助解决约束多目标优化问题。文献 [12] 设计了双存档进化算法，其中一个存档以收敛为导向，另一个存档以多样性为导向，用于探索未开发的区域并保持多样性。文献 [13] 研究了约束之间的关系，根据单个约束的帕累托前沿和它们的共同帕累托前沿的关系确定约束的优先级，并利用优先级最强的约束对应的种群进行辅助。尽管以上的算法都表现出色，但文献 [11] 的两个种群在约束和非约束帕累托前沿有较大分离时，合作效率较低。文献 [13] 中，单纯地根据各个约束条件对应的种群的支配排序来确定约束的优先级可能会忽略掉其他约束条件所能提供的信息。为解决上述问题，本文提出了一种约束多目标进化优化算法，使用多个辅助种群在不同分区下提供不同辅助强度。算法采用了三个阶段的进化过程，每个阶段能够高效地发掘信息。本文所提出的算法与4个约束多目标优化算法在3个测试基下进行比较，结果表明，所提的算法具有较好的表现。

2. 提出的算法

2.1. 算法框架

算法1概述了本文提出算法的步骤，该算法主要用到了C + 2个种群，其中包含1个负责解决原问题的种群，1个不考虑约束条件的多目标优化问题的种群还有C个只考虑一个约束条件的多目标优化问题的种群，为了方便后文的阅读和表述，在本文的后续部分，我们称这些只考虑一个约束条件的多目标优化问题为原问题的子约束问题。每个种群的规模设置为N，设置算法的最大函数评估次数为MaxFEs次。该算法主要分成三个阶段，第一个阶段是探索阶段，其主要目的是利用不考虑约束的种群引领其他种群向前探索。第二个阶段是开发阶段，在这一阶段，多个种群之间会进行信息交互，以实现知识的迁移。第三个阶段是聚焦阶段，其目标是确保每个辅助种群能够为主种群提供更加有效的辅助信息。在算法1的1~8行是一些初始化操作，C代表约束条件的个数，Stage初始化为1表示当前阶段为第一个阶段——探索阶段，种群P₁是不考虑约束的辅助种群，通过初始化P₁并且赋值给其他的C + 1个种群。在算法的9~20行是三个阶段的内容，当满足算法的终止条件，算法返回最终的主种群P。

2.2. 探索阶段

探索阶段的主要作用是选择利用不考虑约束条件的辅助种群解决最简单的无约束多目标优化问题，从而大致探索整个可行域并达到潜在的可行域。这样有助于穿越传统的约束多目标优化算法所无法突破的不可行域。需要注意的是，在这一阶段，只有种群P₁是产生子代的，并且这些子代会与其他种群共享。这么做的原因是为了节省计算资源，并且对于其他C个辅助种群而言，在早期阶段产生的子代尚未展现出较好的收敛性，因此可以认为它们在当前阶段的作用相对较小。算法2中的1~3行对辅助种群P₁进行了父代选择并且产生子代最终通过环境选择更新种群。在4~10行中，将P₁子代共享给其余的种群，最后通过环境选择完成种群更新。12~14行主要是进行了算法阶段数的更新，这个更新策略用到了文献 [10] 的状态转换策略。如公式(2)所示， $r{z}_k$ 代表最理想点和最不理想点变化率的最大值， $r{z}_k$ 小于阈值 就满足转换条件。其中最理想点和最不理想点的变化率用公式(3)和公式(4)表示。

$r_k\equiv \max \left\{r{z}_k,r{n}_k\right\}\le ϵ$ (2)

$r{z}_k={\max }_{i=1,\cdots ,m}\left\{\frac{\left|z_i^k-z_i^{k-l}\right|}{\max \left\{\left|z_i^{k-l}\right|,1\text{e}-6\right\}}\right\}$ (3)

$r{n}_k={\max }_{i=1,\cdots ,m}\left\{\frac{\left|n_i^k-n_i^{k-l}\right|}{\max \left\{\left|n_i^{k-l}\right|,1\text{e}-6\right\}}\right\}$ (4)

2.3. 开发阶段

在探索阶段转换到开发阶段后，由于种群P₁的引领，其余种群也能够到达相对收敛的和可行的区域。探索阶段的主要作用是让除了种群P₁之外的种群通过进化从而获得更优的解，在这个过程当中，由于各个种群用于处理不同的问题，能够产生不同偏好的子代个体，因此具有丰富有价值的信息。种群之间能够互相共享自己产生的子代，为其他种群提供有价值的信息，从而辅助主种群的解集具有更好的收敛性、可行性和多样性。需要注意的是，在开发阶段已经停止了辅助种群P₁的更新，而是通过其余的只考虑原问题的子约束问题的辅助种群来进行辅助，当遇到约束帕累托前沿与非约束帕累托前沿有着较大的差距的优化问题时，这样的设计能够在一定程度上弥补文献 [11] 中辅助种群在后期不能有效地提供辅助信息的缺陷。在算法3的1~7行主要是种群P， $S{P}_1,\cdots ,S{P}_C$ 产生子代并且将它们地子代都放到子代共享池中，8~13行中，每个种群都将自身与共享子代池合，随后通过环境选择更新为新的种群。15~17行是用于更新进化阶段的，当 $S{P}_1,\cdots ,S{P}_C$ 都处于相对停滞时，满足转换条件开始进入第三阶段。

2.4. 聚焦辅助阶段

2.4.1. 聚焦辅助策略

当完成了探索阶段后，处理原问题子约束问题的辅助种群基本上已经探索到属于它们的约束帕累托前沿了。并且，原问题对应的可行域是它各个子约束问题的可行域的交集，这些交集的帕累托前沿跟这些子约束问题对应的帕累托前沿会有一定的关系。本文将原问题的帕累托前沿和它子约束问题对应的帕累托前沿之间的关系简化为两类：1) 子约束问题的帕累托前沿与原问题的帕累托前沿有交集；2) 子约束问题的帕累托前沿与原问题的帕累托前沿没有交集。并且得出以下结论，子约束问题对原问题的辅助效率很大程度上与它和原问题之间的帕累托前沿的相近程度决定。由此本文提出了一个聚焦辅助的策略，用于分配每个处理子约束问题的辅助种群对主种群的辅助强度。

首先，将目标空间均匀地分成K份，计算并统计每个辅助种群在每个分区的可行解的个数，得到矩阵(5)，其中 $a_{c,k}$ 代表第c个辅助种群在第k个分区的可行解的个数。需要注意的是，这里的可行指的是针对原问题的可行，而非针对子约束问题的可行。

$\left(\begin{array}{ccc}{a}_{11}& \dots & a_{1K}\\ ⋮& \ddots & ⋮\\ a_{C1}& \cdots & a_{Ck}\end{array}\right)$ (5)

随后通过公式(6)计算第c个辅助种群在每个分区下的可行解比例，并用矩阵(7)表示每个辅助种群在每个分区对应的可行解比例。

${\text{rate}}_{ck}=\frac{a_{ck}}{{\displaystyle \underset{i=1}{\overset{K}{\sum }}{a}_{ci}}}$ (6)

$Rate=\left(\begin{array}{ccc}rat{e}_{11}& \dots & rat{e}_{1K}\\ ⋮& \ddots & ⋮\\ rat{e}_{C1}& \cdots & rat{e}_{CK}\end{array}\right)$ (7)

针对可能发生某些子约束问题对应的帕累托前沿在某些分区重合从而导致资源浪费的情况，本文认为应该将这些分区交给最擅长在这些分区处理优化问题的辅助种群，由此根据公式(8)计算每个辅助种群在分区k下的辅助资源数。并用矩阵(9)表示每个辅助种群在每个分区的辅助资源， $re{s}_{ck}$ 本质上就是第c个辅助种群在分区k中能容纳的最大个体数。

$re{s}_{ck}=\{\begin{array}{ll}rat{e}_{ck}\times N\hfill & {\text{ifrate}}_{ck}={\max }_{1\le c\le C}\left(rat{e}_{ck}\right)\hfill \\ 0\hfill & \text{otherwise}\hfill \end{array}$ (8)

$resource=\left(\begin{array}{ccc}re{s}_{11}& \dots & re{s}_{1K}\\ ⋮& \ddots & ⋮\\ re{s}_{C1}& \cdots & re{s}_{CK}\end{array}\right)$ (9)

随后设计新的环境选择策略。核心思想是将种群的个体都分配到它所擅长的区间，从而发挥每个辅助种群的辅助优势。算法4中1~3行主要是计算每个候选集的适应值和所属的分区，方便从每个分区筛选出对应资源数的优秀个体更新到下一代。4~12行是对每个分区进行遍历，假如在当前分区中候选解的个数小于其对应的资源数，那么就将该区的全部个体合并到Population_new中，否则的话就选择最优的对应的前资源数个个体。13~17主要是当Population_new个体数不满N个时，便从剩余的候选解中选出最优的leave个个体加入到Population_new中。

2.4.2. 聚焦辅助阶段算法流程

聚焦辅助阶段的目的是让每个辅助种群根据每个分区所分配的辅助资源来进一步为主种群提供有价值信息。算法5的第1行主要是计算每个辅助种群的个体相对原问题而言的可行解的比例，如果一个辅助种群中不存在可行解，说明它的帕累托前沿与原问题的帕累托前沿没有交集，因此在后期不能很好地提供辅助作用，因此便不考虑让其产生子代以此节省计算资源和减少信息干扰。第3行主要是根据公式(8)得出每个辅助种群在各个分区的辅助资源数。3~12行是让主种群和辅助种群产生子代并且都合并添加到共享子代池当中。13~18行是更新主种群。并且利用新设计的环境选择策略更新辅助种群。

3. 实验分析

本文主要选取广泛用于测试约束多目标优化算法性能的DASCMOP测试基 [14] ，该测试基需要平衡约束多目标优化问题中常见的可行性、收敛性、多样性三大难题，包含有三大类的约束条件，分别是控制收敛性的条件、控制可行性的条件和控制多样性的条件。本文使用的评价指标是IGD指标 [15] ，该指标主要反映了一个算法找到的帕累托前沿的收敛性和多样性。

为了检验所提算法的有效性，本文与四个前沿的算法 [10] [11] [12] [13] 进行比较，种群大小设置为100，最大评估次数设置为300,000次。所有测试问题都运行30轮。需要注意的是，对比的算法的参数都参考对应文献的设置。

3.1. 实验结果

算法在测试问题上的IGD指标平均值，如表1所示。

Table 1. The average value of the IGD metric of the algorithm on the test problems

表1. 算法在测试问题上的IGD指标平均值

3.2. 实验结果分析

从表1可以看出，本文提出的算法PACMO在DASCMOP测试基上取得了最好的实验效果，证明了它的有效性，尤其是在DASCMOP3和DASCMOP7-DASCMOP9中遥遥领先于对比的算法，并且说明该算法还在维度为3维的目标空间中也有着很好的表现。其次，算法在DASCMOP4和DASCMOP5中稍稍逊色于CCMO，这两个问题中的约束条件个数有11个，故本算法比CCMO需要消耗更多的资源在辅助种群中。总的而言，本文提出的算法能够较高效地利用到辅助种群提供的信息。

4. 结束语

本文提出了一种约束多目标进化优化算法，采用了三个阶段和多个辅助种群的设计。其核心思想是在第一阶段利用无约束的种群引领其他种群搜索潜在的可行区域，在第二阶段通过协同进化方式在辅助种群和主种群之间传递和共享信息，在第三阶段则采用了基于分区的辅助策略，以更好地让辅助种群为主种群提供可行信息。实验结果表明，本文提出的算法表现良好。但是，在计算资源有限的前提下，优化问题的约束条件越多，所需的辅助种群也就越多，如此平分到每个种群的资源也就随之减少，可能会导致效果略显不足，在DASCMOP1-DASCMOP6中，测试问题的约束条件多达11个，显然本文提出算法在DASCMOP2、DASCMOP4、DASCMOP5中表现较差，然而在DASCMOP7、DASCMOP8、DASCMOP9中测试问题中的约束条件个数为7个，本文所提出的算法效果显著优于其余的算法。因此，在未来的研究中，将进一步改进和优化算法，特别关注处理约束较多情况的问题。