在实际问题及工程优化方面存在着诸多约束限制，这类问题被称为约束优化问题(constrained optimization problems, COPs)，处理这类问题的主要矛盾为最终解须满足全部约束限制，但由于约束的限制使得可行域变小，因而增加了搜索难度。一般进化算法(evolution algorithm, EA)在解决无约束优化问题中取得了优异表现，因此，近几年以来众多学者开始研究不同的约束处理机制，以期改进EA在约束优化问题中的不足，解决约束优化带来的难题^[1]。

差分进化(differential evolution, DE)算法是基于“贪婪竞争”机制的全局寻优算法，具有结构简单、控制参量少，可靠性和鲁棒性强的特点^[2]。将约束处理机制引入到DE(constrained differential evolution, CDE)算法中来解决约束优化问题成为广阔的研究领域。Takahama等人^[3]提出了一种算法，该算法将约束处理机制引入到DE算法中实现对约束优化问题的求解，然而约束缩放程度的选取对于算法寻优性能影响较大；Mallipeddi等人^[4]提出一种整体约束处理机制来解决约束优化问题，该方法为每一约束处理机制分配属于自己的种群进行运算，但是4种不同的约束处理机制大大增加了算法的复杂程度；Wang等人^[5]提出一种(μ+λ)-CDE算法，为了丰富种群多样性，该算法对父代种群采取3种不同的变异策略生成3种不同后代种群共同参与进化；为了克服(μ+λ)-CDE的不足，Jia等人^[6]对该算法进行了改进，并提出了一种基于存档的新型自适应权衡模型(ArATM)来处理约束条件，以上2种算法同时执行3种变异策略，大大增加了算法评价次数，其次，变异策略无法根据种群状态充分利用“精英”个体信息，算法灵活性不足，最终导致算法收敛速度下降；Gong等人^[7]将种群排序嵌入到变异操作中，并对工程优化问题进行分析，证明了算法有效性，但该算法在选择概率计算方面存在不足：不可行状态下的选择概率采用线性计算，无法保证多样性要求，半可行和可行状态下选择概率计算方式无法充分体现个体间的支配优势，无法在利用“精英”个体信息的前提下兼顾种群多样性；Wang等人^[8]提出了一种基于广义反向学习的种群初始化方法，该方法通过在种群初始化阶段生成初始和反向2个种群增加了算法在初始阶段的多样性和效率，然而算法仅考虑在初始阶段采用广义反向学习策略，并未将其应用于全局之中，降低了广义反向学习策略的功效性。本文受文献[5-8]的启发，提出一种基于广义反向学习的自适应约束差分进化(GOBL-ACDE)算法。初始阶段利用广义反向学习生成初始化种群，在每一代进化结束后利用广义反向学习执行种群"代跳"操作，提高算法多样性，避免算法陷入局部最优；引用自适应权衡模型将种群分为3种状态，分别对约束限制进行处理；采用改进自适应变异操作，根据个体排序值，分别选取余弦和反余弦模型计算选择概率，充分利用“精英”个体支配优势，针对前述算法变异策略固定的缺点，依据可行个体比率自适应选择“improved rand-to-best and current/2”策略完成变异，提高算法效率及动态性。通过与几种CDE算法在寻优精度的比较以及对广义反向学习和改进自适应排序操作在收敛性能的分析，证明本算法在处理约束优化问题方面具有较好的表现。

1 基本知识 1.1 约束优化问题

约束优化问题中，限制条件通常包含等式、不等式及边界约束等不同形式，本文对其做出如下定义：

(1)

式中, x=(x₁, x₂, …, x_n)∈D⊆Rⁿ为n维决策向量，f:D→R为目标函数，g_j(x)≤0和h_j(x)=0分别为l个不等式约束和m-l个等式约束，u_i和l_i分别为x_i的上、下界。

处理等式约束时，通常将其转化为相应的不等式约束

(2)

式中, δ为正容忍因子，取值为0.000 1。

解x到第j个约束的距离定义为

(3)

则解x到可行域边界的距离宇航义为约束违反程度，可表示为

(4)

1.2 差分进化算法

差分进化算法是一种基于种群变异的智能算法，种群个体通过差分变异、交叉、“贪婪”选择等操作产生后代个体，实现种群进化^[2]。

差分变异过程：父代向量x_i经变异因子F缩放后产生新的变异向量v_i，根据其生成方式差异，常用策略有：

1) “DE/rand/1”

