基于代理模型可行规则法的优化算法

张慧晶，张国晨，谭 瑛，孙超利

(太原科技大学 计算机科学与技术学院，太原 030024)

0 引言

在工程应用和工业设计中存在着许多的约束优化问题，例如水资源分布网络设计[1]，资源分配[2]，优化控制[3]，DNA序列检测[4]等。这些不仅是单一目标的优化问题，同时有其他的附加目标约束条件。约束条件的存在将决策空间分成可行空间和不可行空间，所以在解决带有约束的优化问题时通常给带来很大的挑战性。

传统算法在解决约束优化问题时需要消耗大量的评价次数，因此使用传统优化算法解决该问题时，往往会因为实验代价昂贵而受到限制。进化算法在求解约束优化问题的过程中不依赖待优化问题的函数特性，因此得到广大科研人员的关注，并且提出了许多优秀的用于解决约束优化问题的优化算法例如jDE-2[5]，MDE[6]，SaDE[7],UDE[8]等。Michalewicz和Schoenauer[9]将目前用于解决约束问题的优化算法分为四种类型，具体如下：(1)优先寻找可行解类型的算法；(2)基于罚函数的优化算法；(3)将个体分为可行解和不可行解，然后根据解的类型分别进行优化的方法；(4)混合类型的优化算法，即同时具有以上两种或者三种的方法的优化算法。其中在以上四种类型的优化算法中最常用的是对不可行解添加罚函数的方法，但由于需要添加过多惩罚因子，该方法在应用过程中受到很大的限制。

同时，注意到代理模型广泛运用在解决代价昂贵的单目标优化问题(即实验代价昂贵或实验耗时较长)[10]，例如药物实验设计[11]，空气动力学实验设计优化[12]等。在将代理模型应用到进化算法时，模型管理往往起着至关重要的作用[13]。

本文所提出的基于代理模型优化的进化算法在解决昂贵单目标约束问题时，针对评价待优化函数约束条件较为昂贵(约束条件昂贵主要表现在两个方面：(1)约束条件过多，计算复杂；(2)单个约束函数的复杂度高，评价次数多)的难题，引入代理模型，主要用于拟合待优化函数的约束函数。本文的主要贡献如下：

(1)提出了将代理模型引入到昂贵约束函数的优化问题中的方法，可以有效地减少优化过程中的实验代价。

(2)提出了新的模型管理方法，主要用于解决含有多个约束问题的优化问题，既可以有效地减少建模成本，也可以提高模型预测的精度。

本文的文章结构安排如下：现阶段约束处理方式在文章的第一部分；本文所提算法的详细描述在第二部分；为了验证本文所提算法的有效性，采用了CEC2017约束函数测试集测试其结果，并且与其他优秀的算法对比，其具体描述在本文的第三部分。最后一部分为文章的总结。

1 相关工作

1.1 约束优化问题

约束优化问题的数学表达式如下：

(1)

在上述的公式(1)中x具体为：x∈RD且x=(x1,x2,x3,…,xD)，其中D表示待优化目标函数的决策空间维度，每个解的取值范围为[xj,min,xj,max];j=1,2,3,…,D.q表示待优化目标函数中不等式约束条件的个数，m-q表示待优化目标函数中含有等式约束条件的个数。

1.2 代理模型的选取及构建

实际的工程中存在很多约束优化问题，其约束函数函数是昂贵的；同时注意到在解决昂贵单目标优化问题中，许多学者将代理模型添加到优化算法中[14-20]，因此本文将采用同样的思想，本文中用到的代理模型为径向基函数模型(Radial Basis Function (RBF))。在把RBF模型与众多代理模型进行比较后，发现RBF模型拟合函数的稳健性和准确性更好，故我们采用此模型。RBF的简要描述如下：

在进行模型训练前，根据拉丁超立方体采样在决策空间中选取n个点作为训练模型的样本数据，其在决策空间的表示为u(1),u(2),…u(n)∈Rd，对应的函数值表示为f(u(1)),f(u(2)),…,f(u(n)).下面的公式(2)是基于插值的RBF模型。

