基于改进布谷鸟算法的梯级水库长期优化调度研究

明 波 黄 强 王义民(西安理工大学 西北旱区生态水利工程国家重点实验室培育基地，陕西 西安 710048)

基于改进布谷鸟算法的梯级水库长期优化调度研究

明 波 黄 强 王义民(西安理工大学 西北旱区生态水利工程国家重点实验室培育基地，陕西 西安 710048)

梯级水库优化调度模型的求解一直是水利学科需要深入研究的基本问题。使用改进布谷鸟算法求解梯级水库优化调度模型是一种新思路。布谷鸟算法是近年来提出的一种新颖的启发式全局搜索算法，该算法参数少、鲁棒性强、搜索效率高，已得到广泛的研究和应用。对标准布谷鸟算法的寻优机制作了阐述，并尝试在算法进化过程中采用动态发现概率以及引入变异机制对标准算法进行改进，提出了改进的布谷鸟算法，并将其应用于某梯级水库优化调度中。以实例验证了布谷鸟算法在梯级水库优化调度中的可行性和有效性，提出的改进策略可有效克服标准算法中的“早熟”现象，改进算法搜索效率更高，寻优结果更稳定。

梯级水库;水库调度;优化调度方法;布谷鸟算法

1 概 述

水库优化调度是一个强约束、非线性、多阶段的组合优化问题[1]，其核心在于建立合理的优化调度模型以及选择合适的求解方法[2]。随着流域梯级水电站群规模的逐步扩大，进一步研究高效的调度方法具有重要的理论和实践价值。水库优化调度的传统方法主要包括线性规划[3]、非线性规划[4]、网络流规划[5]和动态规划[6]等。传统方法或多或少存在收敛结果不稳定、算法复杂或者存在“维数灾”等问题[7]，难以适应梯级水库优化调度的高维、非线性特点。智能算法具有原理简单、易于实现、并行搜索以及全局寻优能力强等优点，为梯级水库联合优化调度提供了一条新途径。其中，具有代表性的有遗传算法[8,9]、粒子群算法[7,10]、蚁群算法[11,12]以及差分进化算法[13]等。

布谷鸟搜索算法 (CS)是由英国学者于2009年提出的一种新的群智能算法[14,15]。研究表明，CS算法的搜索性能高效，并且参数少、鲁棒性强，其搜索效率不亚于传统的GA和PSO[16～19]。作为一种新颖、高效的搜索算法，CS尚未被引入到梯级水库优化调度当中。

本文对标准CS算法的寻优机制作了阐述，并针对标准CS在进化后期收敛速度慢、容易陷入局部最优解的缺陷，尝试采用动态发现概率以及引入种群变异机制对其进行改进，提出了改进的布谷鸟算法(ICS)，并将其应用于某梯级水库中长期优化调度问题当中。

2 标准布谷鸟算法

布谷鸟最特殊的习性是寄生育雏。在繁殖期间，布谷鸟将卵产在宿主鸟窝里让其孵化。卵一旦被发现，则会被宿主推出鸟窝或者宿主放弃原来的鸟窝，这也就意味着，布谷鸟须要重新寻窝，该过程可用一个概率Pa来表示，即新窝替换旧窝的概率为Pa。在寻窝过程，其飞行路径呈现出莱维飞行 (Lévyflight)特征,属于随机游走的一种，其步长满足一个重尾的稳定分布，在行走过程中，短距离的探索与偶尔较长距离的行走相间。

同其他智能算法类似，CS算法首先是生成初始种群，并采用Lévyflight随机游动算子和偏好随机游动算子,对种群不断地更新，经过一定进化代数，直到算法收敛于满意解为止。

(1)Lévyflight更新方式

xi(t+1)=xi(t)+α⊕L(λ)

(1)

式中,xi(t+1)表示第t+1代中的个体i；α为步长控制量，用于控制随机搜索的范围； ⊕为点对点乘法；L(λ)为Lévy随机搜索步长，服从Lévy分布。

L(λ)～u=t-λ, 1<λ≤3

(2)

(2) 偏好随机游动更新方式

xi(t+1)=xi(t)+γ×H(Pa-ε)⊗[xj(t)-xk(t)]

(3)

式中,ε,γ∈[0,1],二者均服从均匀分布；xi(t)、xj(t)和xk(t)分别表示第t代中的3个随机个体。H(Pa-ε)为赫维赛德函数，当Pa-ε>0时，函数值为0；当Pa-ε<0时，函数值为1；当Pa-ε=0时，函数值为0.5。

