（电力系统及其自动化专业论文）基于gaalopex算法的机组优化组合的研究.pdf

声明严明 本人郑重声明：此处所提交的硕士学位论文基于g a - a l o p e x 算法的机组优化组合 的研究，是本人在华北电力大学攻读硕二匕学位期问，在导师指导下进行的研究工作和 取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得华北电力大学或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：主墅圭：日期：一塑六0 ，乙 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校有权保管、 并向有关部门送交学位论文的原件与复印件；学校可以采用影印、缩印或其它复制手 段复制并保存学位论文；学校司允许学位论文被查阅或借阅；学校可以学术交流为 目的，复制赠送和交换学位论文；同意学校可以用不同方式在不同媒体上发表、传播 学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名： 日期：叫3 - j t 导师签名：麦心舷豌 e l 期： 工。口6 、lx 华北【乜力人学硕：卜! 学位论文 第一章绪论 1 1机组优化组合问题的提出 由于电能是不能大量存储的，即电能的生产、输送、分配和使用在同一时刻完 成，发电厂在任何时刻生产的电能恰好等于该时刻用户消耗的电能( 包括输送分配 环节的损耗) ，电力系统中的功率每时每刻都保持着平衡。另外，电能也有使用灵 活、控制方便等优点，是国民经济发展的主要动力，人民的生活也离不开电能。电 能供应不足或突然停电将给国民经济造成巨大损失，给人民生活带来不便。因此， 电力系统运行的首要任务和基本目的是满足用户对供电可靠性的要求、安全地向各 类用户提供质量合格的电能。 但是由于系统中的负荷功率是时刻在变化着的。图l 。1 表示某电力系统在2 4 d 时 内的负荷曲线图，对于负荷的变化，在系统优化调度中就存在这样一个问题，即假 如h 点的负荷d 。己由某台发电机承担，那么当负荷减小到d ，时是否仍由这台 发电机承担? 能否少用几台发电机? 能否另外选定其他几台发电机来承担负荷? d | d o 图卜1 负荷曲线图 还有另外一个问题，我们都知道，发电机组所发的有功功率不同，运行效率及 燃料消耗量也不同。一般机组的最高运行效率点都在接近额定功率处，图1 2 表示出 了这种关系。若不增减或变更参加运行的机组，当系统负荷较大时，各机组的运行 效率将较高；而当系统负荷减少时各机组的运行点将降低，效率也将降低。若在系 统负荷变小的同时，减少参加运行的机组台数或更改为容量较小的发电机组，将有 可能使各运行机组维持较高的运行效率，使系统有较小的燃料消耗。例如有一个两 机系统，各机组的耗量特性示于图1 3 ，当系统负荷为d 时，若两台机组同时运行， 华北l 乜力人! 学硕j = 学位论文 则它们的出力分别为鼻、，总耗量为e4 - 垦；仅由机组1 来承担负荷d ，则总耗 量为b ，比两台机组同时运行减少了燃料消耗，对负荷d 而言仅由机组l 单独运行更 为合适。这就说明，对于给定的负荷从降低运行耗量的角度看有选择运行机组群的必要。 b e 0 b 7 7 0 图 - 2机组耗量特性与效率特性 尸0 p d 图1 - 3 两台机组耗量特性的比较 p 此外，有时还可能出现下面的情况：负荷较大时的机组组合应用于低负荷时， 各个机组的出力下限之和大于负荷，在技术上就要求一定要改变运行的机组组合。 在实际的电网运行过程中，负荷在一天中的变化范围很大，仅仅依靠改变机组的出 力而不改变机组组合将很难满足负荷变化的要求。有时即使勉强地满足了负荷变化 的要求，可是机组在高峰时出力过大而在低谷时出力过小，既不安全也不经济。所 2 华北电力火学硕二卜学位论文 以，电力系统e 常运行时要随负荷的变化而启停机组。 全面的考虑和确定运行机组的问题还应分析与机组启停有关的一些重要因素， 其中的三个主要因素是： ( 1 ) 机组不能频繁启停。在火电厂中通常把配套的锅炉、汽轮机和发电机组成 的联合体称为机组。机组的启停要由锅炉和汽轮机的启停来实现。一般来讲，锅炉 过度的频繁启停可能会引起炉管接头的损坏，而汽轮机的频繁启停又会因机轴的冷 热不均而导致机轴弯曲等问题。因此在确定与机组启停有关的问题时要考虑相应的 技术限制条件，即机组的停机和运行要分别满足最小停机时间和最小运行时间的要 求，不能频繁启停。 ( 2 ) 负荷增长速度的限制。增加发电机有功出力的速度主要是根据汽轮机的要 求来决定的。增长太快，锅炉蒸汽来不及供应，引起汽压及汽温下降，下降过甚时 使蒸汽中带有水分，水滴进入汽轮机易使汽轮机发生水冲击，损坏叶片。有功出力 增加得太快，使进入汽轮机的蒸汽量突然大量增加，汽轮机内部受热不均，各部分 的膨胀不能一致，可能引起额外震动。另外，进入汽轮机内的蒸汽突然大量增加， 在凝汽器内，使循环水来不及冷却汽轮机所排出的乏气，可能引起汽轮机的真空度 下降。因此，机组停机和运行应当满足机组的加减载约束。 ( 3 ) 机组的启动费用。机组在启动和停机过程中要额外消耗一定的燃料，停机 过程中消耗的燃料比启动过程中消耗的燃料小，一般合并到启动耗量中计算，因为 大多数机组停机后还要启动( 在研究周期内或下一周期) 。机组启动时，汽轮机系统 需要暖管，克服摩擦等。锅炉的热容量很大，从锅炉点火开始到产生蒸汽，再到给 锅炉加温、加压，一直到锅炉各部分加热到稳定状态为止要消耗相当的煤量。机组 的启动费用特性有两种模型。一种对应于机组从冷状态启动，用指数函数表示： r b ( 丁) = f o ( 1 一e 几) + e ( 卜1 ) 其中： 只( r ) ：启动耗煤量； f o ：锅炉由冷却状态启动时所需的耗煤量； 口：机组的热时间常数； r ：从停用机组开始到下次再启动所经过的小时数； f ：固定费用( 主要决定于汽机启动消耗的能量和运行人员的费用) 。 式( 卜1 ) 是在汽轮机停机、锅炉熄灭，即停机时间比较长( 大于r 小时) 的情况下采用 的。 另一种情况是在停机时间不太长( 小于f 小时) 时再启动。在这种情况下锅炉不 3 华：l 匕电力人学硕j 卜学位论文 宜熄火，而让其保留余火以防止锅炉汽轮机冷却。机组的这种状态称为 态。机组在压火状态下的启动费用用线形函数表示，即 b ( 丁) = f o 丁+ f 其中： f 。：机组压火一小时所需要的启动费用。 “压火”状 ( 1 - 2 ) 两种启动费用的特性曲线如图1 - 4 所示。由图可以看出，在停机时间比较短( 小 于r ) 时，压火是有利于经济运行的。 综上所述，合理的选定各时间段上参加运行的机组群，应综合考虑机组运行的 经济特性、技术限制和有关启停的_ 些问题，以求得在一个完整调度周期中机组的 最优运行状态，使系统在此周期上的总耗量( 或总发电成本) 最小。 0 图1 - 4机组启动耗量与停机时间的关系 1 2 研究机组优化组合的意义 机组组合问题是一个非常有趣的研究课题，因为它是每天编制调度计划首先要 解决的问题。在确定了机组的启停状态，即某个时刻运行的机组群后，根据系统的 负荷功率在运行的机组间进行有功功率的最优分配即经济调度。电力系统经济调度 的目的是在满足系统安全约束、电能质量要求的条件下尽可能提高运行的经济性。 经济调度的效益很大，根据国外资料和华北、东北等电网的实际测算，节省能源可 达总耗量的o 5 1 5 。经济调度是一个十分复杂的系统优化问题，常常分解为一 系列的子问题来分别处理。从短期发电计划来看，可分为机组组合、水、火电计划、 交换计划、燃料计划等子问题。其中机组的优化组合是编制短期发电计划首先要解 4 华北电力人学硕十学位论文 决的问题，机组组合的经济效益一般大于经济分配负荷的效益。 此外，机组组合已有6 0 多年的研究历史，但由于机组组合问题十分复杂，变 量数和约束条件又很多，是一个高维数、非凸的、漓散的、非线性的优化问题，很 难找出理论上的最优解，人们一直在积极研究并提出各种方法来解决这个问题，如： 优先顺序法、动态规划法、混合整数规划法、拉格朗日松弛法、遗传算法等。但是 各种方法都有自己的局限性。采用传统的数学优化方法经常遇到搜索方向错误、迭 代发散等问题，如果变量和约束条件大大增多，还往往会陷入所谓的“组合爆炸”。 近年来发展起来的遗传算法( g a ) 适用于解决组合优化问题以及目标函数或某些约 束条件不可微的非线性优化问题，在电力系统的优化调度、无功规划、配电系统中 电容器的最优配置、机组检修计划和故障诊断、输电系统规划和城网规划等领域得 到了广泛的应用。但是g a 算法本身爬山能力弱，容易发生早熟现象，过早收敛于 局部最优解。鉴于以上所说的解决机组组合问题的优化算法所存在的问题，我们需 要一种性能更好的算法来解决这个问题，充分利用和提高计算机的效率，得出更科 学和更优的解，提高系统运行的经济性。 1 3 本文的工作 一、基于机组优化组合的g a a l o p e x 算法的设计。 由于遗传算法在解决目标函数及其约束条件不可微的非线性优化问题上存在 的优势，同时又考虑到其传统算法自身存在的缺陷，针对机组优化组合这个复杂的 问题，尝试将a l o p e x 算法和遗传算法结合起来以弥补遗传算法容易陷入局部极 值的缺陷，同时对机组优化组合中最复杂的约束条件采用直接比较比例的方法进行 处理，完成了基于机组优化组合的g a a l o p e x 算法的设计。 二、给出了g a a l o p e x 算法的计算机流程图。 三、g a a l o p e x 算法中对传统遗传算法的改进工作： 1 在编码方式上： 传统的遗传算法一般都采用二进制编码方式，本文采用实数编码，实数编码 无需转换数制，且它表示的数范围大，精度高，还代表着明确的物理意义，有利 于优化。 2 适应度函数的确定： 。 本文的适应度函数直接取为目标函数。由于是最小化优化问题，所以个体适 应度值越小说明个体越优。 3 选择、交叉、变异方式的选取： 5 华北i 也力人! 学硕j 卜学位沦文 本文的选择方法是竞争选择，竞争的标准为直接比较比例方法中的比较准 则；交叉方式采用算术交叉；变异方式采用非均匀变异。 4 对约束条件的处理方式： 目前最广泛的处理约束条件的方法是基于罚函数的方法，但此类方法存在确 定适当的罚因子困难以及最优解依赖于罚因子的选择的缺点，所以本文采用不需 要罚因子而直接比较个体优劣的直接比较比例方法。 5 在遗传算法中嵌入a l o p e x 算法： a l o p e x 算法( a l g o r i t h mf o rp a t t e r ne x t r a c t i o n ) 用过程控制参数来控制行走 方向的概率，它利用“燥声”摆脱局部最优解，具有一定的爬坡能力。这样就解 决了遗传算法本身爬山能力差，容易陷入局部极值的缺陷。 四、对g a a l o p e x 算法的编程与算例验证。 用c + + 编程实现适合于中小电力系统和大型电力系统的g a a l o p e x 算法的计算 软件，并通过算例( 最大机组数为6 0 台) 证明了该算法的计算效率和收敛稳定性。 6 华：j 匕电力人学顶s i s ：- y - 。位论文 第二童机组优化组合的数学模型及常用求解方法 在电力系统传统的短期经济运行中，机组组合是一个重要的优化问题。合理的 开停机方案能节省一次能源，延长机组使用寿命，带来显著的经济效益。改革开放 以来，电网的调度管理工作得到了重视，技术装备水平有了很大提高，部分地区发 电量有了富余，这为机组组合的研究和应用准备了良好的现实条件。 机组组合问题是一个高维数、离散的、非线性的优化问题，很难找出理论上的 最优解，但由于它能带来显著的经济效益，人们一直在积极的研究，提出了各种方 法来解决这个问题。这些方法包括局部寻优法【引、优先顺序法【3 1 、动态规划法【制、混 合整数规划法、线性规划法【5 j 、拉格朗日松弛算法【6 j 、专家系统、神经网络、遗传 算法【7j 等等。其中局部寻优法、优先顺序法、专家系统、神经网络等算法都属于启 发式算法，没有严格的理论依据，而是靠直观的判断和实际的调度经验来寻找最优 解。动态规划法是解决多阶段决策过程的一种数学方法。混合整数规划法是变量中 既有整数又有非整数的数学规划问题，这种规划问题解决起来非常困难，常用的方 法有分支定界法、b e n d e r s 分解法等。近年来兴起的遗传算法对目标函数及约束条 件既不要求可微，也不要求连续，因而灵活性很大，为机组组合问题的解决带来了 别开生面的方法。本章首先给出了机组组合问题的定义及数学模型，在此基础上依 次具体介绍了常用的优先顺序法、动态规划法、混合整数规划法、拉格朗日松弛算 法，通过比较指出了它们的优缺点。 2 1 机组优化组合的数学模型 传统的机组组合问题( u n i tc o m m i t m e n t ，u c ) 是电力系统优化运行的一个重要 方面，也称为开停机计划，指的是：根据负荷预测，在满足系统负荷、备用容量及 启停时间等约束条件下确定一个调度周期( 通常为2 4 h ) 内各时段参加运行的机组和 各机组在运行时段的出力，使得在该周期内的总发电成本最小。 根据实际系统不同的要求，对于机组组合问题可以建立不同的模型。有的模型 为了简化，忽略了某些约束，如线路潮流约束；有的模型考虑了水火电协调问题； 另外一些模型考虑了负荷的随机性和发电机的可靠性。本文采用的是火电厂机组组 合模型，以系统各发电机组的启停状态和出力为控制变量，考虑了功率平衡约束、 旋转备用约束、最小启停时间约束和机组爬坡约束( 即：功率变化速率) 。更详细的模 型应包括线路潮流限制、分区功率平衡、机组的燃料限制和随机停运的影响等，但 本文模型中未考虑这些因素。 华北l 也力人学硕十! 学b - ? 论文 2 1 1变量 。以下是本文所用的数学模型中将用到的变量及其含义： ，：发电成本； 丁：计划的总时段数( 取2 4 ) ； ：系统中可用发电机总数； i ：第i 台机组( i = 1 、2 、) ； f ：第，时刻( t = l 、2 、t ) ； u i t ：发电机的组合状态，其值为0 ，表示停运，为1 时表示运行； 乞：第f 台发电机在，时段的输出功率； c f f ( 最) ：机组f 在时段t 出力为只时的发电成本； s ，：f 时段第f 台机组的启动成本； 砖，e ，0 ：给定常数； s 瓴( f - 1 ) ) ：第? 台机组在th 双_ l 仅- l 还t m 时的启动费用； z 印一1 ) ：第f 台机组在j l 时段连续停运的时间； d f ：时段f 的系统总负荷； 最：时段f 的系统总网损； r ：时段f 的旋转备用； m 戤：发电机组珀勺输出功率上限： 只m ：。：发电机组珀勺输出功率下限； - l ：发电机组f 在时段f 的连续运行时问； j - 。：发电机组z 在时段f 的连续停运时间； m 删：发电机组z 的最小运行时间； 蚝，：发电机组f 的最小停运时间； ：发电机组f 每分钟输出功率所允许的最大下降速度； 发电机组z 每分钟输出功率所允许的最大上升速度； & ：每一时段所延续的时间( 本文取6 0 分钟) 。 2 1 2 目标函数 机组组合问题的目标函数是总发电成本最小。 ( 1 ) 总发电成本 穴 华北电力人学硕- t - ：q - - 一能论文 总发电成本包括发电成本和启动成本。 7 l m i n f = c ，( r ) ，+ ，( 1 一( h ) ) s ， ( 2 1 ) ( 2 ) 发电成本 本文中的发电成本用下面的二次函数表示： c f ( 只) = q 劈+ 6 + q 其中a ，、b 、c ，为机组ix 电成本函数的参数。 ( 3 ) 启动成本 本文中发电机的启动成本采用下面的函数表示： s i ( z ，( ，一1 ) ) = k f + b f ( 1 一e x p ( 一z ，( ，一1 ) t f ) ) 2 1 3约束条件 ( 2 - 2 ) ( 2 3 ) ( 1 ) 功率平衡约束 所有运行机组的总发电量! 西须满足负荷的需要： n e ，= d t + r i = 1 v t = 1 ，2 ，丁( 2 - 4 ) ( 2 ) 旋转备用约束 为了保证可靠供电和良好的电能质量、维持系统的可靠性，还要提供充足 的旋转备用。所谓旋转备用是指运转中的发电设备可能发的最大功率之和与系 统总负荷之差。它主要包括全部负荷备用( 调整系统中短时的负荷波动并负担计 划额外的负荷增加而设置的备用) 和一部分事故备用( 为使电力用户在发电设备 发生偶然事故时不受严重影响、维持系统正常供电所需的备用) 。显然，从保证 可靠供电和良好的电能质量着眼，旋转备用越多越好，但从保证系统运行的经 济性着眼，旋转备用又不易过多。 n 鼻。，一d r r f = l v t = l ，2 ，t( 2 5 ) 9 华：l 匕电力人! 学硕j i 学伉论文 ( 3 ) 最小启停时间约束 由本文第一章可知机组不能频繁启停，所以机组只有在运行( 或停机) 一段时 间后才能停机( 或启动) ，即机组要满足最小启停时间约束，即要满足下面的条件： 发电机最小运行时间约束： ( ，l ，卜。一 互帼，) ( 卜。一，) 0 v t = 2 ，3 ，tv f = l ，2 ，n ( 2 6 ) 发电机最小停运时间约束： ( 忍f ，一l m d n ，) ( 一，一1 ) 0 v t = 2 ，3 ，tv i = 1 ，2 ，n ( 2 7 ) ( 4 ) 机组出力约束 每台运行的机组的出力都要在一定的范围内： 只。伯。p i l e 。、 v t = 1 ，2 ，tv i 兰1 ，2 ，n ( 2 8 ) ( 5 ) 机组爬坡约束 由于机组在单位时间内加减负荷的多少要受汽机和锅炉方面的约束，所以 发电机组还要满足下面的约束条件： 一r d i a t 一只，一i ，f a t v t = 2 ，3 ，tv i = 1 ，2 ，n ( 2 - 9 ) 2 2 解决机组优化组合的常用求解方法 2 2 1优先顺序法 优先顺序法( p r i o r i t yl i s t ，p l ) 提出较早，现在仍在研究和应用之中。它是将 系统可调度的机组按某种经济特性- 丁日1 2 a ，- 列、- - 事ii 先- 排出顺序，根据系统负荷大小按这种顺 序依次投切机组。 机组的单位耗量是随机组出力变化的每度电消耗的煤量： 10 华：i 匕电力人学硕j 卜学位论文 b 2 其中，b 表示单位时间内消耗的燃料， 点连线的斜率，见图2 1 。 0 ( 2 1 0 ) 等于耗量特性曲线上各点与各坐标原 图2 一l机组单位耗量与微增率的关系 b p 。 旯一p 睁p 机组的耗量微增率兄等于耗量曲线上各点切线的斜率： z b 九2 忑 ( 2 一1 1 ) 心 、j 机组的最小单位耗量点是过坐标原点向耗量特性曲线所作切线的切点，在这一 点上： 九3 心i n ( 2 1 2 ) 一般来说它接近于机组额定出力点。 对机组耗量特性曲线上各点计算单位耗量和微增率兄，可以得到机组的一旯 曲线，将全部可启停机组的一无曲线画在一张图上( 见图2 2 ) 。我们知道火电机组 之间应按等微增率原则分配负荷，对于同一个微增率兄( 见图2 2 中的虚线) ，让单位 耗量, u l l , j 、的机组先并列是有利的。可以按最小单位耗量m i 。排队来确, w 机组t t - y - - 列次序，这就是机组的优先顺序表。 机组优先顺序表仅给出了机组并列顺序，还不知道系统负荷变化到什么程度刁 应该并列。换句话说，针对一个具体负荷还不知道在优先顺序表上丌到哪一台机组。 可以这样试探：假设在优先顺序表一i ：j ! j l jz = 台机细可以满足某一系统负荷d ，按等微 增率原则在尼台机组之问分配负荷，并计算其总耗煤量b ；再在优先顺序表上加开 1 1 华：i 匕电力火学硕j ：学位论文 第尼+ 1 台机组，按同样的方法计算出尼+ 1 台机组的总耗煤量色“，取小者为较优的 组合。这样在优先顺序表上前后变化七，便可以得到对系统负荷d 的最优组合。实 际上，上述比较过程可以用下列简单原则来代替：以 五时，七+ 1 号机组不并列是有利的。 0 五= 常数 2 一l 2 图2 - 2 机组单位耗量与微增率允的关系曲线 用优先顺序法计算机组组合的具体步骤可以归纳为： ( 1 ) 将系统机组按可用状态分类：必开机组排在最前；可启停机组按最小单位耗量 心i 。由小到大连续排列，停用机组排到最后。由此得到优先次序表。 ( 2 ) 在优先顺序表上依次计算出前后台机组的最大出力之和及最小出力之和。 ( 3 ) 在优先顺序表上选择出能满足系统负荷( 包含备用) 要求的最小机组号尼，按等 微增率原则计算尼台机组满足此负荷的微增率以。如果以 九，继续试探尼- i - l 台机组。 ( 4 ) 重复( 1 ) ( 3 ) 步骤，计算出一天对应的组合，检查最短停机时间，将小于最短停 机时间的机组改为开机。 一 优先顺序法计算速度快，占用内存少，适用于在线确定机组运行状态。对于小 机组启停的系统，结果接近于最优组合，但对于中型和大型机组启停的系统常常找 不到最优解或次优解，但能满足一般的应用要求；此外用优先顺序法计算机组组合 问题是按时段分别进行的，难以考虑机组的启动成本。 优先顺序法既可单独使用，也可与动态规划法等方法结合使用( 参见2 2 2 动态 规划法) 。 ! p ：i ll b 力人! ! 浮硕：卜! 学位论文 2 2 2 动态规划法 动态规划法d p ( d y n a m i cp r o g r a m m i n g ，d p ) 是解决多阶段决策过程最优化的一 种数学方法，在枚举各种可能的状态组合的过程中，这种方法巧妙地摒弃了那些不 需要考虑的解。动态规划法要求所求解的问题具有明确的阶段性。此方法的细节可 参阅文献 8 。用动态规划法求解机组组合问题时，整个调度期间t 被分成若二f 个时 段，通常每个时段为1 小时，每个时段即动态规划过程中的一个阶段。各阶段的状 态即为该时段所有可能的机组启停状态组合。从初始阶段开始，从前向后计算到达 各阶段各状态的累计发电成本( 包括开停机成本和运行时的发电成本) ，再从最后阶 段累计发电成本最小的状态开始，由后向前回溯，依次记录各阶段使总的累计发电 成本最小的状态，这样就可得到最优的启停机方案。 、 我们用启动成本为常数的2 台机组、3 个时段负荷的最简单例题( 见图2 3 ) ，说明 动态规划法解决机组组合的基本过程。 d 图2 - 3 两台机组三个时段例 d 两台机组可能存在四种运行状态( 1 表示开，o 表示停) ： i 两台全开 1 ，1 ； i i 1 号机开，2 号机停 1 ，0 ； i i i 1 号机停，2 号机开 0 ，1 ； 一 两台全停 0 ，0 。 因为全停不能满足系统负荷要求，故舍弃这科，状态，下面仅研究前三种状态。 两个时段之间的联系称为转移，其成本如下： i 状态不变，即1 _ 1 ，o _ 0 ，转移成本为o ； i i 机组状态由丌转为停，即1 一，o ，转移成本为0 ； i i i 机组状态由停转为丌，即0 _ l ，转移成本等于丌机机组的启动成本( 假设l 号机组的启动成本为1 5 ，2 号机组的启动成本为2 ) ； 13 华：i 匕电力人学硕? 卜：学位论文 动态规划的决策过程分为两大步：一是f 序造表，二是逆序查表( 见图2 4 ，各框 中第一行数字表示本时段机组状态，第二行数字表示本状态的发电成本，第三行数 字表示发电成本最低的转移路径即前一时段的状态，而累计发电成本记在框外) 。 72 3 图2 4 动态规划解决机组组合原理例 这一问题的正序造表过程为： ( 1 ) 列出各时段的三种组合状态，按等微增率原则计算所有组合状态下的发电成 本，记在对应的栏中。 ( 2 ) 确定各时间段间状态转移路径。例如时段2 的状态 1 ，0 孙，可能由时段1 的 三种状态转移来，但前时段累计发电成本和启动成本不同，分别是： 由状态 1 ，1 】1 ) 来：7 + 0 = 7 ； 由状态【1 ，0 1 ) 来：5 + 0 = 5 ； 由状态 o ，1 】1 ) 来：6 + 1 5 = 7 5 ； 取成本最低的 1 ，0 1 为转移路径，记在 1 ，0 2 的栏中。将 1 ，0 1 的累计发 电成本5 j j n 上 1 ，0 ( 到 1 ，0 2 的转移成本0 ，- n 1 j h 上 1 ，0 c 2 ) 1 幂j 发电成本1 l 作为 1 4 华北l u 力歹i ：! 学硕? 卜! 学能论文 1 ，0 【2 ) 的累计发电成本，l6 记在 j ，0 ( 2 ) 的栏中。按时序对所有状态算出转移路 径和累计发电成本，并记在对应的栏中，即完成了正序造表过程。表中的内容为： 状态、发电成本、路径、转移成本和累计发电成本。 以后进入逆序查表过程： 在最后一个时段3 中寻找出全天威本最低的状态 1 ，0 ( 3 ) ，根据它记录的路径找 到前一个时段2 的状态 1 ，1 2 】，疟囊查表可返回第一时段的状态 1 ，o ( 1 1 。这样可 以得到最优开停机计划： 1 ，0 1 ) 一 1 ，1 【2 ) 一 1 ，0 ( 孙。 如果考虑机组启动成本是停机时间的函数和最小开停机时间约束，问题就复杂 化了。因为某一时段中相同的机组启停状态之中增加了不同停机时间的差别，就又 构成了许多新的状态，使状态数随时段数增加而急剧增多，形成所谓“维数灾”。 以1 0 台机组2 4 个时段的机组组合的问题为例，启动成本为常数的动态规划法的状态 数为2 1 0 2 4 ，启动成本为变数的动态规划法的状态数为2 1 0 舵4 ，而实际电力系统的 规模比它大得多。由此可以看出，考虑机组的全部组合状态和各时段之问全部转移 是根本不现实的，其计算代价远远大j ? 机组最优组合司。能得到的经济收益。 因此，应用动态规划法进行机组组合的关键在于降低计算量，而且尽可能不丢 失最优方案。 为了降低计算量，常采取一定的措施来5 艮制状念冉勺数日。首先可立即排除那些 明显不可行的组合，剩下的状态数仍然是大量的，可采用多种方法进行处理。d p s c ( d y n a m i cp r o g r a m m i n gs e q u e n t i a lc o m b i n a t i o n ) 法将动态规划法和优先顺序法相结 合，机组只能按优先顺序启停，大大减少了状态数，但可能丢失最优解或次优解。 d p t c ( d y n a m i cp r o g r a m m i n gt r u n c a t e dc o m b i n a t i o n ) 法选取优先顺序表前面一定数 目的机组的启停状态组合作为各阶段的状态，状态数增加，计算量增大，但优化效 果较好。d p s t c ( d y n a m i cp r o g r a m m i n gs e q u e n t i a lt r u n c a t e dc o m b i n a t i o n ) 法先使用 优先顺序法或d p s c 法产生一个“额定机组组合”，以该额定组合为中心在优先顺 序表中选取一定数目的机组，再使用d p t c 法求解最优解，该法计算量大，但优化 效果好。还有其它近似方法，多是将动态规划法和优先顺序法结合使用，总的目标 是在计算量与优化效果之间寻求折衷。 当考虑机组启动成本是停机时间的函数时，即使使用上述限制状态数的方法， 计算量仍然很大，必须采取简化方法。在动态规划法由前向后计算的过程中，计算 出对应于每个状态的累计启停机时问，这个累计肩停机时阃对应于到达该状态的最 优路径，动态规划法只允许那些满足最小启停机时。问约束的状态转移。累计启停机 时间也用于计算启动成本。应该注意这只是种近似计算方法，可能丢失最优解。 动态规划法另一个难于处理的问题是机缀i 爬坡速率限制，即机组功率变化速 华：忙电力人：学硕? 卜学位论文 率限制。对于某个给定的状态来说，加减载限制是前一阶段与其相连的状态的函数， 对于这个状态，相关于每个前一一阶段状态都要进行一次经济负荷分配计算，使占用 内存量和计算时间增加，因此只能通过近似方法解决。在停机的过程中，考虑机组 的爬坡速率限制也会丢失最优解。 、 动态规划法在机组组合问题中得到了广泛的应用。文献 9 将动态规划法和线性 规划法相结合，使用线性规划法解决约束条件下的负荷经济分配问题，己能考虑机 组的爬坡速率约束。文献 1 0 使用改进的方法来处理与时间有关的约束。文献 1 1 】 将动态规划法和系统分解方法结合起来；机组组合问题被分解为比较容易解决的子 问题，每个子问题用动态规划法解决。9 0 年代，动态规划法又有了一些新的进展， 如加入可靠性模型，考虑系统安全约束等。文献f l2 1 用分段法考虑了负荷的不稳定 性和机组的停机率，并考虑了水火电协调的问题。文献 13 把常规的动态规划法和 启发式的调整规则相结合，效果较好。 动态规划法有如下优点： ( 1 ) 它是一种组合优化算法，对目标函数没有特殊的要求，能求得全局最优解； ( 2 ) 结合优先顺序法等限制状态数目后，能开发出实用算法，因而在实际系统中 取得了广泛的应用。 动态规划法的缺陷是： ( 1 ) 对于机组数较多的电力系统，计算量太大，必须采用近似方法加以简化，这， 样不可避免地要丢失最优解； ( 2 ) 动态规划法要求所求解的问题具有明显的阶段性，难于考虑与时i 可有关的约 束条件和机组加减载约束； ( 3 ) 通盘考虑整个系统的问题时，使用起来不够灵活。 2 2 3混合整数规划法 混合整数规划法【1 4 1 5 】( m i x e d i n t e g e rp r o g r a m m i n g ) 是变量中既有整数又有非 整数的数学规划问题，根据除整数变量以外的其他变量的函数类型，又可分为线性 混合整数规划和非线性混合整数规划。这种规划问题解决起来十分困难，常用的方 法有分支定界( b r a n c h a n d b o u n d ) 法、b e n d e r s 分解( b e n d e r sd e c o m p o s i t i o n ) 法、 广义b e n d e r s 分解( g e n e r a l i z e db e n d e r sd e c o m p o s i t i o n ) 法等。 分支定界法的思路是形成一棵分支定界树，根节点是原问题的松弛，例如，把 整数变量用定区间上的连续变量代替。其子节点也是原问题的一系列松弛问题， 可用固定根节点问题的某些整数变量值得到，它们有不相交的解空间，这些解空间 的并集正好是根节点的解空间。每个子= 肖点又进一步分解为系列解空间不相交的 l6 华北电力火学硕二卜! 学位论文 子问题，这些子问题的解空间的并集是子节点的解空间，这个过程重复进行到树的 叶节点，其解空间是所有离散变量的穷举。由于树的一个节点的解空问是它的所有 后代节点的解空间的松弛。因此在最小化问题中，它的解或解的下界必定是它所有 后代节点的解的下界。分支定界法的关键在于，在计算的过程中，若一个节点的解 ( 或下界) 大于原问题已知的优化可行解，则其后代节点就不再考虑。这样可省去 不必要的计算过程。 、 b e n d e r s 分解法用于解决如下问题： m a x e 7 x 十厂( y ) ，a x + f ( y ) b ，x r p , y s r 9 ) ( 2 1 3 ) x ，y 其中r ，、r a 分别为p 维和印维的欧几里德空间；s 为r ，的任意子集；a 是m p 的 矩阵；( y ) 是一个标量函数；f ( y ) 是一个含有m 个分量的向量函数，都定义在s 上；b 、 c 分别为定义在r p 、r q 上的常向量。 b e n d e r s 分解法将这个问题分解为两个子问题来解决，即一个s 上的规划问题( 线 性，非线性或离散等) 和一个r ，上的线性规划问题，通过多步算法迭代求解。 广义b e n d e r s 分解法用于解决如下问题： m a x f ( x ，y ) ，g ( x ，y ) 0 ，x x 曼r py y r 9 ) ( 2 1 4 ) x ，y 其中，g 是定义在x y 垦r p r 9 上一个有力z 个分量的约束函数；y 为复杂变量， 意味着当y 暂时固定后，原问题是关于x 的简单得多的问题。 广义b e n d e r s 分解法的主要思想是应用非线性对偶理论把b e n d e r s 分解法推广至更 广泛的问题。t 混合整数规划法在机组组合问题中实用化的成果不多。这里不再獒述。 混合整数规划法的优点是： ( 1 ) 求解机组组合问题的数学模型，不需要加入过多的限制和假设。 ( 2 ) 从理论上来说能找到全局最优解。 其缺点是： ( 1 ) 方法比较复杂，不直观，对于分支定界法，为得到比较高的效率，需要精心构思 分支策略和求下界的算法，b e n d e r s 分解法和广义b e n d e r s 分解法使用也较复杂。 ( 2 ) 对于实际系统，直接使用计算量太大，必须对问题进行分解。 ( 3 ) b e n d e r s 分解法和广义b e n d e r s 分解法对目标函数的性态有一些要求。 2 2 4 拉格朗日松弛算法 拉格朗日松弛算法( l a g r a n g i a nr e l a x a t i o n ，l r ) 是解决复杂问题的一类优化算 1 7 华：i 匕l u 力人：学硕? 卜学位论文 法，它的基本思想是：许多困难的整数规划问题可看成是由一些边界约束条件联系 在一起的一系列相对容易的子问题组成，利用这个特点，把约束条件被破坏的量和 它们各自的对偶变量的乘积加在目标函数上作为惩罚项，形成拉格朗日问题。、拉格 朗日问题相对容易解决，对于最大( 小) 化问题，它的优化值是原问题优化值的上 下界。下面以最大化问题为例子说明这种方法： z = m a x c 7 xa x b ，d x e ，x o 且是整数向量 ( 2 一l5 ) 、， 其中x 是刀维向量，b ，c ，e 分别是m 维、，? 维和k 维向量，a ，d 分别为m x ，? ，k x 刀 的矩阵。 假设问题的约束条件可以分为两组，即a x b 和d x e ，并且如果去掉约束a x b 问题会变得相对容易解决。因此可以构造拉格朗日问题： z d ( u ) = 唧x c t x + u t ( b a x ) d x e ，x o l ：j ，e l 击# - 4 a ，g , ，- 向量) ( 2 - 1 6 ) 对偶变量u 的值应该通过解对偶问题z 。= 嚼n z 。( u ) l u o ) 得到。由于z 。( u ) 对h 是不可微的，通常用次梯度法来求解，从初始点i l l o 始用公式 u 。一1 = m a x 0 ，u - t k ( b - a x 。) ) ( 2 1 7 ) 迭代求解。其中幺是标量步长，掣是第k 步拉格朗日问题的优化解。 该方法在机组组合问题中的应用研究始于7 0 年代，8 0 年代逐渐得到推广，9 0 年代成为主流，有大量的理论和应用成果。拉格朗日松弛法在机组组合问题中应用时， 把所有的约束分成两类，一类是全系统的约束( 如系统负荷平衡约束和满足系统备用约 束) ，一类是可以按单台机组分解的约束( 机组发电功率约束、最小启停时间约束和爬坡 约束等) 。前一类可以写成惩罚项的形式( 即进行松弛) ，加入目标函数，形成拉格朗日 函数，拉格朗日函数可按单台机组分解成一系列的子问题，子问题一般用动态规划法求 解，对偶问题一般用次梯度法求解。 应用拉格朗日松弛算法解决机组组合问题时，这样构造拉格朗日函数： tntn l ( u ，p ，允，) = f ( u ，p ) + 旯( d f + 昂一最) + z ， ( d ，+ r ) 一，p 眦。 t = l i - i t = l i = 1 ( 2 1 8 ) 式中f ( u ，p ) 为机组组合问题的目标函数，见式( 2 1 ) ；兄、，z 、t = 1 ，2 ，t 分别为 约束条件( 1 ) 、( 2 ) 的拉格朗日乘子。 i3 华北l 也力人学硕： ：学位论文 原问题的对偶问题是： 其中， q + = m a x q ( 2 ，) q ( 2 ，2 ) = r a i nl ( u ，尸，旯；- 1 ) ( 2 1 9 ) ( 2 2 0 ) 对偶问题的求解方法是交错求解上层主问题( 2 17 ) f i n 下层子问题( 2 18 ) ： ( 1 ) 对于式( 2 1 9 ) ，选定见，使g ( 旯，_ t ) 的值最大； ( 2 ) 对于式( 2 2 0 ) ，假设旯，是固定不变的，确定u ，尸使l ( u ，p ，五，) 的值 最小，由l ( u ，p ，旯，t ) 的表达式可以得出： 7 t n l ( u ，p ，1 , ，) = r ，i v , ，+ 0 - u ，( f - 1 ) ) & 】+ ( d ，+ c ，一u 打b ) ，= l，= i，- i仁l tn + a f ( d ，+ r t ) - 只。 = 喜 喜c g i ( t - i ) + o - u 坶，- 2 7 p ! 一# m 、， = c i ：f ) s ， 7 一、 ，= l【r - lj 7 + 叫( d ，+ 昂) + ( d l - 十r ，) ( 2 - 2 1 ) 7 式( 2 2 1 ) 中，表达式 允( d ，+ r ) + ( d ，+ r ，) 为定值，由于约束( 3 ) 、( 4 ) 、( 5 ) 都 是机组自身的约束，而与其他机组的状态没有关系，因此表达式 7 c i ，+ ( 1 - u i t _ 1 ) ) s - 2 e 一p m 舣】可以由各机组独立计算。这样求解拉格朗日函 数的最小值就可以分解为n 台机组的子优化问题： ，以舻n i i t m i n l ( u p e m i c ，+ ( t - g 溉- 2 7pit-tli=l ) ，咒，) = n ， ( ，) s ， 7 只m 。、” lf =j 7 1 + 允( d ，+ 咒) + ( d ，+ 墨) ( 2 - 2 2 ) 每个子优化问题对应于各机组的状态优化，这样大大降低了计算规模，可以由 19 华北电力人学硕j 卜学位沦文 动态规划法解决。这里，旯7 、1 的调整方法是拉格朗f i 松弛算法的关键所在。一般 可采用梯度法、启发式方法等。 将最终得到的对偶问题的最优解j 耐i h - 入式( 2 1 ) ，可计算得到原目标函数f 的值， 它与由式( 2 2 0 ) 计算得到的g 值并不相同，即存在对偶问隙( d u a l i t yg a p ) ，对偶间隙万 定义为： 扣钎 ( 2 - 2 3 ) 通常以对偶间隙作为算法收敛的判断依据。 该算法有以下优点：随着机组数的增加，计算量近似线性增长，克服了维数障碍， 且机组数目越多，计算效果越好；方法十分灵活，不但可以解决机组组合问题，也可以 推广到水火电联合经济调度问题和电力交易问题；算法的一些因子具有实际的物理意 义，如与系统负荷约束相关的拉格朗日乘子即等于系统边际发电成本。 但是，该算法也有一些缺点：由于目标函数的非凸性，用对偶法求解时，存在对偶 问隙，需要根据对偶问题的优化解采取一定的措施构造原问题的优化可行解，这是拉格 朗日松弛法的一个难点：算法的迭代过程中有可能出现震荡或奇异现象，需要采取措施 加速收敛；考虑某些约束条件( 如机组爬坡速率) 会使计算复杂化。 2 3本章小结 机组优化组合是编制短期发电计划首先要解决的问题，由于问题十分复杂，很 难找出理论上的最优解。机组组合优化问题早在3 0 年代就己提出，5 0 年代以后，由 于优化理论的快速发展和计算机技术的进步，极大地推动了对该问题的研究，已出 现多种计算方法。本章先介绍了机组优化组合问题的数学模型，然后具体介绍了从 6 0 年代起该问题的主要解法：优先顺序法、动态规划法、拉格朗日松弛算法，并比 较了各种方法的优缺点。 2 0 华北电力人! 学硕? 卜! 学位论文 第三章机组优化组合的g a a l o p e x 算法 本章主要讲述遗传算法的基本原理【1 6 之0 1 、特点和不足以及g a a l o p e x 算法的 提出和具体操作步骤。 、 3 1遗传算法 3 1 1遗传算法的基本原理 七十年代中期，美国m i c h i g a n 大学的j h o l l a n d 教授首先提出了一种模拟自然 界的遗传选择和适者生存的生物进化过程的计算模型一遗传算法( g e n e t i c a i g o r i t h m g a ) 。遗传算法是一种随机化搜索、便于计算机实现的全局优化算法。 其机理是根据达尔文的进化论，物种进化遵循“适者生存，不适者淘汰”的自然选 择法则，即自然界生物进化过程中，由于环境的限制，只有适应性强的个体 ( i n d i v i d u a l ) 可以生存下来，并将其优势特性遗传到下代，经过这样代代优选， 存留下来的个体具备更强的适应性，使整个种群( p o p u l a t i o n ) 不断优化并最终找到 最优个体，即问题的全局最优解。 对多变量问题，可以将各变量的初始解编码组合在一起表示成具有固定结构的 码串，称为染色体( c h r o m o s o m e ) ，它可以是一组变