机组组合问题的两阶段优化算法
|
摘要
机组组合问题(UC)是高维、非凸、多约束的混合整数规划问题。拉格朗日松弛算法(LR)可将UC问题进行解耦,使模型简化,但由于目标函数的非凸性,以及梯度搜索方向的单一性,难以保证对偶间隙的可靠收敛,同时安全约束的引入会进一步增加求解的难度。针对这些问题,提出了一种两阶段优化方法(LR-DE),第1阶段利用次梯度优化的LR对UC问题进行计算,快速获得对偶解；第2阶段根据对偶解信息设定全时段拉格朗日乘子更新空间,并利用DE算法进行搜索,通过种群信息的传递改变机组启停,进而修正对偶解,缩小对偶间隙,求出机组组合问题的近似最优解。不同规模的算例分析表明,次梯度与DE算法的配合,搜索更为全面,保证了解的可行性,提高了收敛的精度。同时对于考虑网络安全约束的机组组合问题,将支路约束转换为发电机功率约束进行求解,通过算例验证了算法的适用性。
Unit Commitment (UC) is a high-dimensional, non-convex, multi-constraint mixed integer programming problem. The optimization could be decoupled by Lagrangian Relaxation algorithm(LR) which simples the model, but can hardly ensure the convergence of the duality gap because the single search direction of sub-gradient and non-convex of the target, while security constraints will also increase the complexity. To solve these problems, this paper presents a two-phase optimization method(LR-DE). First the problem is calculated by LR with sub-gradient to derive the dual solution; second, the space of updating Lagrange multipliers is determined by the optimal dual solution, and searched by Differential Evolution algorithm (DE), the unit commitment is changed through communication of the population, and then Lagrangian dual solution is amended, the duality gap is narrowed, and finally the ultimate solution of the original problem is obtained. Analysis of examples shows that the search is more overallly, the precision of convergence has been improvd, the solution is feasible because of the combination of the two method. This algorithm can also be adopted to solve the security constrained unit commitment. It is solved by changing the constraint of branch into generator, simulation demonstrates the applicability of the proposed method.
Unit Commitment (UC) is a high-dimensional, non-convex, multi-constraint mixed integer programming problem. The optimization could be decoupled by Lagrangian Relaxation algorithm(LR) which simples the model, but can hardly ensure the convergence of the duality gap because the single search direction of sub-gradient and non-convex of the target, while security constraints will also increase the complexity. To solve these problems, this paper presents a two-phase optimization method(LR-DE). First the problem is calculated by LR with sub-gradient to derive the dual solution; second, the space of updating Lagrange multipliers is determined by the optimal dual solution, and searched by Differential Evolution algorithm (DE), the unit commitment is changed through communication of the population, and then Lagrangian dual solution is amended, the duality gap is narrowed, and finally the ultimate solution of the original problem is obtained. Analysis of examples shows that the search is more overallly, the precision of convergence has been improvd, the solution is feasible because of the combination of the two method. This algorithm can also be adopted to solve the security constrained unit commitment. It is solved by changing the constraint of branch into generator, simulation demonstrates the applicability of the proposed method.
引文
[1]中电联统计信息部.2009年全国电力工业统计快报.中国电力企业管理,2010,(4)：92-94
[2]李文沉.电力系统安全经济运行-模型与方法.重庆：重庆大学出版社,1989：4-250
[3]耿建,徐帆,姚建国.求解安全约束机组组合问题的混合整数规划算法性能分析.电力系统自动化,2009,33(21)：24-27
[4]杨秀媛,张南,王海宁,等.用于中期电力市场的启发式机组组合算法.电网技术,2004,28(24)：21-24
[5]葛亮,谢宇翔,李湘祁,等.与市场机制相协调的发电交易与调度的节能减排方法.电工技术学报,2009,24(8)：167-173
[6]刘振亚.加快建设坚强国家电网促进中国能源可持续发展.中国电力,2006,39(9)：1-3
[7]戴慧珠,陈默子,王伟胜,等.中国风电发展现状及有关技术服务.中国电力,2005,38(1)：80-84
[8]于尔铿.现代电力系统经济调度.北京：中国水利电力出版社,1989：42-58
[9]王承民,郭志忠.电力市场环境下解决机组组合问题的新方法.电力系统自动化设备,2001,21(11)：14-17
[10]彭明鸿,李彩林.日前市场下发电商机组优化组合研究.水力发电,2008,34(11)：74-77
[11]Arroyo J M, Conejo A J. Optimal Response of a Thermal Unit to an Electricity Spot Market, IEEE Transactions on power systems,2000,15(3):1098～1104
[12]孟祥星.大规模风电并网条件下的电力系统调度.东北电力大学学报,2009,29(1)：1-7
[13]江岳文,陈冲,温步瀛.含风电场的电力系统机组组合问题随机模拟粒子群算法.电工技术学报,2009,24(6)：129-137
[14]丁明,包敏,吴红斌,等.复合能源分布式发电系统的机组组合问题.电力系统自动化,2008,32(6)：46-50
[15]韩彬,周京阳,崔晖,李晓磊.引入SO2排放惩罚价格因子的节能减排发电调模型及实用算法.电网技术,2009,33(9)：50-54
[16]Lu Bo, Shahidehpour M. Unit commitment with flexible generating units. IEEE Transactions on power systems,2005,20(2):1022～1034
[17]马瑞.电力市场中兼顾环境保护和经济效益的双目标模糊优化短期交易计划.中国电机工程学报,2002,22(14)：104-108
[18]张利,赵建国,韩学山.考虑网络安全约束的机组组合新算法.电网技术,2006,30(21)：50～55
[19]Grey A, Sekar A. Unified solution of security-constrained unit commitment problem using a linear programming methodology. IET Generation Transmission & Distribution,2008,2(6):856～867
[20]Lee FN, Huang J, Adapa R. Multi-area unit commitment via sequential method and a DC power flow network model. IEEE Transactions on Power Systems, 1994,9(1):279-287
[21]Ma H, Shahidehpour S M. Unit commitment with transmission security and voltage constraints. IEEE Transaction on Power System,1999,14(2):757～ 764
[22]Senjyu T, Shimabukuro K, Uezato K, et al. A fast technique for unit commitment problem by extended priority list. IEEE Transactions on power systems,2003, 18(2):882～888
[23]黎静华,韦化.求解机组组合问题的领域搜索法.中国电机工程学报,2008,28(13)：33～39
[24]黎静华,兰飞.适合于机组组合问题的扩展优先顺序法.电力系统保护与控制,2010,38(02)：1-7
[25]Bosch V D, Honderd G. A Solution of the Unit Commitment Problem via Decomposition and Dynamic Programming. IEEE Trans on Power Apparatus and Systems,1985(7):104-115
[26]Nieva R, Inda A, Guillen I. Lagrangian Reduction of Search-Range for Large Scale Unit Commitment. IEEE Transactions on power systems,1987(2):2 ～15
[27]王成文,韩勇,谭忠富,等.一种求解机组组合优化问题的降维半解析动态规划方法.电工技术学报,2006,21(5)：110-116
[28]Shih-Yih Lai, Ross Baldick. Unit Commitment with Ramp Multipliers. IEEE Transactions on power systems,1999,14(1):58 ～ 64
[29]Weerakorn Ongsakul, Nit Petcharaks. Unit Commitment by Enhanced Adaptive Lagrangian Relaxation. IEEE Transactions on power systems,2004,19(1):620～ 628
[30]Wang SJ, Shahidehpour S M, KirschenDS, and etal. Short term generation Scheduling with transmission and environmental constraints using an augmented Lagrangian relaxation. IEEE Transactions on power systems,1995,10(3):1294～ 1301
[31]苗青,曹广益,朱新坚.基于集结投影次梯度的机组组合算法研究.计算机仿真,2008,25(2)：245-247,302
[32]Miguel Carrion, Jose M. Arroyo, A Computationally Efficient Mixed-Integer Linear Formulation for the Thermal Unit Commitment Problem. IEEE Transactions on power systems,2006,21(3):1371～1378
[33]Venkatesh B, Jamtsho T, Gooi H B. Unit commitment-a fuzzy mixed integer Linear Programming solution.Generation, Transmission & Distribution, IET, 2007,1(5):836～846
[34]高山,单渊达.遗传算法搜索优化及其在机组启停中的应用.中国电机工程学报,2001,21(3)：45-48
[35]Yang H, Yang P, Huang C. A parallel genetic algorithm approach to solving the unit commitment problem:implementation on the transporter networks. IEEE Transactions on power systems,1997,12(2):661 ～ 668
[36]赵波,曹一家.电力系统机组组合问题的改进粒子群优化算法.电网技术,2004,28(21)：6-10
[37]Walsh M P, Omalley M J. Augmented hopfield network for unit commitment and economic dispatch. IEEE Transactions on power systems,1997.12(4): 1765-1774
[38]Annakkage U D, Numnonda T, Pahalawaththa N C. Unit commitment by parallel simulated annealing Generation. IEE Proceedings Generation, Transmission & Distribution,1995,142(6):595 ～ 600
[39]Keles A, Etaner-Uyar A S, Turkay B. A differential evolution approach for the unit commitment problem.5th International Conference on Electrical and Electronics Engineering, Bursa,2007:132～135
[40]刘可真,高峰,束洪春,等.一种实用的机组最优启停计划方法.昆明理工大学学报(理工版),2002,27(1)：73-77
[41]陈烨,赵国波,刘俊勇,等.用于机组组合优化的蚁群粒子群混合算法.电网技术,2008,32(6)：52-56
[42]Chuan-Ping Cheng, Chih-Wen Liu, Chun-Chang Li. Unit Commitment by Lagrangian Relaxation and Genetic Algorithms. IEEE Transactions on power systems,2000,15(2):707～714
[43]陈皓勇,张靠社,王锡凡.电力系统机组组合问题的系统进化算法.中国电机工程学报,1999,19(12)：9-13,40
[44]王楠,张粒子,舒隽.基于粒子群修正策略的机组组合解耦算法.电网技术, 2010,34(1)：79-83
[45]刘自发,张建华.一种求解电力经济负荷分配问题的改进微分进化算法.中国电机工程学报,2008,10(28)：100-105
[46]王锡凡,王秀丽,陈皓勇.电力市场基础.西安：西安交通大学出版社,2003：80-82
[47]李朝安.发电厂及电力系统经济运行.乌鲁木齐：新疆人民出版社,1985：196-197
[48]廖培鸿.发电厂的计算机控制.北京：水利水电出版社,1987：160-161
[49]夏道止.电力系统分析.北京：中国电力出版社,2004：8-9
[50]杜松怀,温步赢,蒋传文.电力市场.北京：中国电力出版社,2004：160-163
[51]王锡凡.电力系统规划基础.北京：中国电力出版社,1994：140-141
[52]张伯明,陈寿孙.高等电力网络分析.北京：清华大学出版社,1996：187-190
[53]Fu Y, Shahidehpour M, Li Z. AC Contingency Dispatch Based on Security-Constrained Unit Commitment. IEEE Transactions on power systems,2006, 21(2):897～908.
[54]邢文训,谢金星编.现代优化计算方法著.北京：清华大学出版社,2005：231-235
[55]Merlin A, Sandrin P. A new Method for Unit Commitment at Electricite De France. IEEE Transactions on Power Systems,1983,102(5):1218-1225
[56]Storn R, Price K. Minimizing the real functions of the ICEC'96 contest by differential evolution.1996 IEEE Evolutionary Computation conference, Nayoya, Japan,842～844
[57]Ching-Tzong Su, Chu-Sheng Lee.Network reconfiguration of distribution systems using improved mixed-integer hybrid differential evolution. IEEE Transactions on Power Systems,2003,18(3):1022～1027
[58]Ji-Pyng Chiou, Chung-Fu Chang, Ching-Tzong Su. Ant direction hybrid differential evolution for solving large capacitor placement problems. IEEE Transactions on Power Systems,2004,19(4):1794～1800
[59]Anyong Qing. Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problems. IEEE Transactions on Geosciences and Remote Sensing,2006,44(1):116～125
[60]韦化,吴阿琴,白晓清.一种求解机组组合问题的内点半定规划方法.中国电机程学报,2008,28(1)：35-39
[61]Valenzuela J, Smith A E. A seed memetic algorithm for large unit commitment problems. Journal of Heuristics,2002,8(2):173～195
[62]Kazarlis S A, Bakirtzis A, Petridis V. A genetic algorithm solution to the unit commitment problem. IEEE Transactions on power systems,1996,11(1):83～ 92
[63]工喆,余贻鑫,张弘鹏等.社会演化算法在机组组合中的应用.中国电机工程学报,2004,24(4)：12～17
[2]李文沉.电力系统安全经济运行-模型与方法.重庆：重庆大学出版社,1989：4-250
[3]耿建,徐帆,姚建国.求解安全约束机组组合问题的混合整数规划算法性能分析.电力系统自动化,2009,33(21)：24-27
[4]杨秀媛,张南,王海宁,等.用于中期电力市场的启发式机组组合算法.电网技术,2004,28(24)：21-24
[5]葛亮,谢宇翔,李湘祁,等.与市场机制相协调的发电交易与调度的节能减排方法.电工技术学报,2009,24(8)：167-173
[6]刘振亚.加快建设坚强国家电网促进中国能源可持续发展.中国电力,2006,39(9)：1-3
[7]戴慧珠,陈默子,王伟胜,等.中国风电发展现状及有关技术服务.中国电力,2005,38(1)：80-84
[8]于尔铿.现代电力系统经济调度.北京：中国水利电力出版社,1989：42-58
[9]王承民,郭志忠.电力市场环境下解决机组组合问题的新方法.电力系统自动化设备,2001,21(11)：14-17
[10]彭明鸿,李彩林.日前市场下发电商机组优化组合研究.水力发电,2008,34(11)：74-77
[11]Arroyo J M, Conejo A J. Optimal Response of a Thermal Unit to an Electricity Spot Market, IEEE Transactions on power systems,2000,15(3):1098～1104
[12]孟祥星.大规模风电并网条件下的电力系统调度.东北电力大学学报,2009,29(1)：1-7
[13]江岳文,陈冲,温步瀛.含风电场的电力系统机组组合问题随机模拟粒子群算法.电工技术学报,2009,24(6)：129-137
[14]丁明,包敏,吴红斌,等.复合能源分布式发电系统的机组组合问题.电力系统自动化,2008,32(6)：46-50
[15]韩彬,周京阳,崔晖,李晓磊.引入SO2排放惩罚价格因子的节能减排发电调模型及实用算法.电网技术,2009,33(9)：50-54
[16]Lu Bo, Shahidehpour M. Unit commitment with flexible generating units. IEEE Transactions on power systems,2005,20(2):1022～1034
[17]马瑞.电力市场中兼顾环境保护和经济效益的双目标模糊优化短期交易计划.中国电机工程学报,2002,22(14)：104-108
[18]张利,赵建国,韩学山.考虑网络安全约束的机组组合新算法.电网技术,2006,30(21)：50～55
[19]Grey A, Sekar A. Unified solution of security-constrained unit commitment problem using a linear programming methodology. IET Generation Transmission & Distribution,2008,2(6):856～867
[20]Lee FN, Huang J, Adapa R. Multi-area unit commitment via sequential method and a DC power flow network model. IEEE Transactions on Power Systems, 1994,9(1):279-287
[21]Ma H, Shahidehpour S M. Unit commitment with transmission security and voltage constraints. IEEE Transaction on Power System,1999,14(2):757～ 764
[22]Senjyu T, Shimabukuro K, Uezato K, et al. A fast technique for unit commitment problem by extended priority list. IEEE Transactions on power systems,2003, 18(2):882～888
[23]黎静华,韦化.求解机组组合问题的领域搜索法.中国电机工程学报,2008,28(13)：33～39
[24]黎静华,兰飞.适合于机组组合问题的扩展优先顺序法.电力系统保护与控制,2010,38(02)：1-7
[25]Bosch V D, Honderd G. A Solution of the Unit Commitment Problem via Decomposition and Dynamic Programming. IEEE Trans on Power Apparatus and Systems,1985(7):104-115
[26]Nieva R, Inda A, Guillen I. Lagrangian Reduction of Search-Range for Large Scale Unit Commitment. IEEE Transactions on power systems,1987(2):2 ～15
[27]王成文,韩勇,谭忠富,等.一种求解机组组合优化问题的降维半解析动态规划方法.电工技术学报,2006,21(5)：110-116
[28]Shih-Yih Lai, Ross Baldick. Unit Commitment with Ramp Multipliers. IEEE Transactions on power systems,1999,14(1):58 ～ 64
[29]Weerakorn Ongsakul, Nit Petcharaks. Unit Commitment by Enhanced Adaptive Lagrangian Relaxation. IEEE Transactions on power systems,2004,19(1):620～ 628
[30]Wang SJ, Shahidehpour S M, KirschenDS, and etal. Short term generation Scheduling with transmission and environmental constraints using an augmented Lagrangian relaxation. IEEE Transactions on power systems,1995,10(3):1294～ 1301
[31]苗青,曹广益,朱新坚.基于集结投影次梯度的机组组合算法研究.计算机仿真,2008,25(2)：245-247,302
[32]Miguel Carrion, Jose M. Arroyo, A Computationally Efficient Mixed-Integer Linear Formulation for the Thermal Unit Commitment Problem. IEEE Transactions on power systems,2006,21(3):1371～1378
[33]Venkatesh B, Jamtsho T, Gooi H B. Unit commitment-a fuzzy mixed integer Linear Programming solution.Generation, Transmission & Distribution, IET, 2007,1(5):836～846
[34]高山,单渊达.遗传算法搜索优化及其在机组启停中的应用.中国电机工程学报,2001,21(3)：45-48
[35]Yang H, Yang P, Huang C. A parallel genetic algorithm approach to solving the unit commitment problem:implementation on the transporter networks. IEEE Transactions on power systems,1997,12(2):661 ～ 668
[36]赵波,曹一家.电力系统机组组合问题的改进粒子群优化算法.电网技术,2004,28(21)：6-10
[37]Walsh M P, Omalley M J. Augmented hopfield network for unit commitment and economic dispatch. IEEE Transactions on power systems,1997.12(4): 1765-1774
[38]Annakkage U D, Numnonda T, Pahalawaththa N C. Unit commitment by parallel simulated annealing Generation. IEE Proceedings Generation, Transmission & Distribution,1995,142(6):595 ～ 600
[39]Keles A, Etaner-Uyar A S, Turkay B. A differential evolution approach for the unit commitment problem.5th International Conference on Electrical and Electronics Engineering, Bursa,2007:132～135
[40]刘可真,高峰,束洪春,等.一种实用的机组最优启停计划方法.昆明理工大学学报(理工版),2002,27(1)：73-77
[41]陈烨,赵国波,刘俊勇,等.用于机组组合优化的蚁群粒子群混合算法.电网技术,2008,32(6)：52-56
[42]Chuan-Ping Cheng, Chih-Wen Liu, Chun-Chang Li. Unit Commitment by Lagrangian Relaxation and Genetic Algorithms. IEEE Transactions on power systems,2000,15(2):707～714
[43]陈皓勇,张靠社,王锡凡.电力系统机组组合问题的系统进化算法.中国电机工程学报,1999,19(12)：9-13,40
[44]王楠,张粒子,舒隽.基于粒子群修正策略的机组组合解耦算法.电网技术, 2010,34(1)：79-83
[45]刘自发,张建华.一种求解电力经济负荷分配问题的改进微分进化算法.中国电机工程学报,2008,10(28)：100-105
[46]王锡凡,王秀丽,陈皓勇.电力市场基础.西安：西安交通大学出版社,2003：80-82
[47]李朝安.发电厂及电力系统经济运行.乌鲁木齐：新疆人民出版社,1985：196-197
[48]廖培鸿.发电厂的计算机控制.北京：水利水电出版社,1987：160-161
[49]夏道止.电力系统分析.北京：中国电力出版社,2004：8-9
[50]杜松怀,温步赢,蒋传文.电力市场.北京：中国电力出版社,2004：160-163
[51]王锡凡.电力系统规划基础.北京：中国电力出版社,1994：140-141
[52]张伯明,陈寿孙.高等电力网络分析.北京：清华大学出版社,1996：187-190
[53]Fu Y, Shahidehpour M, Li Z. AC Contingency Dispatch Based on Security-Constrained Unit Commitment. IEEE Transactions on power systems,2006, 21(2):897～908.
[54]邢文训,谢金星编.现代优化计算方法著.北京：清华大学出版社,2005：231-235
[55]Merlin A, Sandrin P. A new Method for Unit Commitment at Electricite De France. IEEE Transactions on Power Systems,1983,102(5):1218-1225
[56]Storn R, Price K. Minimizing the real functions of the ICEC'96 contest by differential evolution.1996 IEEE Evolutionary Computation conference, Nayoya, Japan,842～844
[57]Ching-Tzong Su, Chu-Sheng Lee.Network reconfiguration of distribution systems using improved mixed-integer hybrid differential evolution. IEEE Transactions on Power Systems,2003,18(3):1022～1027
[58]Ji-Pyng Chiou, Chung-Fu Chang, Ching-Tzong Su. Ant direction hybrid differential evolution for solving large capacitor placement problems. IEEE Transactions on Power Systems,2004,19(4):1794～1800
[59]Anyong Qing. Dynamic differential evolution strategy and applications in electromagnetic inverse scattering problems. IEEE Transactions on Geosciences and Remote Sensing,2006,44(1):116～125
[60]韦化,吴阿琴,白晓清.一种求解机组组合问题的内点半定规划方法.中国电机程学报,2008,28(1)：35-39
[61]Valenzuela J, Smith A E. A seed memetic algorithm for large unit commitment problems. Journal of Heuristics,2002,8(2):173～195
[62]Kazarlis S A, Bakirtzis A, Petridis V. A genetic algorithm solution to the unit commitment problem. IEEE Transactions on power systems,1996,11(1):83～ 92
[63]工喆,余贻鑫,张弘鹏等.社会演化算法在机组组合中的应用.中国电机工程学报,2004,24(4)：12～17