【论文研读】基于对偶种群的约束多目标优化进化算法-补充材料

基于对偶种群的约束多目标优化进化算法-补充材料

Supplementary File of “A Dual-Population based Evolutionary Algorithm for Constrained Multi-Objective Optimization

最近我在学习约束多目标问题的论文，其中由明博士和张教授发表在TEVC上的c-DPEA非常不错~

• 这是正文的补充材料，之所以也想进行研读，是因为其中的有些实验内容能给我们带来一些思考，并能看到CMOPs问题的一些特性
• 点击阅读原文查看TEVC原文章
• 此篇文章为 M. Ming, A. Trivedi, R. Wang, D. Srinivasan and T. Zhang, "A Dual-Population-Based Evolutionary Algorithm for Constrained Multiobjective Optimization," in IEEE Transactions on Evolutionary Computation, vol. 25, no. 4, pp. 739-753, Aug. 2021, doi: 10.1109/TEVC.2021.3066301. 的论文学习笔记，只供学习使用，不作商业用途，侵权删除。并且本人学术功底有限如果有思路不正确的地方欢迎批评指正！

1.FITNESS ASSIGNMENT IN bCAD

• 本节首先显示第 I-A 节中 α 和 (1 - α) 的变化。I-B节中说明排名Rd的计算方式。此外，为了说明 bCAD 中的适应度分配过程，我们提供了两个简单的示例来说明单个群体和组合群体中的候选解决方案如何获得排名，分别如 I-C 节和 I-D 节所示。

1.1 The Variation of α

• α 和（1-α）是用于控制Rc和Rd的权重，这个参数是随着迭代次数进行变化的。其迭代趋势如图1所示

1.2 The Calculation of Rd

Rd的计算分为三个步骤：

1. 将所有候选解与不同的权重向量相关联，见图2（a）和表I中的第1-2列。在这种情况下，关联关系如下：A ∼ w1, B and C ∼ w2, D ∼ w3, E ∼ w5.
2. 对于每个子区域，对于每个解计算gws值并且给予不同的level值，见图2（b）
3. 根据等级数和密度估计值对所有候选解决方案进行排名，见图2（c）和表I中的第4-6列。即首先根据level数对它们进行排序；然后对于同一level的解，再根据密度估计值从小到大进行排序。

1.3 Fitness Assignment for a Single Population

• 示例 ——为了说明使用 bCAD 对单个群体进行适应度分配的过程，我们提供了一个简单的示例来展示单个群体中的候选解决方案如何获得排名。为了简化问题，这里我们将单个种群的大小和权重向量的数量设置为五个。在此示例中，显示了根据 Rc、Rd 和 R 的候选解决方案的排名。请注意，在针对某个指标对解决方案进行排名时，如果两个解决方案在该指标方面具有相同的排名，则它们是随机排名的。
• 接下来，演示在 bCAD 中显示适应度分配的示例。表二列出了根据 Rc、Rd 和 R 三个不同 α 值的候选解的排名。请注意，α用于权衡Rc和Rd的参数。图 3 说明了上述指标排名之间的差异。在图 3 中，根据相应的指标，解颜色越深，越优选。

从表二和图3 中得到以下观察结果。• 解决方案的排名对于不同的指标是不同的，在不同的α 值的情况下也是不同的。• 无论指标如何，解E 都是种群中最好的。

1.4 Fitness Assignment for a Combined Population

• 示例——为了说明使用 bCAD 在环境选择中的适应度分配过程，我们提供了一个简单的示例来展示组合群体中的候选解决方案如何获得排名。请注意，使用 bCAD 对组合种群进行适应度分配总是发生在生成后代种群之后的环境选择中。为了简化问题，这里我们将组合总体中的解决方案数量设置为 10，使上面使用的单个总体的大小增加一倍。相应地，权重向量的数量设置为五个，即与输出总体的大小相同。在此示例中，显示了根据 Rc、Rd 和 R 的候选解决方案的排名。针对一个指标对解决方案进行排名，如果两个解决方案在该指标方面具有相同的排名，则它们被随机排名。
• 在这个例子中，为了说明使用 bCAD 的环境选择过程，我们不仅列出了根据 Rc、Rd 和 R 的候选解决方案的排名，而且还突出了表 4 中每个指标的五个最佳解决方案。图 4 说明了候选解决方案的位置，并突出显示上述指标排名之间的差异，将每个指标的五个最佳解决方案框在蓝色矩形中。类似地，图 4 中解的颜色越深，根据相应的指标越优选。