(5)

2) “DE/best/1”

(6)

3) “DE/rand/2”

(7)

4) “DE/rand-to-best/1”

(8)

5) “DE/current-to-rand/1”

(9)

式中, x_{r1, t}, x_{r2, t}, x_{r3, t}, x_{r4, t}, x_{r5, t}为种群第t代中随机选取的不同个体，x_{best, t}为种群第t代中适应值最优个体，rand为[0, 1]均匀分布随机数。

交叉过程：父代向量x_{i, t}与变异向量v_{i, t}通过交叉因子C_R杂交，产生试验向量u_{i, t}，具体操作如下

(10)

式中, j=1, 2, …, n, j_rand是为了确保试验向量u_{i, t}异于目标向量x_{i, t}而选取参数，交叉因子C_R∈(0, 1)。

选择过程：差分进化算法对父代向量x_{i, t}和试验向量u_{i, t}的适应值进行比较，选取较优个体进入下代种群：

(11)

1.3 广义反向学习策略

广义反向学习^[9-10]概念定义如下：

n维空间中，设是个体x_i=(x_{i, 1}, x_{i, 2}, …, x_{i, n})的反向解，则定义为

(12)

式中, k为(0, 1)之间的均匀分布随机数，个体x_i在第j维的动态搜索范围为[a_j, b_j]。若取值超出搜索范围，则在[a_j, b_j]内对其进行随机生成：

(13)

由概率论可知，反向解的适应值等概率优于原个体解x_i适应值^[11]，将广义反向学习移植到DE算法中，充分利用反向种群信息，在不增加原有搜索空间前提下，极大地改进算法寻优效率，增加获得最终解的可能性。

基于广义反向学习的种群初始化伪代码如下：

算法1  GOBL种群初始化

随机产生初始化种群P₀=(x₁, x₂, …, x_NP);

for i=1 to N_P do

  for j=1 to n do

    P_{GOPji, 0}=k*(a_j+b_j)-P_{ji, 0};

    if P_{GOPji, 0} < a_j‖P_{GOPji, 0}>b_j then

      P_{GOPji, 0}=rand(a_j, b_j);

    end if

  end for

end for

选取{P_GOP0∪P₀}中前N_P个最优个体组成初始种群

基于广义反向学习的种群“代跳”伪代码如下：

算法2  GOBL种群“代跳”

if rand(0, 1) < J_r then//J_r为代跳率

  for i=1 to N_P do

    for j=1 to n do

    P_{GOPji, t}=k*(min(P_{ji, t})+max(P_{ji, t}))-P_{ji, t};

  if P_{GOPji, t} < min(P_{ji, t})‖P_{GOPji, t}>max(P_{ji, t})then

        P_{GOPji, t}=rand(min(P_{ji, t}), max(P_{ji, t}));

      end if

    end for

  end for

end

选取{P_GOPt∪P_t}中前N_P个最优个体组成新种群

2 自适应约束差分进化算法 2.1 自适应权衡模型

约束优化问题中不能简单的将适应值等同于目标函数值，需要充分考虑约束条件对适应值的影响，为了使CDE算法更加合理，本文引用自适应权衡模型(adaptive trade-off model, ATM)机制^[5]将种群划分为3种状态，分别计算其适应值。

2.1.1 不可行状态约束处理机制

在不可行状态下，约束处理机制不考虑目标函数值，仅计算约束违反程度，采用违约值代替适应值

(14)

2.1.2 半可行状态约束处理机制

半可行状态约束处理机制目的在于将可行与不可行个体维持在合理的状态，平衡目标函数值与约束违反程度，本文采用适应值转换策略^[12](adaptive fitness transformation, AFT)来实现该目标。

该策略将种群P划分为可行个体集合Z₁和不可行个体集合Z₂，分别表示为

(15)

个体x_i的目标函数值f(x_i)根据下式进行转换

(16)

式中，ϕ为种群中可行个体所占比率，f(x_best), f(x_worst)分别为Z₁中最优和最差目标函数值。

将目标函数值f(x_i)标准化

(17)

将违约值G(x_i)标准化

(18)

则个体最终适应值可表示为

(19)

2.1.3 可行状态约束处理机制

该状态下的选择标准只取决目标函数值，即个体适应值由目标函数值确定：

(20)

2.2 改进自适应排序变异操作 2.2.1 排序值分配

