进化算法求解约束优化问题研究进展

转载自 https://www.researchgate.net/publication/323942977_jinhuasuanfaqiujieyueshuyouhuawentiyanjiujinzhan

摘 要：约束优化问题是科学研究和工程实践中普遍存在的一类优化问题，因而如何对约束优化问题进行求 解具有十分重要的理论意义和实际应用价值。约束优化进化算法的核心是约束处理技术，而如何平衡约束 条件和目标函数又是设计约束处理技术的关键。因此，根据平衡约束条件和目标函数方式的不同，本文对 常用的约束处理技术进行了分类并分析了其工作原理，并且对所对应的约束优化进化算法的最新研究进展 进行了介绍。最后指出了该领域值得进一步研究的方向。

进化算法是模拟自然界生物进化的一类基于群 体的优化算法。相比于常规的确定性优化方法，进 化算法对优化问题的先验知识依赖程度较低；相比 于单点的随机搜索算法，基于群体（包含多个个体） 搜索的进化算法具有更强的鲁棒性。由于具有这些 优势，近年来进化算法已被广泛应用于求解约束优 化问题。求解约束优化问题的进化算法称为约束优 化进化算法。如图 2 所示，约束优化进化算法包含 进化算法和约束处理技术两部分。进化算法从父代 群体出发产生子代群体；约束处理技术本质上是比 较准则，它基于约束条件和目标函数比较个体的优 劣，并从父代群体和子代群体中选择优秀个体进入 下一代群体。约束优化进化算法的最终目的是找到 可行域中的最优解（如图 1 所示）。

事实上，可以从平衡约束条件和目标函数的角 度出发来分析约束处理技术的工作原理。如图 3 所 示，对于由约束违反程度 G 和目标函数 f 构成的二 维空间，任意一个个体 x 可将其分为 I、II、III 和 IV 4 个区域。显然，区域 III 中个体的约束违反程度和目标函数值都优于个体 x，该区域中的个体包 含了有用的约束条件信息和目标函数信息；区域 I 中个体的约束违反程度和目标函数值都劣于个体 ， 该区域中的个体几乎不包含有用信息；区域 II 中个 体的约束违反程度优于而目标函数值劣于个体 x， 该区域中的部分个体包含了有用的约束条件信息；区域 IV 中个体的目标函数值优于而约束违反程度 劣于个体 x，该区域中的部分个体包含了有用的目 标函数信息。一般来说，绝大多数约束处理技术认 为区域 III 中的个体优于个体 x，区域 I 中的个体劣 于个体 x。而不同的约束处理技术的主要区别体现 在如何利用区域 II 和 IV 中的有用信息。如果约束 处理技术过多地偏好区域 II 而忽略区域 IV（也即 过多地偏好约束条件），可能造成以下后果：① 群 体迅速朝大的可行域靠近，容易忽略一些小的可行 域，而最优解可能位于某些小的可行域内部；② 对 于一些包含简单约束条件的约束优化问题，群体迅 速进入可行域，往往忽略了可行域边界上的解，而 最优解可能位于可行域的边界上；③ 对于一些包含 复杂约束条件的约束优化问题，由于选择压过大， 群体很容易过早地收敛于不可行域，从而导致最终 无法找到可行解。此外，如果不充分利用区域 II 中 的信息也可能引发以下问题：由于缺少有效的引导， 群体难以找到可行解。因此，如何有效利用区域 II 中的约束条件信息和区域 IV 中的目标函数信息是 设计约束处理技术的关键所在，它涉及到约束处理 技术设计的核心——如何有效平衡约束条件和目标 函数。正是围绕这一核心，近 20 年来，研究人员 提出了大量的约束处理技术，其大致可分为 5 类：

① 惩罚函数法；② 约束和目标分离法；③ 多目标优化法；④ 混合法；⑤ 其他方法。

本文第二部分围绕约束条件和目标函数的平衡 这一核心对上述 5 类约束处理技术的工作原理进行 了深入剖析，并且简要介绍了所对应的约束优化进 化算法的最新研究成果 ; 第三部分指出了约束优化 进化算法值得进一步研究的方向 ; 最后对全文进行 了总结。

约束处理技术原理和相关约束优化进化算法研究进展

惩罚函数法

图 4 所示，斜线下方的个体被认为优于个体 x，斜 线上方的个体劣于个体 x。斜线下方由区域 III、区 域 II 的一部分、区域 IV 的一部分共同组成。值得 注意的是，惩罚系数越大，斜线越陡，包含区域 II 的信息（也就是约束条件的信息）越多，包含区域 IV 的信息（也就是目标函数的信息）越少；反之， 则包含约束条件的信息越少，包含目标函数的信息越 多。因此惩罚系数决定了对约束条件信息和目标函数 信息的利用程度。过大和过小的惩罚系数都会对算法 产生不利影响。如何调节惩罚系数来达到约束条件和 目标函数的平衡是此类方法的一个公开问题。

