基于Pareto支配的双目标优化求解非线性双层规划问题

吴 军 严丽娜

1(宁夏大学新华学院 宁夏 银川 750021)2(北方民族大学医学影像技术系 宁夏 银川 750021)

0 引 言

一般的非线性双层规划(Nonlinear Bilevel Programming,NBLP)问题通常是非凸不可微的，文献[1]证明了即使搜索局部最优解，NBLP问题仍是NP难问题。传统的方法求解NBLP问题主要有以下几类：关于线性规划的极点法、分支定界算法、下降算法、罚函数法和信赖域法[2-7]等。当NBLP问题变得复杂时，这些传统算法将失去作用，在求解时很难获得全局最优解，而智能优化算法对函数要求较低且具有较强的全局搜索能力，因此被逐渐用于求解此类问题。

Mathieu等[8]首次提出将遗传算法应用到求解双层线性规划问题，在算法中使用嵌套策略，用线性规划和遗传算法分别求解下层和上层规划问题。在解决双层规划问题中嵌套策略是一个非常受欢迎的方法，然而，当遇见大规模、复杂问题时，这种方法将出现耗时高甚至不能求解的情况。为了改善这个问题，Sinha等[9]将二次逼近嵌套在进化算法中，使下层规划问题的解无限接近最优解，在有限的计算量下有效地解决了复杂的双层规划问题。何胜学等[10]针对建立的停车设施选择和出行路线选择的双层规划模型，上下层问题通过设施选择概率函数实现了有效关联，在嵌套策略下设计了有效的算法求解模型。刘丹等[11]针对离散交通网络设计的大规模双层规划问题，提出一种机器学习-优化混合算法，上下层问题利用不同算法分别求解。Wang等[12]针对同样的问题，利用新的约束处理机制提高了算法的搜索能力，改善了个体的质量和算法的收敛速度。但这个方法对于下层问题的非凸性无能为力，为了解决这个问题，Wang等[13]在算法中融合了传统的确定性方法求解下层问题，实验结果显示，新的进化算法可以求解各种双层规划问题。Han等[14]依据多层规划问题的求解思路，设计出层次粒子群算法求解双层和三层规划问题，实验结果显示，层次粒子群算法对于非线性和大规模多层规划问题效果显著。Kuo等[15]将遗传算法和粒子群算法融合构造混合算法，拥有同样思路的还有文献[16]，他们将粒子群算法和差分进化算法混合求解实际定价和批量决策问题。Li等[17]将一般的双层规划模型转变为双目标双层规划模型，他们认为在双目标规划中，两个决策者经过“讨价还价”而达到双方都满意的结果并不违背双层规划模型的求解理论，反而可以给出一种形象直观的解帮助决策者在贸易中找到最好的权衡。但是区别于双目标优化问题的Pareto最优集，双层规划问题只需得到一个最优解，文献[17]中该问题并没有得到解决。

综上所述，智能优化算法在复杂的优化问题中得到了成功的应用，大多数文章都利用KT条件转化双层规划为单层规划求解，以双目标优化思想解决双层规划问题的文献却很少见。文献[17]虽提出了双目标双层规划模型，但对Pareto最优集在双层规划问题中的处理并没有给出合理的解决方案。本文将非线性双层规划问题转换为双目标规划问题，在基本的差分进化(Differential Evolution,DE)算法框架中融合非负的最小二乘曲线拟合判定解的可行性，构造了基于动态概率偏好的Pareto支配选择策略。以动态的概率偏好保护候选解朝最优目标前进的同时避免了算法陷入局部最优，提高全局寻优能力，成功地将多目标优化算法的思想用于求解双层规划问题。

1 双层规划问题的等价转换

1.1 双层规划模型

考虑如下非线性双层规划问题：

(1)

式中：F,f:Rn×Rm→R，G:Rn×Rm→Rp，g:Rn×Rm→Rq，上层目标函数F(x,y)和约束函数G(x,y)是非凸不可微的，下层目标函数f(x,y)和约束函数g(x,y)是凸并且可微的。

x为上层决策变量，y为下层决策变量。X、Y分别代表上层变量和下层变量的搜索空间：

(2)

(3)

双层规划问题最优解的相关概念如下所述：

定义1[18-19]

1) 约束空间：S={(x,y)|G(x,y)≤0,g(x,y)≤0}；

2) 对于固定的x∈X，下层问题的可行域：S(x)={y|g(x,y)≤0}；

3)S在上层决策空间的投影：S(X)={x|∃y,(x,y)∈S}；

4) 对每个x∈S(x)，下层问题的合理反应集：M(x)={y|y∈arg min{f(x,y),y∈S(x)}}；

5) 诱导域：IR={(x,y)|(x,y)∈S,y∈M(x)}；

6) 双层规划问题的最优解集：OS={(x,y)|(x,y)∈arg minF(x,y),(x,y)∈IR}。

1.2 双层规划模型的等价形式

对任意x∈S(x)，下层规划模型如下：

