（水利水电工程专业论文）水电站厂内经济运行的策略研究.pdf

华中科技大学硕士学位论文 摘要 f 科学、工程、经济和社会等领域中经常存在许多优化问题。这些问题经常是 类带有约束条件的优化问题，而其中带有非线性约束问题又占有很大的比例。 水电站厂内经济运行问题正是这样一个典型的多约束非线性优化问题，它主 要包括两个方面：机组间负荷分配问题和机组组合优化问题。其中，机组间负荷 分配问题是一个多约束条件的连续参数非线性优化问题，而机组组合问题则是一 、j ， ， 个离散的、非线性的、混合整数优化问题。；本文作耆在总结了优化问题的常用解 “ 决方法的基础上，对水电站经济运行这一典型优化问题作了进步探讨。弓文拳较 t 为详细地介绍了动态规划法和遗传算法针对这一问题的解决方案。 全文主要内容如下：第一章主要介绍了水电站经济运行的主要内容及其目的 和意义。第二章概要介绍了最优化理论及其优化方法，并着重介绍了等微增率法 和动态规划法这两种方法在水电站厂内经济运行中的应用原理。第三章详细介绍 了一种启发式的随机搜索方法一一遗传算法。第四章分别采用动态规划法和最优 个体保留的浮点遗传算法解决厂内经济运行问题中的机组间负荷优化问题。第五 章仔细探讨了机组组合优化问题的动态规划法和遗传算法解决方案。最后在综合 比铰n 种方法件能的基石 l 卜扼要阐述了作者存这方而得到的些认识。 关键词：查蔓趱，垒堕墨箩，墨! 羔坌璺，迅堡! 垦盒，动查塑划，堡堡纂些 最优个体保留 华中科技大学硕士学位论文 a b s t r a c t t h e r ea r em a n y o p t i m iz a t i o np r o b l e m si nt h ed o m a i n so fs c ie n c e ， p r o j e c t ， e c o n o m ica n ds o c ie t y t h e s ep r o b le m s a l w a y sb e lo n g t oak in d 0 fo p t i m i z a t i o np r o b l e m w i t hc o n s t r a i n t s ，a n dm o s to ft h e ma r en o n l in e a r t h ei n t e r n a le c o n o m i co p e r a t i o n0 fh y d r o p o w e rp l a n tjsa t y p ic a l n o n l i n e a r o p t i m iz a t i o np r o b l e m i n c u d e st w o s u b j e c t s ：t h e 1 c a d o p t j m i z a t i o n b e t w e e nu n i t sa n dt h eu n i tc o m m i t m e n t t h ef o r m e risa c o n t i n u o u s ，m u lt j c o n s t r a i n t s ，n o n 一1 i n e a ro p t i m iz a t i o np r o b le ma n dt h e 1 a t t e risad is e r e t e ，m u l t i c o n s t r a i n t s ， m i x e di n t e g e r o p t i m i z a t i o n p r o b l e m b a s e do nt h es u m m a r i z a t i o no ft h ea p p r o a c h e st oo p t i m i z a t i o n p r o b l e m s ，t h ea u t h o rm a k e af u r t h e rd i s c u s st ot h eh y d r o p o w e rp l a n t i n t e r n a lo p t i m i z a t i o n a i m st os o l v et h e s es u b p r o b l e m s ，t h ed i s s e r t a t l o n p r e s e n t st w od e t a i ls c h e m e s w h i c ha d a p tt h em e t h o do f d y n a m i cp r o g r a m m i n g a n dg e n e t i ca l g o r i t h m sr e s p e c t i v e l y t h ec o n t e n to ft h i sd i s s e r t a t i o na r e1 is t e da sf o l l o w ：c h a p t e r1g i v e a no v e r a l ld e s c r i p t i o no f t h ei n t e r n a le c o n o m i c o p e r a t i o n a n di t s a t t r i b u t i o nt ot h ep o w e rp l a n t sa n dp o w e rs y s t e m i nc h a p t e r2 ，t h et h e o r y a n da p p r o a c h e so fo p t j m i z a t i o n ，e s p e c i a l l yt h ep r i n c i p l eo fe q u a li n c r e m e n t d e r iv al iv ea r i dd y n a m i cp jo g ib 1 1 l l l l i i i l g “fu i i il iu d u c c d h ic h u pl c i ：；，“a ，u m e t h o db a s e do nt h eh e u r i s t i cr a n d o ms e a r c h ， isp r e s e n t e d c h a p t e r4g i v e am a t h e m a t i cd e s c r i p t i o no ft h ep o w e rd i s p a t c hb e t w e e n u n i t s ，a n d d is c u s s e dt h eu s eo fd y n a m i cp r o g r a m m i n ga n dr e a l c o d e d g au n d e rb e s t i n d iv i d u a lp r e s e n t a t i o ns t r a t e g yi nd e t a i l t oc o m p a r et h e s et w om e t h o d ac a s ei ss t u d i e d c h a p t e r 5 g i v e t h em a t h e m a t i cm o d e lo f t h eu n i t c o m m i t m e n to fh y d r o p o w e rp l a n t ，a n d d i s c u s s e dt h e a p p l i c a t i o n o f 华中科技大学硕士学位论文 d y n a m i cp r o g r a m m i n ga n ds i g n a l c o d i n gg ao nt h es u bp r o b le md e t a i1e d t o c o m p a r et h e s et w om e t h o d s ，ac a s eisi l l u s t r a t e d f i n a l l y ，t h e1 a s tc h a p t e r g iv eas u m m a r i z et ot h ew o r ko ft h isd is s e t t a t i o na n dt h ef u r t h e rr e s e a r c h isp o i n t e do u t k e yw o r d s ：h y d r o p o w e rp l a n t ，e c o n o m i co p e r a t i o n ，l o a do p t i m a l d i s p a t c h i n g ，u n i tc o m m i t m e n t ，d y n a m i cp r o g r a 衄i n g ， g e n e t i ca 1 9 0 r i t h m ，b e s tj n d i v i d u a lp r e s e r v a t io n i n 华中科技大学硕士学位论文 1绪论 本章概要介绍了水电站经济运行的基本内容及其目的意义，最后阐述了本文 的主要研究内容和相应的课题背景。 1 1 水电站经济运行概要 水电站经济运行主要是研究水电站科学管理的优化技术和调度决策。在保证 电能生产的安全可靠、连续优质以及多目标综合利用的要求下，合理地、有效地 利用水能。它应用系统工程的理论和方法，运用电子计算机作为主要运算手段， 以达到研究系统整体最优的目的。 水电站在电力系统中的最优运行方式，按照工作周期长短的不同，有不同的 内容。为便于针对具体问题的性质建立数学模型和求解，通常划分为三种方式， 即长期运行方式、短期运行方式和厂内运行方式。每种方式有其独立性同时又互 有一定的联系。 在理论研究和分析水电站在电力系统中的运行方式时，总是把一个个电源看 成是一个个单元，认为全厂特性是按各动力设备运行工况最优化而实测得出的， 短期的平均特性又是按经济运行方式所测的参数平均值得到。在此幕础上，最后 明确长期经济运行方式，可以说是“先厂内，次短期，后长期”的关系。而在实 际制定各种经济运行方式的方案，并用于管理决策时，则是“先长期，次短期， 后厂内”的顺序。即先制定长期优化方式，把水电站规定的有限输入能源分配给 短期各时段：进而制定短期优化方式，把由长期优化方式所确定的短期可用的能 源，用负荷分配和逐时段运行状态的形式分给各电源；最后根据短期优化方式所 确定的各电站负荷，各电站分别组织厂内各台动力设备的优化运行。 华中科技大学硕士学位论文 三者互相依从和制约，构成科学的整体关系。如图1 1 【1 1 所示 带蛀 端 图卜1水电站经济运行方式 水电站厂内经济运行的基本任务是研究水电站的出力、流量和水头平衡；机 组间负荷的合理分配方案；最优的运转机组数和机组的起动、停机计划；机组的 合理调节程序和电能生产的质量控制。它其实包含了两个优化问题：空间最优化 和时间最优化问题。所谓空间最优化，是指对于某一发电任务合理地选择机组台 数、台号，并在此组合中实行机组之问的最优负荷分配：而时间最优化则是在空 间最优化的基础上，不仅考虑时段内的优化，同时计及时段之间由于负荷的变化 可能产牛的机绢丌停对整个优化的影响：机绢组合的变化会带束附加耗水和其它 以水当量计算的消耗。因此，时间最优化是全局的最优。 中小型水电站通常以定负荷或定流量两种方式运行。所谓定负荷运行方式 即电力系统在供电相对紧张和富裕这两种极端情况下，由电管部门向电站下达发 电指标，电站按该指标运行；定流量运行方式就是电力系统对电站没有具体的负 荷要求，陔电站根据自己的水量调度需要，自主发电。本文按定负荷运行方式分 2 华中科技大学硕士学位论文 别讨论空间和时间这两个最优化问题的解决力法。 1 2 水电站经济运行的意义 近些年来我国的水电和火电建设均取得了巨大成就，然而与整个国民经济的 高速发展相比还不太适应 ”。我国电力长期供不应求的局面还未根本扭转。虽然 我国河流的水能资源的总蕴藏量居世界之首，但在我国的电源结构中，水电在整 个电力中所占的比重却在不断下降。这不仅使我国丰富的水能资源不能得到相应 的开发利用，并使电力系统调峰、调频及应付紧急事故的能力大为削弱，因而严 重影响了电力系统的安全稳定运行以及电能质量和经济效益的提高。鉴于以上情 况，为缓减我国电力供需矛盾，除大力发展电力工业，特别是加快水电建设外， 还必须贯彻节约方针，加强对整个电力系统和电站的科学管理，不断提高运行管 理水平和经济效益。 水电站运行管理是对已投入运行的水电站的管理，因为水电站既是电力系统 的发电单元，又是水资源系统的组成部分，所以其运行管理既属于电力企业管理 范畴，又属于水利工程管理范畴：既有电力企业管理的特点，又具有水利工程管 理的特点。凶此，其运行管理的目标任务，一方面作为电力企业，应合理利用水 能资源，保证电力系统安全可靠、优质经济供电，最大限度的满足社会的用电要 求，4 、断j 智刀崮球利企业的经坍效益；另一方向，作为水利i 栏，碰保护相台型 使用所涉及的水资源、水域及各项水利工程设施，用尽可能少的投入，最大限度 的减免水害，增加水利，为国民经济建设和人民生活等提供有效服务，充分发挥 综合效益。 水电站经济运行是发挥水电站工程设备潜力，充分利用水能多发电的一项增 产措施，也是减少电力系统其它能源消耗的一项节能措施，是对水电站实行科学 3 华中科技大学硕士学位论文 管理的重要手段。国内外实践表明，丌展水电站经济运行可获得显著的经济效益， 一般可增加1 一3 的发电效益。承担综合利用任务的水电站，还可充分利用水资 源，获得尽可能大的综合利用效益。 1 3 水电站经济运行的国内外概况 在国外，水电站厂内经济运行开展得比较早，早在二十世纪2 0 年代左右，等 微增率方法的思想就已产生，当时人们关心的是如何在机组间经济地分配负荷。 5 0 年代，国内外都进行了不少关于水电站厂内经济运行的理论研究工作，以微增 率方法为代表的各种研究取得了不少成果，在实施方面，靠手工计算绘制的各种 图表开始在一些水电站中使用。6 0 年代后，随着计算机的使用，美国、日本、加 拿大等都取得了一些成功的例子。目前，西方发达国家的大多数水电站已经实现 了经济运行。而我国在这方面经过几十年来的努力和实践，也逐渐形成了以动态 规划法为主流的水电站经济运行有效方案，并在国内许多电站投入运行。通过国 内外学者几十年的研究与发展，目前提出了许多富有成效的方法：等微增率法、 线性规划法、非线性规划法、动态规划法等。此外，基于生物医学和进化理论的 神经网络方法、遗传基因方法，还有混沌优化方法在近十几年得到了飞速发展， 并且近几年在梯级短期优化运行这一领域有了应用。 山l 二经投入经济运行的水电站实尚：数据5 ”3 来看：湖南柘溪水电站实现k 期经 济运行，提高发电量约3 1 0 ；湖北葛洲坝二江水电站实施经济运行提高效益 1 3 ：美国石河段水电站的资料表明，实行经济运行后电站发电效率平均提高 3 。所以水电厂在实施了经济运行后，发电效益均可提高1 3 以上。由此可见， 水电站实行经济运行所取得的经济效益是十分可观的，同时，也将给水电厂设计 和运行管理水平的提高带来新的动力。 4 华中科技大学硕士学位论文 1 4 论文研究的内容 本文的研究是在与许继集团水电自动化所关于水电站厂内经济运行项目的合 作基础进行的。围绕水电站厂内经济运行问题，从理论和实际两方面研究了等微 增率法、动态规划法和遗传算法在厂内经济运行这工程实际中的应用。本文内 容如下： 1 系统的介绍了水电站厂内经济运行这一典型的非线性约束优化问题，建立 了水电站厂内经济运行的数学模型，并简要介绍了目前在这种优化问题方面的各 类寻优方法。 2 比较详细的介绍了动态规划法的寻优原理，并将它应用于水电站厂内经济 运行的空间负荷分配和机组组合这两个不同性质优化的解决。 3 介绍了遗传算法的基本概念，分析了遗传算法的内在机理，并阐述了遗传 算法的进一步改进和发展，讨论了几种遗传算法的收敛性问题。 4 讨论了遗传算法在求解水电站厂内经济运行中的应用，并提出了两种不同 编码的遗传算法分别用来解决水电站厂内负荷分配和机组组合优化这两个问题。 5 最后对上述方法作了系统的比较，阐述了作者在水电站厂内经济运行这一 优化问题解决过程中形成的一些认识。 5 华中科技大学硕士学位论文 2 厂内经济运行原理 在工程技术、经济、科学和社会等许多领域，存在着各种形式的整体优化问 题，物理上表示为费用、时间、风险的整体极小化，以及质量、利润和效益的整 体极大化。而水电站厂内经济运行就属于这样一类典型的优化问题。 2 1 最优化问题 最优化问题的研究是数学的一个重要分支，它主要讨论在众多的方案中什么 样的方案最优以及怎样找出最优方案。依据优化问题的目标数可以分为单目标优 化和多目标优化问题。 2 1 1 单目标优化问题 一般地，最优化问题由目标问题和约束条件两部分构成： m i n i m i z e f ( x ) = f ( x l ，屯，x 。) ( 2 - 1 ) s u b j e c t t o x = ( z i ，x 2 ，x 。) s 亡x ( 2 2 ) 将满足所有约束条件的解空间s 称为可行域，可行域中的解称为可行解；将 可行域中使目标函数最小的解称为最优解。对于最大化问题，可以将目标函数乘 以( 一1 ) ，转化为最小化问题求解。 当z = r ”时( n 元实空间) ，目标函数和约束条件均为线性表达式，最优化 问题称为线性规划问题；否则称之为非线性规划问题。线性规划问题对应于单纯 形法和对偶理论求解。当目标函数f ( x ) 为二次函数、约束条件全部为线性表达式 时称为二次规划，可以找到类似于线性规划的在有限步搜索的优化方法。当目标 函数， ( x ) 为凸函数、可行域为凸空间时，该优化问题称为凸规划，依据连续性和 6 华中科技大学硕士学位论文 可微性的假设，有最小平方和法、最速下降法以及牛顿法等经典无约束方法。对 于非凸规划问题，虽然可以应用互补转轴理论的推广，但一直没有非常有效的最 优化方法，在一定程度上，随机搜索方法是最好的。 当x 和s 为离散集合构成的解空问时，这类虽优化问题称为组合最优化。它 的研究对象是有限集合上定义的函数在各种条件下的极值问题。从理论上说，这 类问题若有解，总是可以用枚举方法找到。这意味着以枚举为基础发展起来的分 技定界法具有普遍适应性。但实际上对于大规模的问题，分枝定界法通常是不能 使用的，该方法的计算时间一般为输入数据量的指数函数，计算时间会迅速增加 到现代计算工具难以承受的地步。根据计算复杂性的理论，计算时间作为输入数 据量的函数应该有一个多项式作为上界，这样的算法称为多项式时间算法，简称 有效算法。一个多项式时间算法问题被称作可解问题，又叫p 问题。组合优化问 题中的多数问题属于一类不知道是否为p 问题的问题，其中，包括所谓的n p 完全 问题。 对于n p 完全问题，没有准确的多项式时间算法，比较现实的妥协方法是采用 多项式时间近似算法。近似算法分为启发式方法和随机方法两种。启发式搜索运 用启发信息，应用某些经验或规则来重新排列o p e n 表中的节点的顺序，使搜索沿 着某个被认为最有希望的前沿区段扩展。启发式方法较多地依赖于对问题构造和 1 峰质的认识和经验适用丁解决不太复杂的问题。随机方法不依赖于问题的性质 从解窄间中随机地选择多个解，检查这些解的可行性，在可行集选择目标函数最 小的解作为最优解。这种方法的算法简单明了，但因为需要检查相当多的可行解 集，计算非常耗时，尤其对于大范围的搜索，很有可能遗漏最优解。 从总体上说，单目标优化问题的优化方法可归纳为如下四类：基于微分的搜 索技术、随机搜索技术、启发式搜索技术和枚举技术口”。 传统的基于微分的方法，包括直接法( 如单纯形法、爬山法) 和问接法( 如 7 华中科技大学硕士学位论文 最速下降法、牛顿法) ，对问题性质有较高的要求，或者足针对特定问题形式而设 计，一般统称为强方法。枚举方法是一种解空间的搜索方法，包括动态规划法、 隐枚举法和完全维数法等，其特点是可以发现问题的全局最优解，但是可能存在 计算效率低的问题( 存在着维数灾数) ，不适用于大型优化问题求解。随机搜索方 法在问题空间中随着选择一定数量的点，然后从中选优，带有一定的盲目性，对 于复杂问题不能保证解的质量，而且其计算效率与枚举方法基本等价。启发式随 机搜索方法( r h s ) 一般统称为弱方法，是目前关于复杂优化问题求解的一类有效 方法，不需要或需要很少的关于问题的先验信息。该类算法具有很强的鲁棒性， 即能适应不同领域的优化问题求解，并在导数情况下都能得到比较满意的解。 2 1 2 多目标优化问题 工程中经常会遇到在多准则和多设计目标下设计和决策的问题，如果这些目 标是相背的，需要找到满足这些目标的最佳设计方案。解决含多目标和多约束的 优化问题，即多目标优化( m o ) ，通常的作法是根据某效用函数将多目标问题合成 单目标来进行优化。但在绝大多数情况下，在优化之前这种效用函数是难以确知 的。这样为了使决策者深入掌握优化问题的特点，有必要提供多个解以便于作出 合理的最终选择。 法国经济学家v p a r e t o 最早研究经济领域的多月标优化问题，他的理论被称 为p a r e t o 最优性理论。对于m o 问题，用求单目标优化方法求最优解，获得所谓 理想解往往在可行域值之外。m o 问题需要优化一组费用函数，其解不是单一点， 而是一组点的集合，称为p a r e t o 最优集1 2 9 1 。 常规m o 求解方法优多目标加权法、层次优先法、占一约束法、全局准则法、 目标规划法等，其中以目标规划法最为著名。这些方法的特点是将多目标转为单 目标处理，往往只能得到一个解。除了预先获知目标函数最优值的情况外，不能 8 华中科技大学硕士学位论文 保证p a r o l o 最优性，即使最优化求解很成功。遗传算法通过代表整个解集的种群 进化，以内在并行的方式搜索多个非劣解，决策者可以在多个解中选择决策方案， 它已经成为m o 问题的研究热点。 2 1 3 优化问题中约束条件的处理 实际所遇到的优化问题的绝大部分是带有约束条件的，所差者往往是约束的 强弱不同而已。目前，在最优化理论与方法的研究中，约束最优化问题的常规解 法可以分为两种途径【3 1 1 ：一种是把有约束问题化为无约束闯题，再用无约束问题 的方法去解；另一种是改进无约束问题的方法，使之能用于有约束的情况。第一 种途径主要是采用c o u r a n 提出的罚函数法。罚函数在实践中使用比较广泛，其要 点是把问题的约束函数以某种形式归并到目标函数上去，使整个问题变为无约束 问题。这种方法对于非线性的约束，设计的算法常常因为迭代点要沿复杂的可行 区域边界移动而花费大量的计算而导致失败。罚函数法根据解序列相对于原问题 的可行性分为外部罚函数法和内部罚函数法。罚函数法的更近发展是乘子法或 l a g r a n g e 法，以及投影l a g r a n g e 法。约束最优化问题的第二种途径发展较晚，2 0 世纪6 0 年代r o s e n 对于带线性约束问题提出了著名的梯度投影算法。这类算法可 以看成是无约束问题中最速下降法在含约束问题上的推广，其基本思想是把负梯 度方向投影到可行方向集的一个子集上，取投影为可行下降方向。简约梯度法| 1 5 j 推广到非线性约束的情况，成为广义简约梯度法。 2 1 4 水电站厂内经济运行 水电站厂内经济运行是一类典型的单目标优化问题，本文以水电站在给定发 电负荷下耗流量最小作为最优化目标来探讨这一问题。正如上一章所述，它包含 了两个子优化问题：机组负荷分配优化问题和机组组合优化问题。 9 华中科技大学硕士学位论文 机组负荷分配问题要求根据水电站给定水头下的各台可供发电的机组出力 与流量之间的特性曲线，得到这些机组在各种负荷下分别要承担的出力状况，并 保证在这负荷要求下，这种分配方案耗流量最少。由于这个过程中所依据的机 组特性曲线是非线性的，因此这是一个非线性的优化问题。它还必须满足下述约 束： 1 分配在各台机组上的出力应该在相应机组的最小出力和最大出力限制范围 之内。 2 在各台机组的最小出力和最大出力之间还存在汽蚀、振动区，在机组负荷 分配时，必须加以规避，以延长机组的使用寿命。 3 水电站所要承担的负荷应该在整个电站的出力范围之内，同时还应保证各 台机组的总出力与该负荷相等。 可见，这是一个多约束条件的非线性优化问题，论文第四章给出了具体的数 学模型和寻优方法。 机组组合优化问题则是根据上级调度部门给出的水电站日负荷曲线，安排水 电站内某一运行周期内的机组开停组合。在机组组合问题中，包含有大量的o l 变量和离散变量，在数学上表现为一个包含大量约束条件的大规模非线性混合整 数规划问题。它需要满足以下的约束条件： 1 负荷备用要求。，由于水申】站的机动件较好，冈此存电力系统中一般都要承 担系统的备用要求，以保证在电力系统出现事故或突发事件时能够迅速满足系统 的负荷需要，因此，在实行机组组合优化时，必须保证目前处于运行状态的机组 能够应付负荷备用的要求。 2 最小丌机时间和最小停机时问。机组频繁的起停会对机组造成损坏，为了 避免机组的频繁起停，水电站要设定机组的最小开机时间和最小停机时问，从而 限定各台机组在一个调度时段内的开停机次数。 1 0 华中科技大学硕士学位论文 = = = # = = = = = = ；= = = = = = = ；= = = = = = = = ：= = ：= = 3 机组爬坡速率( 功率变化速率) 。在电力系统中水轮发电机组及水电的机 动性在电力系统中是最好的，一般来说机纽自停运状态起动至带满负荷一般仅经 历3 - 5 m i n ，而停机过程则更短。因此，在单纯的水电站厂内经济运行中可以不考 虑机组爬坡速率。 本文第5 章给出了它的具体数学模型和机组组合优化策略的详细介绍。 2 2 厂内经济运行传统方法的介绍 几十年来，有关学者在水电站经济运行作了大量的研究工作，提出了多种经 济运行的优化方法。在我国现已开展经济运行项目的水电站中，大多数都采用了 传统的等微增率法和动态规划法，下面对这两种方法的原理作一介绍。 2 2 1 等微增率法 早在本世纪二十年代左右，人们就尝试用等微增率方法来解决水电站厂内经 济运行，当时人们关心的是如何在机组间经济地分配负荷5 ”。 水电站的负荷分配问题其实也就是一个通过多元函数求取极值条件的问题， 假设给定各机组i 流量特性曲线为 对于条件极值问题 q ，= 9 ( ，)( 2 - 3 ) m i n q = q ( ，) s = ， n ，。n 。 利用常用的拉格朗日乘子法，构造一个辅助函数 ( 2 - 4 ) ( 2 5 ) ( 2 - 6 ) 华中科技大学硕士学位论文 零 f = q 】+ q 2 + + g + 五+ ( l + 2 + + ，一 ，) ( 2 7 ) 对上式求无条件极值的必要条件：即令其对各变量，v ，。的偏倒数为 即有 笪：塑+ 五：o a n 8 n 塑：丝一一监：一五 ( 2 9 1 a n la n 2 a n 。 这就是水电站厂内经济运行等微增率法的等微增率原则，但这只是实现水电 站”台机组之间负荷优化分配的必要条件。 要在水电站经济运行中使用等微增率法，还必须保证下面的充分条件得以满 足： v 钒纂 o ( 2 - 1 0 ) 式中：q ，一机组工作流量；一机组出力a 这条件要求机组的流量微增率随机组出力的增加而增加。 当流量微增率不随机组出力的增加而增大时，则应将机组的特性曲线进行修 正后才能按等微增率法分配负荷。若修正误差较大，则不能采用这种方法。这就 使得等微增率法的应用受到限制。 2 3 2 动态规划法 动态规划是一种枚举搜索方法，是解决多阶段决策过程最优化问题的主要方 1 2 8 o o = j i 兄 兄 + + 秘一鹏娥一巩 一一 | i 堡眺望眠 华中科技大学硕士学位论文 法。动态规划法不像线性规划或非线性规划那样有个标准的表达式，而是对一 个具体问题就有一个数学表达式，它依据问题本身的特性，利用灵活的数学机理 来处理。 2 3 2 1 无后效多阶段决策问题 一类实际问题的优化决策和一个过程相应，并且这个过程可以分为若干个互 相联系的阶段，而在它的每个阶段都要做出决策，从而使整个过程达到最好效果。 由于每个阶段的决策选择都要考虑过程的过去情况和决策对以后过程的影响，这 样的过程便称为多阶段决策问题。 在多阶段决策问题中，很多问题的阶段可按时间划分。决策时使状态随着时 间变化而具有动态含义( 动态问题) ，但阶段的划分可以不按时间，因为有些问题 中并没有时间因素( 静态问题) ，不过只要把问题的阶段设想为“时间”，也就有 了动态意义。 动态规划是求解无后效多阶段决策问题的一种方法。所谓无后效性( 亦称马尔 可夫性) ，是指如下的两个条件川。 ( 1 ) 若状态方程式为 x 女“= g i ( z ，“) = 1 , 2 ， ( 2 一1 1 ) l 2 j 存在目标函数族k ：1 , 2 j = ，( x ，“女；x + l ，“女+ l ；) d = 妒女( x ，甜，j i “) ( 2 1 2 ) a 仇a z , “2 0 k = 1 , 2 ，i d 。表示从第k 阶段到最终阶段的目标函数，a 吼a o 表示d “对j t 的 单调关系。这两个条件是分别对状态方程和目标函数而言的：前者是指也+ 。仅决 1 3 华中科技大学硕士学位论文 定于状态x * 和决策“。，而与过程以前的情况z 。，一，；x 。，“。；x ，“，无关 后者是指可以把原目标函数扩展为一族目标函数且目标值问具有单调的递推关 系。满足前一条件的称为状态无后效性，满足后一条件的称为目标无后效性。 无后效性是使用动态规划法的前提条件，检查问题的无后效性是正确使用动 态规划方法的关键。所以除了一些明显满足无后效性条件的问题外，都应注意无 后效性的检查。 2 3 2 2 动态规划法的递推算法 动态规划的递推过程是建立在贝尔曼最优化原理【7 】的基础上的。最优化原理 认为：“最优策略具有这样的特性：不论初始状态合初始决策如何，相对于先前诸 决策所形成的状态而言，剩下的诸决策必须构成余下过程的最优策略”，简言之， 一个最优策略的子策略总是最优的【1 】o 进一步的验证表明，最优化原理适用的正是无后效多阶段决策问题。 依据最优化原理，对动态规划的基本方程 ( ) 2 骝丸 ( x k , u k ，f k + k = 1 ，2 ，i l z + ，( z 。) = 0 首先令= ”，得 ，( 矗) = m 哂丸( ，0 ) “h e 厶 ( 瓯( x k ，) ) ) 】 ( 2 - 1 3 ) 此时只有”，是未知的，对不同的x 。进行优化计算( 求“。) 后可得 六2 ( x 。) ，“。2 “。( x 。) 接下来，令k = 一1 ，得 ( 2 - 1 4 ) ( 2 一1 5 ) 1 4 华中科技大学硕士学位论文 ( x 。1 ) = 哩坤九一1 ( x 。i ，“。1 ，：，( g 。( x 。1 ，“。1 ) ) ) ( 2 1 6 ) l ， i 对于不同得r 。，进行优选“。的优化计算后得 ，h 。 一l ( x ) ，“。i = h ，l ( x 。1 ) ( 2 一1 7 ) 依此类推，令k = 一2 ， 一3 ，2 ，1 进行优化计算并将结果写出得 “3u t ( 以) ( 2 1 8 ) 当己知初始状态为x 。时，利用最优决策函数虬= “。( 以) ，k = 1 , 2 ，z 求出最 优策略为：“? = “。( 一) ，x ：0 = g 。( 一，“? ) ，“：= u 2 ( x ；) ，直到得出z ：= g 。( x 。，“曼，) “：= u n ( 锑) 。其逐次求出的策略 “? ，“：0 ，蚝0 卅：) 即为最优策略，而最优策略相应 的状态序列“，z ；，z ；，x ： 即为最优状态序列，整个过程的最优目标值为 从上述求解过程可见，动态规划能够把多变量的复杂问题进行分阶段的决策， 变成多个较简单的问题( 一般是单变量的) 故而十分方便和有效。从这个意义来 说，动态规划方法不同于通常的算法，相对于各类非线性规划算法而言，它是一 种分解技术? 由于动态规划法要求的条件少，对状态方程和目标函数的解析性质不需要作 任何假定，对约束条件的处理也较容易且能得出问题的全局最优解，因此在优化 问题的求解中被经常采用。 1 5 华中科技大学硕士学位论文 = = = = = = = ；= = = = = = = = = = = = = = = = = = = = = = = 一：= = 3 遗传算法 遗传算法( g a ) 是一种采用群体搜索技术的启发式随机搜索，它具有高度鲁棒 性与并行性，在许多问题上取得了较好的效果。由于它对函数的性质几乎不做要 求，因此具有很广泛的适应性。目前，在水电站厂内经济运行方面，人们开始考 虑采用遗传算法来解决这问题。 3 1 遗传算法概况 3 1 1 遗传算法的发展 早在二十世纪五六十年代，就有计算机科学家进行了所谓的“人工进化系统” 研究，其出发点是进化的思想可以发展成为许多工程问题的优化工具。这些早期 的研究形成了遗传算法的雏形，如大多数系统都遵行“适者生存”的仿自然法则， 有些系统采用了基于种群的设计方案，并且加入了自然选择和变异操作，还有一 些系统对生物染色体编码进行了抽象处理，应用二进制编码。但由于在当时这些 算法只依赖变异而非交叉来产生新的基因结构，收效甚微。 美国m i c h i g a n 大学j o h nh o l l a n d 2 8 1 在a s f r a s e r 和h j b r e m e r m a n 等人 工作的基础上提出了位串编码技术。这种编码既适用于变异操作，又适用于交叉 操作，并且强调将交义作为主要的遗传操作。h o l a n d 将该算法用于自然利人上 系统的自适应行为的研究。1 9 7 5 年他出版的专著自然与人工系统中的适应性行 为( a d a p t i v ei nn a t u r a la n da r t i f i c i a ls y s t e m s ) 一书系统地阐述了遗传 算法的基本理论和方法，提出了对遗传算法的理论发展极为重要的模式理论，其 中首次确认了选择、交叉和变异等遗传算子，以及遗传算法的隐并行性，推动了 遗传算法的研究热潮。随后，d ej o n g 、g o l d b e r g 、m i c h a l e w i c z 等人的研究工 1 6 华中科技大学硕士学位论文 作对遗传算法的广泛应用和研究起到了推波助澜的作用。 二十余年来，遗传算法的应用范围不断扩展，这主要依赖于遗传算法本身的 逐渐成熟。近年来，许多遗传算法的研究与h o l1 a n d 当初提出的算法已少有雷同， 不同的遗传基因表达方式，不同的交叉和变异算子，特殊算子的引用，以及不同 的再生和选择方法，然而这些改进方法的根本思想都源于大自然的生物进化。 我国有关遗传算法的研究，从二十世纪9 0 年代以来一直处于不断上升的时 期，特别是近年来，遗传算法的应用在许多领域取得了令人瞩目的成果。遗传算 法相关文章的发表和书籍的出版呈上升趋势，该类研究获得的经费资助比例也在 逐年增大3 1 1 。 3 1 2 遗传算法的基本思想 遗传算法仿效基于自然选择的生物进化，是一种仿生物进化过程的随机方法。 它是从代表问题可能潜在解集的一个种群开始的，种群中的每个个体实际上是染 色体带有特征的实体。染色体作为遗传物质的主要载体，即多个基因的集合，其 内部表现是某种基因的组合。因此，遗传算法一开始需要实现从表现型到基因型 的映射，即编码工作。由于仿照基因编码的工作很复杂，常常采用二进制编码进 行简化。初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代地演化产生 卅越来越好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并 进行交叉和变异，产生出代表新解集的种群。这个过程将导致种群像自然进化一 样后生代种群比前代更加适应于环境，末代种群中的最优个体经过解码，作为问 题的近似最优解。 遗传算法采纳了自然进化模型，如选择、交叉、变异、迁移等。随机产生初 始种群，并计算每个个体的适应度，如果不满足优化准则，开始产生新一代的计 算。为了产生下一代，按照适应度选择个体，父代要求基因重组( 交叉) 而产生子 1 7 华中科技大学硕士学位论文 代，所有的子代按照一定概率变异，然后子代的适应度又被重新计算，并取代父 代构成新的一代。这一过程循环执行，直到满足优化准则为止。 3 1 3 遗传算法的特点 遗传算法不同于传统的搜索和优化方法。它是一种能以有限的代价来解决搜 索和优化问题的通用方法。它与传统方法的主要区别”】在于： 1 自组织、自适应和自学习性。应用遗传算法求解问题时，在编码方案、适 应度函数以及遗传算子确定以后，算法将利用进化过程中获得的信息自行组织搜 索。由于基于自然的选择策略为“适者生存，不适者被淘汰”，因而适应度大的 个体具有较高的生存概率，然后再通过基因重组和基因突变等遗传操作，就可能 产生更适应环境的后代。进化算法的这种自组织、自适应特征，使它同时具有能 根据环境变化来发现环境的特性和规律的能力。因此，遗传算法可以解决那些复 杂的非结构问题。 2 遗传算法的本质并行性。遗传算法按照并行方式搜索一个种群数目的点， 而不是单点。它的并行性表现在两个方面，一是遗传算法是内在并行的，即遗传 算法本身非常适合大规模并行。最简单的并行方式是让多台计算机进行独立种群 的演化计算，等到运行结束才通信比较，选取最优个体。二是遗传算法的隐含并 行性。由于遗传算法采用种群的方式组织搜索，因而可以同时搜索解守间内的彩 个区域，并相互交流信息，这种搜索方式虽然每次只执行与种群规模n 成比例的 计算，但实质上已进行了大约o ( n 3 ) 次有效搜索，这就使遗传算法能以比较少的 计算获得较大的收益。 3 遗传算法不需要求导或其它辅助知识，而只需要影响搜索方向的目标函数 和相应的适应度函数。 4 遗传算法强调概率转换规则，而不是确定转换规则。 1 8 华中科技大学硕士学位论文 5 遗传算法刘给定问题，可以产生许多潜在解，最终选择可以由使用者确定。 综上所述，遗传算法具有许多其它搜索方法所缺乏的独特优点，另一方面也 存在一些需要深入研究和有待完善的一些课题。现阶段遗传算法的研究重点应该 是基础理论的开拓与深化，以及更通用、更有效的操作技术和方法的研究上。 3 2 遗传算法的基本内容 3 2 1 遗传算法的编码方式 遗传算法求解问题时，必须在目标问题实际表示与遗传算法的染色体位串结 构之间建立联系，即确定编码和解码运算。一般来说，参数集及适应度函数是与 实际问题密切相关的，往往由用户斟酌确定。 由于遗传算法计算过程的鲁棒性，它对编码的要求并不苛刻。然而，编码的 策略或方法对于交叉和变异算子的功能和设计有很大的影响。因此，作为遗传算 法流程中的第一步的编码是遗传算法中需要认真研究的问题。近些年来，人们对 于遗传算法的研究不再局限于传统的二进制编码方式，实数编码、符号编码、二 倍染色体编码等新的编码方式也被应用于实际问题。 对于给定的优化问题，由g a 个体的表现型集合所组成的空间称为问题空间 由g a 基因型个体所组成的空间称为g a 编码空间。遗传算子在g 编码空间中对位 串个体进行操作。问题编码一般应满足以下3 个原则f 3 7 】： 1 完备性：问题空间中的所有点都能成为g a 编码空间中的点( 染色体位串) 的表现型。 2 健全性：g a 编码空间中的染色体位串必须对应问题空间中的某一潜在解。 3 非冗余性：染色体和潜在解必须一一对应。 在某些情况下，为了提高遗传算法的运行效率，允许生成包含致死基因的编 1 9 华中科技大学硕士学位论文 码位串，它们对应于优化问题的非可行解。虽然这会导致冗余或无效的搜索，但 可能有助于生成全局最优解所对应的个体，使所需要的计算量可能反而减少。 编码对于g a 的搜索效果和效率有着重要影响，有关问题还需要进行新的探索 和研究。对特定的优化问题，如何确定合适的编码，l a w r e n c ed a y is 等学者极力 主张采用的编码对问题来讲应该是最自然的，并可据此设计能够处理该编码的遗 传算子。本文所提出的两种遗传算法正是作者从这种思想出发所作的有益尝试。 3 2 2 遗传算法的适应度函数 遗传算法在进化搜索中基本不利用外部信息，仅以适应度函数为依据，利用 种群中每个个体的适应度值来进行搜索。因此适应度函数的选取至关重要，直接 影响到遗传算法的收敛速度以及能否找到最优解。一般而言，适应度函数是由目 标函数变换而成的，对目标函数值域的某种映射变换称为适应度的尺度变换。 适应度函数构成了个体的生存环境。个体的适应值决定了它在此环境下的生 存能力。一般来说，好的染色体位串结构具有比较高的适应度值，具有较强的生 存能力。由于适应度函数是群体中个体生存机会选择的唯一确定性指标，所以适 应度函数的形式直接决定群体的进化行为。为了能够直接将适应函数与群体中的 个体优劣度量相联系，在遗传算法中适应值规定为非负。 计算适应度可以看成是遗传算法与优化问题之间的一个接几。遗传算法评价 一个解的好坏，不是取决于它的解的结构，而是取决于相应于该解的适应度。适 应度的计算完全取决于实际问题本身。对于有些问题，适应度可以通过一个数学 解析公式计算出来；而对于有些问题则可能不存在这样的数学解析式，它可能要 通过一系列基于规则的步骤才能求得，或者在某些情况是上述两种方法的结合。 当某些限制条件非常重要时，可在设计问题表示方法时预先满足这些限制条件， 也可以在适应度中对它们赋予特定的罚函数。 华中科技大学硕士学位论文 3 2 3 遗传算子 标准遗传算法的算子”i - - 般包括选择、交叉和变异三种基本形式，它们构成 了遗传算法具备强大搜索能力的核心，是模拟自然选择以及遗传过程中发生的繁 殖、杂交、突变现象的主要载体。