马 超，练继建

基于聚类遗传算法的梯级水利枢纽短期电力调度优化

马 超，练继建

(天津大学建筑工程学院，天津 300072)

针对标准遗传算法容易“早熟”的缺陷，提出聚类遗传算法；改进了选择算子和交叉算子，并利用Shubert多峰测试函数验证了聚类遗传算法的优势．引入水轮机组运行效率梯度变化因素提出改进变异算子，弥补了变异搜索过随机的缺陷．最后，将改进方式应用于三峡-葛洲坝梯级水利枢纽短期电力调度优化研究中，提出和构建了相应的优化模型以及机组组合启停和运行效率同步实现策略．实例优化结果表明：聚类遗传算法和改进变异算子能有效弥补“早熟”的缺陷，并能显著提高优化搜索效率，适用于梯级电站电力调度优化问题．优化得出的梯级电力调度方案可以满足设定目标和约束，并提高了梯级的发电效率．

聚类遗传算法；机组运行效率变化梯度；改进变异算子；短期电力优化；三峡-葛洲坝梯级水利枢纽

短期电力调度是梯级水利枢纽运行的重点，其主要涉及梯级间电量分配、水量衔接和电站自身的厂内经济运行3部分任务．其中厂内经济运行需要解决机组组合和启停、机组间有功负荷分配、备用负荷和无功负荷的确定以及合理接入方式等问题[1]．研究资料表明，大、中型梯级水利枢纽开展短期电力优化调度可以提高发电效益1%～7%．作为多维、多时空、多阶段和非线性的难题，应用何种优化方法对梯级水利枢纽短期电力调度进行求解一直是广大学者关注的重点．遗传算法是该研究领域应用范围和效果最佳的主流优化算法[2-6]，鲁棒性强，但存在“早熟”和搜索效率低的缺陷；而且随着梯级规模的增加和调度精度的细化，这种缺陷逐渐显著．针对此问题，本文提出改进遗传算法，包括聚类遗传算法和改进变异算子两部分，并将其应用于三峡-葛洲坝梯级水利枢纽短期电力调度优化研究中．

1 聚类遗传算法

群体早熟或陷入局部最优解是遗传算法较难解决的缺陷，在多峰优化问题中体现尤其明显．研究结果表明，搜索空间和个体表征模式的迅速减少是引起上述缺陷的主要原因，具体表现为：①遗传群体初始化不完善，使得初始群体不能均匀分布在整个可行解空间中，从而导致搜索空间的丢失，同时也奠定了早熟发生的基础；②较差的初始群体导致个体集中处于某些模式或者某部分解空间中，甚至可能集中于适应度值高的局部较优点，在此种情况下，标准选择算子就容易过多地选择属于这些模式或者局部解空间中的个体，从而使得搜索空间和群体模式迅速减少，进而导致“早熟”现象的发生；③如果选择运算后的群体较差，随机选择的母体将极大可能属于同一模式或者局部解空间，从而导致交叉后的新个体与母体在模式或所属空间上完全相同，进而使得搜索空间和群体模式无法得到细化和扩充，进一步加剧“早熟”．综上所述，改进遗传群体初始化以及选择算子和交叉算子是缓解甚至避免早熟或陷入局部最优解缺陷的首要措施．

针对上述问题，借鉴“物以类聚、人以群分”的聚类思想，提出聚类遗传算法(cluster genetic algorithm，CGA)，其基本思想是：在选择和交叉运算前，通过无指导学习的聚类运算[7]对遗传群体进行模式划分和归类，形成遗传子部落．然后通过子部落内部的选择运算和子部落间的交叉运算以及变异运算重新组合形成新一代群体．聚类遗传算法的优势体现为：第一，无指导学习的聚类运算根据群体特征确定其类别数目，寻优开始时的模式数目较多，随着搜索的进行，模式数目逐渐减少，最后达到收敛；第二，对不同子部落单独进行选择运算确保了群体模式的延续，避免了模式集中现象，降低了“早熟”发生的机率；第三，在子部落之间进行交叉运算，容易产生属于新模式的个体，从而扩大了搜索空间和细化了搜索精度，缓解和避免了“早熟”的进一步加剧．

1.1 聚类法则

群体聚类首先必须确定聚类法则．对于梯级水利枢纽短期电力调度优化问题，模型决策变量数目(遗传个体的染色体数目)随着梯级水利枢纽规模的增加而增加．此时，复杂的聚类法则虽然能保证聚类效果，但同时也将大幅度增加聚类计算时间，难以满足时效性要求．基于此，本文提出的聚类法采用个体与解空间某点的距离作为聚类标准．其具体思路为：首先计算遗传群体中各个个体与解空间原点的欧式距离，并对距离进行排序并得出最大距离和最小距离；然后以此为范围划分10个区间段，形成10个群体边界范围；按照距离划分每个个体的群体类型，并设定相应的群体编号和群体内部的个体编号．

