（电力系统及其自动化专业论文）社会演化算法在机组组合中的应用.pdf

一一 ! 塑：! ! 竖 _-_-_-_-_r_-_-_一 a b s t r a c t u n i tc o m m i t m e n t i s 锄i m p o r t a n ta s p e c to fo p t i m a lo p e r a t i o no fp o w e rs y s t e m s s i n c ei tc o u l dm e r ns i g n i f i c a n ta n n u a lf i n a n c i a ls a v i n g si np o w e rg e n e r a t i n gc o s t ，l t c o n t i n u e st ob et h em a i no p t i m i z a t i o nt a s ki ne v e r y d a yp o w e rg e n e r a t i o ns c b e d u l e f r o mt h ep o i n to fv i e wo fm m h e m a t i c s ，i ti san ph a r dc o m b i n a t o r i a lo p t i m i z a t i o n p r o b l e mw i t hm a n y c o n s t r a i n t sa n di ti sd i 侬c u l tt of i n dt h eo p t i m a ls o l u t i o ni nt h e o r y s e v e r a ls o l u t i o nt e c h n i q u e sh a v eb e e na p p l i e dt ot h i sp r o b l e mt of i n dag o o ds o l u t i o n i nar e a s o n a b l et i m e a so n eo ft h e s et e c h n i q u e s ，g ah a sb e e nr e c e n t l ya p p l i e dt o s o l v et h eu n i tc o m m i t m e n tp r o b l e ma n dh a sm a d es o m er e m a r k a b l ea c h i e v e m e n t s b e c a u s ei t si n i t i a lp o p u l m i o n sa r eg e n e r a t e da tr a n d o m ，i tc a n tg u a r a n t e ef e 。a s i b l e s o l u t i o n sb e c a u s eo ft h ev i o l a t i o no fc o n s t r a i n t ss b c ha sm i n i m u mu p d o w nt i m e c o n s t r a i n t i na d d i t i o n i nt h ep r o c e s s e so fc r o s s o v e ra n dm u t a t i o nt h eg e n e t i c o p e r a t o r sa r ea l s oo p e r a t e dr a n d o m l y , i t sd i f f i c u l tt og u a r a n t e es a t i s f y i n gm i n i m u m u p d o w nt i m e sc o n s t r a i n t a i it h e s ef a c t o r sr e d u c eg a sc o m p u t a t i o n a le f f i c i e n c y t h i sp a p e rp r e s e n t san e wm e t h o d s o c i a le v o l u t i o n a r yp r o g r a m m i n gt os o l v e t h e s ep r o b l e m s 1 1 1 en e wa l g o r i t h mi sb a s e do nag e n e r a ls o c i a lc o g n i t i v em o d e la n d h a sb e e ns u c c e s s f u l l ya p p l i e dt ot h eo p t i m a lp l a n n i n go fp o w e rd i s t r i b u t i o ns y s t e m 1 1 1 i sp a p e rf i r s ta n a l y z e sp e o p l e sc o g n i t i v eb e h a v i o ri ns o l v i n gu n i tc o m m i t m e n t p r o b l e m ，a n dt h e nm a k e s ad e t a i l e dd e s i g ni nc o g n i t i v ea g e n t s ，c o g n i t i v er e g u l a t i o n ， “p a r a d i g ms t u d ya n du p d a t e ”a n d b r e a k t h r o u g ho fe x i s t i n gp a r a d i g m s ”m e c h a n i s m st h e m i n i m u mu p d o w nt i m ec o n s t r a i n ti sc o n s i d e r e di nc o g n i t i v er e g u l a t i o n c o g n i t i v e a g e n t si m i t a t eh u m a nd e c i s i o n m a k i n gb e h a v i o r st oo b t a i nt h ef e a s i b l es o l u t i o n sa n d t h e “p a r a d i g ms t u d ya n du p d a t e m e c h a n i s mc a na v o i dt h ep r o d u c t i o no fn u m e r o u s i n f e a s i b l es o l u t i o n sc a u s e db yc r o s s o v e ra n dm u t a t i o n t h e r e f o r et h e p r o p o s e d a l g o r i t h m h a sa l l a d v a n t a g e i nt h e c o n v e r g e n ts t a b i l i t y a n dt h e c o m p u t a t i o n a l e f f i c i e n c y t h ep r o p o s e d a l g o r i t h mh a s b e e nt e s t e do n s y s t e m so fu pt o 10 0u n i t st o d e m o n s t r a t ei t sa d v a n t a g e s k e y w o r d s ：u n i tc o m m i t m e n t ；s o c i a le v o l u t i o n a r yp r o g r a m m i n g ；c o g n i t i v ea g e n t ； p a r a d i g ms t u d y a n d u p d a t e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究 二 作和取得的研究成果，除了文中特别加以标注和致谢之处外，论 文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 天洼大堂或其他教育机构的学位或证书而使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示了谢意。 学位论文作者签名：互黼签字日期：a 呻 年肛月t 日 学位论文版权使用授权书 本学位论文作者完全了解 鑫壅盘鲎有关保留、使用学位 论文的规定。特授权鑫洼盘堂可以将学位论文的全部或部分内 容编入有关数据库进行检索，并采用影印、缩印或扫描等复制手段 保存、汇编以供查阅和借阅。同意学校向国家有关部门或机构送交 论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位沦文作者签名：互骺导师签名 |l 管殍教 签字目期：新哆年j d 月 i 日 签字日期：a 尹年，叠月fj 日 笙二至堕笙一 1 1 机组组合问题的提出 第一耄绪论 电能与其它工业产品相比有明显不同的特点，即电能的生产、输送、分 配和使用可以说是在同一时刻完成的。发电厂在任何时刻生产的电能恰好等 于该时刻用户消耗的电能( 包括输送分配环节的损耗) ，这就是说电力系统 中的功率每时每刻都是平衡的，电能不能大量存储。另一方面，由于电能具 有使用灵活、控制方便等优点，国民经济各部门都广泛使用电能作为生产动 力，人民的生活用电也日益增加。电能供应不足或突然停电将给国民经济造 成巨大损失，给人民生活带来不便。 因此，电力系统运行的首要任务和基本目的是满足用户对供电可靠性的 要求、安全地向各类用户提供质量合格的所需功率。但是系统的负荷功率是 时刻在变化着的。图l 一1 表示出某电力系统在一个昼夜的负荷曲线图，在系 统优化调度中就存在这样个问题，即假如日点的负荷d 。已由某g 台发电 机承担，那么当负荷减小到d j 后，是否仍由这g 台发电机承担? 能否少用几 台发电机? 能否另外选定几台发电机? o 图卜1 负荷曲线图1 - 2 机组的耗量特性及效率特性 我们知道，机组运行时发电有功功率不同，运行效率及燃料消耗量也不同。 一般机组的最高运行效率点都在接近额定发电功率处，图卜2 表示出了这种关 系。若不增减或变更参加运行的机组，当系统负荷较大时，各机组的运行效率 将较高：而当系统负荷减少时各机组的运行点将降低，效率也将降低。若在系 统负荷变小的同时，减少参加运行的机组台数或更改为容量较小的发电机组， 第一章绪论 将有可能使各运行机组维持较高的运行效率，使系统有较小的燃料消耗。比如 有一个两机系统，各机组的耗量特性示于图i - 3 ，当系统负荷为d 时，若两台 机组同时运行，则它们的出力分别为p 。、p ，总耗量为蜀+ 曰：若仅由机组l 来承担负荷d ，则总耗量为e ，比两台机组同时运行减少了燃料消耗，即对 于负荷d 而言仅由机组l 单独运行更为合适。这就说明，对于给定的负荷从降 低运行耗量的角度看有选择运行机组群的必要。 图卜3 两台机组的耗量特性比较 另外，有时还可能出现这样的情况：对较大负荷安排的机组组合用于较低 负荷时，各机组出力下限之和大干负荷，这就从技术上要求人们变更运行的机 组组合。实际卜，电力系统的负荷在一天中变化范围很大时，仅改变机组出力 而不改变机组组合时，调剂机难以满足负荷变化的要求。有时即使勉强满足负 荷变化要求，但高峰负荷时机组出力过大，低谷负荷时机组出力过小，既不安 全也不经济。在一般电力系统正常运行中，一般需要随负荷的涨落而启停机组。 要全面的考虑确定运行机组的问题还应分析与机组启停有关的一些重要因 素，其r l 的三个主要因素是： ( 1 ) 机组不能频繁启停。在火电厂中通常把配套的锅炉、汽轮机和发 电机组成的联合体成为机组。机组的启停要由锅炉和汽轮机的启 停来实现。一般来讲，过度的频繁启停可能会引起炉管接头的损 坏，而汽轮机的频繁启停又会因机轴的冷热不均而导致机轴弯曲 等问题。因此在确定与机组启停有关的问题时要考虑相应的技术 限制条件，即机组的停机和运行要分别满足最小停机时间和最小 运行时间的要求，不能频繁启停。 第一章绪论 ( 2 ) ( 3 ) 负荷增长速度的限制。增加发电机有功出力的速度主要是根据汽 轮机的要求来决定的。增长太快，锅炉蒸汽来不及供应，引起气 压及气温下降，下降过甚时使蒸汽中带有水分，水滴进入汽轮机 易使汽轮机发生水冲击，损坏叶片。有功出力增加得太快，使进 入汽轮机的蒸汽量突然大量增加，汽轮机内部受热不均，各部分 的膨胀不能一致，可能引起额外震动。另外，进入汽轮机内的蒸 汽突然大量增加，在凝汽器内，使循环水来不及冷却汽轮机所排 出的乏气，可能引起汽轮机的真空度下降。因此，机组停机和运 行应当满足机组的加减载约束。 机组在启动和停机过程中时要额外消耗一定的燃料，停机过程中 消耗的燃料比启动过程中消耗的燃料小，一般合并到启动耗量中 计算，因为大多数机组停机后还要启动( 在研究周期内或下一周 期) 。机组的启动耗量包括两部分即汽轮机和锅炉启动所需的耗 煤量。其中锅炉的热容量很大，从锅炉点火开始到产生蒸汽，给 锅炉通汽加温、加压，一直到锅炉各部分加热到稳定状态为止要 消耗相当的煤量。启动耗量与机组停机时间长短有关，这是因为 停机时间越长，散热越多，再启动需要的燃料越多。其关系可用 图卜4 表示，其函数表达示为： f = ( 1 一e - a t j + f ， ( 卜1 ) 其中，f ：启动耗煤量； 巳：锅炉由冷却状态肩动时所需的耗煤量； 口：锅炉冷却时间常数； t ：从停用机组开始到+ f 次再启动所经过的小时数； f ，：仪启动汽轮机所需的耗煤量。 式( 卜1 ) 是在汽轮机停机、锅炉熄灭，即停机时间比较长 ( 大于f 小时) 的情况下采用的。 另一种情况是在停机时间不太长( 小于r 小时) 时再启动。 在这种情况下锅炉不宜熄火，而让其保留余火以防以锅炉汽轮机 冷却。机组的这种状态称为“压火”状态。机组在压火状态下再 启动的耗煤量与停机的时间成正比，如图卜4 所示。其函数表达 式为： 只= c t + f ，( 1 2 ) 第一章绪论 其中，c ：机组压火一小时的耗煤量。 耗煤量 图1 - 4 机组启动耗量与停机时间的关系 式( 1 - 2 ) 在图1 - 4 上是一条直线，由图可知若预先让停机限制 在f r 之内，则压火是有利的。 综上所述，合理的选定各时间段上参加运行的机组群，应综合考虑机组 运行的经济特性、技术限制和有关启停的一些问题，以求得一个完整调度周期 中机组的最优运行状态，使系统在此周期上的总耗量( 或总发电成本) 最小。 1 2 机组组合问题的研究意义 机组组合是一个非常有趣的研究课题，因为它是每天编制调度计划首先 要解决的问题。在确定了机组的启停状态即某个时刻运行的机组群后，根据系 统的负荷功率在运行的机组间进行有功功率的最优分配即经济调度。电力系统 经济调度的同的是在满足系统安全约束、电能质量要求的条件下尽可能提高运 行的经济性。经济调度的效益很大，根据国外资料和华北、东北等电网的实际 测算，节省能源可达总耗量的0 1 5 1 1 5 。但是机组组合的经济效益一般 大于经济调度的效益。 在e m s 中，它将启停计划送给发电计划和实时发电控制作为数据，同时还 参与r 水电计划、交换功率计划的协调，使发电计划在更大范围内取得最优结 果。它与其它程序之间的关系见图卜5 。 此外，机组组合已有6 0 多年的研究历史，但由于机组组合问题是一个 高维数、非凸的、离散的、非线性的优化问题，很难找出理论上的最优解，人 们+ 4 直在积极研究并提出各种方法来解决这个问题，如：优先顺序法、动态 第一章绪论 规划法、拉格朗日松弛算法、遗传算法等或是几种算法的结合使用，目标都 图卜5 机组组合优化与其它程序的关系 是为了在合理时间内找到近似最优解。其中，近年来兴起的遗传算法具有很 强的解决问题的能力和很好的适应性，为解决机组组合问题提供了别开生面 的方法并取得r 良好的效果。但是由于遗传算法的初始种群是随机产生的， 得到的个体因不满足最小起停时间等约束而多数为不可行解；此外，在交叉 和变异的进化过程中，由于遗传操作因子是随机操作的，由此得到的新个体 也因破坏了最小启停时间等约束而多数为不可行解，因而大大降低了遗传算 法的计算效率。其它方法也都存在这样或那样的局陷性( 在下一章第二节中 将详细阐述) 。因此尽管存在上述众多的优化方法，但在机组组合优化问题 上，仍然缺乏科学、高效的计算机优化方法的支持。 1 3 本文的主要研究工作 近二i 十年来，认知科学( c o g n i t i v es c i e n c e ) 己逐渐成为国内外的研究 热点。文献【1 】以认知科学中关于社会群体认知的研究成果提出了求解组合 优化问题通用的社会群体认知模型，并在此模型基础上，针对配电网优化规 划这一具体- j ：程问题提出了社会演化算法，在该问题中显示出了很好的适用 性、计算效率及收敛稳定性。 如前所述，机组组合优化问题是一个复杂的组合优化问题，所以本文首 次尝试将社会演化算法 - 3 i 入机组组合优化问题的研究中，完成了基于机组组 合问题的社会演化算法的基本框架和认知规则等设计。本文主要的研究工作 第一章绪论 如f ： l ，分析了人在机组组合优化问题中的认知行为，在此基础上设计了社 会演化算法中认知主体、认知规则、“范式学习与更新”及“范式突破”的 实现方法； 2 将最小启停时间约束引入认知规则，通过认知主体的一系列认知行 为直接生成满足各种约束的可行解： 3 采用c + + 编程实现适合于中小电力系统和大型电力系统的该算法的 计算软件，并通过算例( 最大机组数为1 0 0 台) 证明了该算法的计算效率和 收敛稳定性。 第二章机组组合问题的数学模型及常用算法 第二章机组组合问题的数学模型及常用算法 在电力系统传统的短期经济运行中，机组组合是一个重要的优化问 题。合理的开停机方案能节省一次能源，延长机组使用寿命，带来显著经济 效益。改革开放以来，电网的调度管理工作得到了重视，技术装备水平有了 很大提高，部分地区发电量有了富余，这为机组组合的研究和应用准备了良 好的现实条件。 机组组合问题是一个高维数、离散的、非线性的优化问题，很难找出 理论上的最优解，但由于它能带来显著的经济效益，人们一直在积极的研 究，提出各种方法来解决这个问题。这些方法包括局部寻优法1 2 】、优先顺 序法3 1 、动态规划法 4 - | i l 、混合整数规划法、线性规划法【1 2 】、拉格朗日松 弛算法1 川引、专家系统、神经网络、遗传算法1 6 啦! 等等。其中局部寻优法、 优先顺序法、专家系统、神经网络等算法都属于启发式算法，没有严格的 理论依据。而是靠直观的判断和实际的调度经验来寻找最优解。动态规划 法是解决多阶段决策过程的一种数学方法。混合整数规划法是变量中既有 整数又有非整数的数学规划问题，这种规划问题解决起来非常困难，常用 的方法有分支定届法、b e n d e r s 分解法等。近年来兴起的遗传算法对目标 函数及约束条件既不要求可微，也不要求连续，因而灵活性很大，为机组 组合问题的解决带来了别开生面的方法。 本章首先给出了机组组合问题的定义及数学模型，在此基础上依次具 体介绍了常用的优先顺序法、动态规划法、拉格朗日松弛算法以及遗传算 法，通过比较指出了它们的优缺点。 2 1 机组组合问题的数学模型 传统的机组组合问题( u n i tc o m m i t m e n t ，u c ) ，是电力系统优化运 行的个重要方面，也称为开停机计划，指的是：根据负荷预测，在满足 系统负荷、备用容精及起停时间等约束条件f 确定一个调度周期( 通常为 2 4 h ) 内再时段参j j u 运行的机组和各机组在运行时段的出力，使得在该周期 内的总发电成本最小。 根据实际系统不同的要求，对于机组组合问题可以建立不同的模型。 第二章机组组合问题的数学模型及常用算法 有的模型为了简化，忽略了某些约束，如线路潮流约束：有的模型考虑了 水火电协调问题；另外一些模型考虑了负荷的随机性和发电机的可靠性。 本文采用的是火电厂机组组合模型，以系统各发电机组的启停状态和出力 为控制变量，考虑了功率平衡约束、旋转备用约束、最小启停时间约束和 机组加减载约束( 即功率变化速率) 。更详细的模型应包括线路潮流限制、 分区功率平衡、机组的燃料限制和随机停运的影响等，但本文模型中未考虑 这些因素。 2 1 1 变量 以下是数学模型中将用到的各个变量的含义： v ：机组总数； 7 ：时段总数； f ：第f 台机组，“= 1 , 2 ，n ) ： f ：第f 时刻，( f = 1 , 2 ，t ) ； u 。：机组f 在第t 时刻的状态，u ，。= l ，表示机组处于运行状态；u 。= 0 ，表 示机组处于停机状态； 只，：机组i 在第f 时刻的实际出力： 只。：机组i 的最大出力； 只。：机组f 的最小出力； x 机组f 到第f 时刻已连续运行( 值为正) 或连续停机( 值为负) 的时段数： d ，：第f 时刻的系统总负荷； r ：第f 时刻的系统总备用； m w ：机组i 的最小运行时间； m d t ：机组f 的最小停机时间； r u r ：机组i 的功率上升量的限制： r d r , ：机组，的功率下降量的限制； 配：机组f 的启动成本； k ，：机组f 在第，时刻的发电成本； t c ：总发电成本： h c o s t 。：机组f 的热启动成本； c c o s t ，：机组f 的冷启动成本； - 8 - 第二章机组组合问题的数学模型及常用算法 c j h o u r i ：机组f 的冷启动时间 2 1 2 目标函数 机组组合问题的目标函数是总发电成本最小。 ( 1 ) 总发电成本 总发电成本包含发电成本和启动成本两项。 m i n t c = 窆芝眇。f c , ，+ u 。( 1 一u ，。k 】 ( 2 1 ) ( 2 ) 发电成本 本文中机组的发电成本用以下二次函数表示： f c 。= d 。+ b 。已+ c 。戎( 2 - 2 ) 其中，口，、b i 、c - 为机组f 发电成本函数的参数。 ( 3 ) 启动成本 第一章详细介绍了机组的两种启动耗量一自然冷却状态和压火状态下 的启动耗量，与此对应的发电成本也分为两种一冷启动成本和热启动成本。 本文中将冷启动成本和热启动成本简化为常数考虑，则机组的启动成本表 示为： s q ；r 0 8 “篡i m d 可+ c s h o u r 7 2 1 3 约束条件 以下是在机组组合优化过程中必须满足的约束条件： ( 1 ) 功率平衡约束 所有运行机组的总发电量必须满足负荷的需要： d r = u i ，尸，( f = l ，2 ，r )( 2 4 ) ，t i ( 2 ) 旋转备用约束 为，保证可靠供电和良好的电能质量、维持系统的可靠性，还要提供充 足的旋转备用。所谓旋转备用是指运转中的发电设备可能发的最大功率之 和与系统总负荷之差。它主要包括全部负荷备用( 调整系统中短时的负荷 波动并负担计划额外的负荷增加而设置的备用) 和一部分事故备用( 为使 蔓三至塑塑塑鱼塑壁塑墼堂堡型垄蔓旦星鲨一 电力用户在发电设备发生偶然事故时不受严重影响、维持系统正常供电所 需的备用) 。显然，从保证可靠供电和良好的电能质量着眼，旋转备用越多 越好，但从保证系统运行的经济性着眼，旋转备用又不易过多。本文中， 旋转备用取为系统总负荷的1 0 ，即r = l o xd ，： 乩尸。、d ，+ r ( 2 5 ) ( 3 ) 最小启停时间约束 由本文第一章可知机组不能频繁启停，所以机组只有在运行( 或停机) 一段时间后才能停机( 或起动) ，即机组要满足最小启停时间约束，只有满 足： 挎叩 ( 2 - 6 ) l ( _ x 。) 坳i 、 时机组f 才能改变当前的状态。 ( 4 ) 机组出力约束 每台机组的出力都有一定的范围： 只。只只。 ( 2 - 7 ) ( 5 ) 加减栽约束 r 一只h 尺呱当只 只。 只。一p ，肋r 当p ， 只 ( 2 - 8 ) 2 2 机组组合问题常用的优化算法 2 2 1 优先顺序法 优先顺序法( p r i o r i t yl i s t ，p l ) 提出较早，现在仍在研究和应用之中。 它是将系统可调度的机组按某种经济特性指标事先排出顺序，根据系统负 荷大小按这种顺序依次投切机组。 机组的单位耗量是随机组出力变化的每度电消耗的煤量： “：旦( 2 9 ) 。p 其中，b 表示单位时间内消耗的燃料，t 等于耗量特性曲线上各点与 坐标原点连线的斜率，见图2 一l 。 机组的耗量微增率五等于耗量曲线上各点切线的斜率： 笙三至垫塑丝鱼塑璧塑墼堂堡型璺萱旦簦鲨 b 尸 b 一尸 五一尸 u p p 图2 一l 机组单位耗量和微增率的关系 ( 2 一l o ) 机组的最小单位耗量点是过坐标原点向耗量特性曲线所作切线的切 点，在这一点上： 五= d 。 ( 2 - 1 1 ) 一般来说它接近于机组额定出力点。 对于机组耗量特性曲线上各点计算单位耗量和微增率a ，可以得到机 组的一旯曲线，将全部可启停机组的卢一五曲线画在一张图上( 见图2 2 ) 。 我们知道火电机组之间应按等微增率原则分配负荷，对于同一个微增率a ( 见图2 - 3 中的虚线) ，让单位耗量口值小的机组先并列是有利的。可以 按最小单位耗量芦一排队来确定机组的并列次序，这就是机组的优先顺序 表。 五= 常数 髟纩厶 彳“一。 图2 3 机组单位耗量与微增率丑关系曲线 第二章机组组合问题的数学模型及常用算法 机组优先顺序表仅给出了机组并列顺序，还不知道系统负荷变化到什 么程度才应该并列。换句话说，针对一个具体负荷还不知道在优先顺序表 上开到哪一台机组。可以这样试探：假设在优先顺序表上前k 台机组可以 满足某一系统负荷d ，按等微增率原则在k 台机组之间分配负荷，并计算 其总耗煤量玩；再在优先顺序表上加开第七+ l 台机组，按同样的方法计算 出k + 1 机组的总耗煤量曰。，取小者为较优的组合。这样在优先顺序表上 前后变化k ，便可以得到对系统负荷d 的最优组合。实际上，上述比较过 程可以用下列简单原则来代替：肌 以时，k + l 号机组不并列是有利的。 用优先顺序法计算机组组合的具体步骤可以归纳为： ( 1 ) 将系统机组按可用状态分类：必开机组排在最前；可启停机组按最 小单位耗量。由小到大连续排列；停用机组排到最后。由此得到 优先次序表。 ( 2 ) 在优先顺序表上依次计算出前k 台机组的最大出力之和及最小出力 之和。 ( 3 ) 在优先顺序表上选择出能满足系统负荷( 加备用) 要求的最小机组 号k ，按等微增率原则计算k 台机组满足此负荷的微增率 。如果 以五，k 台机组最优：如果段 五，继续试探t + 1 台机组。 ( 4 ) 重复( 1 ) 一( 3 ) 步骤，计算出一天对应的组合，检查最短停机时间， 将小于最短停机时间的机组改为开机。 优先顺序法计算速度快，占用内存少，适用于在线确定机组运行状态。 对于小机组启停的系统，结果接近于最优组合，但对于中型和大型机组启 停的系统常常找不到最优解或次优解，但能满足一般的应用要求：此外用 优先顺序法计算机组组合问题时按时段分别进行的，难以考虑机组的启动 成本。 优先顺序法既可单独使用，也可与动态规划法等方法结合使用( 参见 2 3 2 动态规划法) 。 2 2 2 动态规划法 动态规划法d p ( d y n a m i cp r o g r a m m i n g ，d p ) 是解决多阶段决策过程最 优化的一1 种数学方法，在枚举各种可能的状态组合的过程中，这种方法巧 妙地摒弃r 那些不需要考虑的解。动态规划法要求所求解的问题具有明确 的阶段胜。此方法的细节可参阅文献 2 3 。用动态规划法求解机组组合问 题时，接个调度期间t 被分成若干个时段，通常每个时段为1 小时，每个 时段即动态规划过程中的一个阶段。各阶段的状态即为该时段所有可能的 笙三童垫望望全塑墼塑墼兰堡型墨苎旦茎鎏一 机组启停状态组合。从初始阶段开始，从前向后计算到达各阶段各状态的 累计发电成本( 包括开停机成本和运行时的发电成本) ，再从最后阶段累计 发电成本最小的状态开始，由后向前回溯，依次记录各阶段使总的累计发 电成本最小的状态，这样就可得到最优的启停机方案。 我们用启动成本为常数的z 台机组、3 个时段负荷的最简单例题( 见 图2 4 ) ，说明动态规划法解决机组组合的基本过程。 两台机组可能存在四种运行状态( 1 表示开，0 表示停) ： 两台全开 1 ，1 ： l 号机开，2 号机停 1 ，0 ； l 号机停，2 号机开 0 ，0 ； 两台全停 0 ，0 。 因为全停不能满足系统负荷要求，故舍弃这种状态，下面仅研究前三种状 态。 d 图2 4 两台机组三个时段的例题 两个时段之闻的联系称为转移，其成本如下： 状态不变，即l l 、0 h ，转移成本为0 ； 机组状态由开转为停，即l 如，转移成本为o ； 机组状态由停转为开，即0 呻l ，转移成本等于开机机组的启动成本 ( 假设i 号机组的启动成本为1 5 ，2 号机组的启动成本为2 ) ； 动态规划的决策过程分为两大步：一是正序造表，二是逆序查表( 见 图2 5 ，各圈中第一行数字表示本时段机组状态，第二行数字表示本状态 的发电成本，第三行数字表示发电成本最低的转移路径前一时段的状态， 而累计发电成本 己在圈外) 。 这问题的正序造表过程为： 第二章机组组合问题的数学模型及常用算法 ( 1 )列出各时段的三种组合状态，按等微增率原则计算所有组合 状态下的发电成本，记在对应的栏中。 ( 2 )确定各时间段问状态转移路径。例如时段2 的状态 1 ，0 ” 可能由时段1 的三种状态转移来，但前时段累计发电成本和 启动成本不同，分别是： 由状态 1 ，1 来：7 + 0 = 7 ； 由状态 1 ，0 来：5 + 0 = 5 ： 由状态 0 ，1 “束：6 + 1 5 = 7 5 ； 取成本最低的 1 ，o “为转移路径，记在 1 ，0 “的栏中。 将 1 ，0 “的累计发电成本5 加上 1 ，0 “到 1 ，0 ”的 转移成本0 ，再加上 1 ，0 “的发电成本l l 作为 1 ，0 ” 的累计发电成本1 6 记在 1 ，0 “的栏中。按时序对所有状 态算出转移路径和累计发电成本，并记在对应的栏中，即完 成了正序造表过程。表中的内容为：状态、发电成本、路径、 转移成本和累计发电成本。 71 62 3 图2 5 动态舰划进行机组组合原理图 第二章机组组合问题的数学模型及常用算法 以后进入逆序查表过程： 在最后一个时段3 中寻找出全天成本最低的状态 1 ，0 ”，根据它记 录的路径找到前一个时段2 的状态 1 ，1 ”，继续查表可返回第一时段的 状态 1 ，o “。这样可以得到最优开停机计划： 1 ，0 “+ 1 ，1 ” 斗 1 ，0 “。 如果考虑机组启动成本是停机时间的函数和最小开停机时间约束，问 题就复杂化了。因为某一时段中相同的机组启停状态之中增加了不同停机 时间的差别，就又构成了许多新的状态，使状态数随时段数增加而急剧增 多，形成所谓“维数灾”。以1 0 台机组2 4 个时段的机组组合的问题为例， 启动成本为常数的动态规划法的状态数为2 ”2 4 ，启动成本为变数的动态 规划法的状态数为2 ”，而实际电力系统的规模比它大得多。由此可以看 出，考虑机组的全部组合状态和各时段之间全部转移是根本不现实的，其 计算代价远远大于机组最优组合可能得到的经济收益。 因此，应用动态规划法进行机组组合的关键在于降低计算量，而且尽 可能不丢失最优方案。 为了降低计算量，常采取一定的措施来限制状态的数目。首先可立即排 除那些明显不可行的组合，剩下的状态数仍然是大量的，可采用多种方法 进行处理ad 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 cf d y n a m i cp r o g r a m m i n g t r u n c a t e dc o m b i n a t i o n ) 法选取优先顺序表前面一定数目的机组的启停状 态组合作为餐阶段的状态，状态数增加，计算量增大，但优化效果较好。 还有其它近似方法，多是将动态规划法和优先顺序法结合使用，总的目标 是在计算量与优化效果之闻寻求折衷。 当考虑机组启动成本是停机时间的函数时，即使使用上述限制状态数目 的办法，讨算量仍然很大，必须采取简化方法。在动态规划法由前向后计 算的过程中，计算出对应于每个状态的累计启停机时间，这个累计启停机 时间对应于到达该状态的最优路径动态规划法只允许那些满足最小启停 机时间约束的状态转移。累计启停机时间也用于计算启动成本。应该注意 这只是种近似计算方法，可能丢失最优解。 动态规划法另一个难于处理的问题是机组的加减载限制，即机组功率 变化速率限制。对于某个给定的状态来说，加减载限制是前一阶段与其相 第二章机组组合问题的数学摸型及常用算法 连的状态的函数，对于这个状态，相关于每个前一阶段状态都要进行一次 经济负荷分配计算，使占用内存量和计算时间增加，因此只能通过近似方 法解决。在停机的过程中，考虑加减载限制也会丢失最优解。 动态规划法在机组组合问题中得到了广泛的应用，文献 5 ，6 是关于动 态规划法应用的比较重要的文献，提出和比较了动态规划法的几种基本形 式。文献 7 将动态规划法和线性规划法相结合，使用线性规划法解决约束 条件下的负荷经济分配问题，已能考虑机组的加减载约束。文献 8 使用改 进的方法来处理与时间有关的约束。文献 9 将动态规划法和系统分解方法 结合起来，机组组合问题被分解为比较容易解决的子问题每个子问题用 动态规划法解决。9 0 年代，动态规划法又有了一些新的进展。如加入可靠 性模型，考虑系统安全约束等。文献 1 0 将系统负荷、安全约束、发电费 用等都用模糊集理论来表示，并采用了模糊动态规划法。文献 1 1 用动态 规划法来优化机组退出过程，取得了与拉格朗日松弛法相当的优化效果和 计算效率。 动态规划法有如下优点： ( 1 ) 它是一种组合优化算法，对目标函数没有特殊的要求，能求得全局 最优解： ( 2 ) 结合优先顺序法等限制状态数目后，能开发出实用算法，因而在实 际系统中取得j ，广泛的应用。 但缺陷是： ( 1 ) 对于机组数较多的电力系统，计算量太大，必须采用近似方法加以 简化，这样不可避免地要丢失最优解； ( 2 ) 动态舰划法要求所求解的问题具有明显的阶段性，难于考虑与时间 有关的约束条件和机组加减载约束； ( 3 ) 通盘考虑整个系统的问题时，使用起来不够灵活。 2 2 3 拉格朗日松弛算法 拉格朗日松弛算法( l a g r a n g i a nr e l a x a t i o n ，l r ) 是解决复杂问题的一 类优化算法，它的基本思想是：许多困难的整数规划问题可看成是由一些 边界约束条件联系在一起的一系列相对容易的子闯题组成，利用这个特点， 把约束条件被破坏的量和它们各自的对偶变量的乘积加在目标函数上作为 第二章机组组合问题的数学模型及常用算法 惩罚项，形成拉格朗曰问题。 该方法在机组组合问题中的应用研究始于7 0 年代，8 0 年代逐渐得到推 广，9 0 年代成为主流，有大量的理论和应用成果。它把全系统的约束如负 荷约束、旋转备用约束等写成目标函数的惩罚项的形式，即进行松弛。约 束条件松弛后的对偶问题可分解为单机组的子优化问题。解子优化问题的 过程和整体协调( 即优化拉格朗日乘子) 的过程交替迭代进行直到找出最 优或次优的对偶问题解。 应用拉格朗目松弛算法解决机组组合问题时，这样构造拉格朗日函数： ( u ，p ，丑，卢) = r c ( u ，j d ) + 爿1d 。一u 。晶l + 卢。i ( q + r ) 一u n 。只。l ， ，、r，、 ( 2 1 2 ) 式中，t c ，j d ) 为机组组合问题的目标函数，见式( 2 1 ) ；z ，t = 1 , 2 ，t ， 分别为约束( 1 ) 、( 2 ) 的拉格朗日乘子。 原问题的对偶问题为： q m a x q ( , i ，) ( 2 - 1 3 ) 其中， q ( a ，卢) = r a i n l ( u ，p ，a ，a ) ( 2 - 1 4 ) 对偶问题的求解方法是交错求解上层主问题( 2 - 1 3 ) 和下层子问题 ( 2 1 4 ) ： ( 1 ) 对于( 2 - 1 3 ) 式，选定a ，卢，使q ( i ，卢) 的值最大； ( 2 ) 对于( 2 1 4 ) 式，假设a ，是固定不变的，确定u ，p 使l ( u ，p ， ，) 的值最小。由( u ，】d ，z ，) 的表达式可得： p ，j d ，五，) ：妻妻，阮+ ( 1 一。) 踞 + 壹爿fd f 一窆b f = 【- t ir = l t = i 7厂v 、 + l ( d ，+ r ，) 一u ，p 。i = 弘 ；| ；匠，+ 。k - 2 8 , - , u 】 + tp t d ，+ t ( d ，+ r ) ) 式( 2 1 5 ) 中，表达式tp td ，+ a t ( d r + r ) ) 为定值，由于约束 ( 2 1 5 ) 第二章机组组合问题的数学模型及常用算法 ( 5 ) 都是机组自身的约束，丽与其它机组的状况无关，因此表达式 阮，+ o - u 。一砖一z 只一只。、j 可由各机组独立计算。这样求解拉格朗 j = 1 日函数的最小值就可以分解为台机组的子优化问题： m i n l p ，尸， ，) = 窆m i n 窆u 。k ，+ ( 1 一u ，。k 一只，一7 只。】 ”8 1 ( 2 1 6 ) + 2 + 妇+ 足) ) _ 】 每个子优化问题对应于各机组的状态优化，这样大大降低了计算规模， 可以由动态规划法解决。这里，彳，的调整方法是拉格朗日松弛算法的关 键所在。一般可采用梯度法、启发式方法或遗传算法等。 将最终得到的对偶问题的最优解带入式( 2 - 1 ) ，可计算得到原目标函数 t c 的值，它与由式( 2 - 1 4 ) 计算得到的值q 并不相同，即存在对偶间隙 ( d u a l i t yg a p ) ，对偶间隙d 定义为： 占：t c _ - q( 2 1 7 ) f 7 q 通常以对偶间隙作为算法收敛的判断依据。 拉格朗日松弛算法用于机组组合优点是拉格朗日松弛法能避免决策 变量很多时造成的“维数灾”问题，可以得到较好的次优解：对于大规模 机组组合问题用对偶方法求解，使其能够考虑不同的约束，并且计算速度 快。其缺点是难于处理以时间为变量的约束条件和机组间耦合的约束条件； 存在对偶间隙，需要根据对偶问题的优化解采取一定的措施构造原问题的 优化解；算法的过程中有可能出现振荡和奇异现象，得到可行解比较困难。 2 2 4 遗传算法 遗传算法( g e n e t i c a l g o r i t h m ，g a ) 是模拟自然界生物进化过程和机制 求解机制问题的一类自组织、自适应的人工智能技术。它模拟达尔文的自 然进化论与孟代尔的遗传变异理论，具有坚实的生物基础；它提供从智能 生成过程观点对生物智能的模拟，具有鲜明的认知学意义；它适于无表达 或有表达任何类函数，具有广泛的应用价值。 遗传算法应用到机组组合，对目标函数没有特殊要求，可以考虑多个 第二章机组组合问题的数学模型及常用算法 约束，方法比较灵活；虽然不能保证得到全局最优解，但是一般情况下， 可以得到和全局最优解非常接近的次最优解，不会出现很难得到可行解的 情况，能够满足工程应用需要。所以在将遗传算法应用到机组组合问题上 也出现了大量的理论和应用研究成果。 由于本文采用的社会演化算法与遗传算法都属于进化寻优算法，在具 体技术手段上也能找出某些对应关系，因此这里将详细介绍一下遗传算法 的基本原理和实现方法，以便更好地理解第四章介绍的社会演化算法。 2 2 4 1 遗传算法的基本原理 遗传算法用生物群体的观点来看待优化的问题。它从一组随机产生的 称为“种群( p o p u l a t i o n ) ”的初始解开始搜索。种群中的每个“个体 ( i n d i v i d u a l ) ”是优化问题的一个解，称为“染色体( c h r o m o s o m e ) ”。染色 体是一串符号，这些染色体在后续迭代中不断进化，称为遗传。染色体的 每一个基本组成单位称为“基因( g e n e ) ”。处于某一时段的群体称为“代 ( g e n e r a t i o n ) ”。在每一代中用“适应度( f i t n e s s ) ”来测量染色体的好坏。 针对具体问题，遗传算法通过定义一个“适应度函数( f i t n e s sf u n c t i o n ) ”来 模拟生物界中的环境，而每一个个体所对应的适应度函数数值代表了该个 体对环境的适应程度。适应度函数数值越高表明该个体适应环境的能力越 强。生成的下一代染色体是由前一代染色体通过交叉( c r o s s o v e r ) 或者变异 ( m u t a t i o n ) 运算形成的。在新一代形成中，根据适应度的大小选择部分后代， 从而保持