为了充分利用种群中“精英”个体所携带的信息，对种群按适应值从最优到最差进行排序^[13]，个体x_i的排序值由下式表示：

(21)

式中，N_P为种群规模，i为第i个个体在排序中的序号。

2.2.2 选择概率计算

约束优化问题中，个体选择概率需根据种群当前所处状态分别计算，不同状态下选择概率计算方法有所差异。

不可行状态下选择概率计算为：

(22)

半可行状态下选择概率计算为：

(23)

可行状态下选择概率计算为：

(24)

式中，i=1, …, N_P。

在不可行状态和半可行状态下采用余弦模型计算选择概率，可行状态下采用反余弦模型计算选择概率，2种模型选择概率与个体排序值之间的关系如图 1所示(种群规模N_P=50)。

如图 1所示，R₁, R₂为个体x₁, x₂的排序值且R₂>R₁，可以得到p₃-p₁>p₄-p₂，2个体选择概率差在不同模型下具有明显差异。这意味着在余弦模型下较优个体比较差个体更占支配优势，在反余弦模型下，由于概率差别微小使得这种优势并不明显。

在不可行状态下，为了使种群更迅速到达可行域，具有较小违约值的占优个体应分配较大的选择概率，所以采用余弦模型计算选择概率。

在半可行状态下，重要的可行个体和不可行个体携带大量重要信息，因此获得较高的排序值。目标函数值小的可行个体能够引导算法找到全局最优解，而目标函数值小、约束违反程度轻的不可行个体能够加速算法搜寻到可行域，这些个体应更加注意，因此，同样采用余弦模型计算选择概率。

在可行状态下，为了避免算法出现早熟情况而陷入局部最优，采用反余弦模型进行计算，以使减小较差个体被支配性，增加其被选中几率，保持种群多样性。

2.2.3 变异操作

本文采用“improved rand-to-best and current/2”变异策略执行变异操作，该策略依据上代种群中可行个体比率φ将变异策略分为两部分：“rand-to-best and current/2”前2项向量基于选择概率选取，剩余向量依照随机规则选取；“rand-to-current/2”前3项向量基于选择概率选取，剩余向量依照随机规则选取。

对每个个体随机生成服从N(0, 5, 0.15)的变异因子F_i和交叉因子Cr_i，进化过程中自适应变异因子与交叉因子通过下式计算^[14]

(25)

(26)

自适应排序变异伪代码如下：

算法3  自适应排序变异伪代码

根据个体适应值对种群排序R_i;

计算种群中每各个体的选择概率p_i;

计算变异因子F_i和交叉因子Cr_i;

if rand(0, 1) < then

依据选择概率选取r₁, r₂, r₃, r₄且r₁≠r₂≠r₃≠r₄≠i

    v_{i, t}=x_{1, t}+F_Z·((x_{r2, t}-x_{i, t})+(x_{r3, t}-x_{r4, t}));

else

依据选择概率选取r₁, r₂, r₃且r₁≠r₂≠r₃≠i

    v_{i, t}=x_{1, t}+Fz·((x_{rbest, t}-x_{r2, t})+(x_{r3, t}-x_{i, t}));

end

在约束优化问题初期，进化种群中可能仅包含不可行个体，此时算法主要目标应尽快使种群接近到达可行域内，因此有必要利用种群中“精英”个体(适应值较低)信息进行变异操作，因此采用“rand-to-best and current/2”变异策略。随着进化过程的发展，种群中可行个体数量增多，若继续向“精英”个体学习，会导致种群多样性急剧下降，陷入局部最优状态，导致算法早熟，所以此时采用“rand-to-current/2”变异策略，在保证种群多样性的前提下提高种群的开发能力。

3 GOBL-ACDE算法流程

基于广义反向学习的自适应约束差分进化算法的伪代码如下：

算法4  GOBL-ACDE算法

输入：搜索空间R，目标函数f，违约函数G，最大函数评价次数NFE_max

t=1;// t为进化代数

执行算法1生成初始种群;

while不满足终止条件do

  for i=1 to N_P do

    for j=1 to n do

    执行算法3生成v_{i, j};

    if rand(0, 1) < Cr_{i, j} or then

      u_{i, j}=v_{i, j}

      else    u_{i, j}=x_{i, j}

        end if

      end for

    for i=1 to N_P do

      if f(u_i)≤f(x_i) then

        x_{i, t+1}=u_{i, t};

      else

        x_{i, t+1}=x_{i, t}

      end if

    end for

    执行算法2进行种群代跳;

    t=t+1;