1.2 优化流程

聚类遗传算法流程见图1，具体步骤如下所述．

(1)确定个体适应度的量化评价方法和遗传算法的有关运行参数．

(2)利用随机数生成初始遗传群体．

(3)计算个体目标函数值，并将其转化为适应度值．根据适应度大小确定精英个体．

(4)根据设定的聚类法则对群体进行归类，形成遗传子部落，并确定各个部落中的个体数目．

(5)进行聚类选择运算．①如果遗传子部落中只存在单一个体，个体较优则保留，否则直接采用精英个体替代；②如果遗传子部落中只存在2个个体，则从中选择出适应度值较高的个体，并同精英个体一起形成新的遗传子部落；③如果遗传子部落的个体超过2个，则按照轮盘赌方式选择出优良个体形成新的遗传子部落，个体选择数目与原遗传子部落中的个体数目相同．前两种为“入侵”选择方式．

(6)进行聚类交叉运算．产生随机整数对应不同的群体编号和群内个体编号；按照编号选择交叉母体，算术交叉运算形成新的个体．聚类运算后的子群体属性不同，不同子群体的个体间的“距离”明显，因此，可以实现搜索空间和群体模式的细化和扩充．

(7)进行变异计算，形成新一代的群体．

(8)重新计算群体的目标值和适应度值，并修订精英个体．

(9)判定是否满足停止准则，满足则转入步骤(10)，不满足则重复进行步骤(4)～(9)．

(10)优化停止，适应度值最优的个体作为最终优化方案输出．

2 实例验证

以Shubert函数为例，通过对比标准遗传算法(standard genetic algorithm，SGA)、小生境遗传算法(niche genetic algorithm，NGA)和聚类遗传算法(CGA)在多峰函数全局优化问题上的应用效果，分析CGA的优化性能．Shubert函数是一个典型的遗传算法测试函数，其形式为

此函数在可行解空间内存在760个局部最优点和18个全局最优点，全局最优点对应的函数值为-186.731.

3种遗传算法的基本参数为：群体规模200，最大迭代次数100；轮盘赌选择算子，选择概率0.08；算术交叉算子，交叉概率0.6；非均匀变异，变异概率0.08，形状系数3；NGA在进行选择、交叉和变异操作后，再进行小生境淘汰运算，即根据个体之间的欧氏距离确定个体间的相似度；然后两个体逐一比较，当距离小于0.5的距离参数时，适应度较低的个体引入惩罚量0.000,05；淘汰适应度值低的个体形成新一代群体．CGA的子部落数目为10，其他参数与SGA相同．

对3种算法分别进行20次随机模拟，取最优值进行对比分析，具体寻优结果如图2、图3和表1所示．从优化结果可以看出，3种不同的遗传算法都能多次搜索到全局最优解，具有较强的优化性能．但是，聚类遗传算法的结果无论从解的优劣性还是优化时间上来看都优于小生境遗传算法和标准遗传算法的结果．因此，聚类遗传算法具有更好的优化搜索性能，再加上实现原理和编程方式简单，可以很好地满足实际优化问题在性能和速度上的要求，是一种有效的改进遗传算法．

图2 群体收敛过程曲线Fig.2 Convergence curves of genetic population

图3 不同迭代次数的聚类群体空间分布Fig.3 Distribution of cluster population in different iterations

表1 不同遗传算法优化结果Tab.1 Optimized results of different genetic algorithms

3 基于机组效率变化梯度的改进变异算子

标准变异算子随机确定变异方向和步长，随机性强但针对性弱，容易造成无效的搜索．梯级水利枢纽短期电力调度优化问题的遗传个体是由机组时段出力或流量组成的决策链．对水轮机组，在固定发电水头下调整出力(流量)会导致发电效率的提高或降低．这种变化可作为变异方向的判定基准．基于此，提出考虑机组运行效率变化梯度的改进变异算子，其基本思想是：首先根据机组运行特性曲线确定不同水头下的发电效率及其随出力(流量)变化的梯度；在变异计算时，先根据梯度函数确定染色体的变异方向，然后随机确定变异；最后根据变异方向和变异步长完成变异计算．引入机组运行效率变化梯度的变异算子仍然采用随机方式确定个体染色体的变异量，但是根据效率变化梯度确定的变异方向针对性更强，能提高局部搜索的效率，进而使得群体变异朝更优的方向发展．改进变异算子的流程如图4所示．

