在工程设计、作业调度、智能控制、交通优化、金融投资、网络通信等诸多优化领域, 常常遇到许多条件限制(约束), 这些条件限制给问题的求解带来了极大的挑战^{[1, 2]}.这类优化问题, 称为约束优化问题(constrained optimization problem, 简称COP).约束优化问题是优化领域的一个重要问题, 约束优化问题中的约束条件通常包括决策变量上下界约束条件、等式/不等式约束条件.按照约束条件的数学特性, 还可以分为线性/非线性约束条件.由于约束条件的存在, 导致在决策变量的搜索空间中产生了不可行域(搜索空间由可行域和不可行域两部分组成).从无约束优化到约束优化, 原本单一的优化目标必须同时考虑优化目标和约束两个方面, 而有效的无约束优化方法处理约束优化问题时却是一筹莫展.因此, 研究约束优化问题具有重要的理论意义和实际价值.

传统的优化算法求解这类问题时都是基于梯度信息, 这只适用于目标函数和约束条件可微的情形, 而且求得的解多为局部最优解.进化算法是一种模拟自然过程的全局优化方法, 它用个体来代表待求解问题的解, 将一定数量的不同个体组成种群.从初始种群开始, 采用变异、交叉、选择等操作, 模仿自然界的进化过程, 引导种群进行进化, 使得种群中的个体逐步接近问题的最优解.与传统优化算法相比, 进化算法是一种基于群体的搜索技术, 具有鲁棒性强、搜索效率高、不易陷入局部最优等特点, 因此, 它更适合于求解约束优化问题.然而, 进化算法的本质是一种无约束的优化技术, 必须将其与一定的约束处理机制相结合, 构成约束优化进化算法, 才能更好地求解复杂的约束优化问题.

约束处理方法对约束优化算法的性能具有重大影响.好的约束处理方法应能将约束优化问题转化为无约束优化问题.同时, 充分发挥作为搜索机制的进化算法的性能, 还应该有较少的参数, 以便于实现.为了提高进化算法求解约束优化问题的效率, 近年来, 研究者提出了大量将约束条件结合到进化算法的约束处理方法.根据约束优化进化算法中约束处理机制从处理约束的方式不同, 可以将它们划分为6类^[3](罚函数法^[4]、可行性法则^[5]、随机排序法^[6]、ε约束处理法^[7]、多目标优化法^[8]、混合法^[9]):罚函数法通过添加惩罚因子的方式将约束优化问题转化为无约束优化问题, 是最为传统的约束处理方法之一, 该类方法的不足在于惩罚参数的选取比较困难; 可行性法则是Deb提出的一种约束处理方法, 其将可行解和不可行解分离处理, 并且可行解的适应度函数值优于不可行解的适应度函数值, 因此, 该方法使得不可行解难以进入种群, 这样就使得该方法在求解最优解位于可行域边界上的约束优化问题时可能存在问题; 随机排序法采用冒泡排序的方法来处理约束优化问题; ε约束处理法通过设定ε值将约束划分为不同的区间, 个体之间的比较在不同的约束区间内采用不同的处理方法, 该方法是对可行性法则的扩展, 它以牺牲时间为前提, 对搜索空间进行充分搜索; 多目标优化法根据将约束优化问题转换为多目标优化问题, 并采用多目标优化技术来处理问题, 然而, 没有引入偏好的多目标优化方法可能并不像人们所想象的那样高效; 混合法求解约束优化问题是近年来研究的热点, 该方法通过将不同的约束处理机制相结合的方法来处理约束优化问题.

纵观国内外对约束优化领域的研究情况, Coello等人的综述主要针对2002年以前的约束优化进化算法, 对近些年出现的约束优化进化算法的讨论较少; 国内在该领域的综述, 主要是偏重于2009年以前的研究成果.鉴于最近几年约束优化进化算法的迅猛发展, 著名的进化优化领域国际会议(IEEE Congress on Evolutionary Computation, 简称CEC)分别于2006年和2010年进行了专题讨论并组织了约束优化竞赛^{[10, 11]}, 促进了约束优化问题的研究与发展.国内外的著名学者对约束约束优化进化算法进行了长期研究, 取得了一定的研究成果^{[12, 13]}.我们认为:有必要对该领域的最新研究成果做全面的介绍和讨论, 并对目前约束优化中存在的挑战和问题进行描述.

本文首先介绍了约束优化问题的定义, 然后结合上述对约束优化进化算法中约束处理机制的分类, 对各类算法的基本思想、最新的研究状况、存在的主要挑战等方面进行了全面的描述与探讨.最后, 本文指出约束优化进化算法需进一步研究的方向与关键问题.

1 约束优化问题的定义

很多实际问题可以归结为决定一组决策变量, 使得目标函数取得最优值的问题.同时, 这组决策变量必须满足一定的约束条件, 这就构成了约束优化问题或者数学规划问题.通常, 约束优化问题可以定义为如下形式(不失一般性, 本文考虑最小化情形):

$ \begin{array}{*{20}{l}} {{\rm{minimize}}\;\;f(x)}\\ {{\rm{subject}}\;{\rm{to}}\;\;{g_j}(x) \le 0,\;j=1,...,q}\\ {\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{h_j}(x)=0,j=q + 1,...,m} \end{array} $

(1)

其中, x=[x₁, x₂, …, x_n]∈S是决策变量, S表示n维搜索空间, 它满足如下边界约束条件:

$ {l_i} \le {x_i} \le {u_i}, 1 \le i \le n $

(2)

f(x)是目标函数, q表示不等式约束条件的个数, m-q表示等式约束的个数.g_j(x)为第j个不等式约束条件, 而h_j(x)为第j-q个等式约束条件.其中, u_i和l_i分别为分量x_i的上界和下界.满足所有约束条件的解是可行解, 而所有的可行解组成可行域Ω∈S, 不满足任意一个约束条件的解被称为不可行解, 所有的不可行解组成不可行域, 如果g_j(x)=0(j=1, …, q)在一个可行解处成立, 则称该不等式约束条件在该可行解处是活跃的.显然, 所有的等式约束在可行域内都是活跃的.

在约束优化中, 等式约束在通常情况下被转化为不等式约束, 于是, 个体x在第j个约束条件上的约束违反程度表示为

