多种群约束多目标优化算法的资源分配指标设计

Resource Allocation Indicator Design of Multi-Population-Based Constrained Multi-Objective Optimization Algorithm

摘要: 本文研究基于多种群的约束多目标优化算法的种群间资源分配问题。本文提出了一个新的指标来衡量种群资源的合理分配。所提出的指标根据不同种群的变化及进化代数，为不同种群分配进化资源。它根据种群中理想点和最差点的变化，来衡量该种群的变化。所提出的指标被嵌入到一个先进的多种群约束多目标算法。在实验中，通过在20个基准函数的数据实验，本文展示了所提出指标可以有效地为不同种群分配资源。

Abstract: In this paper, we study the problem of resource allocation among multiple populations on multi-populations-based constrained multi-objective optimization algorithm. This paper proposes a new indicator to measure the allocation of population evolutionary resources. The proposed indicator allocates evolutionary resources for different populations according to the changes of different populations and evolutionary generations. It measures the change of the population according to the change of the ideal point and the nadir point in the population. The proposed indicator is embedded into an advanced multi-population constrained multi-objective algorithm. In the numerical experiment, this paper shows that the proposed indicators can effectively allocate resources for different populations on 20 benchmark functions.

1. 引言

进化约束多目标优化算法被认为是处理约束多目标优化问题的有效方法 [1] 。近年来，许多进化约束多目标优化算法被提出并被运用到工业和学术界等 [2] [3] 。其中，使用多个种群的混合算法展现出了显著的效果 [4] 。例如，C-TAEA [5] 使用了两个种群协同探索，一个种群以收敛性为指导进行搜索，使得种群逼近Pareto前沿，另一个种群以多样性为指导搜索未被第一个种群搜索过的空间，以此来保证多样性。新个体由两个种群杂交变异产生。ICMA [6] 提出了一个新的指标来衡量个体对探索有前景区域的贡献值。在ICMA中，一个工作种群通过保存贡献值最大的一些个体来尽可能地均匀探索整个目标空间，另一个归档种群通过保存搜索到的精英有效解进行归档。新个体在进化前期更多的由工作种群产生，而后期则更多的由归档种群产生。CCMO [7] 提出一种协同进化框架，一个种群以求解原问题为目标进行优化，另一个种群以求解从原问题提取出来的协助问题为目标进行优化。两个种群分开独立产生个体，并在种群更新时交换信息。

尽管先前的基于多种群的混合算法在求解约束多目标优化问题时展示出了强大的效果，但种群间资源的分配只是简单的平分或者根据进化代数变化。在进化过程中根据不同的优化问题的特征进行种群间资源的合理分配问题仍鲜有研究。然而，合理地分配种群间的资源，可以有效地提高算法的效率。

为了处理多种群间资源的分配问题，本文提出了一种基于种群变化的指标来识别优化问题的特征，从而动态地分配资源。在进化过程中，种群的变化由一定代数的理想点和最差点的变化来衡量。所提出的指标根据种群间的变化的差异，在不同进化阶段以不同程度的更多的资源投入到变化较大的种群中。本文的主要贡献包括以下几点：

1) 计算每个种群的理想点和最差点的变化，以它们的差异来识别问题的特征，从而更好地指导不同问题不同种群需要的资源；

2) 根据不同种群的差异，以及当前进化的阶段，设计一个新的指标。在一个先进的多种群混合优化算法上根据指标实现动态的种群间资源分配；

3) 广泛的实验验证了所提指标的有效性。

本文的其余部分如下。第二节介绍了所提出的指标。第三节介绍了实验和结果，并对其进行了分析。第四节为本文进行了总结。

2. 所提的框架

2.1. 种群变化的衡量

本文使用理想点和最差点的变化来衡量种群变化。不失一般性，本文考虑以下约束多目标：