end while

输出：最优解

4 试验测试及结果分析

为测试GOBL-ACDE算法性能，验证其寻优能力，本文选取CEC2006中13个约束优化测试函数^[15]进行试验，并与CDE^[16]、DDE^[17]、A-DDE^[18]、εDE^[19]以及DPDE^[20]5种算法进行性能对比，各算法均与原文献相同。

4.1 GOBL-ACDE与其他算法性能对比

将GOBL-ACDE算法分别与上述5种算法进行比较，其中GOBL-ACDE、CDE、DDE以及DPDE分别独立运行30次，εDE独立运行50次，A-DDE独立运行100次，最大函数评价次数均为200 000次，各算法运行结果如表 1所示，其中黑体表示为较优算法值。

根据表 1各算法寻优精度指标^[15]可知，GOBL-ACDE算法在除函数g06之外的12个测试函数中，最优值均优于或等于其余5种算法。平均值或最差值结果中，GOBL-ACDE算法在函数g02的最差值略差于εDE和DPDE算法，在函数g03的最差值略差于DDE、A-DDE、εDE和DPDE算法，在函数g06的平均值和最差值略差于DDE、A-DDE和DPDE算法。

函数g02由于可行域大，函数结构复杂，搜索难度大，试验主要考察算法寻优能力，在GOBL-ACDE算法寻得最优值的前提下，仅最差值的表现略差于εDE和DPDE算法，因此综合考虑算法成功率以及评价次数，我们完全可以认为GOBL-ACDE算法的表现不弱于和DPDE算法，具有较强的搜索能力。对于函数g06，GOBL-ACDE算法已获得测试函数给出的标准值，虽然其结果略差于DDE、A-DDE和DPDE算法，但由于其最优值与标准值一致，我们仍可以认为GOBL-ACDE取得满意表现。

函数g03, g05, g11和g13为含有等式约束的测试函数，运行结果表明GOBL-ACDE算法综合表现完全优于其余5种算法，在所有4个测试函数中均寻得最优结果。其中，函数g03只有GOBL-ACDE算法寻得最优值，平均值和最差值方面同样优于其余5种算法；函数g05只有GOBL-ACDE和DPDE算法寻得最优结果，函数g11只有GOBL-ACDE和算法寻得最优结果，2组测试中GOBL-ACDE算法的平均值和最差值均优于其余4种算法；GOBL-ACDE和DDE算法在函数g13测试试验中均寻得最优结果，GOBL-ACDE算法在平均值和最差值表现方面同样取得较好表现，且明显优于其余5种算法，DDE算法虽寻得最优值，但平均值和最差值表现却并不令人满意。因此从综合表现来看，GOBL-ACDE算法在处理含有等式约束的约束优化问题时，相较于其余5种算法在精确寻优方面具有更好的性能。

函数g02和g03为非线性，根据表 1运算结果可知GOBL-ACDE算法在最优值、平均值和最差值三方面均优于A-ADE算法，表明GOBL-ACDE算法在处理非线性约束优化问题时较A-ADE算法更为出色。

函数g05, g07, g10, g11和g13不存在可行域，即在取得最优值时并不满足所有约束限制，在该条件下CDE算法仅在函数g07获得最优值，其余各指标性能均弱于GOBL-ACDE算法，这表明在处理无可行域约束优化问题时，GOBL-ACDE算法较CDE算法具有明显优势。

算法结果稳定性性方面，在函数g01, g02, g04, g10, g11, g12, g13测试中，GOBL-ACDE算法的标准差均优于或等于其余5种算法。其中函数g01和g02为高维函数，函数g01, g04, g11, g12为二次函数，这表明GOBL-ACDE算法在处理高维和二次约束优化方面表现出较强的鲁棒性，算法寻优稳定性优于其余5种算法。

在含有等式约束的测试结果中，GOBL-ACDE算法的标准差较CDE和εDE算法具有明显优势，其中函数g03, g05和g13较CDE算法分别相差6, 13和17个数量级，较εDE算法分别相差2, 7和16个数量级，这表明在等式约束下，GOBL-ACDE算法较CDE和εDE算法鲁棒性更强。

4.2 广义反向学习性能分析

为了对广义反向学习性能进行分析，本文分别对GOBL-ACDE和ACDE算法进行13个标准函数测试试验，2种算法分别独立运行30次，最大函数评价次数为200 000次。

