﻿ 求解非线性双层规划问题的混合变邻域粒子群算法
 文章快速检索 高级检索

A hybrid intelligent algorithm by combining particle swarm optimization with variable neighborhood search for solving nonlinear bilevel programming problems
FAN Cheng-li, XING Qing-hua, FU Qiang, WANG Zhen-jiang, WANG Yi-fei
School of Air and Missile Defense, Air force Engineering University, Xi'an 710051, China
Abstract:In this paper, a hybrid intelligent algorithm by combining the particle swarm optimization (PSO) with variable neighborhood search (VNS) is presented on the basis of analyzing the problem of nonlinear bilevel programming. This method integrates the fast search capability of PSO with the global search ability of VNS. Firstly, the bilevel programming is transformed into a single level programming problem by use of the Kuhn-Tucker conditions. Then, the preferable swarm is obtained by PSO algorithm. Furthermore, the swarm get into local optima, which is estimated by convergence criterions, is optimized by VNS algorithm. Finally, the result of benchmark problems demonstrates the proposed algorithm is effective than the compared algorithms.
Key words: nonlinear bilevel programming     particle swarm optimization     variable neighborhood search     global search

0 引言

NBLP模型如式(1):
 $\left\{ {\begin{array}{l} {\displaystyle \mathop {\min\limits_xF(x,y)}},\\ {\displaystyle \mathop {mbox{s.t.} ~G(x,y)\leq 0}},$其中$y$求解$\\ {\displaystyle \mathop {\min\limits_yf(x,y)}},\\ {\displaystyle \mathop {mbox{s.t.} ~g(x,y)\leq 0}}\\ \end{array}} \right.$ (1)

1)约束空间: $S=\{(x,y)\left| {G(x,y)\le 0,g(x,y)\le 0} \right.\}$;

2)对于固定的$x$,下层可行域为: $S(x)=\{y\left| {g(x,y)\le 0} \right.\}$;

3) $S$在上层决策空间的投影为: $S(X)=\{x\left| {\exists y,(x,y)\in S} \right.\}$;

4)对每个$x\in S(x)$,下层合理反映集为: $M(x)=\{y\left| {y\in \arg \min \{f(x,y),y\in S(x)\}} \right.\}$;

5)诱导域: $IR=\{(x,y)\left| {(x,y)\in S,y\in M(x)} \right.\}$.

1)为保证问题(1)有最优解,设$S$为非空紧集;

2)对每一个上层变量$x\in X$,下层存在唯一的最优解$y(x)$.

 ${\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}\left\{ {\begin{array}{l} \mathop {\min }\limits_y f(x,y),{\kern 1pt}{\kern 1pt}{\kern 1pt} \\ \mbox{s.t.}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}g(x,y)\le 0 \\ \end{array}} \right.{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}$ (2)

 ${\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}\left\{ {\begin{array}{l} \nabla _y f(\mathop x\limits^- ,\mathop y\limits^- )+\lambda ^{\rm T}\nabla _y g(\mathop x\limits^- ,\mathop y\limits^- )=0 \\ \lambda ^{\rm T}g(\mathop x\limits^- ,\mathop y\limits^- )=0 \\ \lambda \ge 0 \\ \end{array}} \right.{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}$ (3)

 $\left\{ {\begin{array}{l} V_i (t+1)=\omega V_i (t)+c_1 \times rand()\times (P_i -X_i (t))+c_2 \times rand()\times (P_g -X_i (t)) \\ X_i (t+1)=X_i (t)+V_i(t+1) \\ \end{array}} \right.$ (5)

 $\omega =\omega _{\rm ini} -\frac{(\omega _{\rm ini} -\omega _{\rm end} )}{t_{\max } }\times t{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}{\kern 1pt}(t=1,2,\cdots,t_{\max } )$ (6)

PSO优化算法在运行过程中, 粒子群会迅速靠拢当前的群体最优位置, 若该最优位置不是全局最优,算法将很难收敛到全局最优而出现 "早熟收敛"现象. 为克服基本PSO算法在运算后期由于种群多样性的快速丧失而造成的算法 "早熟收敛"问题,对$t$代种群中的粒子加入审敛因子. 审敛因子包括聚类操作和聚合度计算两个方面:

1)聚类操作: 对第$t$代粒子群执行$c$均值聚类算法,产生$c$个聚簇, 计算各聚簇内每个粒子与聚类中心粒子的距离;

2)聚合度判断: 判断第$t$代粒子群的聚合度$s$是否趋近于1. 聚合度$s\in(0,1)$是反映种群多样性的测度,$s$越小种群活性越强; $s$越大则粒子的聚集程度越高; 当$s=1$时,粒子趋于同一性.

 $X_{c_{j}}=(x_{c_{j},1},x_{c_{j},2},\cdots,x_{c_{j},d})=\bigg(\sum\limits_{i\in c_{j}}x_{i ,1}/m,\sum\limits_{i\in c_{j}}x_{i,2}/m,\cdots,\sum\limits_{i\in c_{j}}x_{i,d}/m\bigg)$ (7)

 $d_{i,c_{j}} =\sqrt {((x_{i1} -x_{c_j ,1} )^2+(x_{i2} -x_{c_j ,2} )^2+\cdots+(x_{id} -x_{c_j ,d} )^2)}$ (8)

 $d_{c_{j{\rm ave}}}=\bigg(\sum\limits_{i\in c_{j}}\sqrt {((x_{i1} -x_{c_j ,1} )^2+(x_{i2} -x_{c_j ,2} )^2+\cdots+(x_{id} -x_{c_j ,d} )^2)}\bigg)\bigg/n_{j}$ (9)

 $s=\min (avgpi_t ,avg_t )/\max (avgpi_t ,avg_t )$ (10)

