MOEA/D-RDG

A Random-Based Dynamic Grouping Strategy for Large Scale Multi-objective Optimization

A. Song, Q. Yang, W. N. Chen, and J. Zhang, “A random-based dynamic grouping strategy for large scale multi-objective optimization,” in IEEE Congress on Evolutionary Computation. IEEE, Jul. 2016, pp. 468–475.

摘要

提出了一种基于随机的动态分组策略(RDG)，与合作协同进化框架一起来处理大规模多目标优化问题。随机动态分组策略(RDG)是将整个维度分解为若干等大小的变量组

算法

在 RDG 中，不仅每个组中的变量是动态确定的，而且组大小是从一个组大小池中动态选择的

1、RDG

首先，设置一个组大小池（group size pool） S = {s₁, s₂, …, s_k}，包含 K 个不同的组大小；

然后，在每一代开始进化之前，将会从选择池中依概率选择一个分组的大小（size，而不是分组的个数，这是不同的）。公平起见，利用性能提升列表（performance improvement）来确定选择的概率，这反过来又会影响下一代对组大小的选择。这一段很是拗口，原文感受一下（To make a proper choice, we utilize the performance improvement that is caused by the usage of one group size to determine its probability, which in turn influences the selection of this group size in the next generation，但大意就是：分组影响了这一代的性能，根据特定的数学公式，重新计算性能提升列表中各个参数的值，再根据更新后的列表重新选择组的大小）

为了计算每一个组大小的概率，定义了一个性能改进列表 R = {r₁, r₂, …, r_k}，第 i 个分量对应于选择池 S 中的第 i 个组的大小。这个列表 R 用于记录每个组大小导致的相对性能改进。初始时，R 中的每个元素设为 1，表示在初始阶段，每个群体大小的选择概率相等。然后,在进化过程中,使用群体大小的相对性能改进(假设它是 s_i)可以以下面的公式 （1） 计算：
r i = C ( A , B ) = ∣ { u ∈ B ∣ ∃ ν ∈ A : ν ≺ u } ∣ N P N P r_i=C\left( A,B \right) =\frac{|\left\{ u\in B|\exists \nu \in A:\nu \prec u \right\} |}{NP}{NP} ri​=C(A,B)=NP∣{u∈B∣∃ν∈A:ν≺u}∣​NP

在这里 NP 是种群大小，A 和 B 是两个 MOP 的近似 PF。C 这个指标可以不用管，大概知道 C(A,B) 的值在[0,1]内，且 C(A,B)=1 表示 B 中的所有解都被 A 中的某个解支配，C(A,B)=0 表示 B 中的任何解都不被 A 中的某个解支配就行。而根据计算出的性能改进列表 R，可以根据下面的公式 （2） 计算出各组大小 P={p₁, p₂ … p_k} 的概率：

p i = e 7 ∗ r i ∑ j = 1 k e 7 ∗ r j , ( i = 1 , 2 , . . k ) p_i=\frac{e^{7*r_i}}{\sum_{j=1}^k{e^{7*r_j}}},\left( i=1,2,..k \right) pi​=∑j=1k​e7∗rj​e7∗ri​​,(i=1,2,..k)
最后，根据计算的概率，利用轮盘赌轮选择方法从s中选择一个组大小，然后使用随机分组将维度分解成组。

算法 1 给出了提出的RDG的完整过程，如图所示：

用自己的语言解释一下：

1：根据上文的公式（2），计算得出每个 size 被选中的概率

2：使用轮盘赌选择方法从选择池中选择 size

3：依分组的大小，使用随机动态分组方法将整个决策变量分组

---

2、与 MOEA/D 组合

为了简单起见，将提出的 RDG 嵌入 MOEA/D，与 MOEA/DVA 一样，从而得到两种算法之间的公平比较。在此基础上，提出了一种新的 MOEA/D 变体 MOEA/D-RDG，并在算法 2 中给出了完整的算法框架，如图所示：

与 MOEA/DVA 相似，MOEA/D-RDG 的整个过程可以分为三个阶段:

1. 第一阶段（2-4行）：决策变量分析（decision variables analysis）

   通过分析变量的控制性质将变量分为收敛性相关和多样性相关；这一阶段与 MOEA/DVA 相同，可以看作是协同进化的准备阶段

