求解非线性二层规划问题的模拟植物生长算法

中国管理科学 ›› 2012, Vol. ›› Issue (4): 160-166.

求解非线性二层规划问题的模拟植物生长算法

李彤^1,2, 陈畴镛¹

1. 杭州电子科技大学管理学院, 浙江杭州 310018;
2. 先进设计与智能计算教育部重点实验室, 辽宁大连 116622

收稿日期:2011-07-23 修回日期:2012-02-08 出版日期:2012-08-29 发布日期:2012-08-29
基金资助:
国家自然科学基金资助项目(71171070, 71072161, 71173066);浙江省自然科学基金资助项目(Y7100447);教育部人文社会科学研究规划基金(12YJAZH063);浙江省高校人文社科基地重大项目(RWSKZD04-2012ZB,RWSKZD04-2012ZB3)

Plant Growth Simulation Algorithm for Solving Nonlinear Bilevel Programming

LI Tong^1,2, CHEN Chou-yong¹

1. Management College, Hangzhou Dianzi University, Hangzhou 310018, China;
2. Key Laboratory of Advanced Design and Intelligent Computing, Ministry of Education, Dalian 116622, China

Received:2011-07-23 Revised:2012-02-08 Online:2012-08-29 Published:2012-08-29

摘要/Abstract

摘要： 本文以植物向光性生长理论为启发式准则,提出了一种求解非线性二层规划问题的智能优化算法。在该算法中,将二层规划上层解空间和下层反应集分别作为植物的两个生长环境,建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型,两者结合所形成的优化模式,实现了模拟植物从初始状态到完整形式的终态(没有新的树枝生长),从而得到二层规划问题的解。该方法具有搜索精度较高,求解稳定性较强的特点,通过与国外学者在非线性二层规划实际测试问题的最优值进行精度比较,表明模拟植物生长算法是有效可行的。

关键词: 模拟植物生长算法(PGSA), 二层规划, 非线性二层规划

Abstract: Based on plant phototropism growth pattern as its heuristic criterion, an intelligence optimization algorithm for solving nonlinear bilevel programming is proposed herein. In this algorithm, the upper solution space and lower reaction set of bilevel programming are looked as two growth environments of plant. Then the plant system evolution style based on growth regulation and the probability growth model based on plant phototropism theory are established. The optimization model combined with above two realizes the evolution of artificial plant from initial status to whole final status (that means no new branch growing), thus the optimal solution of bilevel programming can be found. This algorithm herein shows its high accuracy and strong astringency. Comparing with typical optimal solutions obtained from western scholars worked on actual test problems of nonlinear bilevel programming, plant growth simulation algorithm herein also shows its good effectiveness and feasibility.

Key words: plant growth simulation algorithm (PGSA), bilevel programming, nonlinear bilevel programming

中图分类号:

O221

李彤, 陈畴镛. 求解非线性二层规划问题的模拟植物生长算法[J]. 中国管理科学, 2012, (4): 160-166.

LI Tong, CHEN Chou-yong. Plant Growth Simulation Algorithm for Solving Nonlinear Bilevel Programming[J]. Chinese Journal of Management Science, 2012, (4): 160-166.

参考文献