综上所述，可得到布谷鸟算法流程图，如图1所示。

3 改进的布谷鸟算法(ICS)

本文主要从2个方面对标准的CS算法进行了改进。

(1) 采用动态发现概率替换原有的固定发现概率，使算法搜索后期更容易生成新的个体，避免算法“早熟”；

(2) 借鉴遗传算法的思想，在算法进化过程中引入变异机制，以进一步增加种群的多样性。

3.1 动态发现概率

在标准的CS算法中,采用一个随机数ε与发现概率Pa作比较,根据比较结果，来确定是否产生新的个体：若ε >Pa，淘汰原有的个体，同时生成新的个体；若ε

因此，本文采用余弦递减策略来实现Pa的动态变化,即

(4)

式中,Tmax为算法的最大进化代数；Titer为当前进化代数；Pa,max与Pa,min分别为Pa的控制参数。

3.2 种群变异机制

在进化算法中,初始解的质量将影响算法的收敛速度以及最终的优化结果。在标准的CS算法中,初始个体的生成方式为

xi=xmin+ξ(xmax-xmin),i∈[1,Npop]

(5)

式中,xi为初始种群中的个体i;xmin和xmax分别为个体生成的上、下限;ξ为[0,1]之间均匀分布的随机数;Npop为种群规模。

由式(5)可知，CS算法初始解的生成方式具有很大的随机性。要获得较高质量的初始种群，必须加大种群的规模。而随着种群规模的增加，计算机占用内存也会随之增加，不利于算法寻优。

因此，本文对CS每代最佳个体进行变异，以进一步提高个体的质量。变异机制如下：在CS算法迭代至第t代时，选择当前最佳的鸟窝xt,bt，不让其直接遗传到下一代，而是继续进行变异操作，并且变异步长会随着进化代数的增加而逐渐减小。变异机制可表示为

〗⊕ε

(6)

式中，xt,b2为变异后的鸟窝位置;ε为1×d向量，服从标准正态分布;d为优化问题的维数。

进行变异后可产生新的个体xt,b2。为保证变异沿着有利的方向进行，比较变异后的个体xt,b2与变异之前的个体xt,b1的适应度值，保留适应度值较优的个体xt,b,并将其遗传到下一代，以此实现有效变异操作。

(7)

基于以上分析，通过采用动态发现概率以及引入种群变异机制,对标准CS算法进行了改进，从而建立改进的布谷鸟算法。

4 梯级水库优化调度数学模型

本文建立了兼顾保证出力的梯级发电量最大模型。问题描述为：给定调度期内各水电站及区间来水过程，综合各种约束条件，确定梯级各水电站水库的发电用水过程，在尽量满足各水电站保证出力的前提下，使整个梯级的发电量最大。

4.1 目标函数

(8)

4.2 约束条件

(1) 水量平衡约束

V(m,t+1)=V(m,t)+[Q1(m,t)-

Q0(m,t)-Qs(m,t)]×Δt

(9)

(2) 水位约束

Zmin(m,t)≤Z(m,t)≤Zmax(m,t)

(10)

(3) 下泄流量约束

Qomin(m,t)≤Qo(m,t)≤Qomax(m,t)

(11)

(4) 电站出力约束

Nmin(m,t)≤N(m,t)≤Nmax(m,t)

(12)

(5) 边界条件约束

Z(m,1)=Zm,b,Z(m,T+1)=Zm,e

(13)

式中，B为目标函数值；t、T分别表示调度时期内的时段编号以及总时段数；m、M分别表示水电站水库的编号和总个数；N(m,t)表示m水电站第t时段的平均出力；Nm,f为m水库的保证出力；H、δ和k均为模型的惩罚参数；V(m+1,t)、V(m,t)分别表示m水库t时段的初、末库容；QI(m,t)、Qo(m,t)、Qs(m,t)分别表示m水库t时段入库、出库、弃水流量;q(i,t)为m水库和m+1水库在t时段的区间入流;Zmax(m,t)、Zmin(m,t)分别表示m水库在t时段允许水位的上、下限;Qomax(m,t)、Qomin(m,t)表示m水库允许下泄流量的上、下限;Nmax(m,t)、Nmin(m,t)分别表示m水库在t时段允许出力的上、下限；Zm,b为m水库调度初期的水位；Zm,e为m水库调度末期的水位。

5 实例计算

为验证ICS算法的可行性和有效性，以某梯级水电站水库的典型年资料为例进行计算。该梯级水电站包含A、B两座大型水库，且均具有年调节库容;A水库位于B水库的上游，调度期为5月～次年的4月;主汛期为7～8月。A、B水电站水库各项参数见表1。