图4 改进变异算子的计算流程Fig.4 Flow chart of improved mutation operator

变异方向的判定准则如下所述．

(1)假定机组的运行范围为[Pmin，Pmax]，以C为单位步长对其进行离散，总离散数目为D；机组运行水头范围为[Hmin，Hmax]，以C1为单位步长对其进行离散，水头离散数目为E．计算离散出力和水头下的机组运行效率矩阵F[D+1][E+1]，其中将禁止运行区效率降至0，而限制运行区的效率乘以减少系数0.8；C值可以根据机组负荷调整特性确定，如图5所示．

图5 机组运行效率离散示意Fig.5 Discrete schematic of operation efficiency of units

(2)按照机组运行效率矩阵数据，确定机组运行效率变化梯度．即在机组的出力和水头为定值时，判断机组增加出力条件下的效率变化情况，效率增加则记为1，效率降低则记为-1．计算所有离散点得出机组的效率变化梯度矩阵Ft[D][E]和效率变化幅度.

(3)确定机组实际的运行水头和出力，如图6中判断点，计算其与对应4个离散点的欧式距离．根据与其距离最短的离散点的位置确定效率变化梯度矩阵的行号和列号．

(4)确定位置后，机组调整出力存在4种效率变化情况，如图7所示．根据所属情况即可确定最终的变异方向．其中，1号情况为机组出力不变动；2号情况为机组出力随机变动，增加或减少出力都可；3号情况为机组增加出力；4号情况为机组减少出力．

图6 欧式距离法则确定位置示意Fig.6 Sketch map of location by Euclidean distance

图7 4种效率变化情况示例Fig.7 Sketch map of 4 efficiency variations

(5)变异操作分为3类不同状态．理想状态是存在对等数目的应采取增加方向变异或减少方向变异的机组，每对直接引入随机等值变异量即可完成变异操作，保证平衡约束．一般状态是应采取增加方向或减少方向变异的机组数目不同，这种情况下按照出力越大效率越高的原则选择出成对机组，同理每对直接引入随机等值变异量即可完成变异操作并保证平衡约束．不利状态是所有机组都应采取增加方向或减少方向变异的情况，此时除了遵循出力越大效率越高的原则外，应选择单位步长变化引起的效率增幅最大和降幅最小的机组成对，同理每对直接引入随机等值变异量即可完成变异操作并保证平衡约束．

4 三峡-葛洲坝梯级水利枢纽短期电力调度优化研究

三峡-葛洲坝梯级水利枢纽是具有防洪、发电、航运以及供水等综合利用效益的特大型水利水电工程．作为未来国家大电网的中心主导电站，其是实现“西电东送”和“全国电力统一调度”的重要措施．三峡枢纽建成后，三峡-葛洲坝梯级水利枢纽将通过梯级统一调度方式向华中、华东、南方和西南电网供电，承担调峰备用任务．年发电量相当于7座2.6× 106,kW的火电站，可减少燃煤5×107,t，并可少排放碳和硫污染物，降低环境污染危害．实现三峡-葛洲坝梯级优质高效的电力调度是保障电能质量、减少发电成本并提高经济效益的基础．三峡建成后，三峡-葛洲坝梯级水利枢纽将执行先“以水定电”、后“以电定水”的运行策略，即梯级调度中心首先结合预测来水和流域机构下达的水量需求，通过“以水定电”方式评估下一个调度期的发电能力，并将其上报给电网调度中心；电网调度中心根据上报数据，结合电网电力需求和网络安全运行的要求提前给电站下达发电计划；然后梯级电力调度中心将按照电网下达的发电计划执行电力调度运行．基于上述特点，以“以电定水”运行为例，结合聚类遗传算法和改进变异算子开展三峡-葛洲坝梯级水利枢纽短期电力调度优化研究．

4.1优化模型和优化思路

三峡-葛洲坝梯级水利枢纽“以电定水”短期电力调度优化模型的目标函数为发电耗水率最小和发电成本最小两部分，其中发电成本为机组启停成本．模型约束条件包括出力平衡约束、水库水量平衡约束、机组出力约束、水库库水位(库容)约束、电站下泄流量与尾水位关系约束、机组启停约束和最小备用约束7个部分，这里需要强调的是：机组启停约束是根据机组最小允许运行和停机时间来制定的．

