《机组组合问题的模型及算法综述.pdf》由会员分享，可在线阅读，更多相关《机组组合问题的模型及算法综述.pdf（13页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2 8 卷第6 期2 0 1 1 年1 2 月现代电力M o d e mE l e c t r i cP o w e rV 0 1 2 8N o 6D e e 2 0 1 1文章编号：1 0 0 7 2 3 2 2(2 0 1 1)0 6 0 0 0 1 1 0文献标志码：A机组组合问题的模型及算法综述黎静华，兰飞(广西大学电气工程学院，广西南宁5 3 0 0 0 4)中图分类号：T M 7 3 2T h eO v e r v i e wo nM o d e l sa n dA l g o r i t h m sf o rU n i tC o m m i t m e n tP r o b l
2、 e m sL IJ i n g h u a，L A NF e i(S c h o o lo fE l e c t r i c a lE n g i n e e r i n g，G u a n g x iU n i v e r s i t y，N a n n i n g5 3 0 0 0 4，C h i n a)摘要：机组组合问题是电力系统优化运行的重要组成部分。在总结传统的机组组合数学模型及经典求解方法的基础上，深入分析了近年来考虑环保、安全、市场及随机性等因素的机组组合模型的特点和意义，详细评述了智能类(如优先顺序法)、数学规划类(如分枝定界、动态规划)、元启发类(如遗传算法、粒子群算法)
3、等各种求解方法的原理、所取得的研究成果及不足之处，介绍了近年来出现的如整数辨识、社会演化、邻域搜索及模式搜索等求解方法的特点，并总结了现有较具代表性的混合整数规划数学软件G A M S 和C P L E X 的优缺点。最后，探讨了未来适应于智能电网的机组组合的发展方向，提出了机组组合尚需研究和解决问题，希望能为机组组合问题的研究者提供参考。关键词：机组组合；混合整数规划；节能调度；智能电网A b s t r a c t：U n i tc o m m i t m e n ti sa ni m p o r t a n tc o m p o n e n to fp o w e rs y s t e
4、mo p t i m a lo p e r a t i o n B a s e do nt h es u m m a r yo ft h et r a d i t i o n a lm a t h e m a t i c a lm o d e la n dt h ec l a s s i c a ls o l u t i o nm e t h o do fu n i tc o m m i t m e n t，t h ec h a r a c t e r i s t i c sa n ds i g n i f i-c a n o eo fu n i tc o m m i t m e n tm o
5、 d e li sa n a l y z e di n-d e p t hb yc o n s i d e r i n gs u c hf a c t o r sa se n v i r o n m e n t a l，s e c u r i t y，m a r-k e t，r a n d o mf a c t o r sa n ds oO i l D e t a i l e dr e v i e wo ft h ep r i n-c i p l e s，r e s e a r c h e sa n ds h o r t c o m i n g so fe a c ha p p r o a c
6、 h，s u c ha st h ei n t e l l i g e n c em e t h o d(s u c ha sp r i o r i t ym e t h o d)。m a t h e m a t i c a lp r o g r a m m i n gm e t h o d(s u c ha sb r a n c ha n db o u n d，d y n a m i cp r o g r a m m i n g)，m e t a-h e u r i s t i cm e t h o d(s u c ha sg e-n e t i ca l g o r i t h m s，p
7、 a r t i c l es w a r mo p t i m i z a t i o n)a n do t h e rm e t h o d s，i sc a r r i e do u ti nt h i sp a p e r T h e nt h ec h a r a c t e r i s t i c so fs o l v i n ga p p r o a c h e st h a ta r ep r o p o s e dr e c e n t l y，s u c ha si n t e g e ri d e n t i f i c a t i o n，s o c i a le v
8、 o l u t i o n，n e i g h b o r h o o ds e a r c ha n dp a t t e r ns e a r c hm e t h o d sa r ei n t r o d u c e d I na d d i t i o n，t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h ee x i s t i n gm i x e di n t e g e rp r o g r a m m i n gs o f t w a r eG A M Sa n dC P L E Xa r es u
9、m m a r i z e d I nt h ee n d，t h ef u t u r eo fu n i tc o m m i t m e n tw h i c hi ss u i t a b l ef o rs m a r tg r i di si n v e s t i g a t e d，a n di s s u e so fu n i tc o m m i t m e n tt h a tn e e dt ob es t u d i e da r eg i v e n，w h i c hp r o v i d e sr e f e r e n c e st or e s e a r
10、 c h e r so fu n i tc o m m i t m e n t K e yw o r d s：u n i tc o m m i t m e n t；m i x e di n t e g e rn o n l i n e a rp r o g r a m m i n g；e n e r g y s a v i n gg e n e r a t i o nd i s p a t c h i n g；s m a r tg r i d0 引言机组优化组合问题一直是电力系统研究中的热点和难点。多年来，研究者对机组组合的模型及求解方法进行了大量的研究，提出满足不同系统及运行要求的数学模型。
11、由于机组组合问题属于大规模的非线性混合整数变量动态优化模型，数学上难以求得精确最优解，几乎所有的优化方法均被运用于求解机组组合模型，如优化顺序法、分枝定界法、割平面法、动态规划法、拉格朗日乘子法、奔德斯分解法、遗传算法、粒子群优化算法等等。文献 1，2 对经典的机组组合求解方法进行了深入的探讨，并加以分类综述。文献 3 针对目前我国节能减排的要求，总结已有节能调度的模型和实现方法，分析了现有节能调度模型的不足与I 口J 题。近些年来，电力工作者根据处理混合整数规划问题数学理论及方法，相继构建了许多新的求解模型。此外，为了实现节能绿色发电，适应智能电网的发展，机组组合模型也E l 趋丰富和完善。
12、基于此，本文在总结早期传统的机组组合模型及经典的求解方法的基础上，深入研究近年来国内外出现的新模型及新方法，探讨未来机组组合发展的方向以及亟待解决的问题，使之适应智能电网的发展，制定满足安全、节能、环保和经济的发电计划。1 模型的发展基金项目：国家自然科学基金(5 0 9 0 7 0 1 2)随着电力工业的发展和社会的进步，研究者根现代电力，2 0 1 1，2 8(6)h t t p：x d d l n c e p u e d u c nE-m a i l：x d d l v i p 1 6 3 c o r n万方数据2现代电力2 0 1 1 年据实际系统的不同要求，建立满足不同需求的机组组合
13、模型，反映了机组组合的评价标准和系统运行环境的演变。下面从目标函数和约束条件两方面进行阐述机组组合模型的发展过程。1 1目标函数的演变机组组合问题的目标函数在很长一段时间内一直是系统的运行费用最小，主要包括发电成本、启动成本及运行维护费用 4-7 。随着电力工业市场化改革后，由基于成本的发电竞争所取代，目标函数演绎为购电成本最小，或反映资源配置效率的社会总收益最大。文献 8 将系统旋转备用的效益与发电成本费用的差值即比较效益最大作为目标函数，从而适应电力市场的需要。文献E 9-针对“一机一价”的市场模式，将目标函数表示为所有机组的电费之和最小，适应不同电价机制。文献E l O-则以系统竞价机组
14、的运行价值之和最大作为目标函数。为了满足含风电等分布式电源的要求，文献E l l-出现了期望值最小的目标函数。文献 1 2 给出了一种包含太阳能、风能、水能、热电联供等多种电源运行成本最小的目标函数。在节能发电模式下，文献E 1 3-在模型中同时计及最优权机组组合的经济陛和可靠性目标，文献E 1 4 提出一种考虑环境效益和经济效益的电力市场短期交易计划新模型。文献E 1 5 考虑最优机组组合的费用最小和所需旋转备用最小为目标。而文献E 1 6-则采用排放价格因子将系统总能耗最小和总排放量最小的多目标转化为单目标函数。1 2 约束条件传统的机组组合模型中考虑的约束有：系统功率平衡约束；系统备用约
15、束；机组的出力限制；爬坡约束；开停机时间限制。传统的模型难以反映实际运行状况，为了得到更符合系统实际运行要求的发电计划，机组组合中考虑的约束条件越来越多，机组动态技术约束、环境约束、网络安全约束和市场约束等约束条件相继出现在机组组合模型中。具体可分为如下几类：1 2 1 考虑环境因素模型随着社会生活水平的提高，人们对环境质量的要求也越来越高，近年来世界各国相继出台了一系列环境保护的法律，其中对发电企业排放的要求主要是限制S O：和N q 的排放总量。文献E 1 7 3 将污染气体排放与发电成本同时作为目标函数，提出不同区域不同权重系数的控制方案，以达到全网污染气体排放总量减少的效果。文献E 1
16、 8 3 建立了包括排污收费环境成本在内的火电机组单位发电量成本模型，计算了特定情形下我国常见各类火电机组的计及环境成本的单位供电成本。文献 1 4 7 提出一种同时考虑效益环境和经济效益的新模型，并基于模糊理论将多目标问题转化为单目标非线性问题进行求解，从而获得经济环保的交易计划。1 2 2 考虑随机因素模型在机组组合中考虑旋转备用，其目的是应付不确定事件的发生，如负荷预报的偏差、机组可能发生的故障停运、线路故障引起的潮流转移等。为了解决此类问题，不少文献对机组组合问题的不确定性因素进行了研究。文献-1 9-将系统的可靠性引入机组组合模型中，建立综合考虑可靠性成本及负荷不确定性的机组组合随机
17、模型进行求解分析。文献E z o-提出综合考虑发电系统可靠性和旋转备用效益的机组组合的模型和方法。文中以旋转备用的比较效益最大为目标函数，通过概率评估方法，利用系统投运风险度确定机组投运台数，依据系统响应风险度确定旋转备用的分布。文献E 2 1-在模型中考虑机组投运风险水平限制，将投运风险度约束以解析表达的方式引入机组组合的拉格朗日松弛法中，实现了概率备用约束的机组组合问题。文献 2 z-考虑负荷的不确定性对调度计划的影响，在模型中引入机会约束，并采用L R 与蒙特卡洛方法进行求解。电力市场价格等的不确定性也影响着日发电调度计划的制定，文献E 2 3 3 建立考虑竞价策略风险的机组组合模型，使
18、所制定的调度计划计及该风险。此外，随着智能电网的建设和发展，随机性强的分布式发电的引入，也是制定日发电计划的不确定因素之一，文献E 2 4 建立风一火混合系统的机组组合随机模型，并采用粒子群优化算法进行求解。1 2 3 考虑网络安全因素模型发电计划必须与网络的传输能力相协调才能使这一计划得以实施。特别是市场机制的驱使下输电网越来越接近于安全极限，运行规划受网络的约束(如线路潮流，节点电压等)愈加明显。若不考虑最现代电力，2 0 1 1，2 8(6)h t t p：x d d l n c e p u e d u c nE-m a i l：x d d l v i p 1 6 3 c o m万方数据
19、第6 期黎静华等：机组组合问题的模型及算法综述3优潮流等确定的发电水平可能与机组投入设想的水平有很大的偏离，从而使机组最优投入计划在一定程度上失去了意义。因此，必须在机组投入研究中考虑网络约束，进一步寻求机组最优投入与安全经济调度的组合优化，从更高层次上找到最优的运行规划。文献 2 5 是早期考虑安全约束机组组合问题的文章，其将电压和无功约束引入传统的机组组合模型中。文献 2 6 以直流潮流模型为基础，将计及电网静态安全约束的机组组合问题分解为无安全约束的机组组合问题和计及电网静态安全约束的优化潮流问题2 个子优化问题。文献E 2 7 提出了考虑直流潮流和电网安全约束的短期经济调度，在模型中考
20、虑了节点电压和输电线路容量限制等安全约束。文献E 2 8 考虑基于交流潮流模型的安全稳定约束，即含最优潮流(O P F)的机组组合模型，从而更准确地反映实际系统情况，缩小所制定计划与实际运行情况的差距，提高实际运行的安全稳定性。文献 2 9 建立含事故前和事故后两个阶段的安全稳定约束的机组组合模型，充分考虑故障过程的机组开停变化。文献 3 0 建立了含交直流混合系统的机组组合模型，为制定含交直流混合系统的安全稳定的调度计划提供理论依据。1 2 4 考虑市场因素模型随着电力市场的深化改革，人们开始考虑含市场因素的调度计划的制定。文献 3 1 将辅助服务需求和合同约束引入机组组合模型。文献 3 2
21、 提出一种基于竞价机组运行价值的机组组合新模型，兼顾了各竞价机组运行的经济性和可靠性，制定出公平合理的发电计划制定。文献 3 3 建立一种考虑能源的出清价格和辅助服务费用的机组组合模型。文献 3 4 对电力市场环境下的机组组合的模型和方法进行全面的阐述，分析电力市场各因素及特点，建立反映电力市场运行的机组组合模型，为实现公平、公开和公正的日调度计划的制定奠定了理论基础。1 2 5 考虑分布式电源的模型随着我国水电建设规模日益扩大，含有多河流、多梯级且河流有分支的大规模水电厂的水火联合电力系统相应增加。人们研究在机组组合模型中加入水系方程，充分利用水资源，避免和尽量减少弃水，最大限度地节省火电燃
22、料成本。随着我国电源结构的调整和节能环保发电计划的实施，建立合理可行的含分布式电源的机组组合模型是一个重要的发展方向。文献 3 5 建立含风力发电机组运行约束的机组组合模型，考虑了风能的随机性对制定调度计划的影响。文献 3 6 针对分布式发电的特点，提出了一种新的含多种复合能源的分布式发电系统的机组组合综合模型。综上所述，为了更精确地模拟实际运行，机组组合模型E l 趋完善和复杂。但是，值得注意的是，机组组合模型发展的模式基本是在原有或传统的模型基础上增加约束条件，扩大模型的规模，这样通过简单堆砌得到的数学模型不仅加大求解的难度，且会影响解的质量，损害所制定的运行方式的质量。因此，研究实际系统
23、的运行需求，建立合适可行的机组组合模型，制定出优质的调度方式是实现机组优化调度的关键。2 求解方法的发展，迄今为止，几乎所有的数学方法均用于求解机组组合问题。下面将全面阐述用于求解机组组合模型的方法，以供学习参考。2 1 经典求解方法2 1 1 优先顺序法优先顺序法(P r i o r i t yL i s tM e t h o d，简称P L)包含顺序投入法(S e q u e n t i a lU n i tC o m m i t m e n tM e t h o d，简称S U C)和逆序切除法两种(U n i tD e c o m m i t m e n tm e t h o d，简称
24、U D)两种。2 1 1 1 顺序投入法(S U C)传统的顺序投入法是按照平均满负荷费用(A v e r a g eF u l lL o a dC o s t，简称A F L C)指标从小到大进行排序。确定组合时，在不违反机组的最小停机时间约束的情况下依次投入机组，直到满足负荷和备用的要求。该方法简单且易于实现。但是，由于机组的排序指标未能考虑启停费用及爬坡速率等运行约束，因此当机组偏离满负荷运行时，A F L C指标不能完全反映发电机组的运行费用。为此，在文献E 3 7 中，B u r n s 等人提出了一种考虑系统变化的动态优先顺序法；S h o u l t s 等人在文献E 3 8 中
25、提出能综合考虑了平均满负荷费用和平均开机费用的排序指标的制定方法；L e e 在文献 3 9 中提出一种将平均满负荷费用指标和投入利用因子(C o m m i t m e n tU t i l i z a t i o nF a c t o r，简称C U F)相结合的排序指标的定义方法，取得了良好的效果。2 1 1 2 逆序切除法(U D)现代电力，2 0 1 1，2 8(6)h t t p：x d d l n c e p u e d u c nE-m a i l：x d d l v i p 1 6 3 c o r n万方数据4现代电力2 0 1 1 年与顺序投入机组相反，逆序切除法首先将所有
26、可调度机组的状态置为“1”，在不违反机组的最小开机时间情况下，按照排序指标从高到低依次切除机组，直到不存在冗余的备用。CL T s e n g 在文献E 4 0 3 中通过数值测试指出，U D 是一种有效、可靠和快速的求解方法。C L T s e n g 在文献 4 1 、C 一A L i 在文献E 4 2 中采用逆序切除法去除拉格朗日松弛方法(L a g r a n g i a nR e l a x a t i o nM e t h o d，简称I。R)所求得组合中的冗余机组，从而获得更经济的解。山东大学韩学山教授在文献 4 3 中，将U D 算法与I。R 方法相结合，一方面采用逆序切除法消
27、除冗余机组，另一方面根据L R方法对偶问题的性质计算每台机组的运行指标，动态地选择最不经济的机组将其停运。优先顺序法是一种简化的算法，从理论上说不一定是最优的，但是对实际工程应用而言，所得结果较接近最优组合方案，且具有计算量小，易于实现等特点。2 1 2 动态规划法动态规划法(D y n a m i cP r o g r a m m i n g，简称D P)是研究多阶段决策过程最优化的一种数学的方法。其将每个调度时间段称为一个阶段，机组在一个时段内的组合称为状态，决策过程就是通过评估从某一时段开始到下一时段所有满足约束的机组组合的经济性，并从中选择费用最小的组合作为下一时段机组状态的过程，从而
28、上一时段机组的状态影响了下一个时段机组状态的决策。尽管动态规划法在规划过程中抛弃了不可行的组合，但是可行解的组合依然很庞大。近年来，人们开始采用分解技术方法将机组组合问题化为多个规模较小的子问题，然后用动态规划方法分别求解各子问题。文献 4 4 ，采用拉格朗日算法(I。R)将S C U C 机组组合问题进行分解，用D P 算法求解子问题。文献7 4 5 将拉格朗日(L R)，邻域搜索(L S)和动态规划(D P)相结合，首先用I。R 求解机组组合问题的对偶问题，根据求解的结果，采用启发式规则构造一可行解，并采用L S 方法获取该可行解的邻域，最后采用D P 在所得邻域进行求解，从而更进一步缩小
29、D P 的求解空间。此类方法涉及与其他方法的结合，有待进一步的研究及发展。2 1 3 拉格朗日松弛法拉格朗日算法(L a g r a n g i a nR e l a x a t i o n，简称L R)是目前求解大规模U C 问题比较有效的方法之一。1 9 7 7 年，M u c k s t a d tJ A 在文献 4 6 最早将L a g r a n g i a n 对偶分解原理应用于求解机组组合问题。然而，M u c k s t a d t 算法是以分枝定界为基本框架的，拉格朗日函数仅是用于确定分枝树上每个节点的最优下限。真正适合于大规模U C 问题求解的拉格朗日松弛法是由M e r
30、l i n 八和S a n d r i nP 于1 9 8 3 年在文献 4 7 中提出。其基本思想是利用D a n t z i g-W o l f e 对偶分解理论，把大规模问题分解为N 个维数较小的子问题进行有效求解。然而L R松弛法的解依赖于拉格朗日乘子的修正策略。因此，设定一个好的拉格朗日乘子的初值及修改策略对获取最优解具有重要意义。不恰当的拉格朗日修正策略会导致迭代在最优解附近发生振荡，从而不能得到最优解。目前，常见的拉格朗日乘子的修正方法有两类：次梯度法和智能方法。如文献 4 8 采用进化算法(E v o l u t i o n a r yP r o g r a m m i n g
31、，简称E P)调整拉格朗日乘子，文献E 4 9 采用遗传算法(G e n e t i cA l g o r i t h m s，简称G A)进行拉格朗日乘子的修正以获得更好的结果。文献E 5 0 基于光束方法(B u n d l eM e t h o d)进行拉格朗日乘子的调整。此外，当系统中具有耗量特性相同或相似机组时，L R 算法易过量投入机组，从而导致备用的冗余及运行成本的升高。这是由于L R 算法主要依靠比较拉格朗日乘子与机组的耗量系数之间的大小确定机组是否投入。2 1 4B e n d e r s 协调分解法1 9 6 2 年，J F B e n d e r s 首次提出B e n
32、d e r s 分解方法，用于求解混合整数规划问题。1 9 7 2 年，为了使B e n d e r s 分解算法能处理更广泛的规划问题，八M G e r f f r i e n 将B e n d e r s 分解做了更进一步的推广，称为广义B e n d e r s 分解法。广义B e n d e r分解方法主要思想是通过解耦决策变量，将原问题分解为主问题和子问题；将主问题的最优解传递给子问题，然后保持该主问题的最优解不变，解子问题；用子问题的解的信息构造新的约束的形式(称为B e n d e r s 割集)添加到主问题的约束中，逐步压缩主问题的搜索空间；交替求解主问题与子问题最终得到最优解
33、。目前，B e n d e r s 分解技术已在电力系统机组组合方面有广泛的应用。H H a b i b o l l a h z a d e h 在文献1 5 1 1 采用B e n d e r s 分解求解水火联合系统的短期运行计划的制定问题，文中将大规模的水火联合系统解耦为离散和连续两部分，主问题仅包含离散变现代电力，2 0 1 1，2 8(6)h t t p：x d d l n c e p u e d u c nE-m a i l：x d d l v i p 1 6 3 c o r f l万方数据第6 期黎静华等：机组组合问题的模型及算法综述5量，且仅考虑火电机组的开停组合，子问题求解仅
34、含连续变量的经济调度问题。通过主问题确定机组的开停状态，将其代入子问题求解对应的最经济负荷分配，然后将根据所得的负荷分配结果形成B e n d e r s 割约束添加到主问题中，交替求解主子问题得到最终解。Y o n gF u 5 2 将B e n d e r s 分解技术用于求解考虑安全约束的机组组合问题(s e c u r i t y-c o n s t r a i n e du n i tc o m m i t m e n t，简称S C U C)。H M a 基于B e n d e r s 理论将含无功约束的机组组合分为仅含离散变量(即机组的开停状态)和考虑无功约束的经济调度两部分，交
35、替求解满足无功要求的机组组合问题L 5 引。C o n gL i u 将B e n d e r 分解技术用于求解含两阶段安全约束(故障前阶段和故障后阶段)的问题，取得较好的解。W i l f r e d oS S i g u e n t e s采用B e n d e r s 分解技术求解含O P F 约束的水火混合系统的机组组合问题 5 4 ，与文献 5 1 分解方式不同，其主问题不仅含火电机组离散变量，且包括水火电机组出力变量，属于混合变量的线性规划问题。近年来，学者们开始将B e n d e r s 分解用于求解含交直流系统 55|，风力发电 4 2 及多种运行方式下f l e x i b
36、 l eg e n e r a t i n gu n i t s c 4 3 等各种机组组合问题，收到良好效果。然而，B e n d e r s 分解仍然存在一些问题，针对实际大规模的电力系统存在计算量过大的问题，且构造恰当、适用的B e n d e r s 割存在一定的难度，且其对目标函数的性态有一定的要求，因此，适用于实际电力系统的B e n d e r s 分解算法还需要进一步研究。2 1 5 分枝定界法理论上，分枝定界法能精确地求解混合整数规划问题。如何构造分枝策略及获取下界是分枝定界的关键，文献 5 6 结合机组运行的部分约束形成分枝和剪枝的策略，大大缩小了解的空间，提高计算效率。但
37、对于大规模的实际系统，应用分枝定界法直接计算非常困难，往往需要采用简化和分解的技术。因此，文献 5 7 将分枝定界法与拉格朗日算法相结合，先利用I。R 将原问题分解为规模较小的子问题，再采用分枝定界法对子问题进行求解，从而节约计算时间。由于分枝定界法比较复杂，需要根据实际问题构造剪枝定界的策略，且对于机组数目较多的系统需要对问题进行简化及分解，在一定程度上阻碍了其在实际工程中的应用及发展。2 2 仿生物智能方法2 2 1 粒子群优化算法1 9 9 5 年，J K e n n e d y 和R C E b e r h a r t 在他们提交给I E E E 神经网络国际会议的论文中首次提出了粒子
38、群优化算法(P a r t i c l eS w a r mO p t i m i z a-t i o n，简称P S O)。其主要有两种求解方式：将机组启停状态(离散变量)和机组的出力(连续变量)同时进行优化和将机组组合问题分解为机组启停优化和经济调度两个子问题分层进行优化。为了加快收敛速度，提高搜索效率，许多学者结合机组组合问题的工程特点，对P S O 算法进行改进。文献 5 8 通过构造“无希望重希望”准则，限制粒子群在可行域内的变化，克服局部最优点的束缚，增强了全局搜索能力。文献 5 9 提出一种能综合反映机组启停状态及机组出力的伪编码方式，通过对机组状态的动态调整及机组出力约束、爬坡
39、约束等的修复，整体优化多时段的机组组合问题。文献 6 0 3 在算法中引入基于机组优先顺序的变异技术和修补策略，有效解决机组最小启停时间约束，提高算法的全局寻优能力。文献 6 1 根据投入机组的数目变化，动态改变粒子群优化空间的维数，从而缩减优化变量的维数，提高计算效率。此外，不少文献将P S O 与其他算法相结合进行求解。如文献 6 2 采用P s()方法与模拟退火算法(S i m u l a t e dA n n e a l i n g，简称S A)。文献 6 3 采用P S O 算法与蚁群算法相结合。文献-6 4 1 采用P S O 算法与遗传算法(G A)相结合。2 2 2 遗传算法遗
40、传算法(G e n e t i cA l g o r i t h m，简称G A)是一种模拟生物界自然选择及遗传机理的高度并行、随机搜索和自适应的寻优方法。其具有如下优点：从多个初值开始，能以较大的概率获取全局最优解；鲁棒性能好，其不要求目标函数连续可微；可方便用于处理含混合整数变量的复杂非线性问题。由于遗传算法具有上述特点，在机组组合问题上有着广泛的应用。然而当适应度函数选择不当时，遗传算法容易收敛于局部最优，且算法中的交叉及变异操作极为重要。为此，学者们对标准G A算法进行了改进。文献 6 5 采用压缩映射传算法(c m G A)，根据B a n a c h 压缩映射定理，如果某一代种群的
41、平均适应值相对于上一代没有得到增长，则不直接进入下一代，而是反复应用遗传算子处理现代电力，2 0 1 1，2 8(6)h t t p：x d d l n c e p u e d u c nE-m a i l：x d d l v i p 1 6 3 c o r n万方数据6现代电力2 0 1 1 年种群，直到种群的平均适应值得到增长才进入下一划问题。系统决策变量包括了离散和连续变量；每代，从而提高G A 算法收敛到最优解的能力。文献台机组都有各自的运行约束和物理约束。因此，这 6 6 在进化过程中基于拉马克理论(L a m a r c kt h e 一一问题在数学上是一个复杂的混合整数规划问题。
42、o r y)构建更好的染色体，从而改善G A 算法的收敛G A M S 和C P L E X 是常被用来求解混合整数规划的性。文献 6 7 采用3 种并行计算的方法对遗传算两种技术软件，推广了其求解策略。法的机组组合问题的计算，提高计算的速度。2 4 1G A M S为了提高G A 算法的搜索速度，往往将G A 算通用数学模型系统(G e n e r a lA l g e b r a i cM o d e l 一法与其他算法相结合，取长补短。文献 6 8 3 采用i n gS y s t e m，简称G A M S)是世界银行与美国G A 算法与T a b u 搜索算法相结合，结合G A 算法
43、G A M S 公司在2 0 世纪9 0 年代初开发的一种旨在建的大规模寻优特性与T a b u 搜索的强局部搜索能立和解决大型复杂数学规划问题的高级计算机软力，较大地减少了算法陷入局部最优的概率，快速件。G A M S 模型与算法独立，可以让使用者迅速搜索到高质量的系统优化解。文献 6 9 3 采用G A建立模型且容易修改。G A M S 让使用者把精力集算法与S A 算法相结合，用S A 算法判断变异操作中到建模上，排除考虑纯技术上的编程问题。是否有效，以提高种群的多样性，防止算法早熟。在数值算法方面，对M I N L P 问题，G A M S 有文献 7 0 3 将G A 算法与L R
44、算法相结合，将复杂效的方法有M I N O S(M o d u l a rI n-c o r eN o n-l i n e-a r问题分解为一系列的简单子问题，形成多层优化问O p t i m i z a t i o nS y s t e m)和Z O O M(Z e r o O n eO p t-题，采用次梯度法优化拉格朗日乘子，对单台机组i m i z a t i o nM e t h o d)算法。M I N O S 是由新南韦尔斯的子问题采用遗传算法求解，两者交替迭代进行求大学的M u t r a g h、及史丹福大学的G i l l、M a r r a y、解。S a u n d e
45、 r s、W r i g h t 等人所发展的算法。Z 0 0 M 是遗传算法本质上属于无约束优化算法，如何处由亚力桑那大学M a r s t e n 及巴尔第摩大学S i n g h a l理约束条件很大程度上影响算法的效率，且由于是共同发展的算法。随机优化算法，计算量大、时间长，不能保证得到G A M S 虽然允许用户改变求解器的默认参数局部最优解。设置选项，但是不允许用户在M I N O S 中选择具体2 3 新方法新技术算法来求解非线性问题。M I N O S 通过确定非线性近来，机组组合的研究开始从单纯的数学方法的程度确定使用的算法。如果只有目标函数是非线应用转向对机组组合问题本质的
46、研究。人们开始在性的，它使用缩减梯度法和拟牛顿法的组合。如果运用数学方法的基础上，融合机组组合问题的模型目标函数和约束条件都是非线性的，它使用增广拉特点及电力系统的物理本质，从而提高运算的效格朗日和缩减梯度法的组合。这是G A M S 的主要率。如文献 7 1 3 依据机组组合模型的特点，获得缺点之一。起作用的整数变量辨识方法，有效缩减了机组组合Z O O M 方法采用的策略是固定顺序分枝定界的寻优空间，大幅度提高机组组合计算效率。文献法。在求解子问题之前确定分枝顺序。因此，在同E 7 2 研究含安全约束的机组组合优化模型基础上，一级别的所有子树具有相同的固定变量。该固定顺通过松弛机组的部分约
47、束，提高算法的收敛性能。序分枝定界法使用深度优先的搜索策略来寻找一个文献在研究机组组合物理本质的基础上，构造适合整数解，然后，选择下界值最小的子问题【76 J。M I 一于机组组合问题的邻域，从而缩小求解空间，提高N O S 选择R M I N L P(R e l a x e dN o n-l i n e a rM i x e&I n 一计算效率。文献 7 3 在对通用安全约束机组组合t e g e rs o l v e r)求解器来处理M I N L P 问题。通过松优化模型分析基础上，提出安全约束发电计划的松弛混合整数非线性规划模型的整数条件，M I N L P弛模型，提高算法的鲁棒性，满
48、足工程应用要求。模型被有效地化为非线性规划模型。文献 7 7 发此外，还出现了基于社会演化 74 I、邻域搜索 5 、现Z O O M 的可靠性和有效性比M I N O S 差。模式搜索方法 6 及贪婪随机搜索 7 5 1 等新方法，均Z O O M 的有效性和鲁棒性与问题的整数变量的个取得不错的效果。数高度相关。使用者可能需要通过实验确定发生崩2 4 混合整数规划的求解计算软件溃时的大小。机组组合属于大规模、离散、非线性的数学规2 4 2C P I。E X现代电力，2 0 1 1，2 8(6)h t t p：x d d l n c e p u e d u c aE-m a i l：x d d
49、 l v i p 1 6 3 c o r n万方数据第6 期黎静华等：机组组合问题的模型及算法综述7C P I。E X 数学优化软件是解决资源分配极为苛刻的应用程序开发中线性、混合整数和二次方规划问题的高性能、健壮、灵活的优化软件。包括C P L E X 接口和C P L E X 算法。其中混合整数优化程序对实际的M I P 问题的求解是有效的口8 f。C P L E X 的每个优化器都有许多调整性能的选项。用户可以根据特定问题的需要，对性能进行相应的调整。i l o gc p l e xm i p 优化器采用分枝定界法(b r a n c h-a n d-b o u n dt e c h n
50、 i q u e)求解混合整数规划问题。i l o gc p l e xm i p 优化器可解决混合整数线性规划问题、混合整数二次规划问题和混合整数二次约束规划问题。用户可以自定义设置和参数选项和搜索策略，或选择专门的方法。3 尚需研究的问题从上述对机组组合模型及求解方法的分析总结可知：为了适应未来电力系统的节能发电的推广实施及智能电网的实现，尚需考虑如下几方面问题：3 1 开发大规模的含混合变量的非线性模型的实用和高效的求解方法能、太阳能等随机性强的分布式电源的接入等。因此，如何在模型中考虑随机因素，建立并有效地求解含机会约束的数学模型，亦是亟待解决的主要问题之一。3 5 众多约束的协调处理