代理模型辅助的初始可行解产生方法

朱 珂，张国晨，谭 瑛，孙超利

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

寻优问题普遍存在于生产、生活中，如房屋设计、车间流水作业问题、车辆调度问题、城市交通管理问题等。这类优化问题都要求在满足主目标函数的同时，满足其他的约束条件[1-2]。在这类问题中，单目标约束优化问题(Single Objective Constraints Optimization Problem，简称SOCOP)是指包含一个目标函数和多种约束的问题，其中，约束函数十分复杂、计算非常昂贵(对于计算电磁学的一次模拟实验可能需要20 min[3-4])的问题又被称为昂贵的单目标约束优化问题(Expensive Single Objective Constraint Optimization Problem，简称ESOCOP).

对于求解ESOCOP，传统的确定性优化算法，主要有梯度投影法、可行方向法、梯度下降法等[5-6]。由于传统算法的优化结果依赖于初始点的选取，且要求目标函数或约束函数具有连续可微的性质，所以应用范围有限。进化算法因其对函数性质的要求较低，且具有智能性、自适应性和自组织性等优点而受到了的重视[7]。

粒子群算法(Particle Swarm Optimization，PSO)是由Kennedy和Eberhart于1995年开发的一种随机搜索算法，该算法对所优化的目标函数无任何连续可微的要求，且能在较短的时间内求得高质量的解，因此得到了广泛的应用。其中，PSO算法解决ESOCOP主要利用其较好的全局搜索能力用于粒子的迭代更新，从而加快优化过程[8-9]。但在现实生活中大部分工程问题的目标变量取值常包含各种各样的限制条件，因此如何合理地处理约束成为随机优化算法在工程应用中的核心问题之一[10]。目前针对此问题的技术主要有罚函数法、约束保持法以及可行规则法[11-12]。这三种方法在一定程度上可以降低问题求解的复杂度，但是它们都存在初始解产生困难导致的计算费时问题。

其中，在采用约束保持法求解SOCOP时，由于其只允许在可行域中的粒子进入下一次迭代，因此需要对产生的试验粒子约束违反度进行反复评价。若要获得较好的结果可能需要几千次、几万次甚至几十万次的评价，这无疑带来巨大的资源浪费，所付出的时间和费用以及人力资源代价很难让人接受。目前很多的算法研究在优化阶段使用代理模型(Surrogate Model，简称SM)预估目标值用以提高算法效率。但尚未有算法研究在生成初始解的阶段引入代理模型[13]。

因此，本文提出了基于代理模型辅助的初始可行解产生方法。通过在初始化阶段引入代理模型[14]估计约束冲突值的策略，着重考虑减少对试验粒子的评价次数，以缓解初始可行解产生费时问题。算法在给定边界约束范围内随机产生初始解后，再由PSO产生试验种群，此时不对试验粒子直接进行约束冲突值的计算，而是进入预判断阶段，采用初始种群中真实评价过的粒子构建模型，此模型用来对试验粒子约束违反度进行预判，若在可行域中，则进行真实约束冲突值的计算。本文通过对CEC2017的28个标准测试函数进行测试，验证了所提算法可大大减少评价次数，解决计算昂贵问题。

1 相关知识

单目标约束优化问题的数学模型可定义为如下所示：

miny=f(x)

s.t.gi(x)≤0;1

hj(x);a+1

x=(x1,x2，…，xn)∈Rn

(1)

在式(1)中，xmin

E=|x|gi(x)≤0，hi(x)=0，

|1

(2)

1.1 约束保持法

约束保持法是目前求解带有约束的问题时处理约束的主要方法之一。该方法的主要思想是确保进化过程中所有粒子始终在可行域范围内，并且该方法要求初始解都必须在可行域中。约束保持法对初始种群的要求较高，故存在初始种群产生困难的问题，本文针对约束保持法初始解产生困难问题展开研究。

对于约束保持法解决约束优化费时问题，当前研究主要采用：在初始化粒子时，直接在给定约束范围内随机产生点，并对这些点的约束冲突值进行评估，若粒子违反其中任一约束条件，则重新产生点，重复上述过程，直到找到所需初始可行解的个数。

约束保持法寻找可行初始解的过程中，其产生可行解没有规律性，因此很长一段时间内都无法产生满足约束条件的可行初始解。而本文针对上述所提问题展开研究，所提算法很大程度上提高了初始可行解的产生效率。

1.2 拉丁超立方体抽样

传统随机抽样方法，总体样本不进行分类、分组等，每个样本被抽中的概率都相等。样本中的个体完全独立，彼此间无关联性和排斥性，这种采样方式仅适用于总体样本之间差异程度较小和样本数目较少的情况。但是样本数较大或样本差异较大时容易出现数据过度聚集的问题。

本文采用的拉丁超立方体采样[15]先将样本按其差异程度或某一特征进行分类、分层，然后在各类或每层中再随机抽取样本单位。这种采样方式考虑了样本本身的特性，使得每类或每个分组都可以等概率的被采样点覆盖，抽取的样本分布比较均匀，保持了样本的多样性。采样过程如算法1所示：

