求解二层规划问题的模拟植物生长算法(系统工程)

1、求解二层规划问题的模拟植物生长算法李 彤（杭州电子科技大学管理学院，杭州 310018）摘 要: 基于模拟植物生长算法(PGSA), 提出了一种求解线性和非线性二层规划问题的智能优化算法. 在该算法中,将二层规划上层解空间和下层反应集分别作为植物的两个生长环境, 建立以生长规则为基础的植物系统演绎方式和以植物向光性理论为基础的概率生长模型, 两者结合所形成的优化模式, 实现了人工植物从初始状态到完整形式的终态（没有新的树枝生长）,从而得到二层规划问题的解.该方法具有搜索精度较高,求解稳定性较强的特点, 通过与国内外学者在线性和非线性二层规划实际测试问题的最优值进行精度比较,表明模拟植物生长算法

2、是有效可行的.关键词: 模拟植物生长算法(PGSA); 线性二层规划; 非线性二层规划中图分类号:TP18 文献标志码:A1 引言二层规划（BLP）是研究复杂系统层次结构的一种有效方法，该方法主要是用来解决分散决策问题的.一个管理系统中，若存在多个决策者，他们各自有不同的目标，而他们的目标达成又是互相关联的，这就是分散决策系统.二层规划问题是1977年由美国数学家Candler和Norton首先提出来的1，其形式为（BLP） s.t. g(x,y)0, y是下层问题的解 s.t. h(x,y)0其中为上层规划问题决策变量, 为下层规划问题的决策变量；F, f: 分别称为上层规划问题和下层规划问

3、题的目标函数；g:为上层规划问题约束条件，h:为下层规划问题约束条件.二层规划主要具有如下特点：系统分上下两级管理，各级决策者依次作出决策，下级服从上级，但下级有相当的自主权；上下级决策者有各自不同的目标，这些目标往往是互相矛盾的；上下级决策者各自控制一部分决策变量，以优化各自的目标；上级决策者优先进行决策，下级决策者优化自己目标而选择策略时，不能违背上级决策；上级的决策可能影响下级的策略集，因而影响下级目标的达成，但上级不能完全控制下级的决策，在上级政策允许范围内下级有自主决策权；下级的决策不但决定着自身目标的达成，而且也影响上级目标的达成，因此上级必须考虑到下级可能采取的策略对自己的不利影

4、响.对分散决策问题的研究已经有较长的历史，20世纪20年代出现的对策论所研究的问题具有分散决策的特征，但一般各个决策者（局中人）没有上、下级之分，而且他们的策略集是分离的.50年代出现的Stackelberg对策，其中的局中人是有上下级之分的，它可以看作特殊的二层规划.60年代，Dantzig和Wolfe提出了大规模线性规划的分解算法，实际上是把它转变成一个分散决策问题，但其中有一个核基金项目：国家自然科学基金(70371051) , 浙江省自然科学基金(Y7100447)作者简介：李彤(1967-), 男, 博士, 教授, 研究方向为优化理论与技术. E-mail: litong67心决策者

5、，其他决策者并没有自己独立的利益，他们实现自己的目标只不过是为实现核心决策者的目标服务. 70年代发展起来的多目标规划通常是寻求多个不同目标的折衷解，有些方法，如目标分层排序法，也可以用来处理分层决策问题，但下级的决策是在保证优化上级的目标前提下作出的，不影响上级目标的达成，故可以逐级求解.但二层规划正是强调下级决策对上级目标的影响，因而一般是不能逐级求解的.2 二层规划问题及其算法自20世纪70年代以来，人们在研究分散管理系统的优化决策问题中，碰到许多用传统方法不能解决的实际问题，如Fortung-Amat和Mecard的化肥价格研究、Candler和Townsley的水资源利用和政府政策研

6、究、Bisschop等人的印度河流域模型、Ansndalingam的印度和孟加拉国恒河水资源冲突分析等，这些应用大大推动了管理科学和国民经济的发展，并逐渐形成了新的概念和方法.在这一阶段二层规划比较具有代表性的研究成果主要有，Cassidy研究的政府效力分析2、Kyland的经济研究分析3、Brocken等人1973-1977年研究的战略武器配置、Desitva研究的美国原油生产模型.20世纪80年代，二层规划的数学模型得到较大发展，文卫平、Candler、Townsley、Bialas、Karwan和Bard等先后提出了一般二层规划的数学模型6-11；Bard利用Kuhn-Tucker条件得