试验运行结果如表 2所示，算法平均函数评价次数对比如表 3所示，其次图 2给出2种算法在函数g01和g06测试中的收敛图。

由表 2可知，GOBL-ACDE与ACDE算法在13个测试函数中均获得最优结果，在寻优性方面2种算法表现相近，其中ACDE算法仅在函数g02平均值略差于GOBL-ACDE算法。除g03和g06，GOBL-ACDE算法在其余11个函数测试中标准差均较小，显示了较好的稳定性、鲁棒性。

由表 3可以看出GOBL-ACDE算法在13个测试函数的12个中，平均函数评价次数均小于ACDE算法，从整体来看GOBL-ACDE算法在收敛速度方面优于ACDE算法。

图 2中a)、b)分别GOBL-ACDE与ACDE算法在函数g01, g06测试中的收敛图，其中实线代表GOBL-ACDE算法，虚线代表ACDE算法。

如图 2a)所示，GOBL-ACDE算法在函数g01测试中，种群从不可行状态过渡到半可行状态、从半可行状态过渡到可行性状态以及获得全局最优解的函数评价次数均小于ACDE算法，收敛速度明显优于ACDE算法。

由图 2b)可知，GOBL-ACDE算法在函数g06测试中，种群跳过半可行状态，直接从不可行状态过渡至可行状态，这是由于在进化过程中，上代种群完成交叉、变异、选择后执行“代跳”操作使得种群个体发生突变，促使后代个体全部满足约束条件转至可行状态，加速收敛速度直至GOBL-ACDE算法寻得全局最优解。ACDE算法在进化过程不存在种群"代跳"，因此种群从不可行状态过渡到半可行状态、从半可行状态过渡到可行性状态以及获得全局最优解的收敛速度慢于GOBL-ACDE算法。

上述分析表明GOBL-ACDE算法的收敛性明显优于ACDE算法，广义方向学习机制对算法收敛速度具有明显的提升。

4.3 改进自适应排序变异操作性能分析

为了分析改进自适应排序变异操作性能，本文对GOBL-ACDE和GOBL-CDE算法进行对比，其中GOBL-CDE算法采用“DE/rand/2”变异策略，随机选取r_i(i=1, 2, …, 5)，选取F=0.8, Cr=0.9, 2种算法分别独立运行30次，最大函数评价次数为200 000次。算法平均函数评价次数对比如表 4所示，图 3给出2种算法在函数g04和g11测试中的收敛图。

由表 4可以看出，GOBL-ACDE算法在13个测试函数中，平均函数评价次数均优于GOBL-CDE算法，这说明相较于采用单一“DE/rand/2”变异策略，改进自适应排序变异操作在寻优过程中具有更加出色的收敛性，提高了算法的收敛速度。

图 3中a)、b)分别为GOBL-ACDE与GOBL-CDE算法在函数g04、g11测试中的收敛图，其中实线代表GOBL-ACDE算法，虚线代表GOBL-CDE算法。

如图 3所示，在函数g04、g11测试中GOBL-ACDE算法均以较小评价次数到达可行状态并获得全局最优解，而GOBL-CDE算法在评价次数方面表现较差，收敛速度缓慢。函数g11测试中GOBL-CDE与GOBL-ACDE算法在收敛速度上有明显差距，这说明GOBL-ACDE算法在含有等式约束的优化问题中具有更好的处理能力。GOBL-ACDE算法在变异操作中充分利用“精英”个体携带的信息，根据种群可行个体所占比率自适应调节变异策略，在保证种群多样性的前提下提高了种群收敛速度，验证了改进自适应排序变异操作的有效性

5 结论

本文提出了一种基于广义反向学习的自适应约束差分进化算法，本算法通过生成反向种群完成种群初始化，进化过程中，通过执行"代跳"操作引导算法跳离局部最优状态，避免算法早熟，提高种群多样性。其次，采用自适应权衡模型将进化过程中的种群状态分为3类，并分别计算其相应适应值。最后，根据改进自适应排序变异操作对种群内个体进行排序，依据可行个体比率调节变异策略，提高算法动态性能，完成种群进化。本文通过对GOBL-ACDE与CDE、DDE、A-DDE、和DPDE 5种算法性能进行测试对比，结果显示GOBL-ACDE在寻优精确能力及稳定性方面具有较好表现，最后通过对广义反向学习机制和改进自适应排序变异操作分析，验证了其对算法收敛性的改进。