算法1:超立方体采样过程假设:D向量空间,搜索范围[xmin,xmax]里抽取模NP个样本;Step1:在D维搜索空间中,每一维的搜索范围[xmin,xmax]分为模NP等份,每个小区间内[i(xmax-xmin)/NP,(i+1)(xmax-xmin)/NP] 根据均匀分布随机产生一个数;Step2:将这NP个随机数的顺序打乱;Step3:这NP个数即为:每个随机样本的概率,按照概率分布函数的反函数生成随机分布的值。

1.3 粒子群优化算法(PSO)

粒子群算法[8-9]是由Kennedy博士和Eberhart博士等于1995年提出来的智能优化算法，其算法思想来源于对鸟群和鱼群觅食行为的模拟。PSO依据对环境的适应度来引导种群中的个体向好的区域移动。该算法中粒子在搜索空间中以一定的速度飞行，忽略其质量和体积。该速度根据粒子自身及种群中其他个体的飞行位置动态调整。第t+1代每个微粒在第d维上的速度和位置更新方程如下：

vid(t+1)=wvid(t)+c1r1(pid(t)-

xid(t))+c2r2(pgd(t)-xid(t))

(3)

xid(t+1)=xid(t)+vid(t+1)

(4)

其中，惯性权重w使粒子保持运动惯性，使其有能力探索新的区域，c1调节粒子飞向自身最好位置方向的步长，c2调节粒子向全局最好位置飞行的步长。式(3)等号右侧分三部分，第一部分为粒子原先的速度，记录粒子的运动方向；第二部分为粒子的“认知”部分，表示对粒子对自身最优位置的记忆；第三部分为粒子的“社会”部分，表示粒子之间的信息共享和合作，代表了粒子有向群体最佳位置靠近的趋势。式(3)和式(4)可用于进化算法中对粒子位置的更新。

2 代理模型辅助的粒子群算法初始可行解生成方法

2.1 模型选择

本文采用径向基函数RBF[16-17](Radial-based Function)来构建模型。RBF是一种插值模型，已广泛应用于各种科学和工程领域[18]。同时利用该模型求解复杂优化问题的有效性已经得到的了证明[19]。RBF使用简单基函数的加权和来内插散点。给定数据点x1，x2……xn∈RD和函数值f(x1)，f(x2)，…，f(xn)，RBF的插值模型为：

(5)

其中：φi(·)是第i个基函数，‖·‖代表欧氏距离，λi表示第i个基函数的权重。

径向基函数的未知参数(λ1，λ2，…λn∈RD)可以作为线性方程的解获得：

(6)

其中：φ是一个n×n的矩阵，φij=φ(‖xi-xj‖)

(7)

(8)

因此，由式(5)-式(8)可以构建径向基模型用于进化算法中对目标值的预测，从而减少真实评价次数。

2.2 约束冲突值计算方式

测试函数中包含的等式约束首先需将等式约束转化成不等式约束，再进行优化。其中：ε=0.000 1，如果|hj(x)|-ε≤0，j=p+1，…，m那么认为粒子在该约束条件下可行。转换方式如式(9)所示，算法约束处理步骤如算法2所示。

Hj(x)=|hj(x)|-ε，j=p+1，…，m (9)

由于每个单目标约束优化问题都在对应一个目标函数的同时，对应着一个或多个约束函数。相应地，每个粒子对应一个目标函数值的同时也对应一个或多个约束函数值，因此本文中所提到的约束冲突值即为将每个粒子对应的一个或多个约束函数值按算法2整合成的一个sum值。

2.3 模型评价方式

研究中首先根据随机搜索建立初始样本库，采用初始样本库中的样本构建RBF模型，在算法执行过程中根据实验粒子的信息在线更新RBF模型，以使得该模型的估计精度越来越高。

2.3.1 样本库构建

1)初始样本库

随机产生NP个在给定边界约束范围内的粒子，并对每一个当前粒子q(i)进行约束冲突值的真实评价。建模训练样本数据集的输入为粒子的位置信息xi=(xi1，xi2，…，xid)，i=1，2，…，NP，输出为约束冲突函数值。其中d表示问题维度，NP为样本个数。同时文献[20]对不同RBF的应用进行了分析和总结，认为高斯函数适用于随机数的模拟，因此本文采用高斯函数为基函数，从而构建式(5)所示的RBF插值模型，模型参数可通过求解式(6)的线性方程获得。

2)样本库更新

使用上述所构建的RBF模型，将试验粒子q(i)的位置信息作为输入，模型的输出即为该试验粒子的约束冲突值。若当前代预估出满足可行域的试验粒子s(i)，则真实评价s(i)后放入模型库中用来更新模型；若没有预估出满足可行域的粒子，则选择当前代预估约束冲突值最小的粒子smin(i)强行真实评价，评价后smin(i)的位置及约束冲突值用来更新模型。

2.3.2 粒子更新准则

