基于改进蚁群算法的梯级水库群优化调度

基于改进蚁群算法的梯级水库群优化调度林剑艺1程春田2滨3筠2于曾(1 . 中国科学院 城市环境研究所 , 福建 厦门 361003 ; 2 . 大连理工大学 土木水利学院 , 辽宁 大连 116024 ;3 . 大连海事大学 交通规划研究所 , 辽宁 大连 116026)摘要 : 针对梯级水库群优化调度的大系统多维多阶段优化决策问题提出改进的蚁群算法 。为提高算法搜索效率采用新的信息素更新策略 A nt2p ropo rtio n ,综合考虑全局和局部信息 。以漫湾 大朝山梯级水电站 优化调度为例 ,计算结果表明 ,改进算法与基本蚁群算法相比具有更好的优化结果和收敛速度 ,与逐步优化 法相比可靠有效 。关键词 : 梯级水库群 ;优化调度 ;蚁群算法 ; A nt2p ropo rtio n中图分类号 : TV697 . 1 + 2文献标志码 : A水库群优化调度是一个复杂的大系统多维多阶段优化决策问题 1 。目前 , 最优化方法有动态 规划逐次逼近法、线性规划 动态规划法、逐次优 化法、网络流算法、逐次聚合法和大系统分解协调 法等 24 。最常采用动态规划及其系列算法 , 但 它往往伴随“维数灾”问题 , 尤其是用于多库联合 调度 时 明 显。20 世 纪 90 年 代 初 意 大 利 学 者 Do ri go 等提出蚁群算法 ( A CO) 5 , 是继模拟退火 算法、遗传算法、禁忌搜索算法、人工神经网络等 后又一种应用于组合优化问题的启发式搜索算 法 , 已成功应用于水库优化调度中 6 , 7 。本文采 用一种新的信息素更新模型 A nt2p ropo r tio n 用 于改进基本蚁群算法 8 , 更新策略综合考虑了全 局和局部的反馈信息 , 有效地提高了搜索质量并 缩短了时间。最后将改进蚁群算法用于解决梯级 水库群优化调度中的计算问题 。图 1 梯级水电站水库群系统示意图S c h e ma t i c di a gr a m of c a s c a d e d h y d r o e l e c t ri c p l a n t s r e s e r vi o r gr o upFi g . 1Tnma x f = ma x 66 A i Q it H it M t( 1)t = 1i = 1( 2) 约束条件 。水量平衡约束为 :V it + 1 = V it + ( Fit - Qit - S it )t水库蓄水量约束为 :V it , min V it V it , max水轮机过水流量约束为 : Qimin Qit Qimax水库泄流量约束为 :qit , min Qit + S it qit , max水电站出力约束为 :N i , min A i Q it H it N imax( 3) 关联方程 。Fi + 1 t = Qit + S it + I B it式中 , T 为年内总时段数 , 以月计 , T = 12 ; A i( 2)( 3)( 4)( 5)( 6)数学模型1( 7)为水假设梯级水电站水库群系统 ( 图 1) 由 n 个水库组成 , 以发电为主 , 兼顾其他综合效益。长期优 化调度的确定性数学模型主要有三项内容 。( 1) 目标函数。电站 I 的出力系数; Qit 为水电站发电引用流量 ,m3 / s ; Fit 为水库 i 的入库流量 , m3 / s ; H it 为水电 站 i 的时段平均水头 , m ; S it 为水库 i 弃水流量 ,收稿日期 : 2007212224 ,修回日期 : 2008204207基金项目 : 国家自然科学基金资助项目 ( 50479055) ; 中国科学院知识创新工程青年人才领域前沿基金资助项目(07l4071d30)作者简介 : 林剑艺 (19652) , 男 ,助理研究员 ,研究方向为复杂系统建模 , Email :jylin iue. ac. cn通讯作者 : 程春田 (19652) , 男 ,教授、博导 ,研究方向为电网与水电站经济运行 , E2mail :ctcheng dl ut . edu. cn54 水 电 能源 科 学2008 年m3 / s ; M t 为第 t 时段小时数; V it 、V it + 1 分别为时段初、末水库 i 的蓄水量 , m3 ;t 为第 t 时段的秒 数; V it , min 、V it , ma x 分别为水库 i 最小、最大允许蓄水量 , m3 ; Qi , min 、Qi , max 分别为水电站 i 最小、最大引用流量 , m3 / s ; qit , min 、qit , max 分别为水库 i 下游综合 利用要求 的最 小、安 全 下 泄 流 量 , m3 / s ; N imin 、 N imax 分别为水电站 i 保证出力、装机容量 , k W 。进行更新。每条路段 ( 局部反馈信息) 对目标函数的贡献不同 , 为使信息素更有效地引导后来蚂蚁 朝正确方向搜索 , 应在较好的路段分配较大的信 息素增量 , 在较差路段分配较小的信息素增量。 这样就有效地利用了全局信息 , 同时可在较好区 域上进行更精细的搜索 , 避免了大量的无效搜索 , 加快算法收敛的同时也提高了搜索全局最佳路径 的可能性。具体的信息素更新如下 :改进蚁群算法第 k 只蚂蚁经过边 ( i , j)其他2f k -f kQijf k ( N - 2) f k0式中 , N 为节点个数。kij =( 11)蚁群算法是受到真实的蚁群行为的启发而提出 , 蚁群运动依据一定的转移规则进行 , 转移规则 依赖于路径上的信息素浓度。常用的更新策略主 要有以下三种 : A nt2de n sit y 。3实例应用Q第 k 只蚂蚁在循环中经过边 ( i , j)0其他kij =( 8)3 . 1 算法步骤根据式 ( 1) ( 7) , 梯级水电站的运行策略一 般用发电引用流量序列 Qit , 而用其又可转换为水 位变化序列 Zit 。因此 , 问题转化为求决策变量为式中 ,k 为第 k 只蚂蚁在当前循环中在 ( i , j ) 边ij上的信息素增量; Q 为常量 。A nt2qua ntit y 。Q/ f k0ij 第 k 只蚂蚁在循环中经过边 ( i , j)其他( 9)kij =各水库水位Zit 的年发电量最大问题。将梯级各水库水位分别离散为若干点 , 各时段库水位散点组合形成水库的一条调度线 , 问题的一个解是各 水库调度线的组合。人工蚂蚁根据转移概率选择 路径 , 在梯级水库水位离散点组合中寻求满足约束条件的最优组合 ( 类似于逐步优化法) , 算法不 断迭代直至迭代结果满足收敛条件要求。同时 , 计算中考虑梯级水力联系 , 当路径中某点发生变 化时 , 即梯级某一级水库某时段水位发生变化时 , 同一时段该级水库以下梯级重新计算目标函数值( 不考虑区间水流滞时) 。改进蚁群算法实现的核 心思想是 : 初始化 。给定参数、取值 , 初始 化各边的信息素强度 , 产生 M 只蚂蚁并将蚂蚁放 置于起点 。 进化。依据转移规则和 A nt2p ro2 po r tio n 策略寻找最优调度线。 终止判断。在进化过程中 , 水库调度线不断调整 , 逐步逼近最优 解 , 当达到精度要求或预设的最大进化代数 , 则算 法结束。3 . 2 改进蚁群算法与基本蚁群算法比较以云南梯级水电站漫湾、大朝山为例。漫湾、 大朝山为不完全年调节电站 ,大朝山水库有区间入流汇入。漫湾水库正常蓄水位 994 m ,死水位 982m ,最大发电流量 1 960 m3 / s ,电站综合出力系数8. 6 ,装机容量 1 250 MW ;大朝山水库正常蓄水位899 m ,死水位 882 m ,最大引水流量2 084 m3 / s ,电 站综合出力系数 8. 8 ,装机容量1 350 MW 。为验证改进蚁群算法的效果 ,利用漫湾 大式中 , f k 为第 k 只蚂蚁在边 ( i , j ) 上的目标函数ij值。 A nt2cycle 。Q/ f k0第 k 只蚂蚁在循环中经过边 ( i , j)其他( 10)kij =式中 , f k 为第 k 只蚂蚁在整个路径中的目标函数值。这三种的区别在于更新信息素的方式 。前两 种模型中每只蚂蚁不是在整个路径结束后释放信 息素 , 即利用局部信息 , 而第三种模型利用的是整 体信息。在现实蚁群中 , 较短路径上的信息素浓度更 高。同理 , 在蚁群算法中 , 与最优方案更接近的路 径 , 获得的信息素数量更多 , 使其在下一循环中更 有吸引力 。因此 , 算法采用何种更新策略 , 关系到 算法效率 。A nt2cycle 使用的反馈信息是全局的 , 而 A nt2de n sit y 和 A nt2qua ntit y 利用的反馈信息是局部的 , 故 A nt2cycle 模型优于另两种模型 。但 A nt2cycle 完全忽略了局部信息 , 在所有路段 上均分信息素增量 ,使很差的路径上也存在很大的信息素增量 ,致使在之后的搜索中存在较大的 被选概率 ,从而错误引导信息 ,造成无效搜索 。为此 ,本文提出一种新的更新策略 A nt2p ropo r tio n ,以全局反馈信息为基础 , 同时又考虑局部信息 7 。A nt2p ropo r tio n 模型指蚂蚁在游历整个路径 后 , 基于其目标函数值 ( 全局反馈信息) 对信息素55 第 26 卷第 4 期林剑艺等 :基于改进蚁群算法的梯级水库群优化调度朝山梯级代表年的数据 ,将水位离散为 200 个点 ,在相同条件下用改进的蚁群算法与基本蚁群算法 连续测试 10 次 ,结果如图 2 所示 。均运行时间为 2 . 47 、2 . 58 s 。由图中看出 ,改进蚁群算法在优化质量和运行时间上稍优于基本蚁群 算法。测试时两种蚁群算法的参数相同 := 0 . 8 ,= 1 ,= 2 , 蚂蚁数 M = 25 , 迭代次数 nc = 400 。3 . 3改进蚁群算法与逐步优化方法计算结果为检验计算结果的可靠性 , 用改进蚁群算法 和逐次逼近法 ( PO A ) 同时求解 , 计算结果如表 1 所示。前者总发电量为 1 . 163 1010 k W h , PO A 总发电量为 1 . 164 1010 k W h 。两者基本 一致 , 但前者大大提高了求解速度 , 无动态规划的 维数灾问题 。结语4a . 提出的改进蚁群算法用于梯级水库优化调度问题 ,通过与基本蚁群算法比较表明该算法在 一定程度上改进了算法的计算性能 。b. 与传统方法相比 , 该算法计算速度快 、搜 索效率高、收敛性能好 ,自然体现了水库调度线的 概念 ,易于考虑如出力限制、水位限制等和梯级间的水力联系 。图 2 改进与基本蚁群算法比较Fi g . 2 Co mp a ri s o n o n i mp r o v e d a n d b a s i c a n t c ol o n y a l g o ri t hm图 2 (a) 为优化结果比较 ,改进蚁群算法的平均优化结果为 1 . 163 98 1010 k W h ,高于基本 蚁群算法的1 . 163 86 1010 k W h ; 图 2 ( b) 为运行时间比较 , 改进蚁群算法和基本蚁群算法的平表 1 改进蚁群算法和 POA 计算结果Ta b . 1 Op t i ma l r e s ul t s of i mp r o v e d a n t c ol o n y a l g o ri t hm a n d POA水库名称年2月入流/ ( m3 s - 1 )库水位/ m发电流量/ ( m3 s - 1 )水头/ m出力/ 104 k W弃水/ ( m3 s - 1 )漫湾197220419722051972206197220719722081972209197221019722111972212197320119732021973203197220419722051972206197220719722081972209197221019722111972212197320119732025218201 0502 0302 1901 6501 04066343935032436113 . 1121 . 1343 . 44150 . 47239 . 82155 . 22122 . 2994 . 4359 . 5043 . 2631 . 57990 ( 990)994 ( 994)987 ( 987)982 ( 982)982 ( 982 . 1)987 ( 987)987 ( 987)994 ( 994)994 ( 994)994 ( 994)994 ( 994)994 ( 994)889 ( 889)899 ( 899)888 ( 888)888 ( 888)888 ( 888)888 ( 888)888 ( 888)899 ( 899)899 ( 899)899 ( 899)899 ( 899)482 . 39 ( 482 . 39)881 . 86 ( 881 . 86)1 088 . 75 ( 1 088 . 74)1 835 . 98 ( 1 834 . 80)1 782 . 69 ( 1 781 . 61)1 650 ( 1 650)978 . 14 ( 978 . 14)663 ( 663)439 ( 439)350 ( 350)324 ( 324)399 . 61 ( 399 . 61)406 . 93 ( 406 . 93)999 . 14 ( 999 . 14)1 132 . 19 ( 1 132 . 19)2 084 ( 2 084)2 084 ( 2 084)1 805 . 22 ( 1 805 . 22)1 004 . 28 ( 1 004 . 28)757 . 43 ( 757 . 43)498 . 5 ( 498 . 5)393 . 26 ( 393 . 26)355 . 57 ( 355 . 57)89 . 85 ( 89 . 85)92 . 82 ( 92 . 82)85 . 33 ( 85 . 33)79 . 17 ( 79 . 17)79 . 03 ( 79 . 13)84 . 56 ( 84 . 56)85 . 56 ( 85 . 56)93 . 40 ( 93 . 40)93 . 95 ( 93 . 95)94 . 15 ( 94 . 15)94 . 21 ( 94 . 21)94 . 04 ( 94 . 04)76 . 94 ( 76 . 94)83 . 99 ( 83 . 99)72 . 16 ( 72 . 16)67 . 84 ( 67 . 84)67 . 09 ( 67 . 09)69 . 03 ( 69 . 03)72 . 95 ( 72 . 95)85 . 37 ( 85 . 37)86 . 46 ( 86 . 46)87 . 01 ( 87 . 01)87 . 21 ( 87 . 21)38 . 11 ( 38 . 11)67 . 74 ( 67 . 74)77 . 56 ( 77 . 56)125 ( 125 . 00)125 ( 125 . 00)119 . 99 ( 119 . 99)74 . 92 ( 74 . 92)53 . 25 ( 53 . 25)35 . 47 ( 35 . 47)28 . 34 ( 28 . 34)26 . 25 ( 26 . 25)31 . 63 ( 31 . 63)29 . 34 ( 29 . 34)69 . 01 ( 69 . 01)71 . 90 ( 71 . 90)124 . 41 ( 124 . 41)123 . 03 ( 123 . 03)109 . 66 ( 109 . 66)69 . 33 ( 69 . 33)56 . 90 ( 56 . 90)37 . 93 ( 37 . 93)30 . 11 ( 30 . 11)27 . 29 ( 27 . 29)0 ( 0)0 ( 0)0 ( 0)194 . 02 ( 194 . 43)368 . 57 ( 370 . 42)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)96 . 47 ( 95 . 70)307 . 07 ( 307 . 85)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)0 ( 0)大朝山 1973203 21 . 14 899 ( 899) 509 . 32 ( 509 . 32) 86 . 41 ( 86 . 41) 36 . 49 ( 36 . 49) 0 ( 0) 注 :括号内为 POA 计算结果。(下转第 204 页)204 水 电 能源 科 学2008 年(上接第 55 页)参考文献 : 1 刘群明 ,陈守伦 ,刘德有. 流域梯级水库防洪优化调 度数学模型及 PSOD P 解法 J . 水 电 能 源 科 学 ,2007 ,25 (1) :34237 2 Yeh W W G. Reservoir Ma nagement a nd Op eratio n Mo del s : a St ate of A rt Review J . Water Re so urce Re search ,1985 ,21 (12) :1 79721 818 3 董子敖. 水库群调度与规划的优化理论和应用 M .济南 :山东科学技术出版社 ,1989 . 4 叶秉如. 水资源系统优化规划和调度 M . 北京 :中 国水利水电出版社 ,1999 . 5 Do rigo M ,Ma niezzo V ,Colo r ni A . The A nt System :Op timizatio n by A Colo ny of Coop erating A gent s J . IE E E Tra nsactio ns o n Systems , Man a nd Cyber netic s ,1996 ,1 (26) :29241徐刚 ,马光文 , 梁武湖 , 等. 蚁群算法在水库优化调度中的应用J . 水科学进展 ,2005 ,16 (3) :3972400 王德智 ,董增川 ,丁胜祥. 基于连续蚁群算法的供水 水库优化调度J . 水电能源科学 ,2006 ,24 (2) :77279Yu B , Ya ng Z ,Cheng C ,et al . Op timizing Bus Tran2 sit Net wo r k Wit h Pa rallel A nt Colo ny Algo rit hm J . Proceedi ngs of t he Ea ster n A sia Societ y fo rTra nspo rtatio n St udie s ,2005 :3742389 6 7 8 Ca sca ded Hydroelectric Opt imized Operat ion Ba sed on Coarse2Gra inParallel Improved Ant Col ony Opt imizat ion AlgorithmL IN J ia nyi1C H EN G Ch untia n2YU Bi n3ZEN G Yun2(1 . Instit ute of U r ba n Envi ro nment , Chinese Academy of Science , Xia men 361003 , China ;2 . Instit ute of Hydroi nfo r matic s , Dep t . of Civil Eng. ,Dalia n U niv. of Technolo gy , Dalian 116024 , China ;3 . Tra nspo rt a nd Lo gi stics College , Dalia n Ma ritime U niv. , Dalia n 116026 , China)Abstract : A n imp ro ved ant colo ny op timizatio n algo rit hm i s int ro duced to solve t he ca scaded hydropo wer op timized scheduli ng p ro blem wit h high2dimensio nal , multi2stage , and no nlinear character s. The imp ro ved algo rit hm adop t s a new p heno meno n up date st rategy called A nt2p ropo rtio n , w hich ta kes into acco unt bo t h glo bal and local info r matio n , to im2 p ro ve t he op timizatio n qualit y. Thus , t he i mp ro ved algo rit hm can hold much higher sta bilit y a nd co nver gence sp eed a nd bet ter qualit y t ha n t hat of cla ssical ant colo ny op timizatio n algo rit hm. By applying t he mo del to t he Manwa n2Dachao shanca scaded hydropo wer statio nsoperatio n p ro blem , it reveal s t he imp ro ved algo rit hm ha s higher co nver gence sp eed a ndbet ter qualit y t ha n t he cla ssical . Co mp aring wit h t he p ro gre ssive op timalit y algo rit hm , it ha s been demo nst rat ed t hat t he imp ro ved algo rit hm i s an eff ective alter native fo r ca scaded hydroelect ric op timal scheduling.Key words : ca scaded hydroelect ric plant s ; op timal operatio n ; a nt colo ny op timizatio n algo rit hm ; A nt2p ropo rtio n(上接第 186 页)参考文献 :Mo to r Tra nsient s J . IE E E Tra nsactio ns o n Indus2t r y Applicatio ns ,1997 ,33 (3) :7222731Ker kman R J ,L eggate D , Skibi nski G. PWM Invert2 er s a nd Their Infl uence of Mo to r Over2voltage C . In : 12t h A nnual Co nf erence o n Applied Po wer Elct ro nic s ( A P EC97) ,1997 (1) :1032113Skibi nski G , Ker kman R J ,L eggate D ,et al . Ref lec2 t ed Wave Mo deling Techniques fo r PWM A C Mo to r Drive C . In : 13t h A nnual Co nf erence o n Applied Po wer Elct ro nic s ,1998 (2) :1 02121 029朱子述. 电力系统过电压 M . 上海 : 上海交通大学出版社 ,1995 .万键如 ,林志强 ,禹华军. 高频 PWM 脉冲传输引起 电机端子过电压的研究 J . 中国电机工程学报 ,2001 ,21 (11) :43247 5 刘学忠 ,徐传骧. PWM 变频调速电动机端子上电压特性的研究J . 电工技术学报 ,2000 ,15 (5) :26229Mo reira A F ,L ipo T A , Venkatarama nan G , et al . High2f requency Mo deling fo r Ca ble a nd Inductio n Mo to r Overvolt age St udie s in Lo ng Ca ble Drive s J . IE E E Transactio ns o n Indust r y Applicatio ns ,2002 ,38 (5) :1 29721 306Mirafzal B , Skibinski G , Tallam R , et al . U niver sal Inductio n Mo to r Mo del wit h Lo w2to2high Frequency Re s