5.1 不同算法对比

采用ICS对调度模型进行求解，同时将GA、CS以及ACS作为对比。算法参数设置如下：种群规模均为Npop=50；最大迭代次数为Tmax=300；在标准CS算法中，发现概率为Pa=0.25;在标准GA中,交叉、变异概率分别为Pc=0.2、Pm=0.08；在动态发现概率策略中，发现概率的控制参数为Pa,min=0.1，Pa,max=0.4。由于较大的变异步长容易使算法跳出可行搜索空间，导致变异效率很低，因此基于局部扰动思想，确定步长控制量为a1=0.5。

由于ICS、GA等均属于随机搜索算法，而且搜索结果不稳定，因此,将程序独立运行10次，取其平均值作对比。

表2给出了上述4种算法的逐次运行结果以及对应的均值、标准差和每种算法的平均寻优时间。此外，为了反映ICS算法优化结果的合理性，挑选出了发电量最大对应的调度结果作为代表进行分析。

由表2可知：

(1) 从发电量来看，ICS的发电量最大值为82.77亿kW·h，相对于标准的CS和GA，分别提高了1.28%和4.37%，但相对于ACS，则降低了0.13%。

(2) 从结果稳定性来看，ICS优化结果的标准差为0.57，均低于其余3种算法，表明优化结果相对来说更稳定。

(3) 从寻优时间来看，CS以及其改进型比GA的要长，不同改进策略均会使算法的寻优时间延长，但ICS与ACS寻优时间相接近，说明本文所提出的改进策略在确保一定精度的前提下,仍具有一定竞争力。

ICS既增加了发电量，又提高了结果的稳定性，考虑到中长期水库调度对时效性的要求不高，不同算法的寻优时长并无本质区别。总体而言，ICS优于GA、CS及ACS，表明改进策略有效。

同时，分析结果也表明，ICS调度结果均满足各项约束条件，各水库水位在蓄水期迅速上升，枯水期水位逐渐回落，体现了水库“蓄丰补枯”的特点。调度结果合理、可靠，显示出ICS算法应用于梯级水库调度中的可行性。

5.2 改进策略作用分析

为区分2种改进策略各自作用的大小，单独采用变异策略以及动态发现概率策略，分别与传统CS的收敛过程进行对比,如图2所示。

从优化结果来看，2种策略均于使优化结果得到改善，但变异策略的改善效果更为明显；从收敛性来看，采用变异策略可明显提升算法的收敛速度，而采用动态发现概率策略在收敛前期可使收敛速度下降，这可能与采用动态发现概率改变了算法进化过程中全局与局部搜索之间的均衡性有关。从算法复杂度来看，采用变异策略增加了目标函数的评价次数，使算法寻优时间变长，而采用动态发现概率并无改变算法的复杂度，因而寻优时间基本不受影响。

总体而言，采用2种改进策略均能使优化的主要目标(梯级发电量)得到改善，但变异策略对于算法整体的改善效果更为明显。

5.3 ICS算法搜索性能分析

在智能算法中，一般通过增大种群规模或者迭代次数可进一步改善优化结果，但同时也占用了更多的计算机内存且延长了寻优时间。因此，高效的算法应该是在较小的种群规模下,经过一定的迭代次数,便可收敛至全局最优或者准全局最优解。为进一步反映ICS的搜索性能，通过设定不同的种群规模进行优化计算，优化结果见表3。

由表3可知，种群规模越大，ICS算法的收敛速度就越快;当进化代数为500时，三者的收敛值相差较小，表明ICS在较小的种群规模下经过一定的迭代次数,仍然可以达到较满意的精度，显示出该算法的高效性。

结合表2，当GA种群规模为50时，进化代数为300次时最大的优化值仅为79.35亿kW·h，而在同等条件下,CS最大优化值为81.93亿kW·h，ICS的最大优化值为82.77亿kW·h，表明GA和CS均不同程度地陷入了局部最优解，但CS在克服算法“早熟”方面的性能明显更优。这是由CS算法搜索机理所决定的，算法中，Lévyflight搜索步长长短相间以及偏好随机游动,在每次迭代时都会产生新的个体，使算法在进化后期仍能够保持较好的种群多样性，因而不容易陷入局部最优解。相对于GA和CS而言，ICS的搜索性能也进一步得到了提升，表明改进策略的有效性。

6 结 语

