高维动态规划试验选优及其在大型渠道工程系统设计中的应用.doc

高维动态规划试验选优及其在大型渠道工程系统设计中的应用摘要：本文用高维动态规划模型进行大型渠道工程系统的优化设计，提出了高维动态规划的试验选优方法，使高维动态规划问题的求解成为可能. 关键词：动态规划 高维 优化方法 渠道工程 目前，动态规划的“维数灾”问题受到计算机高速存储量和计算时间的限制，在求解高维问题时，常遇困难.近40年来，各国学者对动态规划的计算方法进行了多方面的探索，提出了各种方法，如旨在减少维数的拉格朗日乘子法1、动态规划逐次渐近法2，聚合法3，旨在减少离散状态数的离散微分动态规划法4、双状态动态规划法5、状态增量动态规划法6和不离散状态直接求解以减少计算量的微分动态规划7(要求目标函数、约束条件三阶可微)以及H.R.Howson等人1975年提出的以减少阶段数为手段的渐进优化法7.这些方法虽然一定程度上减轻了“维数灾”，但进展并不很大.作者在对大型渠道工程系统优化设计研究时也遇到了这些问题，本文另辟其径，采用文献812中的系统试验选优基本思想，来求解高维动态规划问题，则可在该领域内取得突破性的进展.1大中型渠道工程优化设计的高维动态规划模型及求解方法1.1大中型渠道工程优化设计的高维动态规划模型 文献13提出了大中型渠道工程系统的定性定量混合系统动态规划模型，模型的决策变量为各渠段纵坡(Ii)和各渠段的定性方案(Si)，目标函数为工程计算分析期内的总支出费用，并考虑首末水位、不冲不淤、渠道最小水位衔接和工程总投资约束.为了进一步提高模型决策的精度，在文献13的模型基础上，再考虑以下约束：(1) 填挖土方量约束. 若获得满足约束条件，且使文献13目标函数最小的解，而渠道工程的填方量大于挖方量，附近又没有土方资源，此时文献13中模型获得的解就不一定为最优解，因此，还应加上填挖方量约束方程(1) 式中Vis(Ii,Si)和Vis(Ii,Si)为i渠段的填方和挖方量.(2)流量损失约束.不同的衬砌方式、不同的渠道过水断面影响渠段的流量损失和投资，而输配水渠道的设计主要在于保证下游获得在一定水位时的流量，因此，在可能的情况下还应进一步考虑流量损失约束：(2)式中h4i(Ii,Si)为i渠段的流量输水损失，取决于i渠道的定性方案Si(沿渠衬砌方式等)、土壤性质、流量和过水断面；Q0，QN 分别为渠道工程的渠首设计引水量和渠末应获得的设计流量1.2 求解方法 考虑全部约束条件，则模型为四维问题，该模型的求解工作量、难度比文献13的二维问题大大增加了，为此本文在模型的求解方面进行了一定的探讨，提出了高维动态规划的试验选优方法.1.2.1 基本原理 本文对高维动态规划的降维传统技术之一拉格朗日乘子法1进行了修正，提出了广义拉氏方法，使加入到目标函数中去的约束检验在计算迭代过程中进行，而不是传统的计算迭代结束后检验，因而不管拉格朗日乘子取值多少，采用广义拉氏方法的解均为满足约束条件的可行解.此时的问题就转化为寻找最优拉氏乘子的问题，根据数学模型和拉氏乘子的物理意义，容易知道拉氏乘子的取值范围，在此基础上则可采用部分试验选优方法812(如正交试验法)确定最优的乘子值.1.2.2 拉氏乘子已知时的优化技术 对于一般的高维问题(下面方程式依次为(3)(4)(3)(4)Xi0,(i=1,2,N) 对m-1个约束考虑松驰变量Wj(j=1,2,，m-1),则约束(4)中m-1个约束转化为Wj0；模型(3)、(4)转化为一维问题，其模型为：（下面方程式依次为(5)(6)(5)(6)若 uj 已知，j=1,2，m-1，则有对应的递推关系：1阶段：(7)Wj(1,X1)=bj-hj1(X1),(8)Wi(1)=Wi(1,X*1),j=1,2,，m-1,(9)式中1为hm1(1)=1 的解，0X11，同时迭代过程中X1应满足加入至目标函数中去的m-1个约束，Wj(1,X1)0，j=1,2,m-1.i 阶段：(10)Wj(i,Xi)=Wj(i-1)-hji(Xi),(11)i-1=i-hmi(i),(i=2,3,，N)(12)式中为hmi(i)=i 的解，0Xii，同时迭代过程中Xi应满足 Wj(i,Xi)0(j=1,2,，m-1),最后i=N时式(9)中的松驰变量Wj=Wj(*N).由上递推关系可获得uj(j=1,2,，m-1)已知情况下的最优决策X*i(i=1,2,，N).1.2.3 拉氏乘子的优化技术 由式(5)目标函数可知(F)/(bj)=uj,uj 的物理意义为某种资源(bj)的影子价格，uj 的数值大小取决于该资源的利用情况.在求解实际问题时，使式(3)、(4)最优的u*j 获得是困难的，但确定uj的数值范围是容易的.例如已知uj(j=1,2,，m-1)的数值范围来确定其对应的最优值 u*j，最直接的方法是把uj在其数值范围内离散，然后将所有组合代入模型(5)、(6)，以获得最优解，若m较大时，这样工作量太大，显然是不太实际的，但可以采用部分试验选优方法如正交试验法1417，在全部可能组合中选取少量组合， 采用模型(5)、(6)以获得优化解，然后通过正交分析来获得所有可能组合中的最优解及依次的次优解.1.2.4 正交试验和正交表 采用正交试验在uj(j=1,2,，m-1)的取值范围内确定u*j,其最优性、精度和计算工作量的关键在于正交表的构造选择.正交试验的最优性在文献1517中已被广泛讨论和确认，精度和uj在其对应取值范围内的离散步长有关，并直接影响计算优化的工作量.若构造一般型正交表Lp(tq),t为uj 在其可行域内离散的个数，其为素数或素数幂；q为该正交表最多可以按排uj的个数，即qm-1;P为对应一维动态规划模型计算个数；P、t,q之间存在以下关系17：P=(13)q=(-1)/(t-1)(14)式中v为任意正整数，则可以获得计算工作量(P)和m,t之间的关系P(m-1)(t-1)+1(15)选择构造正交表时完全可以使式(15)取等号，则若m=1001,取t=11或101，那么一个1001维动态规划问题的优化工作量相当于104+1或105+1个对应一维动态规划问题的计算工作量，目前一般计算机均可接受，而对于现行动态规划的所有降维、简化方法是无法想象的. 1.3 渠道工程优化设计模型的求解 模型(1)(6)转化为一维问题：(16) Iby,iIiIbc,i(Si),i=1,2,，N ，(17)I（2）kIkI（）k(18)(ki,kmaxN-1,为渠末有流量变化，且无提水节制建筑的渠段)(19) 可见决策变量Xi为(Ii,Si);状态变量i为水头损失，0ib1，由递推关系式(7)(12)结合文献13可得对应的递推关系：1阶段：(20)Wj(1,X1)=bj-hj1(X1),(21)Wj(1)=Wj(1,X*1),(22)X1(I1,S1),式中1v1,u1，设渠段1定性方案依次代入下式：(23)得对应的，t=1,2,，T1;t1为对应定性方案u时的纵坡I1可行取值范围，结合式(17)、(18)有：（下面的情况分别为：渠段末有流量变化，无交叉节制提水建筑；除上情况）(24)i 阶段：(25)Wj(i,Xi)=Wj(i-1)-hji(Xi),(26)i-1=i-h1i(Xi), i=2,3,，N.(27) Xi(Ii,Si).式中i(vi,ui)，渠段i的定性方案S依次代入下式：(28)得对应定性方案uti的纵坡取值范围，结合式(17)、(18)有：(i=2,3,，N)(29)以此递推得uj已知情况下式(16)(19)的解.关于uj(j=2,3,4)的取值范围确定.本课题根据Ii和Si的可行范围、沿渠地形的变化情况、各渠段的流量，以及模型(16)中目标函数的物理意义，可以知道：的数值范围(Ai,Bi)即：(30)若设u2=u=u=ui,则可得：,(i=1,2,，N)(31)采用最不利的(Ii,Si)代入即可获得uj的取值范围.1.4 实例分析 采用文献13算例，有关主要参数和可能的定性方案见表1.通过计算分析u2,u3,u4的取值范围均取为0，2.4，选用L9(34)型正交表对所选的9个uj组合进行了对应的一维动态规划问题求解，其最优解和采用DDDP法求解结果目标值相差5.6%，对uj进一步离散选用L25(56)型正交表选择对应25个uj组合进行对应的一维动态规划问题求解分析，其最优解和采用DDDP法求解结果基本相同，此时占用计算机的运算时间不到DDDP法的1/6，有关计算主要成果摘要见表2和表3.2结 论(1)寻求高维动态规划的求解方法是近40年国内外众多学者久攻不下的系统科学重大研究的课题.目前经典方法一般仅能求解35维问题，其它近似方法也只能求解数拾维问题.本文提出的试验选优方法可以使较高维数的高维动态规划问题求解成为可能.本文的试验方法主要针对正交试验法而言的，对于采用其它部分试验选优方法进行优化分析，还有待于进一步探讨.(2)本文提出的大型渠道工程优化设计的高维动态规划模型对大型调水工程优化设计具有较为重要的参考价值.表1 定性方案和基本数据渠 段OAABBCCD渠长/km15113221设计流量/m/s1001005050加大流量/m/s1201206060最小流量/m/s40402020沿渠土壤性质砂土砂土砂壤砂壤断面形状和衬砌方案a.梯形断面；扩宽系数 K=2.5，2.2，2.0，1.8；换土压实.b.梯形断面；扩宽系数 K=2.2，2.0，1.8，1.6；无衬砌.可行提水泵站方案的提水扬程/m023023234023沿渠地面高程/m36.337.7其它主要资料a.总投资小于1亿元；b.渠道首末水头分别为35.5m和37.5m.c.要求挖方和填方之差小于10%.表2 计算成果对照表渠 段DDDP 法试验方法uj离散5点试验方法uj离散3点备注运算时间15小时40分2小时32分1小时08分目标值：计算分析期内总支出费用现值/亿元2.8022.8022.96投资现值/亿元0.9340.9340.967总土方量/104m110911091185总挖方/104m602602687总填方/104m507507498表3 DDDP法和采用L25(56)型正交分析优化成果表渠 段OAABBCCD初砌方式换土压实换土压实无无断面形式梯形，K=2.2梯形，K=2.2梯形，K=2.0梯形，K=2.0提水扬程/m和泵位置123设计纵坡1/250001/183001/225001/21000设计底宽/m12.02.08.09.0设计水深/m5.26.04.55.5参 考 文 献1Leon C, Mary W C.Introduction to Dynimic Programming.PergamonmPress, 1981, 197-207.2Bellman R E, Dreyfus S E. Applied Dynamic Programming.Princeton Unversity Press,1962, 293-38523Turgeon A. A decomposition method for the long|term schednling of reservoirs in series.Water resources research, 1981,17(6).4Heidar M,Chow V T, et al. Disrete differential dynamic programming approach to water resource optimization.Water resources research, 1971,17(2).5Ozden M. A binary state DP algorithm for operation problem of multireservoir system. Water resource resecrch.1984,20(1).6Larson R E. State increment dynamic prorgamming.Management science 19, 1973,1452-1458.7白宪台，多维动态规划.北京：水利电力出版社，1988，43-52.8程吉林，金兆森, 大系统模拟试验选优方法及应用.水利学报，1993，(11).9程吉林,孙学华,模拟技术、正交设计、层次分析及其在灌区优化规划中的应用.水利学报，1990，(9).10程吉林.某些特殊路径问题的正交表法.系统工程，1991，(2).11.程吉林.介绍一种大系统优化的知识模型.系统工程理论和实践，1992，(4).12Jilin C, et al. Optimal test theory of large scale system and applying in irrigation district scheme.System science and system engineering,(ICCSSE93)Edited by Zheng Weimin, International Academic Publishers Press, 1993, 348-356.13Jilin C, et al. A dynamic programming medol of mixture system for conveyance canal engineering.Journal of system science and system engineering, 1993,4