2. 第二阶段（5-13行）：合作协同进化（cooperative coevolution）

   在这一阶段，利用RDG将收敛变量动态划分为不同的组，然后分别对每个组进行演化。CC的过程在这一阶段继续优化收敛变量，直到公式 （3） 中定义的度量低于预定义的阈值或最大的函数评估次数耗尽为止。
   u = ∑ i = 1 N P ∑ j = 1 m ∣ o l d ( i ,   j ) − c u r ( i ,   j ) ∣ N P u=\sum_{i=1}^{NP}{\sum_{j=1}^m{\frac{|old\left( i,\ j \right) -cur\left( i,\ j \right) |}{NP}}} u=i=1∑NP​j=1∑m​NP∣old(i, j)−cur(i, j)∣​

   在这里 NP 是种群大小，m 是目标数；old(i, j) 和 cur(i, j) 分别是第 i 个个体在上一代和当代的第 j 个目标值。这个方程测量连续两代人之间目标值的累积差值。如果该指标小于预先设定的阈值(h)，如 MOEA/DVA 和本文采用的0.01，则表示协同进化无法再进行优化。

3. 第三阶段（14-16行）：统一优化（uniform optimization）

   只有当上述指标小于预定义的阈值且最大的函数评估次数未用尽时，才能执行这一阶段。在这一阶段，所有的决策变量，包括收敛变量和多元变量都使用 MOEA/D 进行统一进化，直到用尽适应度评估次数为止。

用自己的语言解释一下：

1. 第一阶段（2-4行）

   使用 MOE/DVA 中同样的决策变量分析技术，将变量分为多样相关和收敛相关；将多样性相关变量用同一的随机值进行初始化；通过初始化收敛性相关变量来初始化种群

2. 第二阶段（5-13行）

   设置 u = 1，当 u >= h ˄ FE < max_FE 时，循环：使用算法 1 对收敛性变量分组，对分成的每一分组使用 CC 优化，然后用公式（1）更新 R，用公式（3）更新 u

3. 第三阶段（14-16行）

   在不满足终止条件（即最大评估次数）时，循环：使用算法 MOEA/D 同一优化种群（所有变量）

结论

文中的评价：与 MOEA/DVA 相比，MOEA/D-RDG 与 MOEA/DVA 的最终区别在于 MOEA/D-RDG 在 CC 中采用了一种动态分组策略来处理 LSMOP。因此，在分组时不需要特殊的函数求值，导致与 MOEA/DVA 相比，更多的函数求值用于进化。这可能使 MOEA/D-RDG 具有良好的性能。

提出了一种基于随机的动态分组(RDG)的协同进化策略来应对 LSMOP。不同于在固定分组策略中将变量依赖作为全局信息，所提出的 RDG 将变量依赖作为局部信息。不仅每个子组件的维数是动态确定的，而且子组件大小是从RDG中的池中动态选择的。这种选择是建立在历史信息的基础上的，因此群体的规模可以在进化过程中得到适当的确定。

缺点分析

在2016年，这种方法也许是性能很强的，分组方法有了很好的改进方法，毕竟2020提出的 PCA-MOEA，在 UF1-10，WFG1-9 这两个测试集中与本文算法在优势项目的个数上一致。

但从18年往后，就不再使用分组这一方法作为主要手段去处理决策变量了，无论是18年的 CCLSM 快速相互依赖识别（Fast Interdependency Identification、FII）还是20年的 PCA-MOEA 所使用的 主成分分析（principal components analysis 、PCA），20年的 OD-NSGA 所使用的操作分解（operational decomposition、OD）等等，都抛弃了使用多年的传统的变量分组方法。

当然，这不是算法的缺点，是时代的局限。也有一说一，性能比起 MOEA/DVA LMEA 来说还是有很大的提升的~

无图无真相：

在这里可以看到对于 UF 和 WFG测试集还是挺占优的，尤其是后者（MOEA/DVA LMEA）更是拉跨，也许它们存在的意义就是入门学习了吧~

改进的方向嘛，当然是对”落后“的处理变量的方法进行改进啦！基于此，2017年提出的 FII 使用了快速相互依赖识别，仅使用简单的数学公式识别决策变量的相互依赖性，不引入较大的额外计算 <(ˉ^ˉ)>

同样的，位置不够啦，写不下啦，且待下文详谈 (＠￣ー￣＠)