最初，惩罚函数法通常采用定常的惩罚系数。随后，研究人员发现，不同的优化问题或者同一 优化问题的不同优化阶段所需的惩罚系数都可能不 同。鉴于此，大量的调节方法被提出。根据惩罚系 数调节方式的不同，惩罚函数法大致可分为以下 3 类（如图 5 所示）。

(1) 静态惩罚函数法：惩罚系数保持不变。例 如，在使用静态惩罚函数法处理约束条件的基础上， Hernández et al[7] 使用混合差异进化算法和爬山算 法作为搜索算法；文献 [8] 提出了一个两阶段的免 疫算法求解具有混合变量的约束优化问题。

(2) 动态惩罚函数法：惩罚系数随进化代数变 化。例如，在文献 [9] 中，惩罚系数沿着一条事先 设计好的 S 型曲线从小到大非线性变化。前期使用 较小的惩罚系数，促进群体的勘探；后期采用较大 的惩罚系数，促进群体的开采和收敛。

(3) 自适应惩罚函数法：惩罚系数根据群体反 馈信息进行调节。例如，Kusakci et al [10] 结合改进 的协方差矩阵自适应进化策略 [11] 和自适应惩罚函数 来求解约束优化问题。Ali et al [12] 自适应调节惩罚系 数，并从理论上分析了调节方式的可行性。文献 [13] 根据粗糙集理论，利用群体进化信息自适应调节惩 罚系数。文献 [14] 根据“最好的可行解转换后仍然 最好”这一原则推导出最小的惩罚系数，随后，惩 罚系数设置为一个稍大于该最小惩罚系数的值。

约束和目标分离法

与惩罚函数法将约束条件和目标函数叠加起来 不同，约束和目标分离法将约束条件和目标函数分 开处理。使用这类方法比较个体时，一般先比较个 体的约束违反程度，当约束违反程度满足一定条件 时，再比较个体的目标函数值。如图 6 所示，这类 方法主要有可行性准则、随机排序法、ε 约束法 3 种。

(1) 可行性准则

可行性准则是由 Deb[15] 提出的一种简单有效的 约束处理技术，它采用以下 3 条准则比较两个个体。

●　可行个体和不可行个体，前者占优；

●　两个可行个体，目标函数值好的个体占优；

●　两个不可行个体，约束违反程度小的个体占优。

可行性准则认为区域 II 和 III 中的个体无条件 优于个体 x（如图 7 所示）。其优势在于原理简单、 执行方便，但是对约束条件信息的过度利用和对部 分目标函数信息的忽略，导致算法容易出现以下问 题：① 由于过分关注于快速进入可行域，使得进入 可行域的方向比较单一；② 当存在多个可行域时， 容易忽略小的可行域；③ 对于最优解位于可行域边 界的约束优化问题，常常忽略对可行域边界的探测。

在基于可行性准则求解约束优化问题时，研究 人员通常将重心放在搜索算法的设计上，并试图通 过提高搜索算法的性能，弥补可行性准则的不足。例如，文献 [16-19] 将改进后的差异进化算法作为 搜索算法。Dhadwal et al[20] 将改进后的粒子群优 化算法作为搜索算法。文献 [21-24] 对其他基于群 体的优化算法进行了改进，并将其用作搜索算法。除此之外，有些方法还通过引入目标函数的信息来 缓解可行性准则的贪婪性。例如，文献 [25] 将被可 行性准则淘汰的区域 IV 中的个体存档，并采用替 换策略将优秀的存档个体引入到群体。通过以上操 作可以有效引入目标函数的信息，达到约束条件与 目标函数的平衡。

（2） 随机排序法

随机排序法 [26] 由 Runarsson 和 Yao 提出。意 识到可行性准则的贪婪性，在比较两个个体时，随 机排序法以概率 pf 比较目标函数值，以概率（1-pf） 比较约束违反程度。如图 8 所示，当 rand（一个 [0,1] 之间均匀分布的随机数）小于预先设定的参数 pf 时， 区域 III 和 IV 中的个体被认为优于个体 x；当 rand 大于或等于 pf 时，区域 II 和 III 中的个体被认为优 于个体 x。显然，pf 决定了对约束条件信息和目标 函数信息的利用程度，也决定了二者之间的平衡。当 pf=0 时，随机排序法退化成可行性准则。为了减 少对 pf 的敏感性，Runarsson 和 Yao 引入了冒泡 排序对群体进行排序选择。通过以一定的概率引入 目标函数的信息，随机排序法能够在一定程度上缓 解可行性准则的贪婪性。