miny∈Yf(x,y)

(4)

s.t.g(x)≤0

对于固定的x，根据最优性条件可知，式(4)等价于求解Kuhn-Tucher点问题[20-21]：

(5)

minx,y,UF(x,y)

(6)

s.t.Ek(x,y,U)=0k=1,2,…,m+1

Ir(x,y,U)≤0r=1,2,…,p+q

U≥0

式中：Ek(x,y,U)是式(5)中前两个方程左边的所有函数；Ir(x,y,U)是G(x,y)和g(x,y)所有的不等式约束的部分。

1.3 双目标优化模型

我们将式(6)中Ek(x,y,U)、Ir(x,y,U)和U结合组成约束违反函数，建立一个特殊的优化问题——双目标优化。根据两个目标函数值，依据动态概率偏好的Pareto支配策略选取优秀个体。

(7)

式中：k=1,2,…,m+1；r=1,2,…,q；It=max{0,It}；t=1,2,…,p+2q+m+1。当It=0时，表示个体(x,y)为可行解，否则为不可行解。显然，对于式(6)，一个可行解优于不可行解；两个可行解中，目标函数值小的解更优秀；但两个不可行解比较时，就无法确认谁好谁坏。因此构造如下双目标优化问题：

min{F(Q),I(Q)}

(8)

式中：I(Q)=max{0,I1,I2,…,Ip+2q+m+1}，表示约束违反中最大的一个，记为可行性度量函数。同时优化目标函数F(Q)和可行性度量函数I(Q)，使种群朝向可行区域和全局最优解前进。

2 双目标优化策略的差分进化算法

2.1 差分进化算法

差分进化[22](Differential Evolution,DE)是一种基于种群的启发式全局搜索算法，它主要包括变异和交叉操作。

(9)

(10)

式中：rand(0,1)是[0,1]区间的随机数；CR是交叉概率；jrand是[1,D]区间内随机产生的整数。

2.2 可行性的度量

约束优化问题最关键的步骤是判定解的可行性。对于式(6)中的约束部分，很多情况下满足Ek(x,y,U)=0是极其困难的，而容忍误差的设定没有具体的标准去衡量。本文依据最小二乘曲线拟合原理，在有限的计算量中，寻找每个候选解对应的Lagrange算子U′>0，使函数|Ek(x,y,U′)|的值尽可能小。

对于Ek(x,y,U)=0，将U看作方程中的未知量，将其改写成方程组形式AU-B=0，其中A是系数矩阵，B是常数向量，那么非负的最小二乘曲线拟合就相当于求解如下最小化问题：

(11)

若Ie=0，证明使用最小二乘曲线拟合的程度最高，等式约束的误差为零，得到了精确的候选解；Ie的值越大，说明拟合程度越低，约束违反值越大。

2.3 动态概率偏好的Pareto支配选择

定义2

(1) Pareto支配：对于解Q1和Q2满足F(Q1)≤F(Q2)和I(Q1)≤I(Q2)时，且至少存在F(Q1)

(2) Pareto最优：设Ω是一解集，如果解Q1是当前Ω集合中Pareto最优的，当且仅当不存在解Q∈Ω，使得解Q支配Q1；

(3) Pareto最优集：设Ω是算法目前为止所有解的集合，那么关于Ω中所有Pareto最优解被称为Pareto最优集。

在通常情况下，双层规划问题的求解理论并不等同于双目标优化问题，因此它不能直接转换为双目标优化问题(上下两层的目标函数作为平行的两个目标函数)，也就是说，双层规划问题的最优解不能等同于双目标优化问题的Pareto最优解。

根据以上定义，对于双目标优化问题(式(8))，如果解Q1支配Q2，那么解Q1优于Q2。如果解Q1和Q2互不支配，那将依概率选择目标函数或可行性度量值较大的解。本文中的双目优化问题(式(8))等价于单层规划问题(式(6))，因此式(8)的Pareto最优解是式(6)的最优解，也就是式(1)的解，具体内容可参照文献[12]中定理1。

设置如下的动态概率Pareto支配选择(DpPa)方案：

(1) 两个都是可行解或者两个不可行解。按照Pareto支配选择一个解进入下一代种群。

(2) 可行解支配不可行解。P、NewP分别代表两代种群，I、NewI分别代表两代解的可行性度量值，F、NewF分别代表两代解的目标函数值，randp代表[0,1]的随机数，pd∈[pl,pu]代表动态概率值，它的取值随着迭代次数的增加而减小。pd的计算公式如下：

具体的伪代码如下所示：

if I=0 & New I≠0 & F

if rand p

Next P←P

else

Next P←NewP

end

end

通过这种选择策略，一个可行解支配一个不可行解，我们以较大概率选择可行解。随着迭代的进行，种群趋于集中，选择可行解的概率逐渐减小到最低下限值pl。相反以较小的概率选择不可行解，随着迭代的增加选择不可行解的概率逐渐增大，最大概率限定为pu-pl。以大概率保护优秀可行解进入下一代种群，以小概率保留不可行解进入下一代种群，增加种群的多样性以及全局搜索能力。