从表二和图4中我们可以看出：Rc—A,B,C,E 和I 是五个最好的解，此处是根据SPEA2[1]

2. COMPUTA TIONAL TIME COMPLEXITY

• 在本节中，分析了 c-DPEA 的计算时间复杂度。需要注意的是，c-DPEA 中的基本操作与 SPEA2 [1] 中的类似，即非支配排序（用于计算强度值和原始适应度）和密度估计操作。然而，与 SPEA2 相比，c-DPEA 需要在 bCAD 适应度函数中进行更多比较。此外，操作在两个排序过程中执行。此外，bCAD 适应度函数适用于 c-DPEA 中的两个群体。下面讨论细节。

3. PARAMETER SETTING

4.INVESTIGATION INTO BEHAVIOR OF DUAL POPULATIONS IN C-DPEA

• 在这里，我们首先展示了两个 c-DPEA群体在进化过程中针对不同问题的不可行解决方案的数量。图 5 展示了 CTP 和 MW 问题的结果
• 红线和蓝线分别表示population1 和population 2中的不可行解的数量。

• 图 6-图 8 展示了双种群在 MW2、MW5 和 MW13 问题上的互补行为

5. EFFECTIVENESS OF COOPERA TIVE COEVOLUTIONARY APPROACH

• 表四c-SPEA在每个问题中每次迭代后剩下的可行解

6.EFFECTIVENESS OF THE saPF STRATEGY

• 本节用于验证文中使用的罚函数法，因此设计了两个对比算法Alg-saPF-1,Alg-saPF-2,这两种算法分别使用文献[5]和[6]中的罚函数法。
• Alg-saPf-1:它根据解的约束违反及其目标性能来修改不可行解的目标函数值。它有两个重要组成部分：距离度量和自适应惩罚，首先介绍它们以方便理解。

• Alg-saPF-2: 它根据不可行解的约束违反值和目标函数值来修改不可行解的目标函数值，其中一个从当前种群反馈的可行性比率用于保持搜索平衡。具体而言，解 x 的第 k 维的修正目标函数值计算如下：

7. EFFECTIVENESS OF THE bCAD FITNESS FUNCTION

• 为了说明 bCAD 适应度函数的有效性，本节提供了 c-DPEA 及其仅使用 Rc 或 Rd 的变体获得的 GD 和 DM 值，即分别介绍了 c-DPEA-Rc 和 c-DPEA-Rd在论文的 V-D 部分。表 V 总结了 31 次独立运行的 GD 和 DM 结果（包括平均值和标准偏差）。Herein, the non-parametric Wilcoxon-ranksum two-sided comparison procedure [7] at the 95% confidence level is employed to examine whether the results are significantly different or not. The symbol ‘+’, ‘−’, or ‘≈’ means that the corresponding variant is better than, worse than, or comparable to c-DPEA.

8.COMPARISON WITH STATE-OF-THE-ART ALGORITHMS

• 本节提供了 c-DPEA 获得的 HV 值与同行算法在 CTP、MW 和约束 DTLZ 问题上的比较结果。三个测试套件的结果分别总结在表 VI, 表VII和表 VIII 中。

• 为了可视化结果，我们描绘了由C-DPEA和一些代表性CMOPS上获得的对等算法获得的最终解决方案，如图17-30所示

9．REFERENCES

[1] E. Zitzler, M. Laumanns, and L. Thiele, “SPEA2: Improving the strength Pareto evolutionary algorithm,” TIK-report, vol. 103, 2001.

[2] K. Deb, R. B. Agrawal et al., “Simulated binary crossover for continuous search space,” Complex Syst., vol. 9, no. 2, pp. 115–148, 1995.

[3] K. Deb and M. Goyal, “A combined genetic adaptive search (GeneAS) for engineering design,” Comput. Sci. Inform., vol. 26, pp. 30–45, 1996.

[4] K. Price, R. M. Storn, and J. A. Lampinen, Differential evolution: A practical approach to global optimization. Springer Science & Business Media,2006.

[5] Y . G. Woldesenbet, G. G. Yen, and B. G. Tessema, “Constraint handling in multiobjective evolutionary optimization,” IEEE Trans. Evol. Comput., vol. 13,no. 3, pp. 514–525, 2009.

[6] L. Jiao, J. Luo, R. Shang, and F. Liu, “A modified objective function method with feasible-guiding strategy to solve constrained multi-objective optimizationproblems,” Appl. Soft Comput., vol. 14, pp. 363–380, 2014.

[7] M. Hollander, D. A. Wolfe, and E. Chicken, Nonparametric statistical methods. John Wiley & Sons, 2013, vol. 751