现实世界中，受限于资源、环境等因素的约束，实际工程优化中的问题不可避免的是一种带约束条件的多目标（节能、环保、经济等目标）优化问题。目前在学术界，在约束多目标优化方面的研究工作由于其难度大而相对较少。但是随着近几年人工智能技术的日益火热，约束多目标进化算法作为求解优化问题的重要工具，国内外对其的关注也越来越多。
一直以来，带约束条件的多目标优化进化算法方面的研究是汕头大学人工智能与机器人实验室的一个特色，近年来在约束多目标优化方面也取得了一系列重要进展。在约束多目标进化算法性能的测试问题方面，针对现有约束多目标测试问题的不足，定义了一类难度可控，目标和约束数量可调的约束多目标测试问题集[1]。在约束处理机制方面，针对现有约束处理机制难以维持种群多样性的缺点，提出了一种基于角度约束支配的方法（Angel-based constraint domination principle，ACDP）[2]。针对现有约束处理机制收敛性不足的问题，提出一种改进的ε约束处理方法（An Improved Epsilon Constraint-handling Method）[3]。此外，针对现有约束多目标进化算法的不足，提出了一种基于Push和Pull机制的搜索框架（Push and Pull Search，PPS）。通过研究[4][5][6]，我们发现PPS是一种非常具有潜力的用于求解约束多目标优化问题的框架，其中的Push和Pull搜索过程都可以进行自由定制，从而衍生出一系列的约束多目标进化算法。目前我们分别在2种基于分解的框架中实现了PPS算法，包括PPS-MOEA/D[4]和PPS-M2M[5]，两种算法被用来求解一个实际的示教机械臂优化问题，与没有采用PPS框架的算法相比，基于PPS框架的算法具有更好的收敛性和多样性[6]。充分说明PPS不仅是一个求解约束多目标优化问题的很好的理论框架，而且对于求解实际的工程优化问题也非常有效。
具体而言，在《Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit》[1]中，我们首次对约束问题的难度类型进行了定义，提出了三种难度的约束类型，即多样性困难、可行性困难和收敛性困难。三种难度类型的约束能够任意组合，构成同时具有多种难度类型的约束多目标测试问题。每种约束类型的难度都可以自由调整，问题可以进行自由定制，能够全面综合评估约束多目标进化算法在单一难度或多种难度下的性能。
1. 多样性困难的约束：
图1 多样性困难的约束函数
2. 可行性困难的约束：
图2 可行性困难的约束函数
3. 收敛性困难的约束：
图3 收敛性困难的约束函数
三种难度类型的约束类似于颜色中的三原色，它们之间能够任意组合，生成7种基本难度类型的约束（如图4(a)和表1所示）。每种约束类型的难度大小都可以自由调整，可构造各种难度等级的约束多目标测试问题（如图4(b)所示）。
图4 难度类型和难度等级示意图
此外，所提出的难度可调、目标和约束可扩展的约束多目标测试问题构建框架（如下图所示）还可以构造约束高维目标（目标个数大于等于4）优化问题。
图5 难度可调、目标和约束可扩展的约束多目标测试问题构建框架
一直以来，约束多目标优化的难点之一是如何在保持多样性和收敛性的同时进行高效的约束处理。由美国密歇根州立大学Kalyanmoy Deb教授提出的约束支配原则CDP已经得到广泛的应用。在CDP原则中，约束违反较小的解总是比约束违反较大的解要好，但这会带来一个问题。如果种群中绝大部分的解是不可行解，那么按照CDP原则，大多数个体的适应值排序将只会按照约束违反的大小来排序，这样在进入下一代的过程中，种群的多样性会急剧下降。
为了克服这一难题，在《MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems》[2]一文中，我们提出了一种基于角度约束支配的方法ACDP，可概括为三条规则：
（1）当两个比较的解都为可行解时，根据Pareto支配规则判断两解的支配关系。
（2）当两个比较的解至少有一个是不可行解时，如果这两个解在目标空间中的角度小于θ（给定参数），约束违反值小的解支配另一个解。
（3）当两个比较的解至少有一个是不可行解时，如果这两个解在目标空间中的角度大于θ，以概率 pf（其值等于当前种群可行解的比例）视两解为可行解，同时根据规则1判断两解支配关系，以概率 1-pf 视两解互不可比。
图6. MOEA/D框架下的ACDP定义
所提出的约束处理机制ACDP在MOEA/D框架下进行了实现，在14个基准测试问题和一个工程（和 I 型焊接梁）优化问题上，与6种当前最好的约束多目标进化算法（CMOEAs）对比（见图7）。ACDP算法在IGD指标方面比其他当前最好的算法提升一定数量级（见图8），在保持种群的收敛性、多样性和可行性方面更具优势，充分体现了所提出的约束处理机制ACDP的有效性。
图7. 6种不同算法在4个测试问题上得到的非支配解集
图8. MOEA/D-ACDP和其他6种算法在IGD指标上的对比结果
此外，在《An Improved Epsilon Constraint-handling Method in MOEA/D for CMOPs with Large Infeasible Regions》[3]一文中，针对最初的ε约束方法对具有较大不可行区域的约束多目标优化问题并不适用的问题，提出了一种改进的ε约束处理方法（An Improved Epsilon Constraint-handling Method）（见图9）。它根据当前总体中可行解的比例动态调整ε(k)的值，以平衡可行区域与不可行区域的探索。与最初提出的ε约束方法相比，它能够在进化过程中增加ε(k)的值，可有效的跨越较大的不可行区域，帮助算法获得收敛性更好的Pareto解集。
图9. 改进的ε约束处理方法
所提出的改进的ε约束处理方法嵌入MOEA/D框架下进行了实现，即MOEA/D-IEpsilon。在包括LIRCMOP1-14（不可行区域较大）在内的14个基准测试问题和机器人抓取优化问题上，与MOEA/D-Epsilon, MOEA/D-SR, MOEA/D-CDP和C-MOEA / D四种约束多目标进化算法对比（见图10）。实验结果表明，在所有测试实例上，MOEA/D-IEpsilon明显优于其他4种算法，在IGD指标方面同样优于其他当前最好的4种算法（见图11），充分说明了MOEA/D-IEpsilon适合求解具有较大不可行区域的约束多目标优化问题。
图10. 五种不同算法在4个测试问题上得到的非支配解集
图11. MOEA/D-IEpsilon和其他4种算法在IGD指标上的对比结果
现有的约束多目标优化算法通常是先搜索可行区域再寻找最优，但是在遇到具有多个大的不可行区域时，现有的算法往往会陷入局部最优，无法跨越多个不可行区域。在《Push and Pull Search for Solving Constrained Multi-objective Optimization Problems》[4]一文中，我们提出了一种Push和Pull的搜索框架（PPS）。具体而言，PPS采用从无约束Pareto前沿反向搜索约束Pareto前沿的思想，从而有效克服了传统约束多目标进化算法无法跨越多个不可行区域的难题。PPS算法把整个搜索过程分为Push 和 Pull两个阶段。在Push阶段，采用多目标进化算法（MOEA）在不考虑约束的情况下探索整个搜索区域，从而有助于快速的跨越不可行区域，得到无约束的Pareto前沿。此外，约束违反程度的信息也能够被探测和估计。在Pull阶段，采用某种约束处理机制并利用探测到的约束违反信息，把整个种群拉回到可行的非支配区域。
图12. Push和Pull的搜索框架图解
在PPS框架下我们提出了两种算法：1） PPS与Multi-objective evolutionary algorithm based on decomposition（MOEA/D）方法相结合的约束多目标进化算法（PPS-MOEA/D）[4]，它的主要思想是在Push阶段它把多目标优化问题分解成若干个单目标优化问题，并以协同的方式同时对它们进行优化，使种群收敛到无约束Pareto前沿，在Pull阶段，利用IEpsilon约束处理机制使种群拉到可行且非支配区域；2）PPS与multi-objective to multi-objective （M2M）分解方法相结合的约束多目标进化算法（PPS-M2M）[5]，它的主要思想是将一个带约束的多目标优化问题分解为一组简单的带约束的多目标优化子问题。每个简单的子问题对应一个子种群，并以协同的方式解决。在搜索阶段，每个子种群都遵循PPS搜索机制，帮助每个工作子种群跨越不可行区，收敛到可行且非支配区域。
PPS-MOEA/D和PPS-M2M主要特点如下：
1) PPS-MOEA/D和PPS-M2M使用不同分解方法。在PPS-M2M中，采用M2M分解方法将带约束的多目标（CMOPs）优化问题分解为一组简单的CMOPs，而PPS-MOEA/D将CMOP分解为若干个单目标优化问题。
2) PPS-M2M和PPS-MOEA/D使用不同的选择策略。在PPS-M2M中，将非支配排序方法和IEpsilon约束处理方法[6]相结合来选择下一代个体，PPS-MOEA/D将分解方法和IEpsilon约束处理方法[6]相结合来选择下一代个体。
3) 尽管PPS-M2M和PPS-MOEA/D都是有效的约束多目标进化算法，但它们适用于求解具有不同特性的CMOPs（见图13）。PPS-M2M更适合求解目标函数不平衡、约束函数具有多样性困难的CMOPs，而PPS-MOEA/D更适合求解具有较大的不可行域的CMOPs（见图14）。
图13. 四种算法在CIMOP2上获得的Pareto前沿。我们可以观察到，PPS-M2M可以找到大部分的Pareto前沿。然而，其他三种算法只能找到部分Pareto前沿或者不能找到Pareto前沿。
图14. 十一种算法在LIR-CMOP7上获得的Pareto前沿。我们可以观察到，PPS-M2M和PPS-MOEA/D可以找到大部分的Pareto前沿。其他九种算法只能找到部分Pareto前沿或者不能找到Pareto前沿。
此外，采用基于PPS框架的两种约束多目标进化算法PPS-MOEA/D和PPS-M2M对示教机械臂设计优化问题进行求解[6]，获得了比人类工程师设计更优的设计方案（见图15）。同时通过与几种经典的约束多目标进化算法（MOEA/D-ACDP, MOEA/D-CDP, NSGA-II-CDP 以及 CM2M）进行对比，采用PPS框架，可以有效的提升对应算法在解决机器人优化的性能（见图16）。
图15. 获得的Pareto前沿上的四个端点个体与工程师设计方案对比图
图16. 6种算法在示教机械臂优化中进行30次独立重复实验中具有最佳HV值的非支配解集
通过以上研究，我们发现PPS是一个非常具有潜力的约束多目标问题求解框架，其中的Push和Pull搜索过程都可以进行自由定制，从而衍生出一系列的约束多目标进化算法。目前，该项工作已经受到加拿大阿尔伯塔大学Witold Pedrycz教授（进化计算领域的权威，SCI一区期刊Information Science杂志主编），Ponnuthurai Nagaratnam Suganthan教授（进化计算领域的权威，SCI一区期刊Swarm and Evolutionary Computation杂志主编）团队的关注和引用。基于上述工作，我们相信PPS将成为求解约束多目标优化问题的一个标杆性框架，在连续约束多目标优化领域，一些新提出的约束多目标优化算法也将不可避免的要在其基础上进行改进或与其进行对比。
参考文献：
[1] Z. Fan, W. Li, X. Cai*, H. Li, C. Wei, Q. Zhang, K. Deb, & E. Goodman. “Difficulty Adjustable and Scalable Constrained Multi-objective Test Problem Toolkit,” Evolutionary Computation, https://doi.org/10.1162/evco_a_00259, 2019.
[2] Z. Fan, Y. Fang, W. Li, X. Cai*, C. Wei, and E. Goodman, “MOEA/D with angle-based constrained dominance principle for constrained multi-objective optimization problems,” Applied Soft Computing, vol. 74, no. 1, pp. 621-633, 2019.
[3] Z. Fan, W. Li, X. Cai*, H. Huang, Y. Fang, Y. You, J. Mo, C Wei, and E. D. Goodman, “An improved epsilon constraint-handling method in MOEA/D for CMOPs with large infeasible regions,” Soft Computing, vol. 23, no. 23, pp. 12491–12510, 2019.
[4] Z. Fan, W. Li, X. Cai, H. Li, C. Wei, Q. Zhang, K. Deb, and E. Goodman, “Push and pull search for solving constrained multi-objective optimization problems,” Swarm and Evolutionary Computation, vol. 44, no. 2, pp. 665-679, 2019.
[5] Z. Fan, Z. Wang, W. Li, Y. Yuan, Y. You, Z. Yang, F. Sun and J. Ruan, Push and pull search embedded in an M2M framework for solving constrained multi-objective optimization problems, Swarm and Evolutionary Computation, vol. 54, p. 100651, 2020.
[6] Z. Fan, Y. You, X. Cai∗, H. Zheng, G. Zhu, W. Li, A. Garg, K. Deb, E. Goodman. "Analysis and Multi-objective Optimization of a Kind of Teaching Manipulator," Swarm and Evolutionary Computation. vol. 50, p. 100554, 2019.
|