(2)

在公式(2)中，‖·‖表示欧氏距离，p(x)是一个线性多项式，φ表示三次多项式具体形式为φ(r)=r3，λi∈R是三次多项式的系数。

为了求解以上基于三次方插值的RBF模型，我们通过φij=φ(‖u(i)-u(j)‖)i,j=1,2,…,n形成矩阵φ∈Rn×n.定义矩阵p∈Rn×(d+1)其中第i行为[1,(u(i))T].RBF模型可以通过公式(3)得到：

(3)

在此处0(d+1)×(d+1)∈R(d+1)×(d+1)是一个零矩阵，0d+1∈Rd+1是一个零向量，λ=(λ1λ2,…，λn)∈Rn和c=(c1,c2,…，cn)∈Rd+1是线性多项式p(x)的系数。

我们发现在进化算法中采用代理模型拟合待优化目标函数可以有效地减少进化过程中的评价次数。在实际应用过程中，将该方法与不用代理模型的方式在相同、有限的资源下进行比较，该方法对于优化问题可以获得更好的实验结果。因此，为解决优化过程中约束条件评价昂贵的问题，本文亦将代理模型添加到种群的进化过程中，同时为了解决在建立多个模型过程中时间复杂度较高和错误率累加的问题，将建立一个代理模型用于拟合从决策空间x到约束条件G(x)的函数。

为使模型可以更好地引导种群的进化，以及对于模型进行更新，会在种群的每一代个体进化的过程中，选择一些个体进行真实计算，并且更新代理模型。本文提出用于真实计算的个体的选择标准为：(1)子代通过模型预测的值G(x)≤0，说明其通过模型预测该个体满足约束解，需要进行真实计算确认其是否满足约束。(2)当子代中所有的个体通过模型预测都不满足约束的话，则首先根据所有子代个体的约束违反值G(x)进行升序排列，根据排序的结果选择前NP/10个个体进行真实计算，经过计算的个体会用于模型更新。

1.3 约束处理方法详述

约束优化问题广泛存在于实际的工程中，而且在许多情况下一个优化问题中往往存在多个约束条件，这些约束条件可分为不等式约束条件，如公式(4)和等式约束条件，如公式(5).在实际优化过程中，往往将等式约束条件转化为不等式约束条件，其转化过程如公式(6)，其中ε表示等式约束条件的容忍度，是一个较小的、接近于0的数。

gi(x)≤0,i=1,2,…,q

(4)

hj(x)=0,j=q+1,q+2，…,m

(5)

|hj(x)|-ε≤0

(6)

在将等式约束转化为不等式约束之后，待优化函数可表示为：

(7)

在优化过程中所有的约束条件都需要被满足，同时为了避免同时优化多个约束条件，因此对每个约束条件做以下处理：

(1)当每个约束条件的计算结果小于0，则表示其满足该约束条件，故每个约束条件的求解结果逐个与0作比较，其较大的值为ci(x)的值，如公式(8)，可以发现当ci(x)的值为0则满足该约束条件。

ci(x)=max(gi(x),0)

(8)

(2)为了避免在种群进化过程中对多个约束条件同时优化而导致单目标约束问题转化成较为复杂的多目标优化问题，我们在经过公式(8)的处理之后，将所有的约束条件ci(x)求和，如公式(9)：

(9)

经过公式(9)计算之后，待优化函数的多个约束条件转化为一个约束条件G(x)，当G(x)=0时，该解满足所有的约束条件。

1.4 遗传算法(GA)

遗传算法(Genetic Algorithm,GA)是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应的全局优化搜索算法。它在20世纪60年代由J.H.Holland教授提出，并且被广泛用于解决优化问题[14]。遗传算法的主要流程包括：选择、交叉和变异，在本文中采用了模拟二进制交叉[15]的交叉算子和多项式变异[16]的变异算子，其表示如公式(10)和公式(11).

其中，

(10)

(11)