$\{\begin{array}{l}\text{minimize}F\left(x\right)={\left(f_1\left(x\right),\cdots ,f_m\left(x\right)\right)}^{\text{T}}\\ \text{subjectto}{g}_i\left(x\right)\ge 0,i=1,\cdots ,q\\ h_j\left(x\right)=0,j=1,\cdots ,p\\ x\in {ℝ}^n\end{array}$ (1)

则第t代种群 $P^t=\left\{x_1^t,x_2^t,\cdots ,x_N^t\right\}$ 中，理想点 $Z^t=\left\{z_1^t,z_2^t,\cdots ,z_m^t\right\}$ 和最差点 $n^t=\left\{n_1^t,n_2^t,\cdots ,n_m^t\right\}$ 的定义分别为：

$z_i^t={\min }_{j=1,2,\cdots ,N}{f}_i\left(x_j\right)$ (2)

$n_i^t={\max }_{j=1,2,\cdots ,N}{f}_i\left(x_j\right)$ (3)

在第t代，理想点的变化 $c{z}_t$ 和最差点的变化 $c{n}_t$ 由当前进化代数t与最近的k代分别定义：

$c{z}_t={\max }_{i=1,2,\cdots ,m}\left\{\left|z_i^t-z_i^{t-k}\right|/\left|z_i^{t-k}\right|\right\}$ (4)

$c{n}_t={\max }_{i=1,2,\cdots ,m}\left\{\left|n_i^t-n_i^{t-k}\right|/\left|n_i^{t-k}\right|\right\}$ (5)

种群的变化由理想点的变化和最差点的变化定义为：

$c{p}_t=\max \left\{c{z}_t,c{n}_t\right\}$ (6)

2.2. 所提的资源分配指标

假设两个种群P₁和P₂，本文使用上述种群变化的衡量两个种群在第t代的变化分别为 $c{p}_t^1$ 和 $c{p}_t^2$ 。在进化第t代，本文提出的基于种群变化的资源分配比例为：

$R=\left(1+1/c{p}_t^1\right)/\left(1+1/c{p}_t^2\right)\times t/T_{\max }$ (7)

其中 $T_{\max }$ 为最大进化代数。根据资源分配比例，种群P₁和P₂的后代产生个数分别为：

$N_1=R\times N$ (8)

$N_2=\left(1-R\right)\times N$ (9)

所提出的资源分配的指标具有以下两个特点：

1) 当种群P₁的比例变化比P₂较大时，更多的资源倾向于分配给P₁，即P₁产生并评估更多的后代；反之，则P₂产生并评估更多的后代。

2) 进化的前期更倾向于分配更多的资源给P₂，进化的后期更偏好于将更多的资源分配给P₁。

2.3. 所提的算法

本文将所提的资源分配指标运用于双种群约束多目标优化算法CCMO上，动态地分配基于以求解原问题为目标的种群的资源和以求解从原问题提取出来的协助问题为目标的种群的资源。我们令以求解原问题为目标的种群为P₁，令以求解从原问题提取出来的协助问题为目标的种群为P₂，即进化前期更倾向于保证算法的收敛性，而进化的后期更强调种群的可行性和多样性。算法1为所提算法的框架。在第t代，如果t大于等于k，则开始计算种群的变化，并根据种群的变化和当前所在代数，即公式(8)和(9)计算每个种群所产生的后代数目。在选择阶段则通过从所产生的所有后代及种群选择个体更新种群。最后输出以求解原问题为目标的最终种群P₁。

算法1. 所提算法的框架

3. 数据实验与分析

3.1. 参数设置

1) 种群规模 $N=100$ ；

2) 最大进化代数 $T_{\max }=500$ ，相隔代数 $k=5$ ；

3) 统计检验：我们使用显著性水平为0.05的Wilcoxon秩和检验来对算法进行比较，符号“−”、“=”和“+”表示所提算法优于、相似和低于其他算法，表格中突出显示的为每行的最佳结果；

4) 对比算法的参数设置与它们各自的原文保持一致。

3.2. 基准函数和对比算法

本文选用DC_DTLZ [5] 系列和MW [8] 系列作为约束多目标优化问题的基准测试函数。另外，本文选择了4种目前先进的CMOEA，即TiGE₂ [9] 、ToP [10] 、I-DBEA [11] 和CCMO进行性能比较。对比算法的主要思想如下：

1) TiGE₂：它旨在平衡种群的多样性、收敛性和可行性。因此它分别为这三种性能设计了三个指标。基于设计的三个指标，提出了一种用于求解CMOP三目标进化框架。

2) ToP：它是一种简单的两阶段约束多目标进化算法。第一阶段用于寻找有希望的可行区域；第二阶段使用现有的CMOEA迫使种群收敛到可行区域的帕累托前沿界面。它在处理目标空间和决策空间都有约束的优化问题上表现良好。

3) I-DBEA：它是一个可行驱动的约束多目标进化算法。它通过参数 $\epsilon$ 来扩大可行解的范围，即违反约束程度小于 $\epsilon$ 的个体也被视为可行解。因此它可以充分利用不可行解携带的有效信息，帮助种群穿越不可行带，从而加速算法的收敛。

4) CCMO：它提出一种双种群的协同进化框架。它将无约束的优化问题作为辅助问题，来帮助解决原始问题。两个种群可以信息共享，共同促进种群的进化。

3.3. 算法性能度量指标

反转世代距离(Inverted Generational Distance, IGD) [12] 和超体积(Hypervolume, HV) [13] 是两种常见的算法性能评价指标。本文选用这两个指标来评估约束优化算法的性能。IGD和HV的具体介绍分别如下：