最初的随机排序法 [26] 使用进化策略作为搜索 算法。近年来，研究人员将它与其他搜索算法结合 起来。例如，文献 [27] 使用差异进化算法作为搜索 算法，使用随机排序法对目标向量和试验向量组成 的群体排序；文献 [28] 结合差异进化算法和随机排 序法求解纳什均衡问题；文献 [29] 使用粒子群优化 算法作为搜索算法，每代更新完个体位置后，利用 随机排序法从中选出一部分个体，再使用选出的个 体产生新的群体；文献 [30] 结合蚁群算法和随机排 序法求解约束优化问题。

（3） ε 约束法

ε 约束法 [31] 是另一种具有代表性的约束和目标 分离法。当比较两个个体 xi 和 xj 时，ε 约束法首先

多目标优化法

多目标优化法通常把一个约束优化问题转换成 形如

的多目标优化问题 ,或者形如

的双目标优化问题。由于前者 的求解难度远高于后者，所以转换成双目标的形式 是目前的主流。在上述转换的基础上，当比较两个 个体时，满足以下任一条件，个体 xi 优于个体 xj ：

考点。通过使用不同的权值向量和参考点，该方法 可以在约束条件和目标函数之间达到平衡。文献 [6] 提出了 CW 算法，该算法分析了不可行解的重要意 义，提出了一种不可行解存档与替换机制，通过发 挥不可行解的作用，引导群体快速朝可行域逼近。而且，CW 还阐述了非劣个体的重要性，并采用子 代群体中的非劣个体替换父代群体中的劣于个体， 提高了群体搜索最优解的能力。更进一步，文献 [34] 从多目标优化的角度出发，进一步完善不可行解存 档与替换机制，提出了 CMODE 算法。CMODE 缓 解了 CW 对参数的依赖性，可同步改善群体质量 和可行性。此外，文献 [35] 设计了由全局搜索模 型和局部搜索模型组成的混合进化搜索框架，并与 基于多目标优化的约束处理技术相结合，提出了 HCOEA 算法。为了进一步优化 HCOEA 的执行效 率、合理分配进化过程中的计算资源，DyHF[36] 利 用群体可行解比例这一进化反馈信息，动态执行全 局搜索模型和局部搜索模型。

混合法

受“没有免费的午餐”定理（No Free Lunch Theorem）[37] 的启发，研究人员提出了大量的混合 约束处理技术，以期能够实现更好的性能。例如， Deb et al[38-40] 将多目标优化法和惩罚函数法结合 起来求解约束优化问题；Cai et al[41] 提出了一种 memetic 算法，该算法分别采用自适应函数值法和 非支配排序法 [42] 比较个体；Li et al[43] 提出了一种 自适应约束人工蜂群算法，在该算法中，根据可行 性准则进行选择的雇佣蜂负责全局搜索，根据多目 标优化法进行选择的观察蜂负责局部搜索；Wang et al[44-45] 将整个约束优化过程划分为不可行阶段、 半可行阶段和可行阶段 3 个阶段，不可行阶段使用 多目标优化法处理约束条件，半可行阶段使用自适 应惩罚函数法处理约束条件。

其他方法

除了以上 4 类主要的约束处理技术外，还有一 些特征不是很明显的约束处理技术，本文将其归结 为其他方法。文献 [46] 使用一种名为约束一致性 （Constraint Consensus）的投影方法引导不可行 解朝可行区域靠近。文献 [47] 专门为协方差矩阵 自适应进化策略 [11] 提出了一种约束处理技术。文 献 [48] 通过在等式约束边界产生大量解来处理约 束条件。

以上根据平衡约束条件和目标函数方式的不 同，对约束处理技术的原理和相关的约束优化进化 算法进行了综述。各种约束处理技术的总结对比如 表 1 所示。从以上介绍不难看出，如何求解约束 优化问题仍然是进化计算领域的一个研究热点和难 点。下面给出简要总结：① 目前很多算法仍使用 惩罚函数法处理约束条件；② 可行性准则由于简 单易实现等优点，受到了研究人员的青睐；③ ε 约 束法是一种有效的约束处理技术，值得一提的是， εDE[49] 和 εDEag[31] 分别是 IEEE CEC2006 和 IEEE CEC2010 约束优化竞赛的冠军；④ 多目标优化为 约束处理提供了全新的视角，多目标优化法展示了 优异的性能；⑤ 混合法大多采用多目标优化法作为 其重要组成部分 [38-41,43]，这可能是混合法未来的一 个发展趋势；⑥ 在约束优化中，差异进化算法是目 前最频繁使用的搜索算法 [7,12,14,16-19,31,41]。

