（电力系统及其自动化专业论文）三峡梯级水库优化调度模型及其应用.pdf

的研究课题。结合现代优化方法与传统优化方法这两种方法的优势互补性，提出了 g a & 2 d d p & d d d p 全局寻优算法。算法在实现过程中应用两级协调结构，第一级应 用g a 全局算法协调器，得到的近似解在全局最优解附近振荡并构成梯调问题的初始 解；第二级应用2 d d p & d d d p 局部算法协调器，这一迭代寻优的过程有力地将g a 所得解推向全局最优解或全局最优解域。通过对三峡梯级这一实际系统进行仿真计 算，结果表明混合算法在解的质量方面( 包括探寻全局最优解的能力) 和算法的稳健性 方面，似乎更具有优越性。为进一步分析算法的有效性，针对具有2 0 0 个变量的 r o s e n b r o c k 函数进行了数值测试，通过对计算结果作细致的比较与分析，相应地得出 了g a & 2 d d p & d d d p 算法是稳健且有效的结论。 ( 6 1 科学计算作为科学研究与工程应用的手段，开益受到人们的重视，并视为与 理论和实验同等重要的科学领域，因此，对于复杂问题的描述所建立的数学模型，必 须要经过科学计算加以检验。文中提出的模型与算法，均经过严格的仿真计算，结论 可信，并针对三峡数字梯级决策支持系统的应用，实践效果良好，为三峡电力生产者 和管理者制定合理的调度计划提供了有效的决策支持。 关键词：厂内经济运行，开关控制策略，面向对象程序设计，二维动态规划，离散微 分动态规划，遗传算法，梯级水库优化调度，决策支持系统 j j a b s t r a c t i nt h i s d i s s e r t a t i o n ，a s e r i e so fc o n c l u s i o n sa n d m e t h o d o l o g i e s w i t ht h e o r e t i c a l s i g n i f i c a n c ea n dp r a c t i c a lw o r t h i n e s sa r ed r a w na g a i n s tt w oa c t u a ls u b j e c t sc o n s i s t i n go f h y d r o p l a n t s c h e d u l i n g a n dd e c i s i o n s u p p o r ts y s t e m i nt h e t h r e e g o r g e s c a s c a d e d h y d r o p o w e rs y s t e m s t h em a j o r r e s e a r c hw o r ki so u t l i n e da sf o l l o w s ： ( 1 ) a c c o r d i n g t op r a c t i c a lo p e r a t i o nr e q u i r e m e n to f h y d r o p o w e r p l a n t s ，ak i n do f o r g o f f c o n t r o lv a r i a b l e sm a p p i n gu n i tc o n s t r a i n t si n t os e c u r i t ya n di n s e c u r i t yo p e r a t i o nz o n ea r e f i r s td e s i g n e d t h e nan e wm e t h o df o ri n n e re c o n o m i co p e r a t i o ni sp r o p o s e d t h em e t h o d u s i n g as w i t c h c o n t r o l s t r a t e g y c a nr e f l e c tt h e o p e r a t i n g s t a t u so fu n i t sa n de n s u r e s u t i l i z a t i o nr a t i oo ff a c i l i t i e s a i m i n ga tt h ep r o b l e m so f i n s e c u r i t yo p e r a t i o nz o n ee f f e c t i n g e f f i c i e n c ya n ds e r v i c el i f ef o rt u r b i n e s ，t h es u g g e s t e dm e t h o d i sf e a s i b l ea n de f f e c t i v e ( 2 ) b ym e a n so ft h eo b j e c t o r i e n t e dp r o g r a m m i n gt e c h n o l o g y ( o o p ) ，t h ec o m p l e t e s t r u c t u r eo fc o m p l i c a t eo b j e c to no p t i m a ld i s p a t c hp r o b l e mo ft h ec a s c a d e dh y d r op l a n t s a n di t sr e u s a b l em u l t i l e v e ls e p a r a t i n ga n d d y n a m i c a l l yc o n s t r u c t i n gt e c h n i q u e sa r ep r o v i d e d t h ec o r r e s p o n d i n ga l g o r i t h mf l o w c h a r t si n c l u d i n gt w od i m e n s i o n a ld y n a m i cp r o g r a m m i n g ( 2 d - d p ) ，d i s c r e t ed i f f e r e n t i a ld y n a m i cp r o g r a m m i n g ( d d d p ) ，g e n e t i ca l g o r i t h m ( g a ) ， 2 d - d p & d d d pa n dg a & 2 d d p & d d d pa r ed e r i v e d t h i sk i n do fs o f t w a r ed e s i g ns t y l e i sc h a r a c t e r i z e db yd a t ae n c a p s u l a t i o n ，r e l a t i o ni n h e r i t a n c ea n dp o l y m o r p h i s m d u r i n gt h e c o u r s eo f d e v e l o p i n gs o f t w a r e ，p r o g r a mc a nb ee d i t e d ，r e v i s e d ，m a i n t a i n e da n de x p a n d e d c o n v e n i e n t l y t h ep r o g r a m r o u t i n ep r o v i d e sa ne f f e c t i v ew a yf o rc o m m e r c i a l i z i n gs o f t w a r e o f c a s c a d e ds c h e d u l i n g ( 3 ) ah y b r i d2 d d pa n dd d d pf o rd a i l yo p t i m a lo p e r a t i o n i nt h et h r e e g o r g e s c a s c a d e dh y d r o p o w e rs y s t e m si s s u g g e s t e d t h i sm e t h o dm e e t sr e q u i r e m e n to fp r a c t i c a l o p e r a t i o n a n d e f f i c i e n t l y o v e r c o m e s “t h ec u r s eo fd i m e n s i o n a l i t y ”w h i c he x i s t si n c o n v e n t i o n a ld y n a m i c p r o g r a m m i n g ，i t sc a l c u l a t i n gs t e p sa r ep r e s e n t e d i nd e t a i la l s o i nt h e m e a n t i m e ，t h ef o r m u l ao nh o wt os e ta ni n i t i a ls o l u t i o na saw a r ms t a r ti nt h eh y b r i d a l g o r i t h m sa sw e l la st h ev e r d i c tc o n d i t i o no nw h e t h e rt h eo p t i m a ld i s p a t c hm o d e le x i s t s f e a s i b l es o l u t i o n sa r ed e p i c t e d ( 4 ) g e n e t i ca l g o r i t h m s ( g a ) a r ek n o w n t ob ee f f i c i e n tf o rg l o b a lo p t i m i z i n gb u t p r o n e i i i t op r e m a t u r ec o n v e r g e n c e ，w h i c ha f f e c t st h es o l v i n go f p r o b l e m s b a s e do i lc o m b i n a t i o no f g e n e t i co p e r a t o r s ，a l li m p r o v e dg e n e t i ca l g o r i t h mi sp r o p o s e d m a k i n gn s eo f t h es e a r c h f e a t u r e so fs o m et y p i c a lg e n e t i co p e r a t o r sa n di n c o r p o r a t e st h e mi n t od e s i g no fa l g o r i t h m ，i t a v o i du t i l i z i n gas i n g l eg e n e t i co p e r a t o rd e s i g nw h i c hh a sb e e na p p l i e di ns i m p l eg e n e t i c a l g o r i t h m s n u m e r i c a lt e s t so nv a r i o u ss c a l ep r o b l e m sr e v e a l t h a tl i m i t a t i o ni ss t i l l r e m a i n i n g w h e nc o m b i n e d g e n e t i ca l g o r i t h m i s a p p l i e d t o l a r g e - s c a l eo p t i m i z a t i o n p r o b l e m s f u r t h e ri m p r o v e dp o l i c y o nt h i sa l g o r i t h mi sa l s oc o n c e i v e d ( 5 ) i nv i e wo fh u g ee c o n o m i cr e t u m ，i ti sn e c e s s a r yt oe x p l o i tg l o b a ls o l u t i o n so rt o i n v e s t i g a t et h ed i s t r i b u t i o nf e a t u r e so fa p p r o x i m a t eg l o b a ls o l u t i o n sf o rc a s c a d e dr e s e r v o i r s s c h e d u l i n g u p t on o w ，t h ed i s p a t c hp r o b l e mi ss t i l la no p e nf i e l d b a s e do ng e n e t i c a l g o r i t h m s ( g a ) a n d i t e r a t i o n m e t h o d ( 2 d d p & d d d p ) ，a n o v e lm i x e d a l g o r i t h m g a & 2 d - d p & d d d pf o rd a i l yo p t i m a lh y d r o p o w e rs c h e d u l i n gi sp u tf o r w a r d t h i sm i x e d a l g o r i t h md i v i d e st h eo p t i m i z a t i o np r o c e s si n t ot w os t e p s ：s e a r c ha n di t e r a t i o ns t e p s i nt h e s e a r c hs t e p ，g ai sa p p l i e dt ot h es c h e d u l i n gp r o b l e mf o rt h en e a rg l o b a lo p t i m a ls o l u t i o n i n t h ei t e r a t i o ns t e p ，2 d - d p & d d d pi se m p l o y e dt oy i e l dt h eb e s ts o l u t i o n s i m u l a t i o no nt h e t h r e eg o r g e sc a s c a d e dp l a n t ss h o w st h a th y b r i da l g o r i t h m ss e e mb e t t e rt h a ns i m p l eo n e s i no r d e rt of u r t h e rd i s c u s s i n gt h ee f f i c i e n c yo fa l g o r i t h mp r o p o s e d ，an u m e r i c a le x p e r i m e n t u s i n gr o s e n b r o c k f u n c t i o nw i t h2 0 0 v a r i a b l e si sc o n s i d e r e d t h r o u g hc a r e f u l l ya n a l y z i n g c o m p u t a t i o n a lr e s u l t s ，w e m a k eac o n c l u s i o nt h a tt h eg a & 2 d - d p & d d d pa l g o r i t h m s u g g e s t e d i sr o b u s ta n de f f i c i e n t ( 6 ) a s ar e s e a r c hm e a n so fs c i e n c ea n d e n g i n e e r i n g ，s c i e n t i f i cc a l c u l a t i n gi sp a i dm o r e a t t e n t i o na n di se q u i v a l e n ti m p o r t a n c et ot h e o r yr e s e a r c ha n dp r a c t i c ea c t i v i t y t h e r e f o r e ， m a t h e m a t i c a lm o d e lb u i l tf o rc o m p l e xp r o b l e m sm u s tb ev e r i f i e db ys c i e n t i f i cc a l c u l a t i o n m o d e l sa n da l g o r i t h m si nt h ed i s s e r t a t i o na r ea l ls i m u l a t e ds t r i c t l y c o n c l u s i o n s a r e c o n v i n c i b l ea n dt h ep r a c t i c a le f f e c ti so u t s t a n d i n g t h ed e s i g n e ds o f t w a r ek i t sh a v eb e c o m e a p a r to f t h et h r e e g o r g e c a s c a d e dh y d r o p o w e rd s s k e y w o r d s ：i n n e r e c o n o m i c o p e r a t i o n ，s w i t c h - c o n t r o ls t r a t e g y , o b j e c t o r i e n t e d p r o g r a m m i n g ，t w o d i m e n s i o n a ld y n a m i cp r o g r a m m i n g ，d i s c r e t ed i f f e r e n t i a l d y n a m i cp r o g r a m m i n g ，g e n e t i ca l g o r i t h m s ，c a s c a d eh y d r o p o w e rs c h e d u l i n g ， d e c i s i o ns u p p o r ts y s t e m 1绪论 摘要：全面评述了各种优化方法在水电站优化运行中的应用及存在的问题，并指 出了进一步研究的方向。同时对三峡工程进行了简要介绍，阐述了梯级水库优化调度 的必要性。 1 1引言 采用系统工程、现代控制论和最优化技术，在不改变水电站现有动力设备与水工 建筑物的条件下，借助电子计算机编制的水库最优调度方案及优化调度图，结合径流 预报来满足电力系统和综合利用部门要求，指导水电站实现最佳运行，不仅可以增发 水电，提高电量效益和容量效益，而且可以提高整个电网的安全，经济运行水平，和 推进水电站及电力系统管理现代化。 目前西方国家及其他一些国家水调自动化系统比较完善，水能资源利用程度也比 较高，如欧、美等国的经济运行资料表明：与常规调度相比较，长期经济运行可增 加发电量2 o 5 5 ：短期经济运行可增加发电量1 5 5 o ：厂内经济运行可节 省燃料费1 5 5 o 。由此可见，水电站经济运行的效果是十分显著的。 此外，由于一个电网内往往有多个水电站，形成一个水电站水库群，不同规模跨 流域的水库群联合优化调度不仅可以起到库容补偿、水文补偿的作用，提高水电站群 的保证出力和保证电能，增加水电站群的工作可靠性，而且可以充分发挥水库综合利 用效益，获得比单库调度较多的经济效益。因此，开展水电站水库群联合优化调度具 有非常重要的经济和现实意义。 1 2 水库优化调度的结构与模型 水电站优化调度【2 , 3 1 ( 或经济运行) 涉及面很宽，因素众多，关系复杂，直接处理有 较大困难，为了使问题便于求解，通常根据问题的性质把抽象的总问题划分为具体子 问题，立n t ( 1 卜_ ( 4 ) 。其中每个子问题既有一定的独立性，又和其它的运行方式有一定 的联系。 ( 1 ) 从空间上划分 ( 2 ) 从时间上划分 f 厂内经济运行 l 站间经济运行 f 短期( 周，日，时) 调度 忡长期( 年，月，旬) 调度 c s ， 从径流描述上划分：f 翟翥差 f 4 )从水电站分布状况上划分 单库 霁鬓等各种形式的优化调度 混联 从系统工程理论出发，梯级水库优化调度的主要内容概述为：首先建立水库调度 数学模型，包括系统输入模型、目标函数、约束方程、优化结果输出等；其次选择最 优化技术；最后确定求解策略( 包括算法流程和软件开发等) 。 西方国家的专业文献一般认为1 9 5 5 年美国哈佛大学水资源大纲( h a r v a r dw a t e r p r o g r a m m i n g ) 标志着系统分析及优化模型在水资源规划及管理中应用研究的丌端。经 过几十年的发展，现有的水库调度数学模型很多，将其分类，一般为：短期( 或长期1 水库优化调度模型；确定性( 或随机性) 水库优化调度模型；模糊水库优化调度模型。 当选定模型的种类后，最优准则的选择至关重要，它是优化模型的核心。几种常见的 水电站最优运行的准则( 1 , 2 , 1 5 , 3 7 , 3 8 】如下： ( 1 )以国民经济效益最大或国民经济费用最小为最优准则 这个最优准则在理论上比较全面，但效益计算往往比较困难，在实际应用中尚有 一定的难度。 ( 2 ) 在满足网调负荷要求下，以梯级水电厂群总耗水量最小( 或其变形) 为最优准则 这个最优准则是国内广泛采用的准则。因为它既满足了整个电力系统的经济运行 的要求，又能节约水资源，从而提高梯级水电厂群的经济效益。 ( 3 )以梯级水电厂群总蓄能量最大为最优准则 这个最优准则由国外学者提出，并把其研究应用于智利喀邦一马奇库梯级水电厂 群实时计算机监控中，取得了很好的效益。 ( 4 ) 以梯级水电厂群发电量最大为最优准则 这个最优准则是在满足电力系统和水资源系统一定要求的前提下，使梯级水电厂 群的发电量最大。这个准则适应于孤立供电系统的梯级水电厂群。 1 3 优化技术简评 水库调度模型确定后，便可用优化技术进行求解。经过国内外学者几十年的研究 与发展提出了许多富有成效的方法，可以概括如下： 1 等微增率和协调方程法 2 线性规划( l p ) 3 非线性规划( n l p ) 4 动态规划( d p ) 5 多目标优化方法 一 6 大系统分解协调方法 7 模糊，灰色优化法 8 神经网络( a n n ) 9 遗传算法( g a ) 1 0 混沌优化法 上述算法都有其不同的特点，兹简述如下： ( 1 ) 等微增率方法是利用古典变分法原理，使目标函数f 取极小值的方法，即满 足如下两个条件：v f = 0 ，v 2 f 0 。该方法具有计算时间快、考虑了机组原先的运 行工况，避免了机组的频繁开停等优点，因而曾广泛地运用于梯级自动发电控g o ( a g c l 之中。但缺点是目标函数取极小值的充分条件不能总保证满足，此外，难以考虑梯级 各水电厂之间复杂的约束，如电厂动力特性不光滑、出力限制、梯级各水电厂之间的 水流时滞等。 ( 2 ) l p 方法作为较成熟的优化理论在水电能源系统中已有了广泛的应用。它的 基本思想是利用线性规划迭代方法求解非线性规划问题。其优点是处理高维问题的能 力强；可从任意初始解开始求解；易于处理复杂的约束条件：算法简单、计算速度快。 但由于l p 方法中目标函数和约束条件必须是线性的，而一个较为复杂的水电系统优 化运行问题其目标函数和大部分约束条件从本质上讲都是非线性的，因此必须将这些 非线性的特性应用线性处理( 例如分段线性逼近) ，然后才能使用l p 算法去进行求解。 这使l p 法在水库优化调度中的应用受到一定限制，进而影响求解的精度，误差较大， 最终影响经济效益。 ( 3 ) n l p 方法可以极严格地描述水库优化调度模型。由于水电系统优化运行问题 中的目标函数及约束条件中的水力特性等都具有非线性的特征，因此，用n l p 法去 求解此问题从理论上来说是最为合适的。n l p 法能如实反映系统非线性因素，理论上 比较严谨，但n l p 问题没有经典的解法，其求解往往是比较困难的( 特别是当约束条 件很复杂时，而梯级各水电厂之间的约束一般是很复杂的) 。最大的困难是收敛问题的 解决。为了解决此问题，常需一些辅助的方法，如变量量纲的处理，以及先用其它近 似的方法，求初始解等，这就要求建模者具有丰富运筹学、专业知识、和计算机编程 经验，稍不小心就可能出现无可行解的情况。其次是解非线性规划需要较长的机时。 ( 4 ) d p 方法在水资源领域得到了广泛的应用，被公认为是解决水库优化调度模 型的最有效的工具。其思想利用美国数学家r b e l l m a n 提出的最优性原理。它具有的 优点是：d p 法通过降维的方式求序列子问题，从而可解决高维的非线性规划问题； 对目标函数和约束条件的限制较宽，处理较方便，常能得到整体最优解，而不是局部 最优解；既能求解确定性的、离散的、线性的多段决策过程；也可用于随机的、连续 的、非线性的多段决策过程的最优化。同时，它的缺点是当求解包括两个以上的水电 站群的联合优化调度时，将遇到多库径流随机描述时复杂的时空关联，数学模型将出 现多维决策空间，导致“维数灾”的障碍，使计算难以实现。 ( 5 ) 多目标优化方法。凡有两个以上目标，各目标所反映的利益相互冲突、相互竞 争都属于多目标。其求解方法或通过权重系数或货币将多目标转化为单目标，或通过求 出各目标利益水平之问的转换关系，然后由决策者权衡各目标之重要性来选择最优方 案。通常解决此两类问题各自的处理方法有权重扰动法、约束扰动法和逐步逼近法及多 目标动态规划法。目前，多目标规划的理论及方法尚不成熟，有待于进一步发展与完善。 ( 6 ) 分解协调技术是目前解决大规模复杂问题的有效途径之一。其基本思想是先 将复杂的大系统分解为若干简单的予系统，以实现子系统局部最优化，再根据大系统的 总任务和总目标，使各子系统相互协调配合，实现全局最优化，其求解的过程是大系统 与子系统之间输入与反馈的过程。该法与一般的方法相比有简化复杂性、减小工作量、 避免维数灾等优点，求解子系统的方法较为灵活，并可用于静态和动态系统。其缺点是 收敛性差，即使收敛也需要较长的记时，对随机入流的考虑也有困难。从整体上讲，它 是一种有发展前途的大系统多目标决策技术。 ( 7 ) 水电站水库( 或水库群) 优化调度问题是一个随机动态和非线性的大系统控制 问题，尽管国内外已广泛地将各种优化技术运用于该问题，但在理论上成熟的实用模 型尚不多见。于是，模糊优化方法，神经网络方法( a n n ) ，遗传算法( g a ) 和混沌优化 方法等学科在水库( 或水库群) 优化调度问题上的应用相应提出，并在最近十几年得到 了飞速发展。这里，仅对遗传基因方法( g a ) 作一概述。g a 方法的基本思想是基于奥 地利的g r e g e r m e n d e l 提出的“自然遗传学说”与英国的d a r w i n 提出的“进化论”。它具 有简单、鲁棒性强，实现全局并行搜索，搜索空问大，并能得到最优解或准最优解等 优点。同时，由于g a 算法存在收敛速度慢、早熟和迭代次数多等缺点，阻碍了其应 用范围。 比较上述各优化模型的优缺点可发现，l p 法对系统模拟存在一定的差异；d p 法在 应用上受“维数灾”的限制需借助于其它方法进行降维处理；n l p 法往往以l p 法子模块 进行求解；多目标优化方法能较好地反映客观系统，在理论求解上仍需做迸一步研究； 大系统分解协调方法、灰色优化方法及g a 法等在应用上更具特色，实用性较强，具有 良好应用| ； 景。但是，在实际工程应用中，这些方法都有一定的局限性，尤其是对于水 库群优化调度这一复杂工程，到目前为止，还没有一种通用的方法适合于所有的系统。 1 4 动态规划法的发展与评价 自从上世纪5 0 年代美国数学家r b e l l m a n 5 2 】提出了解决多阶段过程优化问题的动 态规划法( d p ) 以来，d p 算法一直被公认为是解决水库优化调度模型的最有效的工具。 因为水库运行是一个典型的多阶段生产过程。d p 算法对于单库的计算是卓有成效的。 然而，当以系统的观点来考虑多库联合优化调度时，原始的动态规划算法出现了众所 周知的“维数灾”( c o d ) 问题( 如p u t e r m a n 1 的工作) 。 为了克服“维数灾”障碍，许多基于动态规划最优化原理的改进动态规划相继提 出。改进动态规划可分为如下几种： 1 增量动态规划( d p ) 2 离散微分动态规j i i j ( d d d p i 3 状态增量逐次近似动态规j s j ( i d p s a ) 4 随机动态规划( s d p i 5 微分动态规划( d d p ) 6 逐级优化计算( p o a 、 这些方法在一定程度上限制了“维数灾”，同时也带来了一定的局限性。 1 4 1 “维数灾”问题的处理办法 由于“维数灾”主要是由于状态离散化引起的，因此改进算法只能以此为基点，归 纳起来，主要有以下三种方法： ( 1 ) 减少状态离散点数 状态增量动态规划法( s t a t ei n c r e m e n td y n a m i cp r o g r a m m i n g ；s i d p ) 、离散微分动态 规划法( d i s c r e t ed i f f e r e n t i a ld y n a m i cp r o g r a m m i n g ；d d d p ) 、双状态动态规划法( b i n a r y s t a t ed p ：b s d p ) 等均是动态规划的一种改进方法。其总体思想是：用逐次逼近的方法 f 迭代法1 寻优，每次寻优只是在某个状态序列附近的小范围内，用动态规划法进行。 它比动态规划法能进一步减少计算工作量。 状态增量动态规划法( s i d p ) 的基本过程如下： ( a ) 选初始状态序列和决策序列； ( b ) 选增量形成廊道； f c l 在廊道范围内用常规d p 选优： ( d ) 反复迭代直至收敛。 l a r s o n 幂1 用s i d p 法求解了四库联合优化调度问题，t r o t t 和1 y e h 垤6 1 详细地描述了 s i d p 法在水库优化调度问题的应用，并指出s i d p 法特别适用于水库群优化调度问题， 在多水库情况下，s i d p 法可以这样描述：当优选第i 个水库决策( 如放水量) 时，其余水 库决策( 放水量) 保持不变。应该指出的是，l a r s o n 提出的四库联合优化调度问题已成 为许多新方法检验其是否有效的典型算例。 离散微分动态规划法是h a l l 刀1 、h e i d a r i 7 4 1 等人提出来的。基本过程为：首先假定 一个满足约束方程的初始策略，根据系统方程求得一个满足约束方程的状态序列，这 个序列称为试验轨迹，再在试验轨迹的周围形成决策廊道，通过比较选择较优的轨迹。 c h o w ”j 、n o p m o n g c o l 乖l a s k e w 1 0 2 应用并发展了这种方法。 如上所述，借助于廊道约束，s i d p 法、d d d p 法显然比常规动态规划法有着明显 的优点，即极大地减少了计算工作量。但是，由于状态向量的维数仍然处在指数的位 置上，随着维数的增加，决策比较数的增加仍然是很快的，“维数灾”问题减轻了而不 是克服了。为了进一步减少决策比较次数，o z d e n 1 0 4 1 于1 9 8 4 年提出了双状态动态规划 法，它用于求解多维动态规划问题的思想与d d d p 法基本相同，也是从一个初始试验 轨迹开始，以这个试验轨迹为基准建立状态子集，作为本次迭代的状态域，用一般动 态规划法寻求最优轨迹，再重新建立状态子集并进行择优，通过多次迭代逐步逼近最 优解，b s d p 与d d d p 的主要区别仅在于各个阶段所取的状态点数不一样，b s d p 在各 个阶段取两个状态点，而d d d p 在各个阶段则取三个以上的状态离散值。o z d e n 币l j 用 b s d p 法计算了水库群联合调度问题。 上述的方法都是基于状态增量的概念，而t u r g e o n 认为：如果s i d p 法中每时段状态 增量相同，可能会使s i d p 法的结果不是总体最优解，可能收敛某一局部最优解。为了 增加所得结果为真正的总体最优解的可能性，可采取以下方案进行： ( 曲从几个不同的初始状态序列和决策序列开始，求得几个“近似最优解”后再进 行比较。 ( b ) 采用变增量的方、法【1 2 ”，即在迭代过程中状态增量可由大逐渐变小的方法，提 高最优解的精度。 ( 2 ) 降低问题的维数 状态增量逐次近似动态规划( d pw i t hs u c c e s s i v ea p p r o x i m a t i o n s ；i d p s a ) 、聚合分 解法等均是采用降低问题维数的改进动态规划法。 状态增量逐次近似动态规划是应用b e l l m a n 的逐次渐近的概念，其思想为：将m 维 状态变量的动态规划问题分解成只有一个状态的m 个子问题，通过对各子问题的择优 并反复迭代，使多个子问题的最优解逐步收敛到原问题的最优解。g i l e s 和 w u n d e r l i c k 6 7 】等人都曾使用i d p s a 方法来研究多库系统的优化调度问题。i d p s a 方法 的优点在于：一个m 维问题的求解可以对一系列一维问题的寻优而得到，它有效地避 免了“维数灾”的发生，这是因为随状态变量的增加，计算量随维数的增加成线性关系 而不是呈指数关系。当然，同增量动态规划法一样，也不能保证在所有情况下都收敛 到真f 的总体最优解。 聚合分解法包括聚合和分解两种技术，它是先将多个水库按照某种方法聚合成一 个等效水库，求得等效水库的最优运行策略以后，再按照水库群之间的联系求解各个 水库的运行方案。a r v a n i t i d i s 和r o s i n g 4 8 l 等人曾利用该方法研究多库系统的优化调度 问题。 ( 3 ) 对状态变量不进行离散化 如微分动态规划法( d i f f e r e n t i a ld p ；d d p ) 、逐次优化法( p r o g r e s s i v eo p t i m a l i t y a l g o r i t h m ；p o a l 等。 如果目标函数是可分的且是凸的，并且系统的动态特性可以用线性等式加以描 述，那么决策值与状态变量将成线性函数或二次函数的关系。如果目标函数不是二次 的，或者系统的动态特性不能用线性表达式描述，那么可以用泰勒级数将目标函数近 似展开成二次，约束条件亦可作要相应近似线性处理。这样从每个阶段来看，恰好是 优化理论中的凸规划问题，这样可以极大地减少计算工作量。这一思想是微分动态规 划法的出发点。 d y e r 年l l m c k e y n o l d s t “】等人提出了无约束的微分动态规划法。m u r r a y 年h y a k o w i t z t 9 8 】 对这个方法扩展后应用到多水库系统，修改后的方法称为有约束的微分动态规划法， 并以四个水库的联合优化调度问题为试验对象，比较了微分动态规划法、离散微分动 7 态规划法、状态增量动态规划法的计算效果，其结果是，微分动态规划法比其它两种 方法都好。 逐次优化法是1 9 7 5 由加拿大学者h r h o w s o n 和n g s a n c h o 提出m 】，用于求解多阶 段动态规划问题的数值算法。这一方法的实质是吸收b e l l m a n 最优性原理的思想，提 出了逐步最优化原理，即“最优路线具有这样的性质，每对决策集合相对于它的初始 值和终止值来说是最优的”。具体来说，把具有n 阶段m 维问题分解成n 1 个子问题，每 个子问题的维数仍为m 维，但每个子问题只包含相邻两个阶段，实际上它是把个复 杂的多阶段决策问题化为一系列的二阶段决策问题，使原问题求解得到简化，该算法 不需要将状态空间离散化。m a r i n o $ t l l o a i c i g a 9 3 5 立片j p o a 算法计算了九个水库系统的 联合优化调度问题。在p o a 方法的基础上，文献 4 l ，4 2 】提出了- - 种s e p o a 方法，并从理 论e 证明了在一定条件下该方法将保证所得到的解( 决策) 稳定收敛于唯一的最优调度 线，文献 43 利用p o a 方法的基本原理，提出了一种求解多目标动态规划问题的逐次迭 代算法，为解决多维、多目标动态规划问题的“维数灾”提供了一个新途径。 总之，水库群优化调度模型的动态规划法的改进算法，如d p 、d d p 、p o a 等方 法能有效地避免计算中遇到的“维数灾”障碍，但这些方法不能保证得到全局最优解、 计算时间长不能满足实时调度的要求等缺陷。 1 4 2 混合算法 由于水库群优化调度模型具有复杂的非线性特点，采用任何一种优化算法都将严 重制约着问题的求解，因此往往是多种优化技术联合使用。如，h a l l 4 纠提出动态规划 与线性规划相结合的方法，把多水库优化运行问题分解为一个主问题和若干个子问 题，子问题用动态规划( d p ) 求解，用线性规划进行系统协调。b e c k e r s d y e h 5 0 5 “1 ”峙巴 线性规划与动态规划结合研究利福尼亚中心河谷的运行问题，并取得了较好的结果。 t u r g e o n 1 2 8 将随机动态规划、聚合、分解联合使用对水库群优化问题进行求解。 1 5 遗传算法的发展与评价 1 5 1 遗传算法的特点 遗传算法 1 3 , 3 3 , 4 4 , 6 9 , 9 5 完全区别于传统的优化方法，它是模仿自然界生物进化过程 中的“优胜劣汰，适者生存”的生物进化机制，并模拟人类的优生学原理，利用随机信 息交换思想，使子代不断向着优化方向发展，直到满足终止条件。由于遗传算子充分 利用了上一代性能信息，所以可使优化程度不断提高，同时它算法简单，收敛快，计 算时间仅与规模成正比，可以得到最优解或近似最优解。传统的优化方法难以做到这 一点( 除非目标函数和约束条件具有特殊的性质) 。遗传算法另一大优点是它对优化对 象无特殊要求，只使用目标函数信息，而不使用推导过程或其他辅助知识( 如函数的连 续性及可微性等) 。此外，遗传算法具有运算并行性，它可以在复杂的搜索空间内同时 评价多个点，这样有利于在复杂多值空间中寻找全局最优解。因此，遗传算法尤其适 合不确定问题或非线性复杂问题的求解。 1 5 2 遗传算法的求解步骤 在自然界中，进化过程的发生以下面四点为必要条件： ( a ) 存在可以复制自身的实体； ( b ) 存在这样一个自我复制实体的群体； ( c ) 这些自我复制的实体之间存在某些差异； ( d ) 实体在环境中的生存能力与这些差异有关。 自然界中生物体的不同归根结底是由于决定其遗传特性的染色体的不同，染色体 的差异通过生物体在环境中的结构与行为表现出来，而结构与行为的差异反过来又影 响生物体的存活与繁殖能力。那些能更好的适应环境，更好地进行生存斗争的生物以 较高的几率生存，这就是达尔文的适者生存和自然选择的观点。通过许多世代的这种 过程，群体将包括那些能更好的适应环境与竞争的个体，这样，群体的个体结构由自 然选择而发生变化，这就是我们所说的群体进化。进化是“群体在遗传组成上发生变 化的过程”。奥地利的g r e g e r m e n d e l 提出了自然遗传学说：遗传是作为一种指令遗传 码封装在每个细胞中。这种遗传码的“基因”形式包含在每个“染色体”里。每个基因有 它的特殊位置，并控制一个特殊的性质。m e n d a l 的自然遗传学说支持了d a r w i n 的进 化论，并较详细的解释了群体里的变化是如何发生的。遗传算法的思想正是基于此。 典型遗传算法的基本思路与步骤如下： 所涉及问题的可能解进行染色体( c h r o m o s o m e ) 编码； 针对问题，寻找一个客观的适应度函数( f i t n e s sf u n c t i o n ) ； 生成满足所有约束条件的初始种群( i n i t i a lp o p u l a t i o n ) ； 计算种群中每个染色体的适应度( f i t n e s ss c o r e ) ； 如果找到问题的最优解，退出循环；否则，向下进行； 根据每个染色体的适应度，产生新的种群。此操作称为选择操作( s e l e c t i o n ) ； 进行杂交操作( c r o s s o v e r ) $ 口变异( m u t a t i o n ) 操作。产生杂交操作的概率记为p c ， 产生变异操作的概率记为p 。； 返回进行计算。 1 5 3遗传算法在水库优化调度中的应用 遗传算法以强有力的搜索和优化技术并获得全局最优解或近似最优解，使得它被 广泛地应用到许多复杂的领域。例如机器学习、模式识别、图像处理、神经网络、工 业优化控制和社会科学等方面目3 1 。在