1) IGD：设 $P^{\ast }$ 是一组已知，并且均匀分布在PF上的点集，X是使用算法所求得的最优解集。则X的IGD值可以由以下公式计算：

$\text{IGD}\left(P^{\ast },X\right)=\frac{{\displaystyle \underset{v\in P^{\ast }}{\sum }d}\left(v,X\right)}{\left|P^{\ast }\right|}$ (10)

其中 $d\left(v,X\right)$ 表示点v到集合X的最小距离， $\left|P^{\ast }\right|$ 是集合 $P^{\ast }$ 的规模。IGD值越小，说明算法的性能越好。

2) HV:HV测量的是可行解集X和参考点z所围成区域的超体积。HV值可以由下列公式计算：

$\text{HV}\left(X|z\right)=\text{VOL}\left({\displaystyle \underset{x\in X}{\cup }\left[f_1\left(x\right),z_1\right]\times \cdots \times \left[f_m\left(x\right),z_m\right]}\right)$ (11)

其中 $\text{VOL}(\ast )$ 是用于测量体积的度量指标。参考点z一般由每个目标上的最大函数值的1.1倍组成，因此PF上的任意一个可行解都可以支配参考点z。HV值越大，说明算法的性能越好。

3.4. 所提的算法表现分析

Figure 1. Initial, intermediate and late performance of CCMO and proposed algorithm on DC3_DTLZ1

图1. CCMO和所提算法在DC3_DTLZ1上的初、中和后期表现

其中，红色种群为以求解原问题为目标的种群，蓝色种群为以求解从原问题提取出来的协助问题为目标的种群，黑色边界为真实PF。

本节在一个测试问题DC3_DTLZ1上展示所提的算法的表现。图1展示了CCMO和所提的算法在DC3_DTLZ1上初期，中期和后期的种群分布。从图1可以看出，所提算法具有更高的效率探索到真实的PF。在初期，种群距离PF非常远，此时以求解从原问题提取出来的协助问题为目标的种群(蓝色种群)快速逼近PF，从而更多的资源分配给它，此时根据我们提出的指标得到红色种群和蓝色种群的资源分配比为1:9，算法更加考虑收敛性。到了进化的中期，尽管种群距离PF仍然比较远，但是此时以求解从原问题提取出来的协助问题为目标的种群(蓝色种群)变化的速率下降，根据所提的指标，此时红色种群和蓝色种群的资源分配为3:7，算法同时考虑收敛性和可行性。到了进化的后期，两个种群都已经非常接近PF，此时所提的指标将更多的资源放在了以求解原问题为目标的种群(红色种群)上，红色种群和蓝色种群的资源分配为7:3。到了进化的后期或者两个种群都很接近各自的PF时，所提算法更强调在以求解原问题为目标的种群上分配资源，从而保证种群的可行性和多样性。

3.5. 所提的算法在基准函数上的表现

Table 1. IGD average value of the five algorithms on test instances

表1. 5个算法在测试实例上的IGD平均值

本节将所提的算法与四个对比算法在基准函数上进行比较。每个算法在基准函数的每个测试问题上独立运行三十遍。表1和表2分别展示了五个算法在每个测试问题上的所求IGD和HV的平均值。其中，若三十次独立实验都没有求解到可行解，则记为“NaN”。同时，我们对每个对比算法在每个测试问题上与所求算法进行了统计检验。从表1和表2可以看到，所提算法在20个测试问题上明显优于原双种群约束多目标优化算法CCMO，在IGD和HV上分别都有9个更优的表现。这个结果是符合我们所期望的，因为所提的算法与CCMO使用相同的选择算子，并在种群的资源分配上进行了优化。这使得所提的算法能够更有效的求解约束多目标优化问题。

另外，在IGD上，所提的算法在20个测试问题上分别在10个、19个和18个上优于对比算法TiGE₂、ToP和I-DBEA。在HV上，所提的算法在20个测试问题上分别在8个、20个和18个上优于对比算法TiGE₂、ToP和I-DBEA。这是因为所提算法保存了CCMO算法的优势，同时，资源的更优分配保证了所提的算法的有效性。

Table 2. HV average value of the five algorithms on test instances

表2. 5个算法在测试实例上的HV平均值

4. 总结

考虑到基于多种群的约束多目标优化算法在进化过程中不同种群的变化不同，并且指导其各自进化的原则不同，需要在不同进化阶段对不同种群进行合理的资源分配。本文通过每个种群的变化及当前所在的进化代数，设计了资源分配的指标。根据所提的指标，每个种群产生不同数目的后代。另外，本文将所提的指标运用于一个双种群的约束多目标优化算法上。数据实验结果显示了所提的算法能够更有效地分配种群的资源，从而在不同的测试问题上表现优于四个现有的先进的约束多目标进化算法。