进化约束优化是一个庞大繁杂的研究领域， 篇幅所限，本文不可能囊括所有的约束处理技术 和相关的约束优化进化算法，感兴趣的读者可以 参考文献 [25,50-51]。

未来研究趋势和发展方向

进化约束优化虽然取得了显著进展，我们认为 以下几个方面还值得深入研究。

约束多目标优化

现实生活中存在着大量的约束多目标优化问 题。在进化计算领域，无约束多目标优化和约束单 目标优化均得到了深入研究，然而，约束多目标优 化却没有受到足够重视。

在测试函数方面，2001 年，Deb et al [52] 提 出了一套约束多目标优化测试函数，简称为 CTP1- CTP7。这套测试函数已成为里程碑工作，极大地 促进了约束多目标优化的发展。2008 年，Zhang et al [53] 提出了一套新的测试函数。此外，文 献 [54-55] 对 CTP 系列测试函数进行了改进。但 是这些测试函数都存在可行域比例较大的问题。因 此，如何设计能够体现约束多目标优化问题多面特 征的测试函数是目前面临的一个基本问题。

在对约束多目标进化算法进行性能比较时，通 常采用的是无约束多目标优化中的 IGD[56] 和 HV[57] 两种性能指标。但是，如何设计能够充分体现约束 多目标进化算法性能差异的指标还没有得到研究人 员的重视，例如直接使用 IGD 和 HV 就能客观地反 映性能差异？

在算法设计方面，目前大多数约束多目标优化 进化算法将之前介绍的约束处理技术直接应用或仅 做相应修改，对约束多目标优化问题的本质缺乏深 入研究。而且，如何将约束优化与多目标优化有机 结合，如何平衡进化算法的勘探与开采能力等都没 有展开深入探讨。

动态约束优化

动态约束优化问题在实际应用中十分常见。文 献 [58] 通过对 56 个实际动态优化问题的研究发现， 绝大部分动态优化问题属于动态约束优化问题。目 前，在进化计算领域，动态约束优化的研究尚处于 初期阶段。

在测试函数方面，2012 年，Nguyen et al[59] 构造了一套测试函数集。然而，该测试函数集仅包 含 2 个决策变量，在可扩展性方面存在一定的缺陷。因此，目前亟需一套能够反映实际动态约束优化问 题性质的测试函数集。基于进化算法求解动态约束优化问题时，应同 时设计搜索算法和约束处理技术。而且，它们还应 具备识别环境变化、跟踪最优解的能力。目前，研 究人员对如何设计面向动态约束优化问题的搜索算 法和约束处理技术缺乏深入探讨。

昂贵约束优化

在实际应用中，有些优化问题的评估非常耗时， 这类问题称为昂贵优化问题。使用进化算法求解这 类问题时，需要使用模型对其进行近似。研究人员 对昂贵无约束优化问题进行了广泛研究 [60]。然而， 实际优化问题往往带有约束条件。目前，昂贵约束 优化在进化计算领域很少受到研究人员的关注。相 比于昂贵无约束优化问题，求解昂贵约束优化问题 的难度大大增加。

在测试函数方面，目前绝大多数文献均采用常 规的约束优化测试集 [63] 进行性能测试。在测试过 程中，首先假设常规的约束优化测试集就是昂贵约 束优化问题；接着在尽可能少地评估真实目标函数 和约束条件的情况下，搜索最优解。很明显，常规 的约束优化测试集并不能有效反映实际昂贵约束优 化问题的特征。所以，收集实际的昂贵约束优化问 题，或者设计新的测试函数集是这个领域需要解决 的首要问题。

设计面向昂贵约束优化问题的进化算法也面临 了巨大的挑战。在模型选择方面，需要考虑的问题 有：约束条件和目标函数是否可以使用同一模型近 似？不同的约束条件使用相同模型还是不同模型进 行近似？近似模型采用回归模型还是分类模型？此 外，如何设计适合于昂贵约束优化问题的约束处理 技术和搜索算法？以上几个方面都需要深入思考。

理论研究

目前，进化算法求解约束优化问题的理论基础 还非常薄弱。文献 [64] 对多目标优化法进行了理论 分析，证明了多目标优化法在两类约束布尔优化问 题上优于惩罚函数法。文献 [65] 对进化算法求解约 束优化问题的运行时间进行了理论分析。文献 [66] 分析了不可行解在进化约束优化中的作用。整体而 言，该领域亟需更多的理论分析来指导算法设计， 例如需要从理论上分析各种约束处理技术的优势和 适合求解的约束优化问题类型等。

结束语

本文从平衡约束条件和目标函数的角度出发， 对不同约束处理技术的原理进行了分析，并对相关 的约束优化进化算法的研究进展进行了介绍；最后 对未来的研究趋势和发展方向进行了展望。