[1] Candler W, Norton R. Multilevel programming. Techinical Report 20, Word Bank Development Research Center, Washington, 1977.
[2] Hansen P,Jaumard B,Savard G. New branch-and-bound rules for linear bilevel programming [J]. SIAM Journal on Science and Statistical Computing, 1992,13:1194-1217.
[3] Vicente L, Savard G, Judice J. Descent approaches for quadratic bilevel programming [J]. Journal of Optimization Theory and Applications, 1994,81:379-399.
[4] Bard J F. Practical bilevel optimization: algorithm and applications [M]. Dordrecht: Kluwer Academic Publishers, 1998.
[5] Dempe S. Foundation of bilevel programming [M]. London: Kluwer Academic Publishers, 2002.
[6] Closon B, Marcotte P, Savard G. atrust-region method for nonlinear bilevel programming: algorithm and computational experience [J]. Computational Optimization and Applications, 2005,30(3):211-227.
[7] 吕一兵,陈忠等.非线性-线性二层规划问题的罚函数方法[J]. 系统科学与数学, 2009,29(5):630-636
[8] 李彤. 基于模拟植物生长的二级整数规划算法研究. 天津: 大学博士学位论文, 2005.
[9] 李彤等.求解整数规划的一种仿生类全局优化算法—模拟植物生长算法[J]. 系统工程理论与实践, 2005,25(1):76-85.
[10] 王淳,程浩忠. 基于模拟植物生长算法的电力系统无功优化[J]. 电网技术, 2006, 30(11): 37-41.
[11] 李彤, 宿伟玲. 单级与二级整数规划算法原理及应用[M]. 北京:科学出版社, 2007.
[12] 王淳, 程浩忠. 基于模拟植物生长算法的配电网重构[J]. 中国电机工程学报, 2007,27(19):50-55
[13] 王淳. 模拟植物生长算法及其在输电网规划中的应用[J]. 电力系统自动化, 2007,31(7):24-28.
[14] 李彤,王众托. 模拟植物生长算法在设施选址问题中的应用[J]. 系统工程理论与实践, 2008, 28(12): 107-115
[15] Rao R S, Narasimham S. Optimal capacitor placement in a radial distribution system using plant growth simulation algorithm[J]. International Journal of Electrical Power and Eenergy and Energy Systems Engineering, 2008,1(2):123-130.
[16] 罗伟强,于建涛,黄家栋.一种求非线性整数规划最优解的仿生算法[J]. 计算机工程与应用, 2008, 44(7):57-68
[17] 杨俊,艾欣,邵淮岭,等. 基于模拟植物生长算法考虑安全成本的最优潮流[J]. 中国电机工程学报,2008,23(10):35-40.
[18] 王淳,程浩忠,谭永香,等. 发电机组检修计划的模拟植物生长算法[J]. 电工技术学报, 2008, 23 (9):105-110.
[19] Wang Chun, Cheng Haozhang, Hu Zechun, et al. Distribution system optimization planning based on plant growth simulation algorithm [J]. Journal of Shanghai Jiaotong University (Science), 2008,13(4): 462-467.
[20] Wang Chun, Cheng Haozhong. Reactive power optimization by plant growth simulation algorithm[J]. Electric Utility Deregulation and Restructuring and Power Technologies, 2008,(4): 771-774
[21] Guney K, Durmus A, Basbug S. A plant growth simulation algorithm for pattern nulling of linear antenna arrays by amplitude control[J]. Progress In Electromagnetics Research B, 2009,(17):69-84
[22] Thiruvenkadam S, Nirmalkumar A. Energy management of large distribution network with plant growth simulation algorithm and heuristic fuzzy[J]. International Journal on Electronic & Electrical Engineering, 2009, 1(1):97-108.
[23] Rama P, Sivanaga Raju S. Optimal conductor selection in radial distribution system using plant growth simulation algorithm[J]. International Journal of Engineering Studies, 2009,1(3):229-240.
[24] Wang Chun, Cheng Haozhong.Transmission network optimal planning based on plant growth simulation algorithm [J]. European Transactions on Electrical Power, 2009, 19(2): 291-301.
[25] Rao R S, Narasimham S. A new heuristic approach for optimal network reconfiguration in distribution systems[J]. Journal of Applied Science, Engineering and Technology, 2009,5(1):15-21.
[26] Thiruvenkadam S,Nirmalkumar A, Sakthivel A. Optimal reconfiguration algorithm for radial distribution system feasible under normal and abnormal conditions[J]. International Journal of Applied Engineering Research, 2009, 4(9):115-122.
[27] 杨磊,刘义保. 基于模拟植物生长算法的钴源源棒的排列优化[J]. 核技术, 2009,32(12):915-921.
[28] 丁雪枫,马良. 基于模拟植物生长算法的易腐物品物流中心选址[J]. 系统工程,2009,27(2):96-101.
[29] 叶婧,汪芳宗. 基于改进模拟植物生长算法的配电网重构[J]. 计算技术与自动化,2009,28(3):49-59.
[30] 赵颖,罗伟强. 基于改进模拟植物生长算法的输电网络扩展规划[J]. 电力科学与工程,2009,25(5):6-10.
[31] 张节潭,程浩忠,姚良忠,等. 分布式风电源选址定容规划研究[J]. 中国电机工程学报, 2009,29(16):1-7.
[32] 王淳,万卫,程虹,等. 多阶段输电网络最优规划的模拟植物生长算法[J]. 高电压技术,2009,35(4):937-942.
[33] 杨丽徙,王锴. 应用改进模拟植物生长算法求解无功优化问题[J]. 高电压技术,2009,35(3):694-698.
[34] 武娜,焦彦军,于建涛. 一种基于模拟植物生长算法的输电网故障诊断方法[J]. 电力科学与工程, 2009,25(3):5-9.
[35] 李彤, 王众托. 模拟植物生长算法与知识创新的几点思考[J]. 管理科学学报, 2010,13(3):87-96.
[36] Li Tong, Su Weiling. Application of plant growth simulation algorithm on SMT problem[J]. ICIC Express Letters, 2010,4(5):1945-1950.
[37] Li Tong, Han Jianhu. Plant growth simulation algorithm for solving bilevel programming[J]. ICIC Express Letters, 2011,5(6):1857-1861.
[38] 辻隆男,大山力,橋口卓平,等. 配電損失低減を目的とした将来型配電系統の自律分散型電圧分布制御方式[J]. 電気学会論文誌. 2010,130(11):941-954.
[39] Sirjani R, Mohamed A, Shareef H. Optimal capacitor placement in a radial distribution system using harmony search algorithm[J]. Journal of Applied Sciences, 2010,10(23):2998-3006.
[40] 杨磊,刘义保,龚学余,等. 改进的模拟植物生长算法及其在大型辐照装置自动排源中的实用化[J]. 原子能科学技术, 2010,44(11):1403-1408.
[41] 陈立华,梅亚东. 模拟植物生长算法在水库群优化调度中的应用[J]. 水电自动化与大坝监测, 2010,34(2):1-5.
[42] 于永哲,黄家栋. 基于改进模拟植物生长法的配电网络重构[J]. 电力系统保护与控制, 2010,38(2):40-43.
[43] 唐海波,叶春明. 基于模拟植物生长算法的车间调度问题研究[J]. 机械科学与技术, 2010,29(11): 1581-1585.
[44] 唐海波,叶春明,张新功. 应用模拟植物生长算法求解置换流水车间调度问题[J]. 计算机应用研究, 2010,27(10): 3670-3672.
[45] 丁雪枫,马良. 基于模拟植物生长算法的求解MCCS问题的研究[J]. 计算机工程与设计, 2010,31(7): 1405-1412.
[46] 杨磊,刘珂,刘义保. 模拟植物生长算法在⁶⁰Co源栅格排布中的应用. 核技术,2011,34(3):199-204.
[47] 杨琴,周国华.改进模拟植物生长算法求解汽车维修车间瓶颈工序的多目标动态调度问题[J]. 系统管理学报, 2011,20(5):595-599
[48] 丁雪枫,马良,尤建新,等. 基于模拟植物生长算法虚拟企业盟友选择问题研究[J]. 管理学报,2011,8(2): 278-283.
[49] Floudas C,et al. Handbook of test problems for local and global optimization, Kluwer[Z]. http:// titan.princeton.edu/research.htm.
[50] 邵帅,徐庆. 关于一类二层规划问题的一阶最优性条件研究[J]. 运筹与管理, 2009,18(2):35-40