7、到了二层规划问题的最优解必要条件，还证明了二层线性规划的可行集是容许集的若干个面的并集，并且是连通的，从而存在最优解12；G.Anandalingam提出基于罚函数的求解多部门系统的新方法，讨论了不同分配形式的Nash均衡解的存在，为减少计算时间，他还提出了基于Kuhn-Tucker条件的Stckelberg均衡算法，将得到的非线性问题再转化为整数规划问题；W.Bialas提出了一种混合算法，首先采用K次最好法，通过优化第三层问题产生第K步最好解，然后用PCP法检验第二层问题的最优性条件.20世纪90年代以来二层规划的理论和算法研究有了较深入的发展，J.J.Judice和A.Faustion给

8、出了二层线性规划的SICP算法14；H.D.Serall等人给出了线性互补性问题的增强的交叉割平面近似法，从而推动了算法研究的进一步开展.我国在该领域的研究工作起步较晚，20世纪80年代阮国桢、左晓波教授把二级线性规划的解集推广到无界的情形17；此后涉足该领域的学者逐渐增多，夏洪胜、贺建勋将二级规划的研究与两层决策问题相结合，此后他们将二层决策问题扩展到多目标问题18；杨若黎、顾基发给出了一类二级非线性规划的模拟退火求解19；刘国山提出了双层优化问题的信赖域算法20；滕春贤等人研究了二层广义凸规划并讨论了其基本性质21 ；刘树安、刘新旺、达庆利、王广民、王先甲、万仲平、刘三阳等学者分别提出了不

9、同类型的二层线性规划问题的遗传算法22-25，这些内容大大丰富了二层规划问题的理论和方法.目前二层规划问题尚缺乏有效算法，其主要原因在于二层规划的复杂性，Jeroslow首次在文献27中证明二层线性规划是NP-难题，Hansen和Jaumard等人进一步证明了二层线性规划是强NP-难题28，此后Vicente和Savard等人证明了即使是求解二层规划的局部最优解也是一个NP-难题29.对于此类问题，近年来智能算法取得了十分突出的成绩，这些算法都有一个共同的特点：从随机的可行初始解出发，采用迭代改进的策略，去逼近问题的最优解. 他们的基本要素：（1）随机初始可行解；（）给定一个评价函数（常常与目

10、标函数值有关）；（）邻域，产生新的可行解；（）选择和接受解的准则；（）终止准则. 然而，这些算法（如遗传算法、蚁群算法、粒子群算法等）需要给出诸如惩罚系数、初始染色体群、交叉率、变异率、初始粒子群等直接影响计算速度和收敛性的参数，在大多数情况下，这些参数选择的本身就是一个难题. 针对以上问题，本文作者在文献30中提出了一种以植物向光性理论为启发式准则的智能算法模拟植物生长算法（Plant Growth Simulation Algorithm，PGSA），在本文中我们探索将PGSA应用于求解二层规划问题.3 模拟植物生长算法植物可看作由大量枝、节组成的系统，其研究的重点是L-系统（L-syst

11、ems），该系统是美国生物学家A.Lindenmayer在20世纪60年代末提出.L-系统将植物生长视为一系列事件的综合，在构型上其前驱（父）模块被后继（子）模块代替，替代规则被称为繁殖（productions），这些替代具有定型或定量的特点.生物学实验已经证明，决定植物细胞分裂和枝芽生长的生长素信息并非是预先一个个赋予给细胞的，而是细胞系统从其环境中接受到了它的位置信息，依据这种信息，植物表现出明显的向光性特点，即形态素浓度较高的生长点，将具有较大的优先生长机会. 模拟植物生长算法借鉴以上机理，在各类优化问题解空间中构建模拟植物并按照L-系统模型使其快速生长，形成分形生长树，实现模拟植物从初

12、始状态到完整形式终态的过程，这就是PGSA，其数学模型和迭代过程详见文献30. 3.1 模拟植物生长算法的应用情况目前模拟植物生长算法主要被国内外学者用于系统优化领域（整数规划、组合优化等）和工程技术领域（电力、计算机、核工业等）.文献30-36主要利用模拟植物生长算法解决优化领域的问题.文献37-48主要利用模拟植物生长算法解决工程技术领域的问题.以上国内外学者在解决实际问题的同时还将模拟植物生长算法与遗传算法、蚁群算法、模拟退火算法、协同进化算法、粒子群算法、Tabu搜索等算法进行了比较研究，表明模拟植物生长算法在计算精度、收敛性和计算速度等方面具有一定的优势. R. Srinivasa