${G_j}(x)=\left\{ {\begin{array}{*{20}{l}} {\max \{ {g_j}(x), 0\}, {\rm{ }}1 \le j \le q}\\ {\max \{ |{h_j}(x)| - \delta, 0\}, {\rm{ }}q + 1 \le j \le m} \end{array}} \right.$

(3)

上面公式中, δ为等式约束的容忍参数, 该参数可以定义为一个特定的值(一般设为0.0001) 或采用自适应变化的方式定义.所以, 个体x总的约束违反程度(又称约束违约度)表示为

$v(x)=\sum\limits_{j=1}^m {{G_j}(x)} $

(4)

通过上述定义, 约束优化问题的优化目标就是:在满足所有不等式约束的前提下, 在变量的定义范围内, 找到使得目标函数f(x)达到最优的解(最优解).

值得注意的是:由于约束条件之间的存在差异, 从而会出现某些约束条件可能对个体的约束违约度v(x)起着主导性的作用, 所以, 可通过采用标准化来平等地对待每个约束条件.在标准化过程中, 首先找出群体中的个体违反每个约束条件的最大值$G_j^{\max }(j \in \{ 1, \ldots, m\} )$:

$ G_j^{\max }=\mathop {\max }\limits_{i=1, ..., NP} ({G_j}({x_i})), j \in \{ 1, ..., m\} $

(5)

其中, NP为种群规模, 即群体中所包含的个体数.于是, 个体x的标准化约束违反程度v_norm(x)定义为该个体的每个约束违反标准值的平均值:

$ {v_{norm}}\left( x \right)=\frac{1}{m}\sum\limits_{j=1}^m {\frac{{{G_j}({x_i})}}{{G_j^{\max }}}}, {\rm{ }}i \in {\rm{\{ 1, 2, }}...{\rm{, }}NP{\rm{\} }} $

(6)

另外, 有时为了均衡目标函数和约束条件之间的差异, 可以通过标准化目标函数来使目标函数和约束违反程度的数量级相同, 最后, 个体x的标准化目标函数f_norm(x)如下显示:

$ {f_{vorm}}(x)=\frac{{f({x_i})-{f_{min}}}}{{{f_{_{max}}}-{f_{min}}}}, i \in {\rm{\{ 1, 2, }}...{\rm{, }}NP{\rm{\} }} $

(7)

其中, f_min和f_max分别定义为当前种群中所有个体的目标函数的最小值与最大值:

$ {f_{_{\max }}}=\mathop {\min }\limits_{i=1, ..., NP} f({x_i}), {f_{_{\max }}}=\mathop {\max }\limits_{i=1, ..., NP} f({x_i}) $

(8)

通过以上标准化之后, 每个个体的目标函数和约束违反程度的值将在[0, 1]区间内变化.

2 基于约束处理的进化算法

进化算法因其优良的性能被用于处理约束优化问题, 但其本质上是一种无约束优化进化算法, 必须要将其与一定的约束处理机制结合, 才能对约束优化问题进行求解.进化算法和约束处理方法相结合构成完整的约束优化进化算法.进化计算领域的研究人员已经提出了大量的约束处理方法和约束优化进化算法, 下面根据近年来进化算法中约束处理技术的研究趋势, 将约束优化算法间接地划分为以下6类:(1) 罚函数法; (2) 可行性法则; (3) 随机排序法; (4) ε约束处理法; (5) 多目标优化法; (6) 混合法.

2.1 罚函数法

罚函数法因为执行十分简单而得到了广泛的应用, 尤其是应用到进化算法里处理约束优化问题.其主要思想是:基于个体的约束违反程度构造惩罚项, 通过对目标函数f(x)增加惩罚项p(x)来构造惩罚适应度函数fitness(x), 将约束优化问题转换为无约束优化问题进行处理.通用的惩罚适应度函数可以定义为如下形式:

$fitness(x)=f(x) + \alpha \sum\limits_{i=1}^m {{r_i}{G_i}(x)}, \sum\limits_{i=1}^m {{r_i}}=1$

(9)

其中, r_i表示为用户对每个约束条件定义的约束违反水平数, α为惩罚系数.为了在目标函数和约束之间起到平衡, 罚函数法通过调整惩罚项中惩罚系数来实现.显然, α的值过小, 则对不可行解的惩罚不够, 不利于算法搜索到可行解; α的值过大时, 惩罚程度大, 则不利于算法收敛于最优解.此外, α值的设定, 面向不同的目标优化函数设定也不同.所以, 如何合理设置惩罚系数, 是利用罚函数法求解约束优化问题的一个瓶颈, 也是约束优化领域的关键问题.下面围绕惩罚系数的选取来介绍几种应对策略.

静态罚函数法是指惩罚项中的惩罚系数不依赖于进化代数, 在种群的整个进化过程中设置为定值, 但算法通常因数值的单一性而效果不佳.文献[14]提出了一种分层惩罚参数法, 采用如下的惩罚适应度函数:

$ fitness(x)=f(x) + \sum\limits_{i=1}^m {{R_{k, i}}} imes {G_i}(x) $

(10)

其中, R_{k, i}(k=1, …, q, i=1, …, p)为惩罚系数, q为用户对每个约束条件定义的约束违反水平数.该方法将约束违反的程度分为多个等级, 不同等级采用不同的惩罚系数R_{k, i}, 约束违反程度越大, 则违反等级越高, 对应的惩罚力度也就越大.分级处理机制相对单一数值法更为合理, 但该方法需要一定的先验信息来确定各等级的惩罚系数值, 另外还产生了较多需要调节的参数.这类方法实现相对简单且多用于求解简单的约束优化问题, 不足之处在于它的通用性, 因为它对每一类问题, 都需要进行惩罚系数的反复实验, 寻找到合适的惩罚系数.

动态罚函数法指惩罚系数随着进化代数的变化而变化, 惩罚系数的数值是时变的, 通常它是随着进化代数增大而增大.其理由是:在进化初期采用较小的惩罚系数, 因对不可行解的惩罚较小, 算法将有可能对可行域之外进行一定程度的搜索; 而进化后期采用较大的惩罚系数, 使得算法的搜索集中在可行域, 寻找目标更优的可行解.文献[15]提出了如下的方式构造惩罚适应度函数:

$ fitness(x)=f(x) + {(C imes t)^\alpha }\sum\limits_{i=1}^m {G_i^\beta (x)} $

(11)

其中, t为进化代数, C, α, β为事先设定的常数.虽然该方法不需要设定惩罚系数值, 但其他参数仍需要设定.与静态罚函数法相比, 虽然动态罚函数法在性能方面上更具优越性, 但是找到理想的惩罚系数动态变化规律(初始化惩罚系数的选取)仍然是一个棘手的问题.

死罚函数法^[16]是最简单的罚函数法, 它总是拒绝不可行解, 完全忽略不可行个体所提供的任何有价值的信息.在死罚函数法中, 不可行解的惩罚适应度值定义为0, 这样, 当初始种群不包含可行解, 进化过程趋于停滞, 因为种群中的所有个体的惩罚适应度值都一样, 此时需要重新生成初始可行性种群.死罚函数法仅适合于可行域为凸形或可行域占搜索空间比例较大的约束优化问题.

自适应罚函数法是一种通用性更强的约束处理方法, 因为它能够把从种群的进化过程中获取的信息作为反馈动态地调整惩罚系数.如文献[17]中提出了一种自适应惩罚适应度函数形式:

$fitness(x)=f(x) + \lambda (t)\sum\limits_{i=1}^m {{G_i}(x)} $

(12)

其中, λ(t)在每一代按如下方式更新:

$ \lambda (t + 1)=\begin{array}{*{20}{c}} {\left\{ {\begin{array}{*{20}{l}} {(1/{\beta _1})\lambda (t),{\rm{if}}case\# 1}\\ {{\beta _2}\lambda (t),\;\;\;\;\;\;\;{\rm{if}}case\# 2}\\ {\lambda (t),\;\;\;\;\;\;\;\;\;\;\;{\rm{otherwise}}} \end{array}} \right.} \end{array} $

(13)

其中, β₁ > β₂ > 1.case # 1表示在过去g(用户定义的参数)代中找到的最好个体均为可行解, case # 2表示在过去g代中找到的最好个体均为不可行解.其原理可理解为:若在此之前所找到的最好个体均为可行解, 则表明惩罚系数已足够大, 可适当减少来降低对不可行解的惩罚压力; 若此前所找到的最好个体均为不可行解, 则表明惩罚系数过小, 需适当增大来增强对不可行解的惩罚力度.

除了上述几种方法外, 广泛使用的罚函数法还有退火罚函数法、隔离遗传算法、协同罚函数法等.在退火罚函数法^[18]中, 惩罚系数随着温度的降低而不断增加; 隔离遗传算法^[19]通过两个不同的惩罚系数来对群体中的个体进行评价, 其旨在于在过大和过小的惩罚系数之间达到平衡; 协同罚函数法^{[20, 21]}包括两个群体, 第1个群体中个体表示问题的解, 第2个群体的个体为惩罚系数的集合, 利用它来计算第1个群体中个体的适应度值.文献[22]采用进化策略作为搜索框架, 为保持种群中可行解与不可行解的平衡, 始终允许在种群中保留不可行个体以增强全局搜索能力, 算法根据种群中可行解在整个种群中所占的比例来动态调整惩罚系数.Farmani和Wright^[23]提出一种自适应适应值表示法, 该方法将惩罚分为两个阶段进行, 都是通过提取种群中的边界个体的信息来确定惩罚强度.Xiao等人^[24]设计了一种遗传算法求解多约束优化问题, 它利用KS函数的融合特征将多个约束条件融合成一个约束条件, 从而减少了静态罚函数法中惩罚系数数量过多的问题和避免了约束条件权重分配问题.

近年来出现了一些具有收敛性能较优的约束优化进化算法^{[25, 26]}, 其中有很多方法的研究重点是如何构造出合理的自适应或适应性的惩罚函数.因为自适应惩罚函数相比动态、静态等其他方法, 自适应调整参数策略的优点在于不需要引入额外的一些参数并略去参数反复调优的过程, 所以目前自适应策略是惩罚法的研究热点.

Tessema和Yen^[27]提出了一种自适应惩罚函数的方法, 该方法采用当前种群中可行解的比例来自适应地控制惩罚的强度.与其他方法不同的是:该方法除了引入距离项(把种群中的个体映射到二维坐标系内的点, 而该点到坐标原点的距离)之外, 还为了找到最佳不可行解, 对不可行解采用双惩罚.该方法旨在于先挖掘出种群中具有较好质量的不可行解, 然后再引导种群向可行域或者最优解逼近.文献[27]中的惩罚适应度函数:

$ fitness(x)=\left\{ {\begin{array}{*{20}{l}} {{f_{norm}}(x),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{for}}\;{\rm{feasible}}\;{\rm{individual}}}\\ {{v_{norm}}(x),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{if}}\;{\rm{there}}\;{\rm{is}}\;{\rm{no}}\;{\rm{feasible}}\;{\rm{individual}}}\\ {\sqrt {{f_{norm}}{{(x)}^2} + {v_{norm}}{{(x)}^2}} + [(1 - rf){f_{norm}}(x) + rf imes {v_{norm}}(x)],{\rm{otherwise}}} \end{array}} \right. $

(14)

其中, f_norm(x)为标准化(单位化)目标函数, v_norm(x)为标准化(单位化)约束违约度, rf为种群中可行个体所占的百分比(简称可行比率).在进化的过程中, 种群中的可行个体的数目是用来指导搜索的方向:若可行比率较小, 倾向于发现更多的可行个体’若可行比率较大, 偏向于寻找到问题的最优解.

Lemonge和Barbosa等人^[28]提出了一种自适应惩罚函数方法, 并将其和稳态遗传算法相结合, 用于解决工程优化问题.该方法为每个约束条件分配各自的惩罚系数, 这样来实现约束条件之间的平衡.在进化的过程中, 该方法根据种群状态信息(比如种群中是否存在可行解和每个约束的违反程度)自适应地决定每个约束条件的惩罚系数的变化.惩罚适应度函数的表示形式如下:

$ fitness(x)=\left\{ {\begin{array}{*{20}{l}} {f(x),\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;{\rm{if}}\;x\;{\rm{is}}\;{\rm{feasible}}}\\ {h(x) + \sum olimits_{j=1}^m {{k_j}{v_j}(x)} ,{\rm{otherwise}}} \end{array}} \right. $

(15)

其中, h(x)函数的表示形式如下:

$ h(x)=\left\{ {\begin{array}{*{20}{l}} {f(x), {\rm{ if }}f(x) > \langle f(x)\rangle }\\ {\langle f(x)\rangle, {\rm{ otherwise}}} \end{array}} \right. $

(16)

〈f(x)〉是指当前种群的目标函数平均值, 而惩罚系数采用如下的公式进行计算:

$ H=\left\{ {\begin{array}{*{20}{l}} {f({x_{worst}}),\;\;\;\;\;\;{\rm{if}}\;{\rm{there}}\;{\rm{is}}\;{\rm{no}}\;{\rm{feasible}}\;{\rm{element}}\;{\rm{in}}\;{\rm{thepopulation}}}\\ {f({x_{bestfeasible}}),{\rm{otherwise}}} \end{array}} \right. $

(17)

H系数的定义如下:

$ {k_j}=|H|\frac{{\langle {v_j}(x)\rangle }}{{\sum olimits_{i=1}^m {{{[\langle {v_i}(x)\rangle]}^2}} }} $

(18)

其中, 〈v_i(x)〉为当前种群的第i个约束条件的违反程度均值.当种群发生一定的变化时, 惩罚系数和H系数按公式(17)、公式(18) 重新进行计算.显然, 从H系数的定义形式来看:如果当前种群中不存在可行个体, 在不需要考虑真实目标函数的情况下, 此时约束优化问题可以看作个体到可行域之间距离的最小优化问题(简称约束满足问题).然而当种群中出现可行个体, 再根据公式(15) 来更新种群中所有个体的适应度值, 而此可行个体最终成为种群中适应度最大的个体.该方法能容忍部分不可行个体保留下来继续生存.得注意的是, 该方法可以很好地解决全局最优解位于可行域边界上的约束问题.

Melo和Iacca^[29]提出了一种自适应罚函数法, 并将其与改进的自适应协方差矩阵进化策略(CMA-ES)结合起来, 得到了一个新的约束优化算法.在自适应罚函数法中, 惩罚系数随着每一代群体中全部不可行个体的约束违反信息的变化而变化; 采用如下的惩罚适应度函数:

$ fitness\left( x \right)=bestfeas + |f\left( x \right)-bestfeas|{\rm{ imes }}\left| {v\left( x \right)/{\rm{max}}\_penalty} \right| $

(19)

其中, bestfeas是当前种群中可行个体的最好的目标函数值, 若群体中没有可行解, 此时, bestfeas的值由用户定义; max_penalty指约束违反程度最大不可行个体的约束违约度.从上式可以发现:该方法对违反约束程度越大的不可行个体施加的惩罚强度也就越大; 相对可行个体, 违约度小的不可行个体可能具有更好的适应度, 但不可行个体的适应度是不可能比种群中最好的可行个体的适应度更好.基于上述约束处理方法, 文献[30]提出一种两阶段的文化基因框架:第1阶段将约束优化问题变成无约束优化问题进行处理, 其目标是为局部搜索阶段找到好的初始个体, 为了实现这个目标, 采用自适应惩罚CMA-ES作为全局搜索策略; 第2阶段使用局部搜索策略(比如单形法)来进一步改善解的质量, 其目标是为了找到全局最优解.该方法用于解决规模大的约束优化问题具有很好的优化效果.

Saha和Das等人^[31]提出了一种模糊惩罚法(fuzzy rule-based penalty function approach, 简称FRSP), 并将该模糊惩罚法与差分进化算法结合, 用来解决约束优化问题, 它具有两个惩罚项, 其中:第1项惩罚采用了基于条件法则的Mamdani模糊推理系统, 该模型事先掌握了自适应函数所有必需的条件(作为条件库), 然后通过模糊逻辑控制(FLC), 将个体的约束违反程度、目标函数和种群中可行解的比例作为模糊输入, 经过模糊推理过程后, 最终得到模糊输出量, 即惩罚值; 第2项惩罚项是根据种群中可行解所占百分比来动态地平衡目标函数和约束条件.由前面的两项构成的惩罚适应度函数的形式如下:

$ fitness\left( x \right)=p\left( x \right) + d\left( x \right) $

(20)

其中, p(x)函数即Mamdani模糊模型的输出函数, d(x)函数的具体形式如下:

$ d\left( x \right)=rf{\rm{ imes }}{f_{norm}}\left( x \right) + (1-rf){\rm{ imes }}{v_{norm}}\left( x \right) $

(21)

在上面的公式中, rf为当前种群中可行个体占的百分比, f_norm(x)和v_norm(x)分别为个体的标准化目标函数和标准化约束违反程度.

尽管罚函数法是约束优化进化算法里最易于实现的方法, 但仍然存在着缺陷, 最主要的不足是惩罚参数的选取比较困难, 而且算法的性能强烈地依赖于参数的选择.若选取的参数过大, 则进入可行域可能得以保证, 但会降低对可行域的探索, 因此失去了由不可行个体提供的一些有价值的信息; 若选取的参数过小, 相对于目标函数而言, 惩罚项将被忽略.这两种情况都会导致得不到高质量的解.

2.2 可行性法则

由于罚函数存在着一定的缺陷, 近些年来, 研究人员将目光放到了其他约束优化机制上, 最终提出了几种新的约束处理方法, 其中, Deb^[32]提出的可行性法则是当前应用最受欢迎和最有效的约束处理技术之一, 在可行性法则中, 当两个解x_i和x_j进行比较时, x_i比x_j更优, 通常按以下准则进行解的比较^[33].

(1)x_i是可行解而x_j是不可行解;

(2)x_i和x_j都是可行解, x_i具有更小的目标函数值;

(3)x_i和x_j都是不可行解, x_i具有更小的约束违约度.

显然, 上述准则(1) 和准则(3) 是针对约束的, 使搜索方向指向可行域; 准则(2) 则是针对目标, 使搜索方向指向目标值好的区域.但上述比较准则存在主要的不足是难以发挥不可行个体的作用, 尤其是当种群中的大部分个体都是可行个体时, 不可行个体将很难进入群体.为了保持种群的多样性, 该文还引入了一种小生境技术.在文献[32]的基础上, Mezure-Montes和Coello^[34]提出了一种简单多成员进化策略, 在该算法中, 一些有潜力的不可行解被保留到下一代中继续存活.同年, 他们^[35]将可行性法则与差分进化算法的贪婪选择方法进行结合, 用来解决约束优化问题; 在进化的过程中, 该方法允许一个父代个体可以产生多个子代个体并从多个子代个体中选择一个可行性更优的个体作为其子代, 旨在增加产生更优越子代的概率.另外, 该方法通过选择概率S_r来控制种群的多样性.选择概率S_r指定了群体中基于目标函数进行比较的个体比例.

可行性法则将比较个体仅划分为可行个体和不可行个体, 如果面对可行域占整个搜索空间比例较小而且其空间拓扑结构复杂的约束问题, 种群可能处于停滞不可行域.于是, 为了扩展对于个体的分类, Cui和Li等人^[36]利用个体之间存在的优劣关系, 在文中提出个体的相对可行度的概念, 并根据个体相对可行性度来进行个体的比较.

(1)当两个比较的个体x_i和x_j均为可行个体时, 目标函数值小的个体占优;

(2)当两个比较的个体中, x_i为可行个体而x_j为不可行个体时, 可行个体x_i占优;

(3)当两个个体x_i和x_j均为不可行个体时, 如果它们之间的相对可行度相等, 比较它们的约束违约度, 违反约束程度小的个体占优; 否则, 相对可行度大的个体占优.

对于个体的相对可行度的相关定义如下:

定义1(约束条件的相对可行度(relative feasibility degree of a constraint)).给定约束问题, 设F指整个可行域, F_i指满足约束条件i的空间区域.整个可行域的空间大小与满足第i约束条件的可行区间大小的比值ρ_i=|F|/|F_i|即为约束条件i的相对可行度.

定义2(相对非共同满足约束集合(relative non-common satisfied constraint set)).设x_i与x_j分别是种群中两个不同的个体, G代表约束问题的约束条件集合, G_i和B_i分别指个体x_i满足约束条件集合与违反约束条件集合, 对应G_j和B_j分别是个体x_j满足约束条件集合和违反约束条件集合.G_i和B_j的交集表示为:Q(x_i→x_j), 即, x_i相对x_j的非共同满足约束集合.

定义3(个体的相对可行度(relative feasibility degree of a solution candidate)).设x_i与x_j分别是种群中的两个不同的个体, Q(x_i→x_j)指x_i相对x_j的非共同满足约束集合, ρ_k(k∈Q(x_i→x_j))指约束条件k的相对可行度.x_i相对x_j的可行度:

$ R({x_i} o {x_j})=\left\{ {\begin{array}{*{20}{l}} {0, {\rm{ }}Q({x_i} o {x_j})=\emptyset }\\ {1, {\rm{ }}Q({x_i} o {x_j})=\{ 1, 2, ..., m\} }\\ {{{\max }_{i \in Q({x_i} o {x_j})}}{\rho _i}, {\rm{ otherwise}}} \end{array}} \right. $

(22)

Ullah和Sarker等人^[37]针对很多约束优化问题的可行域占搜索空间比例很小并很难找到可行解的特点, 设计了一种缩减搜索空间技术(SSRT), 该技术用于引导初始化种群中不可行解向可行域靠近.此外, 该文还采用了类似于联赛选择算子(基于可行性法则成对比较个体).该算子从解的领域内寻找到局部最优解, 并将它用于进化策略中交叉操作来提高搜索机制的效率.虽然文献[37]提出的约束优化进化算法性能较好, 但其实现比较复杂, 还引入了额外的参数.

约束优化进化算法性能的好坏取决于两个因素:一是作为搜索引擎的进化算法, 二是用来处理约束的约束处理方法.最近几年, 研究者们把焦点放在了进化算法的搜索效率上, 提出了大量的约束优化算法.下面将对一些代表性的约束优化进化算法进行简要的概述.

Elsayed和Sarker等人^[38]为了提高遗传算法的性能, 对遗传算法进行了改进.新算法采用多父体交叉操作(multi-parent crossover, 简称MPC)和随机变异操作:交叉操作首先通过类似锦标赛选择算子的方式从种群中选出3个父代, 然后根据目标函数或者约束违约度进行个体之间的排序, 最后进行3种不同序列的交叉, 产生3个新的子代, 其中, 前两个子代用来帮助于种群的局部开发, 第3个子代有助于增强遗传算法的全局搜索能力; 随机变异操作能帮助逃离局部最优解, 避免过早成熟, 该算法能解决大部分约束优化问题, 但处理高维离散搜索空间的优化问题上存在不足.

Sarker和Elsayed等人^[39]提出一种具有通用性的DE-DPS(differential evolution with dynamic parameters selection)算法, 用于解决所有的约束问题.在进化的过程中, 在给定种群规模的情况下, 种群中的个体根据不同的参数组合(F扩张因子、CR交叉概率)进行变异、交叉、选择后产生新一代种群.这样循环经过t代数后, 根据每组参数的成功率进行排序(成功率:采用特定组合的控制参数产生成功保留到下一代种群后代的个体数目与采用该组控制参数进行进化的个体数目之比), 筛选出部分最好的参数组合.当种群经过g(g > t)代时, 在用户给定的种群规模范围内逐渐减少种群规模.最终, 确定种群进化阶段的最优参数组合(包括NP种群规模、F扩张因子、CR交叉概率), 直到循环迭代结束时找到不同问题的各个进化阶段的性能最优的参数组合.

Wang等人^[40]认为解决约束优化问题的本质在于如何有效地均衡目标函数和约束条件, 提出了一种FROFI (the feasible rule with the incorporation of objective function information)方法, 该方法通过将目标函数的信息融入到可行性法则来使目标函数和约束条件之间达到一个有效的平衡.在该方法中, 种群中个体经过差分进化的变异、交叉操作后产生子代个体, 父代个体与子代个体首先基于可行性法则比较来决定子代个体是否直接进入下一代, 然后将不能进入下一代种群的子代个体再根据目标函数与其对应的父代个体比较, 把所有目标函数好的实验个体归档保存, 然后根据目标函数, 将归档中的子代个体替换新的群体中的部分个体进入下一代种群.

可行性法则总是认为可行解优于不可行解, 该方法相对其他方法可以更快速地找到可行解, 且该方法简单易实现.与其他方法相比, 不需要使用定义任何参数, 具有较好的普适性(适合与不同的进化算法相结合, 而不去过多地改变算法本身), 因此其受到广泛的应用.注意:该类约束处理方法忽略了不可行个体所携带有价值的信息, 不利于算法更快地收敛于可行区域内的最优解.

2.3 随机排序法

随机排序法(stochastic ranking, 简称SR)是由Runarsson和Yao^[6]于2000年提出, 随机排序被用来平衡目标函数和约束违约度之间的矛盾关系.在该方法中, 采用概率参数(pf)来决定是根据目标函数还是根据个体总的约束违约程度来评判两个个体的优越性, 其基本流程如下:

随机排序法
if可行解或者rand < pf then
基于解的目标函数评判先后顺序
else
基于解的约束违约度评判先后顺序
end if

该方法将目标函数和约束违约度之间的平衡问题转换为一个基于某个概率的随机排序问题, 它相对传统的随机排序方法具有更好的普适性, 没有必要针对不同的目标优化函数和优化阶段设置不同的约束惩罚因子.但又引发了另外一个问题, 即, 如何设定概率参数pf的值.在最基本的随机排序法中, pf的值设定为0.475.针对该问题, 有较多研究者提出了改进方法, 例如:文献[41]提出了一种pf值动态变化的方法, 其pf值由0.475线性下降至0.025;文献[42]采用在随机排序法中的概率参数pf随着种群进化代数动态变化的方法, 并将该方法与新的多成员差分进化算法进行结合, 设计出DSS-MD算法.

2.4 ε约束处理法

Takahama和Sakai^[7]在2006年CEC关于约束处理的专题会议上提出了一种ε约束处理法, 该方法的核心思想是:通过人为设定ε值, 基于个体的约束违约度分为不同的区域, 在不同的区域, 可行解和不可行解分别采用不同的评判方法.该方法相对于可行性法则, 利用了不可行区域中具有较好目标函数值的不可行解的信息, 具有更好的收敛性能.该方法使用一个显式的分段函数(如公式(23)、公式(24))控制ε, 然后根据公式(25)(ε水平比较)来评判个体的优劣:

$ \varepsilon (k)=\left\{ {\begin{array}{*{20}{l}} {\varepsilon (0){{\left( {1-\frac{k}{{{T_c}}}} \right)}^{cp}}, {\rm{ }}0 < k < {T_c}}\\ {0, {\rm{ }}k \ge {T_c}} \end{array}} \right. $

(23)

其中, ε(0) 的定义为

$ \varepsilon \left( 0 \right)=v({X_ heta }) $

(24)

$ ({f_1}, {v_1}) < ({f_2}, {v_2}) \Leftrightarrow \left\{ {\begin{array}{*{20}{l}} {{f_1} < {f_2}, {\rm{ if }}{v_1}, {v_2} < \varepsilon }\\ {{f_1} < {f_2}, {\rm{ if }}{v_1}={v_2}}\\ {{v_1} < {v_2}, {\rm{ otherwise}}} \end{array}} \right. $

(25)

其中, X_θ是种群个体根据约束违约度升序排序后第θ(θ=0.05×NP)个个体, NP为种群的规模, k为当前代数或迭代次数以及控制代数T_c∈[0.1T_max, 0.8T_max]; 而cp满足区间^{[2, 10]}.在文献[7]中, 两位作者将ε约束处理方法与差分进化算法结合构成ε差分进化算法(εDE), 该算法采用了一个基于梯度的变异算子来寻找可行解.虽然基于梯度的变异算子可以避免对不可行域进行无意义搜索, 但若对种群中全部的不可行解进行修复, 则它很耗时.因此, 在文献[7]的基础上, Bu和Luo等人^[43]提出了一种基于群体的修复策略, 该策略不是盲目地从种群中选择不可行个体, 而是从种群中选择一些具有代表性的不可行解基于梯度修复法进行修复.

ε约束处理方法的本质是通过用ε水平比较方法替换普通的比较方法来评价个体的优劣, 将用来求解无约束优化问题的算法转换成求解带约束的优化问题的算法.所以, 该类算法的性能主要由进化算法性能的好坏来决定.研究者们已针对如何有效提高该类约束优化进化算法(εDE)的稳定性、效率等性能问题进行了一系列后续的研究.

Brest等人^[44]提出了一种自适应差分进化算法(jDEsoco)用于求解单目标实值约束优化问题, 该算法除了使用老化机制重新初始化停滞不前的个体来加快种群的收敛速率的同时避免陷入局部最优之外, 还采用基于概率选择不同的DE策略(“rand/1/bin”|0.9和“best/1/bin”|0.1), 而每种DE策略的控制参数根据公式(26)、公式(27) 来进行自适应调整:

$ {F_{i, gen + 1}}=\left\{ {\begin{array}{*{20}{l}} {{F_l} + ran{d_1}*{F_u}, {\rm{ if }} \,\, ran{d_2} < { au _1}}\\ {{F_{i, gen}}, {\rm{\,\, \,\, \,\, \,\, \,\, \,\, \,\, \,\, \,\, \,\, \,\, \,\, \,\, otherwise}}} \end{array}} \right. $

(26)

$ C{R_{i, gen + 1}}=\left\{ {\begin{array}{*{20}{l}} {ran{d_3}, {\rm{ if }}\,\, \,\, ran{d_4} < { au _2}}\\ {C{R_{i, gen}}, {\rm{ otherwise}}} \end{array}} \right. $

(27)

其中, gen指遗传代数或称迭代次数, rand_i(i=1, 2, 3, 4) 取值范围为[0, 1], τ₁, τ₂, F_l, F_u的值分别为0.1, 0.1, 0.1, 0.9.

为了改善εDE的效率与稳定性, 必须要解决算法收敛性与种群多样性之间的冲突.Takahama和Sakai^[45]基于等级的ε约束差分进化算法(εRDE)来解决约束问题.通过ε水平比较为种群的每个个体进行排序并分配等级(等级越低说明解的质量越好).在DE操作中, 个体根据所选基向量(个体)的等级高低选择不同的参数值(F扩张因子、CR交叉概率), 基向量(个体)的等级越低, 则选择的参数值(F扩张因子越小和CR交叉概率越大)有助于增加算法的收敛速度; 相反(F扩张因子越大和CR交叉概率越小), 则有助于保持种群的多样性.

该方法具有较好的收敛性能, 已与GA^[46], PSO^[47]等算法相结合, 并取得了较好的优化效果.但该方法需要人为地设定不同的ε水平, 没有考虑实际的搜索场景, 因此, 这类约束优化算法的收敛速度方面存在一定的不足.此外, 该方法高度依赖ε初始值和变化函数的选取, 这也是ε约束处理法需要进一步改进的地方.

2.5 多目标优化法

多目标优化法的主要思想是:将约束优化问题转换为多目标优化问题, 然后利用多目标优化技术来处理转换后的问题.所以下面先给出了多目标优化问题的相关描述和多目标优化中的几个重要定义, 不失一般性, 考虑以下具有n个决策变量和m个目标函数的多目标优化问题(multi-objective optimization problems, 简称MOPs):

$ {\rm{min\,\, or\,\, max}}\;f\left( x \right)=\left( {{f_1}\left( x \right), {f_2}\left( x \right), \ldots, {f_m}\left( x \right)} \right) $

(28)

其中, x=(x₁, x₂, …, x_n)∈X?$\Re $ⁿ为决策变量, X为决策空间; f(x)∈Y?$\Re $^m为目标向量, Y为目标空间.

定义4(Pareto支配(Pareto dominance)).决策向量x_u∈X Pareto支配决策变量x_v∈X, 记为x_u?x_v, 当且仅当:

●i∈{1, …, m}满足f_i(x_u)≤f_i(x_v);

●j∈{1, …, m}满足f_j(x_u) < f_j(x_v).

此时, 也称决策变量x_v Pareto劣于(dominated by)决策变量x_u.若决策变量x_u与决策变量x_v不存在Pareto支配关系, 则称它们非劣(non-dominated).

定义5(Pareto最优解(Pareto optimality)).变量x_u∈X称为X上的Pareto最优解, 当且仅当$ eg $?x_v∈X使得:

$ {x_v} \prec {x_u}. $

定义6(Pareto最优解集(Pareto optimal set)).对于给定的多目标优化问题f(x), Pareto最优解集(ρ^*)定义为

$ {\rho ^ * }=\{ {x_u} \in X| eg \exists {x_v} \in X, {x_v} \prec {x_u}\} $

在将约束优化问题转换为多目标优化问题时, 通常存在着两种方式:第1种方式将约束优化问题转换为具有两个目标的多目标优化问题, 其中, 第1个目标是目标函数f(x), 第2个目标为个体的约束违约度函数v(x); 第2种方式将约束优化问题的目标函数和约束条件分别作为不同的目标看待, 这样, 将优化约束问题转化为具有m+1个目标的多目标优化问题.

在多目标技术方面, 一般来说, 主要有3种多目标优化技术运用于处理转换后的问题.

(1)使用Pareto占优作为一种选择准则;

(2)使用Pareto排序(ranking)来定义个体适应度值;

(3)将种群体划分为若干个子群体, 对子群体中个体的评估或者基于目标函数, 或者基于某个约束条件.

多目标优化法不仅成功地避免了目标函数和约束之间的不平衡问题, 而且在处理约束优化上取得了较好的性能.在2009年, 王勇等人^[48]对该类算法进行了系统的分析与论述, 所以本文首先选取其中具有代表性的几种算法进行回顾, 然后再对该类算法的最新的研究成果进行详细论述.

Surry等人^[49]提出了COMOGA(constrained optimization by multi-objective genetic algorithm)算法, 在该算法中, 约束优化问题被视作约束满足问题或无约束优化问题来处理.当约束优化问题被视为约束满足问题时, 目标函数被忽略, 此时, 个体之间的比较由Pareto排序决定, Pareto排序基于约束违反来定义.当约束优化问题被视为无约束优化问题时, 约束条件被忽略, 此时, 个体之间的比较由目标函数决定.Venkatraman和Yen^[50]提出了一种包含两个阶段的通用框架来处理约束问题:第1阶段, 当种群里没有可行解时, 该方法仅使用约束违反程度选择个体; 当种群中出现可行解时(第2阶段), 原来的约束优化问题转化为一个双目标优化问题, 其中, 一个目标是原来的目标函数, 而另外一个目标则是约束违反程度, 之后, 再使用Pareto排序的方法来选择个体.

Wang等人^[8]提出了一种HCOEA(hybrid constrained optimization evolutionary algorithm)算法, 在该算法中, 将约束问题转化为双目标优化问题, 采用带小生境操作的遗传算法框架, 并基于非支配解的概念进行解之间的替换, 但只有子代个体在支配父代个体时, 才以概率1替换父代个体.同时, 算法除了引入类似于MOEA中不可行解的存储和替换机制外, 还引入一种聚类分割和多个父代交叉的局部搜索技术, 根据搜索空间中各个个体之间的相互距离, 将种群聚类为M个子种群, 各子种群通过内部交叉产生新个体, 进而组合新种群.

Coello^[51]基于向量评估遗传算法求解约束优化问题.将种群分成相等规模的子种群, 每个子群对应一个约束条件, 其中, 某个子群体将目标函数作为适应度函数来评价个体, 其余的子群体将相应的单个约束条件作为适应度函数来评价个体, 其目的在于:每个子群体试图找到对应约束条件的可行解, 通过联合所有的子种群, 该方法找到所有约束条件下的可行解.该算法的主要缺陷在于:子群体的个数会随着约束条件的个数呈线性增加; 另外, 如何确定子群体的合理规模有待进一步研究.

Gong和Cai^[52]提出了一种多目标差分进化算法, 该算法引入正交设计法用于种群的初始化以及基于正交的交叉算子来提高算法的局部搜索能力, 并采用差分进化作为搜索机制.在该算法中, 比较父代个体和子代个体时先优考虑约束条件.如果子代个体Pareto支配父代个体, 则立即用子代个体取代父代个体.如果两个比较个体在约束条件上存在非支配关系, 则再考虑目标函数和约束违约度, 被支配的父代个体则立即被子代个体取代.之后, 将非劣的子代个体与父代个体组成一个混合群体, 然后选取其中的非劣个体进入下一代.

Reynoso-Meza和Blasco等人^[53]提出了一种sp-MODE(the multiobjective differential evolution algorithm with spherical pruning)法来解决高约束优化问题, 该方法基于双重选择策略.在每一次迭代, 首先从种群(P)中随机选择N个个体组成的子群体通过DE进化产生子代群体(P_n)后, 然后利用Pareto排序的方法从联合群体(P_n∪D)中找出所有的非劣个体, 最后采用球形修剪技术从非劣解集中筛选出每个球形网格内具有较小约束违反程度的非劣个体(D).同时, 球形裁剪技术维持了种群的多样性.当产生一个新的个体时, Pareto占优用于比较该个体与其父代个体的优劣.

Singh和Ray等人^[54]针对很多约束优化问题的最优解位于可行域边界的特点, 提出了IDEA(infeasibility driven evolutionary algorithm)法.在该方法中, 约束优化问题被转化为两个目标的多目标优化问题来处理:第1个目标为原目标函数f(x); 另外一个目标为基于种群成员之间的个体相对约束违约度(根据每个约束条件的违反程度, 将种群中的每个个体从低到高进行排序; 同时, 约束违反度越低的个体分配的等级越高(可行个体对应的等级为0), 个体相对约束违约度是所有约束条件上对应等级的总和).在进化的过程, IDEA首先根据个体的可行性将种群划分成两个群体(可行解集和不可行解集), 并分别对该两个群体使用Pareto排序过程的方法来定义个体的等级, 然后再按一定比例u(用户定义), 分别从两个群体中选择个体组成下一代种群.

Wang和Cai^[55]提出CMODE(combining multiobjective optimization with differential evolution)算法, 该算法将多目标优化策略与差分进化算法结合来处理约束问题.CMODE首先从种群中随机选择n个个体组成的群体经过差分进化的变异、交叉操作产生子代群体, 然后从子代群体找出全部的非劣个体; 接着, 随机替换父代群体中的任意一个被支配个体(如果该劣于个体存在).此外, 该方法采用一种不可行解存档和替换机制, 将每一代种群中好的不可行解存档起来, 用于在后续进化中随机地替换种群中的个体.一方面, 该机制保证了种群的多样性, 使算法不会过早收敛到某些可行的局部最优; 另一方面, 该机制有利于对边界区域进行局部搜索.同年, Wang和Cai^[56]再次提出了一种由全局模型和局部模型动态组成的混合框架(dynamic hybrid framework, 简称DyHF), 用来求解约束问题.DyHF根据当前种群中可行解的比例自发地实行全局搜索模型或者局部搜索模型.局部搜索模型首先将种群通过聚类方法划分成多个群体, 然后分别从每个子代群体中找出所有的非劣个体, 最后选择一个非劣个体随机地替换其父代群体中一个劣于个体(如果该个体存在), 使种群从不同方向迫近可行域.全局搜索模型是从整个种群的角度利用Pareto优劣关系比较个体, 选择父代个体和子代个体中的优胜者.

Li和Zhang^[57]提出了一种有偏支配的约束处理技术, 使用该有偏支配进行个体的比较.假设第k个目标函数f_k(x)是偏向的目标函数(有偏目标函数), 有偏支配的定义如下:

定义7(有偏支配或b-支配(biased dominance or b-dominance)).决策向量x_u∈X有偏支配决策变量x_v∈X, 记为x_v?_bx_u, 当且仅当:

$ \left\{ {\begin{array}{*{20}{l}} {{x_u} \prec {x_v}, {\rm{\,\, \,\, \,\, \,\, \,\, \,\, }}f({x_u}) < b \wedge f({x_v}) < b}\\ {f({x_u}) < f({x_v}), {\rm{ otherwise}}} \end{array}} \right. $

(29)

其中, b为有偏阙值.当两个比较个体的第k个目标函数的函数值小于或等于b时, 有偏支配等价于Pareto支配; 当两个比较个体中任何一个的第k个目标函数的函数值超过b时, 有偏支配只考虑第k个目标函数而忽视其他目标函数.文献[57]将有偏支配与差分进化算法结合, 提出了一种有偏的多目标优化算法(biased multiobjective optimization, 简称BMO).在每一代开始时, 使用公式(30) 来更新b的值, 对种群中的每个个体使用差分进化的变异和交叉操作生成一个子代个体.如果新生成的子代个体有偏支配对应的父代个体, 则立即用新的子代个体取代父代个体.算法重复上述迭代过程, 直到终止条件满足.最后, 种群中的最好个体就是算法得到的最终解.

$ b={G_{{\rm{max}}}}-{G_{{\rm{min}}}}-0.0001 $

(30)

其中, G_min是种群中个体的最小约束违反程度值, 而G_max为种群中个体的最大约束违反程度值.当种群中所有的个体都远离可行域时, b取值较小, 进化的目标侧重于减小约束违反程度, 使种群中的个体向可行域靠近; 当种群中部分个体已接近可行域或者种群中存在可行个体时, b值较大, 使得目标函数和约束违反程度得到同时考虑, 进而找到全局最优解.

Gao和Yen^[58]提出了一种双种群协同进化差分算法, 它把原来的约束问题转变成一个双目标优化问题, 其中, 第1个目标是目标函数, 第2个目标是约束违约度.在进化过程中, 为了分别对待这两个目标, 整个种群根据个体的可行性被划分成两个子群体, 每个子群体优化对应的目标.同时, 该文还引用了一种信息共享机制促进两个子群体之间搜索信息的相互交流, 旨在让不可行个体变成可行个体并寻找到最优解.

多目标优化法在求解约束优化问题时表现出来突出的收敛结果和性能, 特别适用于解决可行域空间很小的问题.但不得不承认的是, 该方法需要耗费较高的计算资源, 这也是多目标优化法应用的瓶颈之一.

2.6 混合法

由于约束问题的复杂性和多样性, 采用单一的约束处理技术往往达不到理想的效果.目前, 约束优化技术研究的主流方向是设计具有自适应机制和混合机制的高效技术.混合法就是将两种或者以上不同的约束处理技术相结合用于处理约束问题, 该方法充分利用不同约束处理技术的特点来更有效地解决约束优化问题, 但如何合理地混合不同约束处理技术, 是研究该方法的关键点.

基于上述思想, Mallipeddi等人^[9]提出了一种约束处理技术的集成框架(ensemble of constraint handling techniques, 简称ECHT)来综合利用各种已有的约束处理技术.该方法采用多种群策略, 不同的种群采用不同的约束处理机制, 并通过种群间的相互学习来应对复杂的搜索场景.

Wang和Cai等人^[59]提出了一种自适应均衡模型(adaptive trade-off model, 简称ATM), 该模型将种群的进化过程分为3个阶段, 并根据群体在3个不同阶段的特点采取不同的选择策略.当种群中只存在不可行解时, 该模型首先将约束问题转换成多目标优化问题, 然后通过Pareto排序的方法从种群中选择具有较小约束违约度的非劣解进入下一代种群.当种群中同时包含不可行个体和可行个体时, 该模型采用自适应罚函数法将有约束问题转化成无约束优化问题处理, 并根据转变后的个体适应度函数选择个体.当种群中仅包含可行解时, 个体之间的比较和选择基于目标函数.他们还提出一种ATM-HD(hybrid differential evolution and adaptive trade-off model)算法^[60], 该算法将混合了多种变异策略的差分进化算法和ATM相结合用来处理约束问题.

Elsayed等人^[61]提出了一种差分进化的集成框架, 该框架包含不同的差分进化操作——由4种变异操作、两种不同的重组操作和两种约束处理机制(可行性法则和ε约束处理法)随机组合16种不同策略的集成.在进化的过程中, 种群中的个体选择随机选择一种策略, 每种策略通过它改善个体的能力来决定种群中个体采用该策略的使用比例(概率).此外, 该文采用了一种局部搜索操作来提高解的精度.Jiao等人^[62]提出了一种新型的选择进化策略算法, 在该算法中:首先, 种群的个体全部经过进化策略后产生新的子代种群; 然后将父代种群和子代种群组合, 除去其中具有较大约束违反程度的个体; 最后, 从组合种群中选出所有的非劣个体进入下一代种群, 若非劣个体数少于规定的种群规模, 则使用自适应转换个体的目标函数的方法(罚函数法)从组合群体选择剩余个体进入下一代种群.

Wang和Liu等人^[63]基于正交设计差分进化算法用于处理约束优化问题, 该算法把种群中的个体随机成对采用正交设计产生多个子群体, 然后合并多个子群体成一个群体, 再用Pareto排序选出群体中选择所有的非劣个体.根据所有非劣个体组成的群体中是否存在可行解, 采用两种不同的替换操作.如果群体中不存在可行个体, 用约束违反程度最小的非劣个体随机替换父代种群中的劣于个体(假如该劣于个体存在).如果群体中存在可行个体, 以概率0.8选择群体中的两个非劣个体随机替换父代群体中的两个个体或者以概率0.2基于可行性法则用非劣的可行子代个体替换最差的劣于父代个体.

Cai和Wang^[64]提出了MOEA(multi-objective optimization-based evolutionary algorithm, 简称MOEA)算法, 算法以实数编码GA作为搜索框架, 根据替换操作的差异, 给出3种不同模型:在模型Ⅰ中, 每次迭代获得的所有非劣个体, 均用一对一方式替换父代个体中受支配的劣于个体; 在模型Ⅱ中, 每次迭代获得的所有非劣个体, 仅从中随机选取一个非劣个体用于替换父代个体中任意一个被支配个体; 在模型Ⅲ中, 采用可行性法则进行替换操作.同时, 算法根据种群中可行解与不可行解的比例以及解的目标函数值与约束违约度, 适应性地从3种模型中选择一种模型进行父代与子代间的替换.另外, 该算法还引入一种不可行解的存档和替换机制, 其旨在于引导种群向可行域靠近.

在2010年的约束优化的国际竞赛中, Tasgetiren和Suganthan等人^[65]提出了eDE(ensemble of differential evolution algorithms)算法.在该算法中, 种群中每个个体采用不同的差分进化策略(比如DE/best/1/bin, VPS).在算法的不同过程中采用不同的约束处理技术, 比如可行性准则, 用于选出种群中最好的个体.当产生一个新的个体后, ε水平比较用于判断父代个体和子代个体的优劣, 在VPS(variable parameter search)操作产生的子代个体和父代个体间之根据自适应惩罚适应度进行比较.

Mani和Patvardhan^[66]通过实验和理论分析发现适应性罚函数法和可行性法则之间存在性能互补的关系(存在优势和劣势互补), 设计了一种双种群的自适应协同法, 该方法使用了两个同等规模的种群.在进化的过程中, 第1个种群中个体采用自适应罚函数法来计算个体的适应度值, 第2个种群中个体采用可行法则计算个体的适应度值.同时, 第2个种群的个体与第1个种群进行个体交换(信息交流)来自适应地调整惩罚系数.

Gan和Peng等人^[67]提出了一种自适应决策者(adaptive decision maker, 简称ADM), 该ADM以自适应惩罚函数的形式决定候选解(子代群体中的非劣个体)是否取代其父代个体.在每一代开始时, 先从种群中随机选取u个个体组成一个群体, 对群体中个体进行单形交叉(simplex crossover, 简称SPX)操作后产生新的子代群体; 然后, 采用Pareto占优的选择准则从子代群体中找出所有的非劣个体; 最后, 根据转换后的自适应惩罚函数公式(31) 来计算个体的适应度值, 再从种群中选择一个最优的非劣个体(惩罚适应度最好的个体), 并将此非劣个体与种群中最差的劣于个体(惩罚适应度最差的个体)进行比较, 如果非劣个体具有更小的目标函数值, 则立即用新的非劣个体取代父代个体:

$ F\left( x \right)=f\left( x \right) + {10^a}^{(1-\rho )} \cdot v\left( x \right) $

(31)

其中, f(x)为目标函数, v(x)为个体总的约束违反程度, ρ为当前种群中可行解的百分比, α满足区间^{[1, 15]}.该方法存在的主要限制在于, 需要反复实验来进行参数的调优.

Deb和Datta^[68]提出一种多目标优化和惩罚函数方法相结合的方法来处理约束优化问题.在方法中, 约束优化问题被转变成无约束优化问题.在每一次迭代, 首先用双目标优化法找到非支配前沿, 若满足条件(隔一定代数t), 根据当前非支配前沿与惩罚函数之间存在的关系(在二维坐标系(f-v)里, 非支配前沿中位于约束违约度等于零处的点斜率来估计惩罚函数中惩罚系数)确定优良惩罚系数的估计值, 然后利用罚函数法将约束问题转变成无约束优化问题, 并用局部搜索模型来求解转换后的无约束优化问题, 直到终止条件满足(解在局部搜索前后所对应的目标函数值之间的差值小于0.000 1), 最终得到约束问题的最优解.在文献[68]的基础上, 他们加入了一种自适应的约束标准化技术^[69].近年来, 他们再次提出一种基于个体惩罚的约束处理方法^[70], 与之前提出的方法不同之处在于, 该方法利用双目标优化法来确定每个约束条件的惩罚系数的优良估计.

3 亟待解决的问题

虽然约束优化进化算法已经取得了一定的成果, 但是仍有很多问题需要解决, 主要是:

(1) 等式约束处理

目前, 约束优化进化算法对于等式约束优化问题的约束效果并不令人满意, 难以收敛算法最优解.目前主要采用动态缩小δ值来提高算法的收敛性能, 但面对非线性等式约束、离散等式约束等问题, 依然具有较大的挑战.

(2) 离散约束优化问题

在该类约束优化问题中, 问题的可行区域是离散的, 这使得算法容易陷入某个可行区域中的最优解, 难以获得全局最优解.如何使得搜索能穿梭于各个可行区域间, 是该问题的主要挑战.多种群、分布估计可能是解决该问题的可行方案之一.

(3) 约束条件与优化目标之间的不平衡

约束优化不仅要求所得解的质量, 同时要求满足约束条件.对于有些情况, 如过分强调满足约束条件, 将有可能导致搜索偏离性能好的区域; 相反, 如果过分强调解的质量, 则有可能导致搜索空间偏离可行域.因此, 如何根据问题的先验信息和从搜索过程中得到的知识来有效协调约束与目标之间的不平衡非常重要.

(4) 可行解与不可行解的分别对待

约束优化问题相对于普通约束优化问题, 其本质区别在于如何对待不可行解携带的信息.在早期的研究中, 对该问题的研究取得了较大的进展, 但近年来对该基本问题并没有取得实质性的进展.这主要是由于近年来进化算法的搜索效率得到了快速的发展, 弥补了约束处理的不足.模糊理论、粗糙理论、ε约束处理等技术可能是该问题的研究方向.

(5) 普适的约束处理技术

目前, 不同的约束处理技术对应不同的随机搜索技术有着不同的搜索效率.无免费的午餐定理告诉我们, 没有任何算法能对所有问题都高效.但我们能不能设计一种对大多数类别算法都高效的约束处理机制?这将会是未来研究的方向之一.

(6) 自适应约束处理技术

正如前面所说, 不同的约束处理技术对应不同的随机搜索技术有着不同的搜索效率.设计一种针对不同的搜索状态而采用不同的约束处理机制, 自适应地选择不同的约束处理技术可能是可行的方案之一.另外, 超启发式框架也具有一定的可行性.

4 结束语

约束优化进化算法是智能优化算法研究领域研究的重要课题之一.虽然经过多年的研究, 但依然存在较多的问题亟待解决.本文对现有进化算法中的约束处理技术进行了系统的分析, 并将其根据处理约束的方式不同划分为6大类, 同时, 对各方法的研究现状和主要不足进行了逐一分析, 最后给出了进化算法中的约束处理技术研究亟待解决的问题与拟解决方案.由于问题所涉及的方面过多, 不可能面面俱到, 希望与研究者们广泛交流共同促进该领域的发展.