作为一种新颖的群智能算法，布谷鸟算法参数少、搜索效率高、寻优结果稳定、鲁棒性强，可为梯级水库优化调度提供一条有效途径。标准的CS算法在进化过程中同样存在收敛速度慢、种群活力不足等缺陷，本文通过采用动态发现概率以及引入变异机制,对标准算法进行了改进，提出了改进的布谷鸟算法，并将其应用于求解梯级水库优化调度问题当中。实例应用结果验证了布谷鸟算法在梯级水库优化调度中的可行性和有效性。

此外，本文所提出的改进策略,可以进一步提高算法的搜索性能。总之，改进的布谷鸟算法搜索性能更高，寻优结果也更加稳定。

[1] 赵明雁,程春田,李刚. 水库群系统优化调度新进展[J]. 水文,2005,25(6):18-23.

[2] 陈立华,梅亚东,董雅洁,等. 改进遗传算法及其在水库群优化调度中的应用[J]. 水利学报,2008,39(5):550-556.

[3]ZiadK.Shawwash,ThomasK.Siu,S.O.DenisRussell.TheB.C.HydroShortTermHydroSchedulingOptimizationModel[J].IEEETransactionsonPowerSystems, 2000, 15(3): 1125-1131.

[4]GuanX,LuhPB,ZhangL.NonlinearApproximationinLagrangianRelaxation-basedforHydrothermalScheduling[J].IEEETransactionsonPowerSystems, 2000, 10(2): 772-778.

[5]P.E.C.Franco,M.F.Carvalho,S.Soares.ANetworkFlowModelforShorttermHydro-dominatedHydrothermalSchedulingProblems[J].IEEETransactionsonPowerSystems, 1994, 9(2): 1016-1022.

[6]TraversDL,KayeRJ.DynamicDispatchbyConstructiveDynamicProgramming[J].IEEETransactionsonPowerSystems, 1998, 13(1): 72-78.[7] 彭勇,梁国华,周惠成. 基于改进微粒群算法的梯级水库群优化调度[J].水力发电学报,2009,28(4):49-55.[8] 王少波,解建仓,孔珂. 自适应遗传算法在水库优化调度中的应用[J].水利学报,2006,37(4):480-485.

[9] 郑姣,杨侃,倪福全,等. 水库群发电优化调度遗传算法整体改进策略研究[J].水利学报,2013,44(2):205-211.

[10]张双虎,黄强,吴洪寿,等. 水电站水库优化调度的改进粒子群算法[J].水力发电学报,2007,26(1):1-5.

[11]徐刚,马光文,梁武湖,等. 蚁群算法在水库优化调度中的应用[J].水科学进展,2005,16(3):397-400.

[12]徐刚,马光文.基于蚁群算法的梯级水电站群优化调度[J].水力发电学报,2005,24(5):7-10.

[13]郑慧涛,梅亚东,胡挺,等. 改进差分进化算法在梯级水库优化调度中的应用[J].武汉大学学报(工学版),2013,46(1)：57-61.

[14]Xin-sheYang,DebSuash.CuckoosearchviaLévyFlights[C].ProceedingsofWorldCongressonNature&BiologicallyInspiredComputing.Piscataway:IEEEPublications, 2009: 210-214.

[15]Xin-sheYang,DebSuash.Engineeringoptimizationbycuckoosearch[J].Int’lJournalofMathematicalModelingandNumericalOptimization, 2010, 1(4):330-343.

[16]G.Kanagaraj,S.G.Ponnambalam,N.Jawahar.Ahybridcuckoosearchandgeneticalgorithmforreliability-redundancyallocationproblems[J].Computers&IndustrialEngineering, 2013, 66(4):1115-1124.

[17]M.Dhivya,M.Sundarambal.CuckooSearchforDataGatheringinWirelessSensorNetworks[J].Int’lJournalofMobileComnunications, 2011, 9(6):642-654.

[18]AmirHosseinGandomi,Xin-SheYang,AmirHosseinAlavi.Cuckoosearchalgorithm:ametaheuristicapproachtosolvestructuraloptimizationproblems[J].EngineeringwithComputers,2013,29:17-35.

[19]ApoorvP.Patwardhan,RohanPatidar,NithinV.George.Onacuckoosearchoptimizationapproachtowardsfeedbacksystemidentification[J].DigitalSignalProcessing,2014,32(9):156-163.

[20]李煜,马良. 新型元启发布谷鸟搜索算法[J].系统工程,2012,30(8):64-69.

(编辑：赵秋云)

2015-04-09

明 波，男，西安理工大学水利水电学院，硕士研究生.

1006-0081(2015)04-0009-05

TV697.12

A