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

1 高维动态规划试验选优及其在大型渠道工程系统设计中的应用摘要: 本文用高维动态规划模型进行大型渠道工程系统的优化设计, 提出了高维动态规划的试验选优方法, 使高维动态规划问题的求解成为可能. 关键词:动态规划高维优化方法渠道工程目前, 动态规划的“维数灾”问题受到计算机高速存储量和计算时间的限制,在求解高维问题时, 40 年来, 各国学者对动态规划的计算方法进行了多方面的探索,提出了各种方法,如旨在减少维数的拉格朗日乘子法[1]、动态规划逐次渐近法[2], 聚合法[3], 旨在减少离散状态数的离散微分动态规划法[ 4] 、双状态动态规划法[5] 、状态增量动态规划法[ 6 ]和不离散状态直接求解以减少计算量的微分动态规划[ 7]( 要求目标函数、约束条件三阶可微) 以及 等人 1975 年提出的以减少阶段 2 数为手段的渐进优化法[ 7]. 这些方法虽然一定程度上减轻了“维数灾”, 但进展并不很大. 作者在对大型渠道工程系统优化设计研究时也遇到了这些问题, 本文另辟其径, 采用文献[8— 12] 中的系统试验选优基本思想, 来求解高维动态规划问题,则可在该领域内取得突破性的进展. 1 大中型渠道工程优化设计的高维动态规划模型及求解方法 大中型渠道工程优化设计的高维动态规划模型文献[ 13] 提出了大中型渠道工程系统的定性定量混合系统动态规划模型, 模型的决策变量为各渠段纵坡(Ii) 和各渠段的定性方案(Si) ,目标函数为工程计算分析期内的总支出费用, 并考虑首末水位、不冲不淤、渠道最小水位衔接和工程总投资约束. 为了进一步提高模型决策的精度,在文献[ 13 ]的模型基础上,再考虑以下约束: (1) 填挖土方量约束. 若获得满足约束条件,且使文献[ 13] 目标函数最小的解, 而渠道工程的填方量大于挖方量, 附近又没有土方资源, 此时文献[ 13] 中模型获得的解就不 3 一定为最优解,因此,还应加上填挖方量约束方程(1) 式中 Vis(Ii,Si) 和 Vis(Ii,Si) 为i 渠段的填方和挖方量. (2) 流量损失约束. 不同的衬砌方式、不同的渠道过水断面影响渠段的流量损失和投资, 而输配水渠道的设计主要在于保证下游获得在一定水位时的流量, 因此, 在可能的情况下还应进一步考虑流量损失约束: (2) 式中 h4i(Ii,Si) 为i 渠段的流量输水损失,取决于 i 渠道的定性方案 Si( 沿渠衬砌方式等) 、土壤性质、流量和过水断面; Q0 , QN 分别为渠道工程的渠首设计引水量和渠末应获得的设计流量 求解方法考虑全部约束条件,则模型为四维问题, 该模型的求解工作量、难度比文献[ 13] 的二维问题大大增加了,为此本文在模型的求解方面进行了一定的探讨, 提出了高维动态规划的试验选优方法. 基本原理本文对高维动态规划的降维传统技 4 术之一——拉格朗日乘子法[ 1 ]进行了修正,提出了广义拉氏方法, 使加入到目标函数中去的约束检验在计算迭代过程中进行, 而不是传统的计算迭代结束后检验, 因而不管拉格朗日乘子取值多少, 采用广义拉氏方法的解均为满足约束条件的可行解. 此时的问题就转化为寻找最优拉氏乘子的问题, 根据数学模型和拉氏乘子的物理意义, 容易知道拉氏乘子的取值范围,在此基础上则可采用部分试验选优方法[8— 12]( 如正交试验法) 确定最优的乘子值. 拉氏乘子已知时的优化技术对于一般的高维问题( 下面方程式依次为(3)(4)) (3)(4) Xi≥ 0,(i=1,2, …,N) 对 m-1 个约束考虑松驰变量 Wj(j=1,2, …, m-1), 则约束(4) 中 m-1 个约束转化为 Wj ≥0 ;模型(3) 、(4) 转化为一维问题,其模型为: (下面方程式依次为(5)(6) (5)(6) 若 uj 已知, j=1,2 ,…, m-1 ,则有对应的递推关系: 5 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 的解, 0≤ X1 ≤ζ1 ,同时迭代过程中 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的解, 0≤ Xi ≤ζi , 同时迭代过程中 Xi 应满足 Wj( λ i,Xi) ≥ 0(j=1,2, …, m-1),