工程应用优化问题多数存在各种各样的条件限制, 即约束条件, 该类问题一般被称为约束优化问题. 一个拥有n个变量和m个优化目标的约束优化问题可以定义为如下形式:
| $ \left. \begin{gathered} { ext{min}}:\;\;F(X)=\{ {f_k}(X)|k=1, ..., m\} \hfill \\ { ext{s}}{ ext{.t}}{ ext{.}}\;\;{g_i}(X) \leqslant 0, \;i=1, ..., p \hfill \\ \;\;\;\;\;{h_j}(X)=0, \;j=1, ..., w \hfill \\ \;\;\;\;\;X=({x_1}, {x_2}, ..., {x_n})\; \hfill \\ \;\;\;\;\;X \in {R^n} \hfill \\ \end{gathered} \right\} $ | (1) |
其中, F为目标优化函数集合, g和h分别表示问题的不等式约束和等式约束函数, 当m > 1时, 表示该问题为多目标优化问题; Rn为问题搜索空间, n为问题的维度, 当n值较大时(例如n≥100[1]), 问题一般被认为是高维优化问题或者大规模优化问题; p为不等式约束条件的个数, w为问题的等式约束个数. 近年来, 进化算法结合约束处理技术被广泛应用于约束问题优化, 同时提出了不同类型的约束处理技术. 基于处理机制的不同, 这些方法被分为惩罚函数法、可行性法则、随机排序法、ε-约束处理法、多目标优化法、混合法等, 相关技术的详细介绍与讨论可查看综述文献[2]. 文献[2]从约束处理机制本身的区别出发, 重点讨论了各种约束处理技术的原理和优缺点, 但较少讨论实际工程问题本身的复杂性造成的约束处理挑战. 此外, 该综述发表于2017年, 近几年来, 进化约束处理技术有着很大发展. 立足于工程实际问题本身的复杂性对约束处理技术的影响, 对近年来约束处理技术进行论述, 将对该领域的发展有着重要的意义.
工程应用中, 约束优化问题的复杂性主要表现在优化目标和约束场景两个方面.
● 优化目标的复杂性主要表现在目标的个数、目标变量的维度、目标评估的计算开销等. 例如: 当约束优化问题存在多个优化目标时, 即问题是多目标约束优化问题时, 单一采用传统的约束处理技术(例如惩罚函数法、可行解更优法、随机排序法等)将无法满足应用需求. 多目标优化的目标是获得均匀分布在Pareto前沿的最优解集, 而不是约束优化问题期望获得的最优可行解. 不同的优化目标使得方法需要的推动种群进化的机制需求不同, 而约束处理是该进化机制设置的核心问题. 此外, 问题的约束条件会造成Pareto前沿形状和位置完全改变, 且分布于多个可行区域, 这将造成种群更易困在部分区域, 无法获得均匀分布的Pareto前沿. 由此可知: 为了保持进化算法求解多目标约束问题的高效性, 必须研发相对应的约束处理技术;
● 约束场景复杂性主要表现在可行区域的大小、形状、是否连续等. 例如: 当约束优化问题存在等式约束时, 等式约束将使得解空间的可行解区域极度缩小, 很大程度上减少了优化方法获得可行解的可能性. 此外, 即使算法可以获得可行解, 面对狭小的可行区域, 算法在可行区域中搜索仍然是困难的, 这将使得算法更容易陷入局部最优.
本文根据引发约束优化处理复杂性缘由的不同, 将面向复杂约束优化问题的进化算法分为面向复杂目标的进化约束优化算法和面向复杂约束场景的进化算法两大类.
基于进化算法的复杂约束优化具体分类见表 1. 表中对复杂目标和复杂约束场景优化进行了细化和简单介绍. 面向复杂目标的进化约束优化算法分为多目标约束优化、大规模约束优化、高计算开销约束优化, 其主要从问题的优化目标个数、问题的维度、问题目标的评估代价方面考虑. 面向复杂约束场景的进化算法分为等式约束优化、平衡约束优化、普适约束优化, 其主要考虑到约束特性引发的可行区域大小、多样以及与目标的差异等对约束优化问题求解的挑战. 相关问题的简要描述可查看表 1. 基于上述分类, 本文综述了《IEEE Trans. on Evolutionary Computation》、《Evolutionary Computation》、《IEEE Trans. on Cybernetics》、《IEEE Trans. on Systems Man Cybernetics-systems》、《Expert Systems with Applications》、《Knowledge-based Systems》、《Information Sciences》、《Congress on Evolutionary Computation (CEC)》、《软件学报》、《计算机学报》、《计算机研究与发展》、《电子学报》等国内外重要期刊与会议关于约束处理的近5年的相关研究成果, 其中包括2017年5篇、2018年11篇、2019年17篇、2020年11篇、2021年20篇. 面向复杂约束优化的进化算法研究近年来备受关注并快速发展, 并且越来越受到重视, 为其在实际工程应用提供了扎实的理论基础. 本文首先分别对面向复杂目标的进化约束优化算法和面向复杂约束场景的进化算法进行了介绍, 其中包括问题描述、解决方案、挑战等. 并在此基础上, 本文最后对该领域的发展趋势进行了总结和论述.
|
表 1 复杂约束优化问题分类与描述 |
本文第1节介绍面向复杂目标的进化约束优化算法. 第2节介绍面向复杂约束场景的进化算法. 第3节对未来发展趋势进行论述. 最后总结全文.
1 面向复杂目标的进化约束优化算法目前, 在进化约束研究领域, 面向复杂目标的进化约束优化算法可分为3类: 多目标约束优化、大规模约束优化、高计算开销约束优化.
1.1 多目标约束优化多目标优化是工程应用中普遍存在的优化问题[14?16], 且这些问题优化中往往存在各种约束条件, 这类问题被称为多目标约束优化问题(constrained multi-objective optimization problems, CMOPs). CMOPs既包含相互冲突的目标函数, 又包含各种各样的约束条件. 约束条件将搜索空间分为不同的可行区域与不可行区域, 使得Pareto最优解分布在多个可行区域, 种群极易困在某个区域内, 这极大地增加了优化方法获得均匀分布的Pareto最优解的难度. 同时, 约束条件使得Pareto前沿(Pareto front, PF)的形状和位置完全不同于无约束场景的(如图 1所示). 如何平衡收敛性、多样性和可行性三者之间的关系, 成为面向CMOPs的进化算法设计所面临的主要挑战[17, 18]. 与单目标相比, 多目标进化算法的优化目标是获得均匀分布在Pareto前沿的可行的Pareto最优解集, 而不是最优可行解. 优化目标的不同, 使得传统的约束处理技术应用到多目标优化存在局限性. 面对这个挑战, 近年来国内外学者进行了广泛研究, 这些研究可分为基于多种群的方法、基于排序的方法、基于分阶段的方法、改进的ε约束处理技术以及其他方法(见表 2).
|
图 1 多目标约束优化示意图 |
|
|
表 2 面向多目标约束优化的进化算法分类与描述 |
(1) 基于多种群的方法.
基于多种群的方法主要通过设计多个种群, 各个种群负责不同的优化任务, 同时彼此协同, 最终获得分布在不同可行区域的均匀的Pareto最优解集. 例如: Liu等人[19]将种群分为一个主种群和一个归档集种群, 主种群采用约束支配原则促使种群进入可行区域, 同时逼近可行区域边缘的Pareto前沿, 而归档集种群向不可行区域的Pareto前沿优化, 同时采用非支配解排序方法来保持种群的多样性, 同时, 算法采用一种选择机制来协调主种群和归档种群之间的相互作用; Peng等人[20]在采用进化算法进行优化CMOPs优化时, 设计了两个子种群, 一个用于探索可行区域, 另一个用于探索整个问题搜索空间; Tian等人[21]在主种群之外添加了一个辅助种群, 主种群面向原始CMOP进行优化, 辅助种群用于优化从原始CMOP提取出来的部分优化目标和约束条件, 同时, 通过在两个种群之间共享有用的信息来提高算法性能; Wang等人[22]提出了一种协同进化框架, 该框架中给每个目标在约束条件下设计一个子种群进行优化(M个子种群), 同时采用一个种群收集存储这些子种群的非支配解, 用这些解来引导子种群向Pareto前沿搜索.
(2) 基于排序的方法.
文献[23]为了实现约束和目标的平衡, 它分别对个体进行基于约束优势(“可行性”)和不考虑约束的Pareto优势(“最优性”)排序, 然后, 基于这两个排名和当前种群的可行比例重新对个体的适应度值进行定义, 个体i的具体定义如下所示:
| $ fi{t_i}=\alpha R_i^C + (1 - \alpha )R_i^P $ | (2) |
其中, α=0.5+0.5Pfea,
| $ {f_{fitness}}(X)={f_{rank}}(X) + \frac{{{f_{cv}}(X)}}{{{f_{cv}}(X) + 1}} $ | (3) |
其中, frank(X)为非支配解排序, 而fcv(X)为个体的约束违约度.
(3) 分阶段的方法.
分阶段的方法通过将进化过程分阶段来协调可行区域和不可行区域的搜索. Tan等人[3]通过自适应调节约束和目标的优化权重来使得算法具有在离散的可行区域间跨越的能力, 同时将进化过程分为两个阶段: 第1阶段设置相同的约束和目标优化权重, 从而使得种群可以进入可行区域; 第2阶段约束权重小于目标优化权重, 从而种群可以保持多样性并向可行区域边缘搜索. Liu等人[25]引进了目标约束和决策约束的概念, 同时提出了一种两阶段优化框架: 在第1阶段中, 将多个目标加权转换为单目标, 同时考虑约束条件(其定义如公式(4)所示), 算法中该阶段的操作使得种群搜索到位于Pareto前沿中心位置的Pareto最优解以及可行区域; 而第2阶段采用普通的多目标约束优化方法, 使得种群分散于Pareto前沿:
| $ \left. \begin{gathered} \min \;f(X)=\sum\limits_{i=1}^m {{f_i}(X)} \hfill \\ { ext{s}}{ ext{.t}}{ ext{. }}{g_j}(X) \leqslant 0, { ext{ }}j=1, ..., l \hfill \\ \;\;\;\;{ ext{ }}\;{h_j}(X)=0, { ext{ }}j=l + 1, ..., n \hfill \\ \;\;\;\;{ ext{ }}X={({x_1}, {x_2}, ..., {x_n})^T} \in {R^n} \hfill \\ \end{gathered} \right\} $ | (4) |
(4) 改进的ε约束处理技术.
ε-约束法是缓解算法陷入单个可行区域的有效方法, 在很多约束多目标优化算法中广泛使用. 文献[26]将ε-约束法与基于分解的多目标优化方法相结合, 算法优化过程中, 多目标约束优化问题转换为如下加权优化问题:
| $ \left. \begin{array}{l} P1: \min { ext{ }}{f_{main}}={ ext{ }}{f_s}(X) + \rho \sum\limits_{i=1}^m {{f_i}(X)} \\ { ext{ s}}{ ext{.t}}{ ext{. }}\left\{ {\begin{array}{*{20}{l}} {\frac{{{f_i}(X) - z_i^*}}{{z_i^{nad} - z_i^*}} \leqslant {\varepsilon _i}, { ext{ }}\forall i \in \{ 1, 2, ..., m\} /\{ s\} } \\ {X=({x_1}, {x_2}, ..., {x_n}) \in {R^n}} \end{array}} \right. \\ \end{array} \right\} $ | (5) |
其中, ρ是权重因子;
(5) 其他方法.
除了上述方法, 相关研究学者也从解的质量定义、PF形状、种群多样性等方面来解决约束多目标优化问题. 例如, 文献[4]引入了期望可行区域的概念, 并对多目标约束个体的质量进行了新的定义, 具体定义如下:
| $ I({\mathit{\boldsymbol{x}}^i}|{\mathit{\boldsymbol{x}}^j})=\left\{ {\begin{array}{*{20}{l}} {\log CV({\mathit{\boldsymbol{y}}^i},{\mathit{\boldsymbol{y}}^j}),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{if }}\;{g^i}=0,{g^j}=0,}\\ {\infty ,\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{ if }}\;{g^i}=0,{g^i} e 0,}\\ {\log CV({\mathit{\boldsymbol{y}}^i},{\mathit{\boldsymbol{y}}^j}),{\rm{ }}\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{if }}\;{g^i} e 0,{g^j}=0,}\\ {\max \left( {{d^{CV}}({\mathit{\boldsymbol{y}}^i},{\mathit{\boldsymbol{y}}^j}),\log \frac{{{g^j}}}{{{g^i}}}} \right),{\rm{ otherwize}}} \end{array}} \right. $ | (6) |
| $ I({\mathit{\boldsymbol{x}}^i}|\mathit{\boldsymbol{X}})=\mathop {\min }\limits_{{\mathit{\boldsymbol{x}}^j} \in \mathit{\boldsymbol{X}}\backslash {\mathit{\boldsymbol{x}}^i}} I({\mathit{\boldsymbol{x}}^i}|{\mathit{\boldsymbol{x}}^j}) $ | (7) |
其中, gi表示第i个个体的违约度; CV(yi|yj)是一个基于比率的价值函数; I(xi|xj)越大, 表明个体质量越好. 该定义被应用到了基于分解的多目标进化算法. 文献[30]提出了一种约束优化和Pareto优化协同处理的机制, 在该算法过程中, 如果种群中没有可行解, 种群向低约束违约度领域进化; 否则, 算法不考虑个体约束违约情况. 此外, 采用一个外部归档集来保存可行解, 并参与种群的个体更新, 从而提高种群的分布. 文献[31]将约束多目标优化问题的PF分为3种主要类型: 全部、部分和没有约束的PF组成. 并且, 针对每种可能的类型, 定制了一种机制来处理约束和目标之间的关系, 包括约束优先级、目标优先级或它们之间的切换. 文献[32]提出了一种基于多样性距离测度的目标空间修正机制, 从而可以更有效地利用好不可行解以寻找最优解; 同时, 采用推拉搜索自适应地调整Pareto前沿的位置, 避免种群被卡在局部最优或局部可行区域, 从而提高种群的多样性. Zhu等人[33]提出了一种新的基于分解的约束多目标进化算法, 算法采用两类权重向量, 分别针对收敛性和多样性: 收敛权向量相关的解仅考虑聚合函数来更新, 以便自由搜索整个搜索空间; 而多样性权向量通过同时考虑聚合函数和整体约束违约度来更新, 使得可以围绕目前发现的可行区域进行搜索. 当一段时间内多样性权向量没有发生变化时, 相应的多样性权向量将被转移到收敛的多样性权向量. 然后, 所有的解最终都会在可行区域周围搜索, 从而有助于找到更可行或更好的解.
从上述研究可知: 当前, 国内外学者面向CMOPs的进化算法进行了广泛的研究, 并提出了多样可行的方法. 这些方法分别从搜索算子、优化阶段、解的评估等角度出发, 重点关注了以下3个问题: 如何避免Pareto最优解集陷入局部可行区域、如何使得Pareto最优解均匀分布于不规则的可行区域、如何收敛于位于可行区域边缘的Pareto最优解. 面向CMOPs的进化算法在以下问题上值得深入研究.
1) Pareto最优解在离散可行区域背景下的均匀分布定义. 根据当前拥挤距离的定义, 目前研究中, 通常大的可行区域分布较多的Pareto最优解, 而小的分布少量Pareto最优解, 甚至没有. 而在实际工程应用中, 不同可行区域往往有着不同的优化权重. 当前基于拥挤距离的Pareto最优解显然不能满足该种需求;
2) 面向CMOPs的约束处理技术的通用性. 当前, 面向CMOPs的约束处理技术大多从多个角度出发进行设计, 与所提出方法的搜索算子捆绑紧密, 通用性不足;
3) 面向可行区域极少情况下的CMOPs的进化算法. 目前研究通常考虑一般情况下的收敛性、多样性和可行性三者之间的平衡, 缺少对极端情况下的讨论与研究.
1.2 大规模约束优化大数据计算时代, 大部分优化问题变量具有上百维度和广泛多样的约束条件, 其求解方法是当前工程应用的迫切需求, 例如卫星设计优化(292维)、耦合航空推进设计优化(316维)等[34]. 大规模约束优化问题(large- scale constrained optimization problems, LSCOPs)面临着大规模优化的维度灾难问题和约束条件复杂化搜索空间问题的双重挑战. 大规模优化背景下, 约束处理的关键问题已不仅仅是目标与优化之间的平衡、约束带来的空间离散使得算法更易陷入局部最优等. 约束条件使得传统的面向无约束大规模优化的方法应用到LSOPs求解面临着最大的挑战. 例如基于分解的方法(目前面向大规模无约束优化最热门的方法之一)[35?38], 其基本原理是将大规模优化问题分解为若干个子问题, 使得各个子问题可以采用现有进化算法进行求解. 如何进行变量分组, 是基于分解的方法求解大规模优化问题的关键, 即希望分解后子问题变量间的关联性越低越好. 但是随着约束条件的考虑, 也就意味着约束条件中变量间的依赖关系也需考虑, 这极大地降低了该类方法的实用性. 当前, 面向LSCOPs的进化优化方法研究得相对较少, 其研究进展主要体现在测试集和约束技术应用方面.
在约束优化测试集方面, 传统约束优化方法使用的标准测试集通常由CEC 2006和CEC 2010会议所提供, 提供的测试集包含的测试问题的维度从2到30维. 该测试集显然不能满足LSCOPs问题的测试需求. 在此背景下, 国防科技大学的伍国华等人[39]在CEC 2017中设计了维度可扩展的约束问题的基准测试函数, 并且考虑了目标与约束的可分性和旋转特性, 目前广泛使用的最高维度是100维; Sayed等人[5]设计了一个拥有18个大规模约束测试问题的测试集, 该测试集合考虑了子问题间重叠和依赖关系, 维度通常设置为100、500、1 000维; 此外, 2021年, 哈尔滨工业大学的罗文坚教授等人[6]对CEC 2010和CEC 2017测试集进行了扩展, 设计了12个LSCOPs测试函数, 其中考虑了可分、不平衡、重叠等问题. 从上述可知: 面向LSCOPs的测试问题目前还不够丰富, 也是该领域研究发展不得不面临的一个问题.
目前, 在面向LSCOPs优化的进化算法研究中, 所提方法主要考虑如何改进面向无约束的大规模优化方法, 使之适应LSCOPs优化场景. 文献[5]提出了面向LSCOPs的变量交互识别技术(variable interaction identification for constrained problems, VIIC), 该技术为问题目标和每个约束确定最佳的变量分组, 在分组过程中引进了频率矩阵, 其中, 频率记录了在N次分组优化中, 各个维度分配到各个子问题的频率. 在各个子问题的约束处理中, 算法采用了可行解优先策略. 文献[40]为了提高变量分组的效率, 对VIIC技术进行了改进, 在该改进技术中, 首先只对单个变量分组, 同时提出了启发式方法用于产生新的分组, 而不是原来的随机生成. 实验结果显示, 改进方法具有更好的表现. Aguilar-Justo等人[1]将协同进化策略引入到模因算法框架以优化LSCOPs, 其中, 采用基于问题分解的方法和Hooke-Jeeves法来引导算法局部搜索(称之为局部协同搜索策略), 采用DE/rand/1/bin策略进行全局搜索. 此外, 算法采用了可行解优先策略进行约束处理. 文献[41]将大规模无约束领域的合作协同进化粒子群优化算法(CCPSO)与ε约束处理技术相结合. 在算法优化过程中, 采用传统的基于随机分组的合作协同进化框架, 同时, 基于不同的随机分组方式提出了3种不同的算法, 分别为ε CCPSOd、ε CCPSOw和ε CCPSOw2. 文献[6]提出了一种约束-目标合作协同进化框架, 它考虑到约束的模块化特性, 即在可行区域内各模块间不相关联, 该特性使得问题可以分解并逐个优化. 所提出的算法考虑到各个模块对寻找到可行区域的影响不同, 即有的模块可行区域少(寻找困难), 有的大(寻找容易), 算法根据影响的不同投入不同的计算资源. 在具体进化过程中, 各个组件对目标和约束的影响进行了定义; 此外, 在问题分解过程中, 将多个约束条件当作一个整体, 即只要变量在其中一个约束中存在关联性, 改组变量就当作相关联, 而不是文献[5]中基于频率矩阵的方法; 并在具体的进化过程中采用了ε约束处理技术.
目前, 在大规模进化优化领域, 大多研究学者针对无约束大规模优化问题, 而面向LSCOPs的进化优化研究还处于开始阶段. 在CEC 2017面向约束优化问题的竞赛中, 大多数优化方法在多个100维度的COPs中无法获得可行解. 传统的面向无约束大规模优化的进化算法由于其自身应用限制往往无法获得期望的优秀表现. 根据LSCOPs自身的特点与限制, 设计针对性的优化框架和约束处理技术, 或者平衡大规模和约束处理复杂性, 提出可优化更高维度的LSCOPs可能是当前研究值得探索的方向.
1.3 高计算开销约束优化高计算开销约束优化问题(expensive constrained optimization problems, ECOPs)面临着目标函数与约束的高昂计算开销. 近年来, 基于代理的进化算法(surrogate assisted eas, SAEAs)被广泛应用于求解无约束的高计算开销优化问题(expensive unconstrained optimization problems, EUOPs)[7, 42]. SAEAs的基本原理是, 建立一个低计算开销的代理模型来模拟原来计算开销昂贵的目标函数. 目前, 已有较多模型应用于求解EUOPs, 包括人工神经网络、支持向量机(SVM)、多项式回归函数、高斯过程等. 在进化过程中, 模型与目标函数如何协作, 也是该类研究的重要问题之一. 此外, 如何进行SAEAs与约束处理技术的深入融合, 也是求解ECOPs不得不考虑的一个问题[43]. 目前已有较多研究针对该问题进行探讨, 接下来我们将一一进行简要介绍.
文献[8]提出了一种基于局部和全局代理的约束进化算法, 算法将进化过程分为两个阶段: 全局代理阶段和局部代理阶段. 在全局代理阶段, 采用广义回归神经网络对DE算法产生的个体进行评估, 并基于可行解优化原则(用于寻找可行区域)和不确定性原则(减轻代理不准确带来的影响)进行候选个体的选择; 在局部代理阶段, 结合了内点法和径向基函数来提高算法的收敛速度. 在上述过程中, 为了识别每个约束条件的结构和边界, 该算法对每一个约束条件都采用代理进行评估.
文献[44]提出了一种面向包含等式和不等式约束ECOPs的算法, 算法提出了一种个体生成机制和两个局部代理: 个体生成机制利用历史精英解集与当前种群进行信息交换; 在局部搜索阶段, 引导当前种群向可行区域移动, 以减轻代理在约束边界上的不准确性给算法带来的影响.
文献[45]提出了一种针对ECOPs的多惩罚和多局部代理的进化算法, 算法中采用不同的约束惩罚系数将ECOPs定义为多个子问题, 然后给每个子问题设计一个局部代理, 其子问题定义如公式(8)所示, 问题数量为N, λi为惩罚因子. 该算法通过该这种方法来保持种群的多样性, 使得算法可以从不同方向逼近可行解, 且局部代理相对全局代理构建开销少, 减少了算法的计算开销:
| $ \left. \begin{gathered} \min { ext{ }}F(X|{\lambda _i})=f(X) + {\lambda _i}G(X) \hfill \\ { ext{s}}{ ext{.t}}{ ext{. }}X \in {{\mathit{\Omega}} _i} \hfill \\ {\lambda _i}=\bar \lambda - (i - 1)\frac{{\bar \lambda - {緻line \lambda } }}{{N - 1}}, { ext{ }}i=1, ..., N \hfill \\ \end{gathered} \right\} $ | (8) |
Rahi等人[46]提出了面向包含不等式约束ECOPs的部分评估的约束处理策略. 考虑到实际工程应用中很多问题的约束条件彼此具有独立性, 在优化过程中, 直到存在约束情况就停止. 该方法可以减少约束计算次数, 从而降低计算开销. 此外, 该方法考虑了不同场景下各约束的优化评估排序, 例如: 在只有不可行解的情况下, 各个个体根据各约束违约情况从高到低加以排序.
文献[47]在求解包含不等式约束ECOPs时, 提出了一种基于代理的分类协作差分进化算法. 该算法将当前种群划分为两个子种群, 同时设计了一种分类协同突变操作, 利用好的解中的有用的信息和坏的解中隐藏的潜在信息, 生成多个有希望的候选解; 然后, 利用代理(径向基函数RBF)来确定最有希望的子代解, 用以加快收敛速度. 此外, 考虑到由于优秀解的信息过多而导致种群多样性降低, 提出了一种基于自适应调整迭代信息的全局搜索算法.
当前, 面向ECOPs的进化算法研究主要考虑如何进行SAEAs与约束处理技术的融合, 而在约束代理方面采用简单的单个代理或者多个代理方式. 该领域的研究依然面临着众多挑战, 例如: 代理的精度问题, 该问题一直困扰着SAEAs, 而约束条件的考虑, 无疑使得该问题更加严重[42]; 等式约束的代理问题, 目前较多研究中大多针对不等式约束问题, 目前尚未有高效的代理来近似等式约束, 尤其是非线性等式约束等[8, 45].
2 面向复杂约束场景的进化算法当前, 约束处理技术面临着复杂约束场景, 例如可行区域离散、比例少、多样形状等, 所带来的挑战. 本文从等式约束优化、平衡约束优化、普适约束优化以及其他一些方面, 对近年来的研究成果进行了总结分析.
2.1 等式约束优化等式约束使得解空间的可行解区域极度缩小, 很大程度上减少了优化方法获得可行解的可能性. 算法即使可以获得可行解, 但由于其在狭小的可行区域中搜索困难, 或可行区域的不连续等因素, 极易造成算法陷入局部最优. 面对等式约束的特殊性, 近年来, 较多学者进行了针对性的研究, 这些研究可分为基于容差参数设置的方法、基于局部搜索的方法、基于等式函数特征的方法等(见表 3).
|
|
表 3 面向等式约束优化的进化算法分类与描述 |
基于容差参数设置的方法是处理等式约束最传统的方法, 该类方法中, 将等式约束条件添加容差参数转换为不等式约束条件来处理, 如下所示:
| $ {g_j}(\vec x)=|{h_j}(\vec x)| - \delta \leqslant 0, \;j=m + 1, ..., p $ | (9) |
其中, δ为容差参数. 该方法扩展了可行区域, 但该种转换将使得可行域的拓扑结构发生变化. 该种方法当容差参数过大时, 全局最优解将发生改变; 而过小时, 算法又寻找可行解困难. 为此, 动态调节容差参数, 成为处理等式约束的方法之一. 文献[48, 49]根据算法迭代次数对δ值从0.001局部减少至0.000 4, 其定义如下:
| $ {\delta _j}(t + 1)=\frac{{{\delta _j}(t)}}{{1.00195}} $ | (10) |
其中, δj为j代的δ值. Ho等人[50]提出了一种按比例缩小的容差参数设置方法, 该方法在当前容差参数可以寻找到可行解时, 就按比例缩小, 直到该参数缩小到最小值, 具体定义如下:
| $ {\delta _j}=B imes \max (|{h_j}(\vec x)|) $ | (11) |
B为缩小比例, B的取值范围为0到1. 文献[51]将约束容忍度参数和惩罚因子随种群进化进行动态调整, 避免了人工调节约束容忍度参数的困难, 同时也实现了约束容忍度参数自适应地进化, 有效地提高了求解等式约束优化问题的效率. 该类方法通过设置容差参数, 逐步引导种群搜索到可行解, 缓解了等式约束背景下可行解区域太少而使得算法无法找到可行区域的问题. 但该参数的设置受到过多因素的干扰, 从而很难使得一种设置方案在很多问题上都是高效的.
基于局部搜索的方法也是当前处理等式约束问题时备受欢迎的方法之一, 该类方法通过对可行区域进行局部搜索来实现快速获得优秀可行解的目的. 文献[9]提出了一种基于迭代局部搜索的粒子群算法, 用于求解等式约束优化问题. 该算法对最优个体的领域进行局部搜索, 使得算法可以快速收敛. 该算法在多个等式问题求解中表现较好. Ullah等人[52]改进了基于agent的进化算法, 使其可以优化等式约束优化问题. 其基本思想是: 从现有个体出发寻找到一个可行解, 然后搜索该可行区域, 从而达到获得可行最优解的目的. 相关类似的解决方案也出现在文献[53]中, 在该方案中, 对各个等式约束条件分别进行优化. 其基本思路是: 随机选择一个等式约束条件和个体, 如果个体不满足该等式约束条件, 则选择个体的一个变量进行调整; 否则, 选择两个变量进行搜索. 该方法在特定形式的等式约束优化场景中表现出了较好的效果. 文献[54]基于二次函数近似非线性等式约束, 同时采用迭代投影算法将部分解投影到近似的约束曲面上(类似局部搜索); 此外, 将满足约束违约度的优化个体重新插入种群(起到修复种群的作用). 该方法不需要额外的计算, 仅仅利用了种群的历史信息. Spettel等人[55]提出了一种协方差矩阵自适应进化策略, 算法在求解线性等式约束问题时表现突出, 优化过程中采用专门构造的突变算子, 并结合投影修复来满足约束条件(类似局部搜索), 其中, 目标函数只在可行搜索点处求值(内点法). 文献[56]提出了一种基于人工蜂群算法等式约束优化方法, 该方法将优化过程分为两个阶段: 首先, 由侦查蜂搜索满足所有约束条件的可行解决个体; 然后, 对这些解在满足约束条件的情况下进行动态边界搜索. 该方法被应用于电力投资分配等问题.
部分等式约束问题可以根据等式特性来获取可行解. 例如: 当面向线性等式约束时, 在知道n?1个变量时, 可以轻松通过线性等式特性确定第n个变量. 基于这一考虑, 较多研究学者提出了面向特定等式约束问题的约束进化算法. Barbosa等人[57, 58]提出了一种面向线性等式约束的差分进化算法, 在该算法中, 首先利用问题等式特性生成一个可行解种群, 仅当最优候选个体是不可行解时, 将之投影到可行区域, 从而减少计算开销. 文献[59]采用变量消元法减少变量来处理等式约束优化问题, 在该方法中, 基于变量间的关系通过部分变量来确定其他变量, 从而缩小搜索空间. 该方法可应用于非线性等式约束问题. Orito等人[60, 61]将等式约束问题重新定义, 如下所示:
| $ \left. \begin{array}{l} \min \;f(\vec x) \hfill \\ {x_i}=\prod\limits_{j=1}^M {{{({{\cos }^2}{ heta _j})}^{{\alpha _j}}}{{({{\sin }^2}{ heta _j})}^{1 - {\alpha _j}}}} , \;(i=1, ..., n) \hfill \\ \end{array} \right\} $ | (12) |
算法只需在无约束θ空间中寻找最优解. 该方法有效地将等式约束问题转换成了无约束优化问题, 但该方法对应用问题有着诸多限制, 严重限制了其实用性.
等式约束依然是当前约束处理技术所面临的主要挑战之一. 当前, 基于容差参数设置的方法、基于局部搜索的方法、基于等式函数特征的方法在一定优化场景下提高了算法面对等式优化问题的优化效率, 但在离散等式约束、非线性等式约束背景下存在着一定的局限性.
2.2 平衡约束优化约束与目标之间的平衡问题, 是基于进化算法求解COP的关键问题之一. 相对于无约束问题, 约束优化的关键是如何处理可行解和不可行解之间的关系, 其本质是根据优化场景调节算法对约束与目标的偏好, 使得算法具有平衡约束与目标的能力. 不同约束优化问题搜索空间的可行区域和不可行区域存在比例差异、函数值大小差异、形状差异等, 都给算法在约束与目标之间的平衡搜索带来了巨大的挑战. 面对这一挑战. 近年来, 较多学者对该问题进行了深入研究, 研究方法可分为提升目标函数值搜索偏好的方法、基于排序的方法、多目标约束处理优化方法以及其他方法(见表 4).
|
|
表 4 面向平衡约束优化的进化算法分类与描述 |
传统约束处理技术研究中潜意识地优先考虑个体违约程度, 即算法一般先搜索到可行区域, 然后再在可行区域内搜索可行最优解, 例如可行性原则(可行解优于不可行解)、ε约束处理(当个体约束违约度小于ε值时再考虑目标函数值)、基于排序的方法(小概率考虑目标函数值). 近年来, 越来越多的研究学者观察到了该现象, 从而提出了相应的提升目标函数值搜索偏好的方法以平衡约束与目标优化. 文献[10]为了实现约束和目标函数之间的权衡, 对个体生成过程采用不同的个体引导, 分别是种群中违反约束程度最小的个体和目标函数值最佳的个体, 传统算法一般选择由最优可行解或者违约度最小的个体引导. 其实验结果表明, 该种策略对很多约束场景优化都有效. 文献[62]提出了一种结合目标函数信息的可行优先原则, 在可行优先原则中, 父代和子代都是不可行解, 且当子代的约束违约度大于父代时, 子代将被淘汰. 而在该种场景中, 结合目标函数信息的可行优先原则, 当子代的目标函数优于父代时, 子代个体将存入归档集, 用于种群更新. 实验结果表明, 该方法可以更好地平衡目标与函数优化. 文献[63]针对可行优先原则中过于优先约束优化问题, 提出了一种基于个体的可行优先原则. 该文献主要从两方面来解决该问题: (1) 一些不重要的约束信息可以抛弃;
(2) 一些有用的目标函数信息应该重视. 信息的价值是依托于个体的, 当满足公式(13)条件时, 个体
| $ \left. \begin{gathered} G(\vec y) \leqslant G(\vec x) - \Delta { ext{ }}\& { ext{ }}f(\vec y) > f(\vec x), \\ G(\vec y) \leqslant G(\vec x)\& f(\vec y) < f(\vec x), \\ G(\vec y) \leqslant G(\vec x) \leqslant G(\vec x) + \Delta { ext{ }}\& { ext{ }}f(\vec y) < f(\vec x), \\ \Delta=\left\{ {\begin{array}{*{20}{l}} {{\Delta _0}{{\left( {1 - \frac{t}{T}} \right)}^{cp}}, { ext{ if }}t \leqslant Tc} \\ {0, { ext{ otherwise}}} \end{array}} \right.{ ext{, }}cp=- \frac{{\log {\Delta _0} + \lambda }}{{\log \left( {1 - \frac{{Tc}}{T}} \right)}} \\ \end{gathered} \right\} $ | (13) |
文献[11]利用约束与目标函数之间的相关性来平衡约束与目标函数. 算法先通过学习算法来挖掘两者之间的关系, 这个关系有两种可能: 当目标函数值下降时, 约束违约度也下降(相似的变化趋势); 或当目标函数值下降时, 约束违约度不下降(变化趋势不同). 当约束与目标函数具有相似的变化趋势时, 个体的目标值优化有助于个体进入可行区域, 当问题的约束函数非常复杂时, 该种关系的利用将极大地促进算法的性能. 当约束与目标函数变化不同时, 过多利用目标函数信息将不利于个体进入可行区域, 这时算法可以更多利用约束条件信息. 基于上述思路, 文献[11]在较多优化问题上表现突出.
目前, 有较多的研究者采用排序的方法来平衡目标与约束优化. 文献[65]采用排序的方法来平衡约束和目标优化. 算法首先对种群个体进行了两次排序, 分别基于ε约束和目标函数值; 然后, 算法考虑到种群可行解比例和算法的搜索阶段, 对个体的两次排序序号进行加权, 从而构建个体的适应度值. 文献[66]提出了一种平衡排序方法, 该方法分别基于可行解和不可行解进行排序, 然后考虑了搜索状态和总体特性对两种排序进行合并. 该方法与优化算法不耦合, 相对于其他约束处理技术, 表现出了更高的鲁棒性.
多目标约束处理优化方法利用多目标优化理论来处理目标与约束优化平衡问题. 该类方法通常将约束条件作为问题优化目标之一, 进而采用多目标优化方法进行优化求解. 近年来, 该类约束处理方法得到了广泛的发展. 文献[67]提出了一种基于分解的约束处理技术, 它将目标与约束进行均匀的权重求和. 该方法较好地平衡了约束与目标优化, 同时又缓解了多目标优化方法应用于约束处理计算开销大的问题. 文献[68]将约束优化问题转化为一个具有辅助目标和等效目标的优化问题, 然后利用加权和方法将该多目标优化问题分解为若干子问题. 动态调整权重, 使每个子问题最终趋向于相同目标. 该方法在应用到“宽间隙”问题优化中表现突出. 文献[69]在基于多目标的约束处理技术中提出了一种基于偏置动态权值的约束处理方法, 算法采用有偏好的权重方法选择不同的个体, 使其具有较低的目标值和较低的约束违约度. 同时, 随着演化过程的进行, 通过动态调节权重, 以促进约束与目标优化的平衡. 文献[70]将约束优化问题转化为一个双目标优化问题, 然后使用协方差矩阵自适应进化策略进行求解. 优化过程中, 采用一种基于参考向量的排序策略来更新协方差矩阵, 并对不可行解提出了一种修复机制和重新启动战略, 以促进种群逃离不可行区域.
除上述研究方法外, 还有较多研究学者提出了其他方法. 文献[71]对ε约束处理技术进行了改进, 传统的ε技术仅考虑算法搜索的不同阶段, 而在该研究中, 将当前种群中可行解的比例也考虑到ε值的调节, 从而在算法面对不同可行区域与不可行区域比例时表现出更高的鲁棒性, 起到平衡可行区域和不可行区域之间搜索的作用. 文献[72]提出了一种推拉搜索策略来应对s形函数造成的目标与约束优化的平衡问题, 该方法将整个进化过程分为两个阶段, 分别为推搜索阶段和拉搜索阶段: 推阶段将种群推入目标函数的最优区域, 而拉阶段将不可行个体拉回可行区域. 文献[73]为了平衡目标与约束搜索, 提出了一种协同进化的双种群优化方法. 该研究将种群划分为两个子种群, 一个子种群关注于优化目标, 另外一个关注约束条件优化, 并通过信息共享策略进行两个子种群的交流. 如何进行子种群的协同, 是该研究方法的关键问题. 文献[74]将约束违约度和小生境计数作为两个新的目标, 从而将约束优化问题定义为三目标优化问题, 并采用多目标优化方法和ε支配进行问题求解. 此外, 在个体选择时, 控制可行解比例来平衡目标与约束优化. 文献[75]将教与学优化方法进行改进以求解约束优化问题, 它将种群划分为几个子种群, 利用每个子种群的平均位置与种群最佳位置信息来引导子种群迅速到达有希望的区域; 同时. 利用不同子种群之间的信息交互来防止种群过早收敛. 此外, 在演化过程中, 针对种群不可行、半可行和可行这3种情况, 采用3种不同的约束处理方法来平衡目标与约束优化.
平衡优化是一个开放性的问题, 目前, 提升目标函数值搜索偏好的方法、基于排序的方法、多目标约束处理优化方法等从不同角度来优化该问题, 并从实验结果和经验评判其是否达到优化目标, 但依然缺少一定的理论分析和公认的平衡架构.
2.3 普适约束优化不同的约束优化问题具有不同的特征和数学性质, 例如问题可能是单模态或多模态、连续或不连续、线性或非线性, 它们的变量可以是离散的或连续的. 面对多样的约束优化问题, 近年来, 研究学者提出了不同的约束处理机制. 根据约束优化进化算法中的约束处理机制对约束处理的方式不同, 可以将它们划分为罚函数法、可行性法则法、随机排序法、ε约束处理法、多目标优化法、混合法. 这些方法在某些优化场景中都有着各自的优秀表现, 但这些方法也往往存在这样或那样的局限性, 例如: 罚函数法的惩罚因子设置困难; 可行性法则法容易陷入局部最优, 且当全局最优解在边缘时表现不佳; ε约束处理法表现不稳定; 随机排序法表现稳定, 但效果一般; 多目标优化法计算开销大等, 更加详细的关于约束处理技术的介绍可参看文献[2]. 算法搜索过程中, 有着太多因素影响搜索偏好, 总是考虑到一些因素, 但又会忽略其他. 根据没有免费午餐理论, 一种约束处理技术在所有问题上都优于其他技术是不可能的. 在此背景下, 研究者们试图研究一种具有更高普适性的约束处理技术, 即该约束处理技术可以适用于更多类型的约束优化问题. 根据我们的观察, 目前这些方法大体上可以分为两类: 基于集成的方法和基于模糊理论的方法.
基于集成的方法主要考虑到不同的约束处理技术和搜索策略在某些优化场景或者阶段有着各自的优点, 将这些技术和策略集中考虑, 根据其表现进行集成, 将很大可能提高算法的普适性. Mallipeddi等人[76]考虑到可行区域的比例、问题多模态、选择的搜索策略以及搜索的阶段都影响着约束处理技术的有效性, 为此采用多种群策略, 不同的种群采用不同的约束处理机制(该研究集成了4种约束处理技术), 并通过种群间的学习来更新搜索策略与约束处理技术的组合, 即统计搜索策略和约束处理技术的组合在新产生个体的优秀比例. 文献[77]采用基于概率的算子选择和种群聚类来提高算法的普适性, 该研究将若干变异算子、交叉算子及参数存储到候选池中, 然后根据种群进化历史信息来更新这些算子或参数的选择概率, 从而达到结合各个算子优点的目的. 此外, 在约束处理技术方面, 算法先将种群聚类成多个簇, 每个簇中基于可行性规则进行个体选择, 并采用归档集中优秀的不可行解对各簇部分个体进行替换. 文献[12]通过两种途径来提高算法的普适性: (1) 考虑到没有一种算子可以在所有场景下都优于其他算子, 算法将多个DE算子整合到了一个算法中; (2) 利用优化场景信息选择算子, 文献[12]采用了信息矩阵(种群个体间优劣表现). 文献[78]也提出了采用多种粒子群搜索算子来提高算法求解不同类型COPs时的普适性, 该研究约束处理技术采用可行性原则, 同时采用了多种群和概率变异算子来维持算法搜索的多样性. 文献[79, 80]提出了一种基于投票机制的约束处理技术集成框架, 每种约束处理技术对产生的个体进行投票, 获得更多投票的个体被认为是优秀的个体, 从而进入下一代种群. 该框架借鉴了人类在决策过程中的集体智慧. 文献[81]提出了自适应选择差分变异策略来处理约束优化问题, 在优化过程中, 对变异策略设置了信用分配机制, 该信用机制考虑了如何衡量由单个策略造成的适应值变化和如何根据适应值变化分配恰当的信用值. Malan等人[82]引入了场景分析技术, 研究了相关场景属性对6种约束处理技术的影响, 从而将其应用于约束处理技术的自适应处理中.
基于模糊理论的技术也是提高约束处理技术普适性的有效途径. 约束处理技术根据搜索偏好划分为确定型约束处理技术和非确定型约束处理技术: 确定型约束处理技术在某些场景下表现突出, 但建立精确的搜索偏好与优化场景间的映射关系存在巨大的挑战; 而非确定型约束处理技术寄托于采用基于概率的方法来缓解该问题, 但是目前非确定型约束处理技术在概率设定时完全不考虑优化场景和搜索偏好的相关联系, 从而影响到该类方法的性能. 该研究采用基于确定型约束处理中的经验知识来进行搜索偏好的随机模型建立, 从而提高了约束处理技术的普适性. 基于上述基本思路, 较多研究提出了基于模糊理论的约束处理技术. Saha等人[83]提出了一种基于模糊规则的罚函数方法, 该研究基于Mamdani类型IF-THEN规则的模糊推理系统(包含了自适应惩罚所需的所有标准), 从而无需制定明确的映射, 而不是识别一个复杂的数学函数来计算约束违反的惩罚. 文献[3]提出了一种基于模糊偏好搜索的约束处理技术, 该研究中定义了一种模糊的知识, 即“大约束违约度的个体偏好违约度少的个体, 约束违约度少的个体偏好目标函数值优的个体”. 文献[84]提出了一种包含两层(个体和种群)约束进化优化的自适应模糊惩罚方法, 该方法弥补了传统基于模糊理论只考虑个体信息进行惩罚系数设置的不足, 提出了融合个体和种群信息的模糊约束处理方法.
提出一种高效且具有更高普适性的约束处理技术, 一直是该领域研究的向往. 基于集成的方法和基于模糊理论的方法可能都是有效的途径. 基于集成的方法期望根据当前的优化场景选择合适的算子和约束处理技术以提高算法的效率和普适性, 但算子和约束处理技术受到众多场景因素的影响, 目前尚未有高效的优化场景描述方法. 基于模糊理论的方法试图通过模糊理论来描述约束处理的经验知识, 在保证其高效性的同时, 保持方法的多样性. 但在当前方法中, 模糊规则及隶属函数完全凭经验设计, 也缺乏系统性.
3 未来发展趋势近年来, 虽然进化算法在面向复杂的工程应用约束优化问题优化中已经取得了较多的成果, 但随着应用的深入, 尤其是在重大工业装备智能优化控制、复杂流程工业优化、综合交通网络设计与优化、高动态异构物联网络资源优化等应用中, 依然存在许多亟待解决的问题, 这也给约束进化算法带来了新的机遇与需求, 其主要表现在以下几个方面.
(1) 大规模约束优化. 当前, 工程应用优化问题大多体现了大规模和多约束特性. 但近年来, 进化算法主要面向无约束大规模优化问题, 当面对约束优化场景时, 其表现往往一般. 传统的约束进化框架或简单的约束技术应用已无法满足工程应用的需要. 根据大规模约束优化自身的特点与限制, 设计针对性的优化框架和约束处理技术, 平衡大规模和约束处理的复杂性, 是当前进化算法应用于大规模约束优化亟待解决的问题.
(2) 离散非线性等式约束优化. 当前, 约束处理技术在应用于离散、非线性等式约束时存在局限性, 而离散、非线性在等式约束问题中普遍存在, 且在多目标、昂贵计算开销等优化背景下该问题更具有挑战. 提取、分析、描述等式约束优化场景, 设计相应的由点到面、约束投影等方法, 可能是解决该问题的有效途径.
(3) 基于超启发式理念的普适约束优化. 普适约束优化与超启发式优化理念具有很大的相似性. 超启发式思想已被广泛应用于提高算法的普适性. 根据当前约束场景选择或生成对应的高效约束处理技术, 可能是提高约束处理技术的有效途径, 而如何进行优化场景描述与高效的上层学习算法设计是关键.
(4) 动态约束优化. 动态优化是工程应用中优化问题存在的普遍特征. 当前, 该领域的研究主要针对无约束的动态优化问题, 没有考虑问题约束的动态变化特性, 极大地妨碍了其实际工程应用. 面向动态约束优化的研究有着重要的工程应用价值.
4 总结进化算法是一种高效的智能计算方法, 被广泛应用于工程应用优化问题, 而约束处理是其中关键技术之一. 本文从工程应用优化问题的复杂性出发, 分别对近年来面向复杂目标的进化约束优化算法和面向复杂约束场景的进化算法的研究进展进行综述. 其中, 面向复杂目标的进化约束优化算法重点介绍多目标约束优化、大规模约束优化、高计算开销约束优化; 而在面向复杂约束场景的进化算法的论述方面, 较详细地介绍了等式约束优化、平衡约束优化、普适约束优化等目前研究备受关注的问题. 相对于已有基于约束技术处理方式不同的分类, 本文方法更能突出工程应用的实际需求. 此外, 本文也就当前研究方法的主要挑战和发展趋势进行了论述, 为进化约束处理技术的未来发展提供支持.