(4) 两个不可行解互不支配。以大概率选择可行性度量值小的，使种群快速朝着可行区域进化，本文设置定值pd=0.7。

2.4 基于Pareto支配的双目标差分进化算法

基于Pareto支配的双目标差分进化算法(DPDE)求解非线性双层规划问题，具体的算法流程如下：

步骤1设置初始参数，种群规模ps，交叉概率cr，动态概率上限和下限pu、pl，当前迭代次数in，缩放因子F，最大迭代次数inmax。

步骤2初始化种群，在变量范围内随机产生初始种群P={Qi|i=1,2,…,ps}，计算每个个体的目标函数值F(Q)和约束违反值I(Q)。

步骤3依据约束违反值I(Q)判断个体的可行性，将可行解中目标函数值F(Q)最小的个体作为最好个体Qbest，如果不存在可行解，那么将不可行解中约束违反值I(Q)最小的个体作为最好个体Qbest。

步骤4随机选择4个个体Qr1、Qr2、Qr3和Qr4，根据式(9)进行变异操作，产生变异个体Vi，根据式(10)进行交叉操作，产生子代候选个体Si，计算Si目标函数值F(Si)和可行性度量值I(Si)，依据DaPa策略比较Qi与Si的目标函数值和可行性度量值，选择较好个体。

步骤5更新种群，判断算法终止条件，如果in

3 实验结果及分析

表1 测试函数及其相关来源

(1) 最优解(x*,y*)；

(2) 上层目标函数F(x,y)的最优值、最差值、均值、方差；

(3) 下层目标函数f(x,y)的最优值、最差值、均值、方差；

(4) 算法50次独立运行适应度函数的平均计算次数(MNI)和平均CPU运行时间(CPU)。

表2记录了DPDE算法的最好解数值及与文献[12]和文献[14]的比较，可以看出，DPDE算法在大多数问题中可以得到与算法NEA和BL-PSO基本一致的结果，而测试函数6的结果和其他两种算法有较大不同。由于小数位的限制，我们也不能比较谁好谁坏。

表3和表4统计了DPDE算法的最好解的上层和下层函数值及与文献[12]和文献[14]的比较，对比文献[14]可以看出，DPDE算法对于函数3、函数5、函数11和函数12的解绝对优于算法NEA[12]，其他函数的解在精度允许范围内也和其相等；对比文献[14]可以看出，DPDE算法对于函数5和函数8得到的解绝对优于算法BL-PSO[14]。对于函数10，算法BL-PSO得到了(F,f)=(1,0)，从数值上看明显优于DPDE算法，但是经过验证，当x=1时，下层目标函数最小值应该为f(x,y)=-101 250。因此，算法BL-PSO得到的解(x,y)=(1,0)不是全局最优解。剩余函数中，除过函数12本文算法稍显劣势外，其他函数都与BL-PSO算法得到的函数值相等。

表3 最好解F(x*,y*)函数值的比较

表4 最好解f(x*,y*)函数值的比较

续表4

特别说明的是，函数6的上层函数中x的系数为0，即上层目标函数只是关于变量y的函数，在要求下层目标最小的情况下，DPDE算法计算出x=(61.306,25.768)，比较下层函数值可以看出解(x,y)=(61.306,25.768,2.999,2.999)明显优于算法NEA[12]和BL-PSO[14]的解。

表5和表6分别显示了DPDE算法的计算结果在上层和下层函数的最好值、最差值、平均值和标准差，函数6的均值和方差出现较大变化，具体原因已解释过。其他函数的均值都非常接近最优值，方差都不超过10-6数量级，最小的方差值如函数3和函数14的0，表明算法DPDE具有极强的抗变换性。

表5 上层函数的最好值、最差值、平均值、标准差

表6 下层函数的最好值、最差值、平均值、标准差

表7显示了算法的CPU平均运行时间和适应度函数的平均计算次数MNI。从各个函数的平均CPU时间上看，本文算法DPDE大多数超过了NEA算法，但每个问题的平均CPU耗时相差不多，而算法NEA则具有较强的波动，15个函数的CPU时间的平均值显示DPDE算法优于NEA算法，表明本文算法具有较强的稳定性，同样MNI值也低于NEA算法。

表7 CPU时间和计算次数

续表7

4 结 语

本文首先将双层规划问题等价转化为双目标规划问题，采用了非负的最小二乘曲线拟合，利用拟合结果判断候选街的可行性，基于动态概率的Pareto支配选择策略挑选下一代个体，解决了NBLP问题容易陷入局部最优的缺陷，提高了算法的搜索性能，改善全局寻优能力。15个标准测试函数的实验数据表明，DPDE算法在求解NBLP问题具有较好的全局寻优能力，较低的计算复杂度，较强的稳定性和适用性，可以获得全局最优解。双目标和双层规划问题深层结合，自适应的Pareto支配选择策略是下一步探索的问题。