Multi-objective CuckooSearch Algorithm for Bi-level Programming Problems

doi:10.12005/orms.2017.0180

Abstract

Abstract: The bi-level programming problem(BLPP)addresses an optimization problem with leader-follower hierarchical?structure, an NP-hard problem in the strong sense. The BLPP is reformulated into an equivalent single-level constrained optimization problem by using the KKT conditions associated to the lower-level problem. Further, the derived problem is transformed into a bi-objective optimization problem by a constraints handling scheme, i.e., introducing a new objective of minimizing constraints violation. For the resolution, a multi-objective cuckoo search algorithm is proposed. In the algorithm, the Pareto dominance and ε-comparison rule are adopted in purpose of exploiting the information of in-feasible solutions to efficiently guide the search process. Additionally, an archive is used to store better-performing candidate and a Gaussian mutation is applied on it in order to search promising solutions. Then, some worstest individuals are periodically substituted by the archive. The computational experiments and parameter analysis claim the effectiveness of the proposed algorithm.

Key words: bi-level programming problem, multi-objective cuckoo search algorithm, ε-comparison rule, archive and replacement scheme

摘要： 双层规划是一类具有主从递阶结构的优化问题,属于NP-hard范畴。本文利用KKT条件将双层规划问题转化为等价的单层约束规划问题,通过约束处理技术进一步转化为带偏好双目标无约束优化问题,提出多目标布谷鸟算法求解策略。该算法采用Pareto支配和ε-个体比较准则,充分利用种群中优秀不可行解的信息指导搜索过程;设置外部档案集存储迭代过程中的优秀个体并通过高斯扰动改善外部档案集的质量,周期性替换群体中的劣势个体,引导种群不断向可行域或最优解逼近。数值实验及其参数分析验证了算法的有效性。

关键词: 双层规划, 多目标布谷鸟算法, ε-比较准则, 存档替换机制

CLC Number:

O221

SONG Yu-jian, ZHANG Jian-tong. Multi-objective CuckooSearch Algorithm for Bi-level Programming Problems[J]. Operations Research and Management Science, 2017, 26(8): 1-10.

宋玉坚, 张建同. 求解双层规划的多目标布谷鸟算法[J]. 运筹与管理, 2017, 26(8): 1-10.

References

[1] Cancela H, Mauttone A, Urquhart M E. Mathematical programming formulations for transit network design[J]. Transportation Research Part B Methodological, 2015, 77: 17-37.
[2] Xu J, Tu Y, Zeng Z. Bilevel optimization of regional water resources allocation problem under fuzzy fandom environment[J]. Journal of Water Resources Planning & Management, 2014, 139(3): 246-264.
[3] Gang J, Tu Y, Lev B, et al. A multi-objective bi-level location planning problem for stone industrial parks[J]. Computers & Operations Research, 2015: 8–21.
[4] 蒋敏.一种多损失条件风险值的双层规划模型及应用[J].系统工程理论与实践,2013,33(4):926-933.
[5] Bialas W F, Chew M N. On two-level programming[J]. IEEE transactions on automatic control, 1982, AC-26: 211-214.
[6] Giimus Z H,Floudas C A. Global optimization of nonlinear bilevel programming problems[J]. Journal of Global Optimization, 2001, 20(1): 1-31.
[7] Vicente L, Savard G, Judice J. Descent approaches for quadratic bilevelprogramming[J]. Journal of Optimization Theory and Applications, 1994, 81(2): 379-399.
[8] 李和成,王宇平.一类特殊的非线性双层规划问题及其遗传算法[J].西安电子科技大学学报(自然科学版),2007,34(1):101-105.
[9] 范成礼,邢清华,付强,等.求解非线性双层规划问题的混合变邻域粒子群算法[J].系统工程理论与实践,2015,35(2):473-480.
[10] Wang Y P, Jiao L C,LI H. An Evolutionary Algorithm for Solving Nonlinear Bilevel Programming Based on a New Constraint-Handling Scheme[J]. IEEE Transaction on Systems, Man, and Cybernetics—Part C: Applicationand Reviews, 2005, 35(2) , 221-232.
[11] 赵志刚,顾新一,李陶深,等.求解双层规划模型的粒子群优化算法[J].系统工程理论与实践,2007,27(8):92-98.
[12] 李昌兵,杜茂康,付德强,等.基于层次粒子群算法的非线性双层规划问题求解策略[J].系统工程理论与实践,2013,33(9):2292-2298.
[13] 李昌兵,杜茂康,付德强,等.求解双层规划问题的层次混沌量子遗传算法[J].系统工程学报,2013,28(2):159-166.
[14] 江燕,胡铁松,黄崇超,等.基于粒子群算法的非线性二层规划问题的求解算法[J].运筹与管理,2006,15(2):18-22.
[15] 李相勇,田澎.双层规划问题的粒子群算法研究[J].管理科学学报,2008,11(5):41-52.
[16] 何正文,刘人境,胡信布,等.基于合同双方交互作用的项目调度优化[J].管理科学学报,2014,17(8):48-59.
[17] Yang X S, Suash D. Cuckoo search via Levy flight[C]// Proceedings of the 2009 World Congress on Nature& Biologically Inspired Computing. Piscataway, NJ: IEEE Press, 2009: 210-214.
[18] Datta R, Deb K. Individual penalty based constraint handling using a hybrid bi-objective and penalty function approach[C]//Evolutionary Computation (CEC), 2013 IEEE Congress on. IEEE, 2013: 2720-2727.
[19] 郑建国,王翔,刘荣辉.求解约束优化问题的ε-DE算法[J].软件学报,2012,23(9):2374-2387.
[20] Wang Y, Cai Z. Combining multi-objective optimization with differential evolution to solve constrained optimization problems[J]. IEEE Transactions on Evolutionary Computation, 2012, 16(1): 117-134.
[21] Wang Y, Li H, Dang C. A new evolutionary algorithm for a class of nonlinear bi-level programming problems and its global convergence[J]. Informs Journal on Computing, 2011, 23(4): 618-629.