机组启停组合和有功负荷分配属于不同类型的优化问题，同步实现两种目标提高了优化计算的复杂度，降低了优化效率和速度．针对此问题，本文提出综合优化策略[8]，其流程如图8所示．首先划分了机组运行类别和机组运行区域类别，并根据机组运行启停要求建立了时段间机组运行状态转换准则；然后按照时段负荷要求(有功出力加旋转备用)、机组时段发电效率、预见性启停机组策略[9]设定各时段机组的运行状态，并建立机组运行启停方案；最后，根据时段机组运行启停方案和机组稳定性运行区域划分结论实现负荷优化分配．

机组类别划分为5个机组．①必开机组：运行时间未满足机组最小运行时间约束的机组．②必停机组：停机时间未满足机组最小停机时间约束的机组．③自由(开)机组：运行时间满足机组最小运行时间约束，下一时段可开、可停的机组．④自由(停)机组：停机时间满足机组最小停机时间约束，下一时段可开、可停的机组．⑤空载机组：机组处于空载导叶开度状态运行，定位为开机不发电机组．

运行机组分为稳定运行区运行机组、限制运行区运行机组和禁止运行区运行机组．

图8 综合优化策略流程示意Fig.8 Flow chart of comprehensive optimization strategies

4.2优化结果和结论分析

为了进行对比，利用标准遗传算法、聚类遗传算法以及聚类遗传算法结合改进变异算子3种不同的算法分别进行优化求解．调度周期为1,d，以0.5,h为单位，计算步长离散为48个时段．算法对比结果和最优的调度方案如表2和图9～图11所示．

分析结果如下．

(1)如图9所示，标准遗传算法在初期(300次前)搜寻的优化效率较高，但是在迭代寻优400次后，优化搜索逐渐缓慢直至停滞，从而陷入局部较优解．对于聚类遗传算法，优化速率虽然在局部迭代次数劣于标准遗传算法，但是优化效率在整个寻优过程中始终呈现平稳延续的特点，最终的群体最优目标值也明显优于标准遗传算法的结果．除此以外，随着迭代次数的增加，优化幅度将进一步扩大．引入基于机组运行效率变化梯度的改进变异算子的聚类遗传算法进一步提高了优化效率，最终的群体最优目标值也优于其他两种遗传算法的结果．综上所述，聚类遗传算法和改进变异算子可以有效地弥补遗传算法“早熟”或陷入局部最优解的缺陷，并能显著提高优化搜索的效率．两者结合的改进遗传算法能很好地解决梯级电站电力调度优化问题．

图9 群体最优目标值的变化过程Fig.9 Convergence course of optimal target value

(2)如图10所示，优化方案实现了三峡-葛洲坝梯级电站间合理的有功负荷分配，确保梯级之间稳定的水力联系和水量补偿．调度期内两个电站的机组出力过程平稳，时段间也无大幅度波动；而且机组出力分配满足不同水头下的机组出力限制约束．除此以外，两电站调度运行过程没有发生机组频繁启停现象，机组启停次数小于1次/台；满足机组启停时间约束和机组运行最优性的原则．上述结论表明：所提出的机组组合、启停、效率同步实现策略满足水电站厂内经济运行的要求，并可通过参数调整满足不同的实例，鲁棒性强，如图11和表2所示．

(3)“以电定水”优化模型全面地考虑三峡-葛洲坝梯级水电站短期电力调度的需求．所得的优化发电方案满足设定的目标和约束条件，可以为实际调度运行提供数据支持．

图10 负荷需求和最优的出力过程曲线Fig.10 Load demand and optimal output curves

表2 最优调度方案数据表Tab.2 Optimal dispatching solution

图11 不同时段最优的三峡电站和葛洲坝电站机组累加出力过程Fig.11 Optimal accumulated output curves of Three Gorges and Gezhouba hydropower junctions

5 结 语

梯级水利枢纽短期电力调度优化问题是多维、多时空、多阶段和非线性的难题，其优化算法一直是广大学者重点研究的课题．本文以三峡-葛洲坝梯级水利枢纽为例，采用遗传算法开展梯级水利枢纽短期电力调度研究．针对标准遗传算法存在“早熟”和搜索效率低的缺陷，引入聚类思想，提出聚类遗传算法，并利用Shubert函数对聚类遗传算法的有效性进行了验证．针对变异算法多随机的缺陷，利用机组运行效率变化梯度因素改进了变异算子．最后，通过实例对提出的改进算法和构建的优化模型进行了验证．优化结果表明：聚类遗传算法和改进变异算子可以有效地弥补遗传算法早熟或陷入局部最优解的缺陷，并能显著提高优化搜索的效率，两者结合的改进遗传算法能很好地适用于梯级电站电力调度优化问题．构建的模型和优化思路符合三峡-葛洲坝实际运行需求，所得的优化发电方案满足设定的目标和约束条件，可以为实际调度运行提供数据支持．