Step 7 根据式 (5) 对粒子的速度和位置进行更新;

Step 8 判断是否满足终止条件. 如果满足,转Step 9; 否则, 转Step 2,继续迭代;

Step 9 输出全局最优$P_{g}$、上层目标函数值$F(x,y)$、下层目标函数值$f(x,y)$, 算法运行结束.

1)现有的求解非线性双层规划的算法大多是给定上层决策变量$x$, 并通过$x$求解下层决策变量$y$, 而本文算法中上层决策变量由PSO算法随机产生, 进而由VNS算法和PSO算法更新粒子;

2)当粒子为不可行解时,用可行度测量$w(x,y)$,作为粒子的适应度值, 迫使不可行粒子向可行粒子靠近;

3)在PSO优化过程中,通过增加审敛因子,判断粒子是否陷入 "早熟收敛'';

4)利用VNS算法的全局搜索能力对已陷入 "早熟收敛'' 的粒子进行变邻域搜索,既增加了种群的多样性又避免了PSO算法容易 陷入局部最优的问题,从而最终得到全局最优解.

 图 1 混合PSO-VNS算法流程图
3 数值算例与算法性能分析

1)在50次运行中,所得到的最优解$(x^{*},y^{*})$;

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

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

4)适应度函数的平均计算次数 (mean numbers of individuals, MNI)、平均CPU运行时间 (CPU) 以及算法首次得到最好解时的平均代数($g_{\rm mean}$)以测试算法收敛速度.

 图 2 T01-$F(x,y)$的最优值及均值

4 结论

 [1] Bard J F. Practical bilevel optimization: Algorithm and applications[M]. The Netherlands: Kluwer Academic Publishers, 1998: 193-386. [2] 许项东, 程琳. 城市道路单行系统布局优化的双层规划模型和混合算法[J]. 系统工程理论与实践, 2009, 29(10): 180-187.Xu Xiangdong, Cheng Lin. Bilevel programming model and hybrid solution algorithm for the configuration of one-way streets[J]. Systems Engineering —— Theory & Practice, 2009, 29(10): 180-187. [3] Vicente L, Savard G, Judice J. Decent approaches for quadratic bilevel programming[J]. Journal of Optimization Theory and Applications, 1994, 81: 379-399. [4] Mathieu R. Genetic algorithm based approach to bilevel linear programming[J]. Operations Research, 1994, 28(1): 1-21. [5] Wang Y P, Jiao Y C, Li H. An evolutionary algorithm for solving nonlinear bilevel programming based on a new constraint-handing scheme[J]. IEEE Transactions on Systems, Man, and Cybernetics, Part C, 2005, 35(2): 221-232. [6] Yaakob S B, Watada J. Double-layered hybrid neural network approach for solving mixed integer quadratic bilevel problems[J]. Integrated Uncertainty Management and Applications, 2010, 68: 221-230. [7] Küςükaydin H, Aras N, Altinel I K. A hybrid tabu search heuristic for a bilevel competitive facility location model[J]. Hybrid Metaheuristics, 2010, 6373: 31-45. [8] Sakawa M, Katagiri H, Matsui T. Stackelberg solutions for fuzzy random two-level linear programming through probability maximization with possibility[J]. Fuzzy Sets and Systems, 2012, 188(1): 45-57. [9] Wan Z P, Wang G M, Sun B. A hybrid intelligent algorithm by combining particle swarm optimization with chaos searching technique for solving nonlinear bilevel programming problems[J]. Swarm and Evolutionary Computation, 2013, 8: 26-32. [10] Kennedy J, Eberhart R. Particle swarm optimization[C]// Proceedings of the IEEE International Conference on Neural Networks, Perth, Australia, Piscataway, 1995: 1942-1948. [11] 刘衍民, 隋常玲, 赵庆祯. 基于K-均值聚类的动态多种群粒子群算法及其应用[J]. 控制与决策, 2011, 26(7): 1019-1025.Liu Yanmin, Sui Changling, Zhao Qingzhen. Dynamic multi-swarm particle swarm optimizer based on K-means clustering and its application[J]. Control and Decision, 2011, 26(7): 1019-1025. [12] Marinakis Y, Iordanidou G R, Marinaki M. Particle swarm optimization for the vehicle routing problem with stochastic demands[J]. Applied Soft Computing, 2013, 13: 1693-1704. [13] Drazic M, Lavor C, Maculan N, et al. A continuous variable neighborhood search heuristic for finding the three-dimensional structure of a molecule[J]. European Journal of Operational Research, 2008, 185: 1265-1273. [14] Mladenovic N, Drazic M, Kovacevic-Vujcic V, et al. General variable neighborhood search for the continuous optimization[J]. European Journal of Operational Research, 2008, 191(3): 753-770. [15] Chen Y Y, Cheng C Y, Wang L C. A hybrid approach based on the variable neighborhood search and particle swarm optimization for parallel machine scheduling problems —— A case study for solar cell industry[J]. International Journal of Production Economics, 2013, 141: 66-78. [16] Hansen P, Mladenovic N. Variable neighborhood search[J]. Computers and Operations Research, 1997, 24(11): 1097-1100.
0

#### 文章信息

FAN Cheng-li, XING Qing-hua, FU Qiang, WANG Zhen-jiang, WANG Yi-fei

A hybrid intelligent algorithm by combining particle swarm optimization with variable neighborhood search for solving nonlinear bilevel programming problems

Systems Engineering - Theory & practice, 2015, 35(2): 473-480.