适当的变异算子能够增强种群的多样性，减少其陷入局部最优的概率，同时可以对种群的局部搜索能力进行改进。

在本文中提出的个体选择策略主要采用的是可行规则法，可行规则法具体描述见3.

2 基于代理模型的费时优化问题优化算法

在解决费时的昂贵约束优化问题时，添加代理模型到种群进化过程中能够有效地降低种群的评价次数，从而减少实验代价。在本文提出的基于代理模型的费时昂贵约束优化算法中，首先将个体的所有约束违反度进行求和，具体的方法见2.3，然后根据合并之后的函数进行建模。通过此方法可以有效的降低由于同时使用多个代理模型而造成的错误率累加的问题，并且降低建立代理模型的时间，进而用其在引导种群进化时，减少使得种群向错误的方向进化的情况发生。

本文提出的用于解决昂贵约束问题的基于代理模型辅助的进化算法的算法流程图，如图1所示。具体描述如下：

图1 算法流程图Fig.1 Flow chart of the algorithm

Step1.依据拉丁超立方体采样产生个体，并且进行真实计算，存储于数据库Data.设定最大评价次数ffmax，交叉概率Cr，变异概率Mr，种群数量Np；

Step2.从数据库中选择10*D个个体，计算这些个体的约束违反度G(x)，并且建立代理模型M；

Step3.根据进化算法产生子代个体，计算其适应值f(x)，通过模型M预测其约束违反值G(x).

Step4.根据可行规则法对子代和父代进行筛选。可行规则法具体描述如下：(1)如果两个个体都满足约束，则适应值较小的个体保留到下一代。(2)如果两个个体一个满足约束而一个不满足约束，那么满足约束的个体将保留到下一代。(3)如果两个个体都不满足约束，则约束违反值较小的个体会保留到下一代；

Step5.选择ff个体进行真实计算，其选择标准详见2.2；

Step6.f=f+ff；

Step7.如果实际评价次数f小于等于ffmax则进行Step3，否则结束种群进化，输出最优解。

3 实验

3.1 实验函数选取及参数设定

为了验证本文提出算法的有效性，选取被广泛采用的CEC2017[19]单目标约束测试函数来进行实验，同时将本文提出的代理模型的算法框架MGA，与基础算法GA分别做实验对比，并进行结果分析。

实验过程中用到的参数有：种群数量为100，最大评价次数为1 000次，GA变异概率、交叉概率分别为1/d、1.为了使实验结果具有说服力，本文提出的代理模型的算法MGA和原算法GA使用相同的参数进行实验对比。同时，为了说明算法在解决昂贵优化问题时的有效性，每个测试函数独立运行30次，取其均值作为对比结果。

3.2 结果及分析

表1展示了添加代理模型的MGA和原算法GA在CEC2017约束测试函数中的对比实验结果。添加代理模型的算法相比原算法在有效次数评价次数下，有25个函数的实验结果较好。原函数GA在1 000次评价次数下只有5个函数可以寻找到最优解，并且与MGA相比，有三个表现较好。而MGA可以寻找到可行解的函数有12个，比GA能找到可行解的函数多7个。另外，在其余的测试函数中，虽然MGA和GA都未能找到可行解，但是MGA得到的结果中约束违反值比GA小，所以可以得到使用代理模型能够有效地解决昂贵约束条件的优化问题。

4 结论与讨论

本文提出将代理模型添加到进化算法的框架运用在解决昂贵约束条件的优化问题中，通过添加代理模型的MGA与GA在CEC2017约束测试函数实验对比显示： MGA在相同的实验条件下对比原算法GA可以得到更优秀的实验结果。这说明本文提出的将代理模型添加到进化算法的框架，来解决昂贵约束条件的优化问题是有效的，可以有效降低算法的评价次数；在实际应用过程中，亦可以节省大量的资源。同时，仍有部分函数在较少的评价次数下未能找到可行解，因此在将来，我们将提出更为有效的模型管理方法，使其在更少的资源下可以得到更为优秀的结果。