［1］ 张勇传. 水电站经济运行原理[M]. 2版. 北京：中国水利水电出版社，1998.

Zhang Yongchuan. Economic Operation of Hydropower Station [M]. 2nd ed. Beijing：China Water Conservancy and Hydropower Press，1998(in Chinese).

［2］ 畅建霞，黄 强，王义民. 基于改进遗传算法的水电站水库优化调度[J]. 水力发电学报，2001，20(3)：85-90.

Chang Jianxia，Huang Qiang，Wang Yimin. Optimal operation of hydropower station reservoir by using an improved genetic algorithm[J]. Journal of Hydroelectric Engineering，2001，20(3)：85-90(in Chinese).

［3］ 伍永刚，王定一. 二倍体遗传算法求解梯级水电站日优化调度问题[J]. 水电能源科学，1999，17(3)：31-34.

Wu Yonggang，Wang Dingyi. To solve the daily cascaded stations optimal scheduling with a diploid genotypes based on genetic algorithm[J]. Water Resource and Power，1999，17(3)：31-34(in Chinese).

［4］ 刘学海，练继建，马 超，等. 基于市场竞价的梯级水电站群的实时优化运行研究[J]. 水利水电技术，2005，36(10)：53-57.

Liu Xuehai，Lian Jijian，Ma Chao，et al. Study on realtime optimized operation of cascaded hydropower stations based on market price bidding[J]. Water Resource and Hydropower Engineering，2005，36(10)：53-57(in Chinese).

［5］ 练继建，马 超. 市场竞价下梯级水电站短期优化调度研究[J]. 水力发电学报，2007，26(4)：16-21.

Lian Jijian，Ma Chao. Short-term optimal dispatching of cascade hydropower stations in competitive power market[J]. Journal of Hydroelectric Engineering，2007，26(4)：16-21(in Chinese).

［6］ 王大刚，程春田，李 敏. 基于遗传算法的水电站优化调度研究[J]. 华北水利水电学院学报，2001，22(1)：5-10.

Wang Dagang，Cheng Chuntian，Li Min. Study on the optimal operation of hydropower station based on genetic algorithms[J]. Journal of North China Institute of Water Conservancy and Hydroelectric Power，2001，22(1)：5-10(in Chinese).

［7］ 高新波. 模糊聚类分析及其应用[M]. 西安：西安电子科技大学出版社，2004.

Gao Xinbo. Fuzzy Cluster Analysis and Its Applications Engineering[M]. Xi’an：Xidian University Press，2004 (in Chinese).

［8］ 马 超. 梯级水利枢纽多尺度多目标联合优化调度研究[D]. 天津：天津大学建筑工程学院，2008.

Ma Chao. Research on Multi-Scale and Multi-Objective Combined Optimal Dispatching of Cascaded Hydropower Junctions[D]. Tianjin：School of Civil Engineering，Tianjin University，2008(in Chinese).

［9］ 方辉钦. 现代水电厂计算机监控技术与试验[M]. 北京：中国电力出版社，2004.

Fang Huiqin. Technology of Computer Monitoring and Its Tests in Modern Hydropower Stations[M]. Beijing：China Electric Power Press，2004(in Chinese).

Short Term Hydropower Dispatching Optimization of Cascaded Hydropower Junctions Based on Cluster Genetic Algorithm

MA Chao，LIAN Ji-jian
(School of Civil Engineering，Tianjin University，Tianjin 300072，China)

In view of the premature weakness of standard genetic algorithm，a cluster genetic algorithm has been put forward to improve the selection and crossover operators，and its advantages has beentestified by Shubert multimodal function. Based on the change gradient of unit’s operation efficiency，improved mutation operator has been proposed to deal with excessive randomization. All the above improvements have beenapplied to short term hydropower dispatching optimization of Three Gorges and Gezhouba cascaded hydropower junctions and the optimization model and synchronization optimization strategies have been developed. Real case optimization results show that cluster genetic algorithm and improved mutation operator can reduce the premature possibility and enhance the optimization efficiency. Hydropower dispatching solutions based on such improvements can meet all the objectives and constraints，and also increase the power generation efficiency.

cluster genetic algorithm；change gradient of unit’s operation efficiency；improved mutation operator；short term hydropower dispatching optimization；Three Gorges and Gezhouba cascaded hydropower junctions

TV697.1

A

0493-2137(2010)01-0001-08

2008-09-01；

2009-09-15．

“十一五”国家科技支撑计划资助项目(2008BAB29B09)；国家杰出青年科学基金资助项目(50725929).

马 超（1981— ），男，博士，讲师.

马 超，mac_tju@126.com.