产生试验粒子s(i)后，若模型估计其满足约束，则进行真实计算。真实计算后，若满足约束则比较s(i)和当前粒子q(i)的约束冲突值，约束冲突值小的更新为个体最优pbest；若不满足约束，则个体最优pbest不更新。若模型估计其不满足约束，则个体最优pbest不更新。C库中有可行解，则每次随机选择一个可行粒子更新全局最优gbest；若C中无可行粒子，则选择当前种群最小约束冲突值的粒子更新gbest.

2.4 本文所提算法的具体步骤

本文所提代理模型辅助的初始可行解产生方法，主要是采用径向基函数构建代理模型，并使用代理模型估计试验粒子的约束冲突值。具体步骤如算法3所示。

算法3:具体步骤Step1:参数设置:群体规模NP,惯性权重ω,加速权重c1和c2,最大速度vmax最小速度vmin,真实评价库Archive,可行解库C;Step2:拉丁超立方体采样,产生微粒的初始位置及初始速度;Step3:对每个微粒i进行真实约束冲突值计算,真实计算后的粒子i的位置信息及约束冲突值存放在Archive中;Step4:在可行域中的粒子放入C库中;

Step5:产生个体最优pbest以及全局最优gbest;Step6:使用粒子群算法速度更新公式(3)(4)更新粒子的位置信息,并产生实验个体s(i);Step7:采用Archive中的粒子建立模型,该模型估计试验个体s(i)约束冲突值;Step8:若预估s(i)在可行域中,则对s(i)的约束冲突值进行真实计算,并将该粒子s(i)的位置信息放入Archive中,否则转Step10;Step9:真实计算后满足约束条件的试验粒子s(i)的位置信息放入C中,否则转到Step10;Step10:若当前代没有粒子被预估在可行域中,则选择预估值最小的粒子进行真实评价,评价后的粒子信息放入Archive中,否则转到Step11;Step11:根据更新准则更新个体最优pbest以及全局最优gbest;Step12:若未达到结束条件(设置为产生满足要求的初始解的个数),则返回Step 6.

3 实验结果及分析

3.1 采样方式

对于样本库中的粒子，本文算法分别将样本数设为10D、20D、50D(D代表维度)以及样本库中所有粒子来更新模型。其中，若模型库中的粒子数不足所要求的建模数量时，则将样本库中的粒子全部用于构建模型。本文经过对10D、20D、50D以及全部样本建模的实验结果表明，在低维问题中，样本数越多构建的模型可以找到更多的解，因此最终采用Archive中全部粒子来构建模型时。

3.2 结果及分析

为验证方法的有效性，本文针对cec2017[21]中的28个标准单目标约束函数进行测试，具体实验结果如表1所示。并与传统粒子群算法的可行初始解产生方法进行比较，以下简称其为传统方法。在表1中给出种群大小NP=100，维度D=10，独立运行30次的运行结果。

表1 传统算法与本文所提算法实验结果

表1中对比实验1是约束值评价1 000次，两种算法所找可行解个数，找到可行解个数多的方法即为好方法。对比实验1中：在C01-C05、C20测试函数上传统及所提方法均能找到可行解，且所提方法找到可行解个数大于传统方法，其中C02、C05效果尤为明显；在C06-C10、C12-C14、C21-C25测试函数中，传统方法无法找到可行解，而所提方法可以找到可行解；C15、C16函数中，传统方法找到可行解的实验次数分别为8次和5次，而所提方法30次独立实验均可找到可行解，且找到可行解个数远大于传统方法。因此，在试验1中本文所提算法在相同评价次数条件下，能找到更多的可行解，效果明显好于传统算法。

表1中对比试验2是设置找到100个可行解时，两种算法所需的评价次数对比，评价次数少的方法较好。该实验仅针对可以找到可行解的测试函数做对比。对比实验2中：在C01-C05、C12、C14-C16、C20-C21、C23-C25测试函数上，所提方法的评价次数均小于传统方法。其中在C02、C05、C12、C14-C16、C21、C23-C25测试函数上所提算法评价次数远小于传统方法；在C06-C10、C13、C22测试函数上，传统方法均无法找到可行解，而所提算法可以找到可行解。因此，对比实验2中，在产生初始可行解效率方面，本文所提算法同样优于传统算法，能在找到相同数量可行解的情况下大大减少评价次数，提高生成初始解的效率。

4 总结

针对采用约束保持法的粒子群算法在产生初始可行解时存在评价次数过高、计算昂贵的问题，本文将代理模型预估约束冲突值的策略引入算法产生初始可行解的过程中。在初始种群更新位置信息后，首先进行约束冲突值预判断，预判可行的粒子才进行真实评价，用以减少浪费资源评价不可行粒子的次数。实验结果证明本文所提算法能解决产生初始可行解困难的问题。未来将进一步丰富和完善初始可行解产生机制，提高策略的稳定性，获得更精确的粒子评估资源。在此基础上，将本文所提算法运用到的智能优化算法中，提高算法优化效率。