13、Rao和S. V. L. Narasimham在文献37中应用模拟植物生长算法来解决雷达分布的优化问题。他们的应用结论为：“The advantages with the Plant Growth Simulation algorithm(PGSA) is that it treats the objective function and constraints separately, which averts the trouble to determine the barrier factors and makes the increase/decrease of constraints

14、convenient, and that it does not need any external parameters such as crossover rate, mutation rate, etc. It adopts a guiding search direction that changes dynamically as the change of the objective function.” 在另外的优化领域，K. Guney 、A. Durmus和S. Basbug在文献38中将PGSA分别于MTACO、BA、BFA三种智能算法比较，PGSA均得到了更优的结果，且收敛

15、性和计算速度明显优于其他算法。他们的应用结论为：“As an optimization algorithm, the PGSA will most likely be an increasingly attractive alternative, in the electromagnetics and antennas community, to other optimization algorithms.”文献45对模拟植物生长算法做过一个总结：“与遗传算法为代表的现代启发式算法相比，模拟植物生长算法具有以下优点：模拟植物生长算法将目标函数和约束条件分开处理，且无需编码和解码，避免了构造新的

16、计算用目标函数，也不存在惩罚系数、交叉率、变异率选取等问题，解的稳定性好；模拟植物生长算法具有一个由形态素浓度决定的方向性和随机性平衡比较理想的搜索机制，能以较快的速度寻找到全局最优解.”3.2 二层规划的模拟植物生长算法程序设计对于二层规划问题（BLP） s.t. g(x,y)0, y是下层问题的解 s.t. h(x,y)0为问题的约束域，x为上层决策变量解空间，Mx(Si)为下层规划问题对应上层给定值Si的反应集.Step1: 在上层决策变量解空间 x中选择k个初始植物生长点（S1，S2，Sk）；图1 形态素浓度状态空间Step2: 在Si的各自反应集中选择下层植物生长点Tj(Si)Mx(

17、Si)，连接Si与Tj(Si)形成树干，树干长度为F(Si, Tj(Si)；Step3: 计算（S1，S2，Sk）形态素浓度值：Step4: Pi+1Pi +1+ Pi，PiPi/Pk；Step5: 如果Pi<random0,1<Pi+1，则HSi（见图1）Step6: 上层变量初始状态：H旋转角度：90°*生长规则: FFFF F新生长点为: Si(1), Si(2), , Si(2n)，其中n为上层规划决策变量维度*注：生长规则是A.Lindenmayer所建立的L-系统形式语法，设（H,）为植物生长点的当前状态. 其中H为其位置的坐标，为生长点的指向，节的长度为d，

18、顶的角度增量为. “”代表的含义是将当前信息记录下来，即将该节点（树枝的分叉点）的信息保存起来，先画第一个分枝；而“”表示的含义是将“”时刻记录的信息释放出来，当画完一个分枝后，利用“”将上一个节点的信息（即上一分叉点的状态）取出，然后从该分叉点继续画第二个分枝. 其他相关符号的含义为，F表示在当前方向上生长节长d，表示逆时针旋转一个角度（规定逆时针方向为正），表示顺时针旋转一个角度.Step7: Simin F(Si, Tj(Si) ), F(Si(1) , Tj(Si) ), F(Si(2) , Tj(Si), , F(Si(2n) , Tj(Si)；Step8: 下层变量初始状态：L旋转

19、角度：90°生长规则: FFFF F新生长点为Tj1(Si), Tj2(Si), , Tj2m(Si)，其中m为下层规划决策变量维度Step9: Tj(Si)min F(Si, Tj(Si) )+f(Si, Tj(Si), F(Si , Tj1(Si)+f(Si , Tj1(Si) ), F(Si, Tj2(Si)+f(Si, Tj2(Si), , F(Si, Tj2m(Si)+f(Si, Tj2m(Si)；Step10:若连续m次迭代无新枝生长（或设定迭代次数，如50000次迭代），则植物生长结束，否则返回Step3.以上Step3-Step9是上层植物生长点通过向光性概率机制选定

20、后，与其对应反应集中下层生长点所形成的植物树干Si-Tj(Si)在各自邻域中的一次生长过程，可以简单地用下图表示Mx(Si) Si Tj(Si) xMx(Si) Si Tj(Si) xMx(Si) Si Tj(Si) xMx(Si) Si Tj(Si) 图2 植物树干Si-Tj(Si)邻域生长过程4 数值试验算法的可行性和有效性需要通过与其它方法进行比较才能得到验证.本文中模拟植物生长算法用Matlab编程实现，试验中计算机为Celeron(R) CPU 3.06GHz，1.00GB内存，Windows XP.我们与以下三个测试问题进行精度比较，其中例1、例2来自于普林斯顿大学C.Flouda

21、s教授在“Handbook of Test Problems for Local and Global Optimization”49中收录的二层规划测试问题，例3为复旦大学邵帅、徐庆在文献52中的优化问题.例1 求解以下二层优化问题min (x-4y)s.t. x0, y是下层规划的解min (y)该问题最早由P.Clark和A.Westerberg提出49，后来被A.Yezza作为二层规划的测试问题50，该问题目前的最好结果由C.Floudas求得并公布在其测试问题手册当中，结果如下最优解：x=18.929688 y=13.953125最优值：-36.882813我们得到了一个全局最优解和

22、三个局部最优解（见表1），4个求解结果均比现有文献中最好的结果有较大程度的提高（其中全局最优解精度提高了57.65%）.表1 模拟植物生长算法得到例1全局最优解和局部最优解最优解序号最优解最优值x y全局最优解8.7706 16.7294-58.1470局部最优解112.8767 16.4493-52.9205局部最优解29.0366 13.4634-44.8170局部最优解313.1452 13.3548-40.2740例2 求解以下非线性二层优化问题min (x2+y2)s.t. x0, y0, y是下层规划的解min (-y)该问题由H.Tuy和A.Migdalas求解结果如下最优解：x

23、=4.492188 y=1.523438最优值：22.500610本文的计算结果表明，该问题的以上最优解有很大问题，我们利用模拟植物生长算法得到了一个全局最优解和11个局部最优解（见表2）均远远优于H.Tuy等人得到的最优解.表2 模拟植物生长算法得到例2全局最优解和局部最优解最优解序号最优解最优值序号最优解最优值x yx y全局最优解0.1069 1.40691.9908局部最优解61.6831 2.58319.5052局部最优解11.0492 1.34922.9212局部最优解70.7030 3.00309.5122局部最优解20.9070 2.20705.6935局部最优解82.5872

24、 2.087211.0500局部最优解31.8572 1.75726.5369局部最优解91.4478 3.347813.3039局部最优解42.7353 1.23539.0078局部最优解100.4237 3.723714.0455局部最优解50.0000 3.03099.1864局部最优解112.3956 2.895614.1234例3 求解下列非线性二层优化问题min (x+y)s.t. x-3y-60, y是下层规划的解min (y2+5xy+x2) s.t. 2x-y-40文献52利用Fritz John方法给出该问题的最终结果为最优解：x=12/17 y=-30/17最优值：-18

25、/17（-1.0588）本文利用模拟植物生长算法得到了一个全局最优解和两个局部最优解，见表3表3 模拟植物生长算法得到例3全局最优解和局部最优解最优解序号最优解最优值x y全局最优解0.5787 -1.8071-1.2284局部最优解10.6108 -1.7964-1.1856局部最优解20.6750 -1.7750-1.1000以上三个测试问题我们分别进行15次运算，其中全局最优解的最好结果和最差结果误差均小于0.0001，例1平均计算时间为16秒，例2平均计算时间为21秒，例3平均计算时间为19秒.5 结束语模拟植物生长算法(PGSA)是以植物向光性概率生长为启发式准则的智能算法,在解决二

26、层优化问题当中,该算法表现出了较强的全局搜索能力.由于模拟植物生长算法对初始点的选择要求宽松,同时没有遗传算法、蚁群算法、模拟退火算法等其他智能算法需要的一些较难确定的参数，因此解的稳定性好.本文通过对国内外学者提出的线性和非线性两类二层规划问题的具体应用，显示出模拟植物生长算法具有计算精度较高，稳定性较好的特点.参考文献1 Candler W, Norton R. Multilevel Programming. Techinical Report 20, Word Bank Development Research Center, Washington D.C.19772 Cassidy R

27、 G, Kirby M J L and Raike W M, Efficient distribution of resources through three level of government. Mgmt Sci., 1971, 17: 462-4733 Kyland F, Hierarchical decomposition linear economic model, Mgmt Sci., 1975, 21: 1029-10394 Gogan W W, Point-to-set maps in mathematical programming, SIAM Review, 1973,

28、 15: 591-6035 Naccache P H. Connectedness of the set of nondominated outcomes in multicriteria optimization. Journal of Optimization Theory and Applications, 1978, 25: 459-4676 U P Wen, Hsu Shuhtzy, Linear bilevel programming problems-A Review, J.Opl.Res, 1991, 42(2): 125-1337 Candler W J, Fortuny-A

29、mat and Mccarl B, The potential role of multilevel programming in agricuitural economics, Am J.Agric.Econ, 1981, 63: 521-5318 Bard J F, An algorithm for solving the general bilevel programming problem, Mathemat, Opns Res,1983, (8): 260-2729 Bialas W F, Karwan M H. Two-level linear programming.Manage

30、ment Science. 1984, 40(8): 1004-102010Sawaragi Y, Nakayama H and Tanino T, Theory of multiobjective optimization, Academic Press, Inc. (London), 1985, 21-2511Takayam a T, Judge G. Spatial and temporal price and allocation models, North-Holland, Am sterdam，Holland, 1971,3712Bard J F, An efficient poi

31、nt algorithm for a linear two-stage optimization problem, Operations Research, 1983, 31(4): 670-68413Bard J F, Geometric and algorithmic developments for a Hierarchica planning problem, European Journal of Operational Research, 1985, 19: 146-16414J.J.Judice and A Favstion, The Linear-Quadratic Bilev

32、e Programming Problem. 1994,32(2)15C.Audet, P.Hansen, B.Jaumard and G.Savard Links, Between Linear Bilevel and Mixed 0-1 Programming Problems. Journal of Optimization Theory and Applications. 1997, 93(2): 273-30016A.Yezza, First-Order Necessary Optimizality Conditions for Jeneral Bilevel Programming

33、 Problems, Journal of Optimization Theory and Applications, April 1996,89(1):189-21917阮国桢,左晓波.线性多级规划的最优性条件和基本性质.系统科学与数学.1988,18(2):159-16618夏洪胜,贺建勋,基于满意度的两层多目标决策问题的交互式外部逼近算法,系统工程理论方法应用,1993,2(1):14-2219杨若黎,顾基发.一类非线性双级规划问题的模拟退火求解.系统工程理论与实践.1997,(7):52-5820刘国山. 双层优化问题的信赖域算法,科学通报,1998,43(4): 383-38721张

34、铁柱,陈东彦,滕春贤. 二层广义凸规划及其性质. 数学的实践与认识. 2004,34(3):98-10222刘树安,尹新. 二层线性规划问题的遗传算法求解. 系统工程学报. 1999,14(3):280-28523刘新旺,达庆利.一类两层规划问题模糊满意解的遗传算法.管理科学学报.1999,2(3):33-3824杨亚红,刘三阳.非线性整数二层规划的一种算法.西安电子科技大学学报.2001,28(2):198-20125王广民,万仲平,王先甲.基于遗传算法的二层线性规划问题的求解算法.运筹与管理.2005,14(2): 54-5826王广民,万仲平,王先甲. 二（双）层规划综述.运筹与管理.2

35、007,36(5):513-52927Jeroslow R. The Polynomial Hierarchy and a Simple Model for Competitive Analysis. Mathematical Programming. 1985,32:146-16428Hansen P,Jaumard B,Savard G. New Branch-and-Bound Rules for Linear Bilevel Programming. SIAM Journal on Science and Statistical Computing. 1992,13:1194-1217

36、29Vicente L, Savard G, Judice J. Descent Approaches for Quadratic Bilevel Programming. Journal of Optimization Theory and Applications. 1994,81:379-39930李彤.求解整数规划的一种仿生类全局优化算法模拟植物生长算法J.系统工程理论与实践.2005, 25(1):76-8531李彤,王众托. 模拟植物生长算法在设施选址问题中的应用J.系统工程理论与实践. 2008.28(12): 107-11532李彤,王众托. 模拟植物生长算法与知识创新的几点思

37、考J. 管理科学学报. 2010,13(3):87-9633李彤 著. 单级与二级整数规划算法原理及应用M. 科学出版社. 2007.734丁雪枫,马良. 基于模拟植物生长算法的易腐物品物流中心选址J. 系统工程,2009.27(2):96-10135丁雪枫,马良. 基于模拟植物生长算法构造Steiner最优树问题研究J.数学的实践与认识.2010,40(9):149-15336丁雪枫,马良. 基于模拟植物生长算法的求解MCCS问题的研究J.计算机工程与设计.2010,31(7):7-1137R. Srinivasa Rao, S. V. L. Narasimham. Optimal Capa

38、citor Placement in a Radial Distribution System using Plant Growth Simulation AlgorithmJ. International Journal of Electrical Power and Eenergy and Energy Systems Engineering. 2008.1(2):123-130.38K. Guney, A. Durmus, S. Basbug. A Plant Growth Simulation Algorithm for Pattern Nulling of Linear Antenna Arrays by Amplitude Control. Progress In Electromagnetics Research B. 2009(17):698439P.V.V. Rama, S. Sivanaga Raju. Optimal Conductor Se