粒子群算法在水库(群)优化调度研究中的应用综述

邓显羽,彭 勇,叶碎高,温进化,何 斌

(1.大连理工大学水利工程学院,辽宁 大连, 116024;2.浙江省水利河口研究院,浙江 杭州 310008)

随着我国经济建设的迅猛发展,水库的数量和规模都呈现出快速增长的势头。水库(群)调度问题是结合决策者的经验知识对水库进行科学调度的应用科学技术,已成为现代水文学和决策论研究的热点,它直接为防汛抢险、水资源合理利用与保护、水利工程建设及其调度运用管理以及发展工农业生产服务。水库(群)优化调度运用系统工程方法建立水库调度有关的数学模型,并对数学模型进行求解,寻求最优答案。水利科学工作者尝试了应用各种优化算法来解决水库(群)的优化调度问题,目前运用的主要有线性规划、非线性规划、动态规划、大系统分解协调方法和遗传算法等。应用研究表明,这些方法各具特色,但也存在一定局限,比如在计算速度、收敛性能方面存在不足等[1]。为此,在已有研究成果的基础上继续完善、改进和探索新的求解方法是水库(群)优化调度所面临的亟待解决的问题。粒子群算法(PSO算法)凭借自身的特点为这一问题提供了一条新的求解途径。

PSO算法作为一种新兴的群体智能优化算法[2],在水库调度系统中的应用研究起步较晚,但随着研究的深入,逐渐在水库优化调度领域中显示出广阔的应用前景,已开始引起我国水利科学工作者的广泛关注[3-6]。为此,笔者在介绍PSO算法的基础上对PSO算法在水库(群)优化调度中的应用研究现状进行归纳,并对算法的应用前景进行探讨。

1 PSO算法基本原理

POS算法是一种随机全局优化技术,通过粒子间的相互作用产生的群体智能进行搜索[7-9],已被广泛应用于函数优化、神经网络训练、模糊系统控制、电力系统优化与控制等领域[10-11],并在短短的几年时间里涌现出大量的研究成果。

Shi等[8]在POS算法的最初版本基础上引入惯性权重w来更好地控制开发和探索,形成了当前的标准版本[12]。

PSO算法在搜索过程中每个粒子在解空间中同时向2个点接近,第1个点是整个粒子群中所有粒子在历代搜索过程中所达到的最优解,被称为全局最优解gbest;另一个点则是每个粒子在历代搜索过程中自身所达到的最优解,被称为个体最优解 pbest。x i=[xi1,xi2,…,xin]表示第i个粒子在解空间中的位置,其最优解表示为 pbesti =[pi1,pi2,…,pin],全局最优解表示为 gbest=[g1,g2,…,gn],第k次修正量表示为vi,k=[vi1,k,vi2,k,…,vin,k],计算公式为

式中:m为粒子群中粒子的个数;l为解向量的维数;c1和c2为学习因子,一般取 c1=c2=2;r1和 r2为2个独立的介于[0,1]之间的随机数;wi为动量项系数,是平衡全局与局部搜索的系数,随算法迭代的进行而线性减小;vid为第i个微粒在解空间第d维的速度;vid,k为第i个粒子第k次修正的速度;vmaxd为粒子允许最大速度,其决定了微粒在解空间第d维的搜索精度。

PSO算法具有以下优点[8-9,13]:①算法通用,不依赖于问题信息;②群体搜索,并具有记忆能力,保留局部个体和全局种群的最优信息;③原理简单,容易实现;④协同搜索,同时利用个体局部信息和群体全局信息指导算法下一步的搜索。

2 水库(群)优化调度模型及PSO算法步骤

2.1 水库(群)优化调度数学模型

本文以梯级水电站水库群优化调度为例介绍水库群优化调度数学模型。梯级水电站水库群优化调度根据入库流量过程,以发电引用流量为决策变量,以水库水电站群在调度周期内总发电量最大为目标进行调度。假设有图1所示的梯级水电站水库群系统,目标函数见式(3),约束条件见式(4)～(12):

图1 梯级水电站水库群系统示意图

式中:E为梯级电站总发电量;Qpt为电站p在时段t的发电流量;Mt为时段t的小时数;Rpt为电站p在一定水头条件下时段t的平均耗水率;n为水库个数;T为计算总时段;Vp,t+1为水库p在t时段末的库容;Vpt为水库p在t时段初的库容;Ipt为水库p在时段t的平均入库流量;IZpt为水库p在时段t的区间入流;Spt为水库p在时段t的弃水流量;Sptmax为水库p的溢洪道在时段t的泄流能力;Δt为第t时段长;Vptmin为水库p在t时段初应保证的最小库容;Vptmax为水库p在t时段初允许的最大库容;Qptmin为电站p在时段t允许的最小引用流量;Qptmax为电站p在时段t允许的最大引用流量,由于水库群的发电用水与下游灌溉及城市用水相结合,因此在Qpt＜Qptmax时 Spt=0,而当 Qpt=Qptmax时 Spt≥0;Vp1,c,Vp,T+1,c分别为水库p在优化调度期的初、末库容;qpt min为水库p在时段t的最小下泄流量;qptmAx为水库p在时段t的下游河道安全泄流量;Npmin为电站p的最小出力;Npmax为电站 p的最大出力限制;Zpt为水库p在t时段初的水位;Up为水库p的水位-库容关系函数。

2.2 POS算法步骤

基于PSO算法的梯级水库群优化调度步骤如下:①对微粒群进行初始化设置,包括设置群体规模、迭代次数、粒子最大允许速度,随机给出初始粒子位置和粒子初始速度。其中每个粒子向量代表一个水库群调度过程,粒子向量的坐标对应水库每一时段的水位。②按照式(3)计算适应函数值E(xi)并与自身的最优值E进行比较,如果E(xi)＞E(),则用新的适应值取代前一轮的优化解,用新的粒子取代前一轮的粒子,即E(pbesti)=E(xi),pbesti=xi。③将每个粒子的最好适应值E(pbesti)与所有粒子的最好适应值 E(gbest)进行比较,如果E()＞E(gbest),则用该粒子的最好适应值取代原有的全局最好适应值,同时保存粒子的当前状态,即 E(gbest)=E,gbest=④判断是否满足迭代停止条件,如果不满足,则进行新一轮的计算,按式(1)(2)将粒子进行移动,从而产生新的粒子(即新的解),返回步骤②;如果满足迭代停止条件则计算结束。

3 PSO算法应用于水库(群)优化调度

3.1 应用研究概述

PSO算法是近年来提出的一种新型优化算法,在求解水库单目标、多目标、日优化、长期优化和防洪调度等方面都取得了一定的成果。李崇浩等[14]将PSO算法应用于求解梯级水电厂短期优化调度问题,提出以确定微粒群在多维空间中的最优位置来实现多阶段优化调度决策的方法;钟建伟等[15]提出了基于POS算法求解梯级电站单目标优化调度问题的一般算法结构,通过计算时段库水位的变化范围,把梯级电站优化调度问题转化为无约束的优化问题处理;袁鹏等[6]将PSO算法应用于南盘江上游水库洪水调度计算,证明了POS算法在水库防洪优化调度中的可行性;杨道辉等[16]对PSO算法在水电站日优化调度中的应用进行了初步尝试,研究了单一水电站的日优化调度问题;芮钧等[5]探讨了PSO算法在水电站中长期优化调度的应用方法及效果;程春田等[17]探讨了代替动态规划的必然性和潜力,认为PSO算法是代替动态规划来求解装机规模庞大的巨型水电站厂内经济运行的有效方法。

3.2 关键问题

通过对前人研究成果的分析可知,应用PSO算法进行水库(群)优化调度问题的求解,主要存在以下几个问题:

a.水库(群)优化调度问题的约束条件较多,在PSO算法求解步骤中,第2.2节中步骤①随机生成粒子的过程只考虑了水库允许的蓄水量约束,对水量平衡约束、流量范围约束、出力范围约束等均未考虑。这直接导致了初始化粒子群体的质量很差,绝大部分初始粒子的个体适应值为零,仅有少量粒子的适应值大于零,从而导致群体收敛速度慢[18]。

b.以水位为决策变量时,由于水量平衡的约束条件使得同一水库相邻时段的水位联系比较紧密,随机产生的粒子群中大多数粒子为不可行解,而且各个电站的最小平均出力约束和库群最小平均出力约束导致得到可行解更为困难,所以从随机产生的粒子群开始按照目标函数和约束要求进行优化往往得不到理想解[19]。

c.在PSO算法的搜索后期,每个粒子的历史最优解、所有粒子的历史最优中的最优解、每个粒子的当前位置都会趋向于同一点,并且每个粒子的运动速度趋于零。在这种情况下,如果不调整粒子的位置或速度,则粒子群所趋向的那个点即为最终求解结果的极限值。由于水库优化调度往往存在多个局部极值,所以求解结果为局部最优解的概率远大于为全局最优解的概率。

d.最大速度限制决定了微粒在解空间的搜索精度,如果最大速度限制太大,微粒可能会飞过最优解,如果最大速度限制太小则微粒陷入局部搜索空间而无法进行全局搜索。最大速度限制需要反复调试确定。

e.水库的优化调度是典型的多约束优化问题,对于状态变量约束(如水位或库容),由于微粒在多维空间中的位置代表的便是水库的状态,因此可以直接通过对各维的坐标范围进行限定来实现;其他约束条件(如流量、保证出力等)则通过罚函数的形式进行处理。

可见,PSO算法在水库群优化调度应用中还存在一些缺陷,有待进一步解决的主要问题如下:①PSO算法的数学基础研究还相对薄弱,一些学者只是进行了初步的分析[20-21],缺乏深刻且具有普遍意义的理论分析,学习因子、最大速度、惯性权重等参数还需要依靠经验进行取值,没有理论指导。因此,对数学基础的研究非常重要,包括对不同搜索问题的收敛性及收敛速度估计、预防陷入局部优值和参数设置影响等。②PSO算法在水库(群)应用中遇到的一个主要问题就是种群多样性的损失过快,当种群缺乏多样性时,粒子群就会发生高度聚集现象,长时间或永远跳不出聚集点,这就导致早熟收敛或停滞[22],无法保证收敛到最优点。③PSO算法在接近或进入最优点区域时的收敛速度比较缓慢,研究发现PSO算法早期收敛速度较快,但到寻优后期的结果改进不理想,主要是因为算法收敛到局部极小,缺乏有效机制使算法逃离局部极值点[23]。④目前PSO算法在水库优化调度中所得到的最优解依然是相对最优解,只是在一定的空间和迭代代数条件下的最优解。因而,需要采取各种方法对其进行改进。

4 PSO算法改进技术及其在水库优化调度中的应用

为了将粒子群算法更好地应用于解决复杂的有约束非线性问题,一些学者对基本POS算法做了各式各样的改进,主要集中在3个方面:①基于POS算法位置和速度更新公式的改进;②基于遗传算法进化机理的改进;③与其他算法结合的改进。

4.1 基于PSO算法位置和速度更新公式的改进

为了更好地控制PSO算法的开发和探测能力,文献[8]把惯性权重因子引入算法的速度公式中,形成现在标准的PSO算法。惯性权重因子的引入使算法在性能及收敛速度方面有了大幅度提高,包括Eberhart等在内的许多学者对其取值方法和取值范围做了大量的研究。惯性权重的选择主要分为2类:固定权重和时变权重。大多数的研究都集中在后者。最初是对线性规律变化的惯性权重的研究,后来发展到对非线性规律变化的研究。文献[24]讨论了一种非线性动态调整惯性权重的方法,文献[25]采用一种基于目标函数信息而变化的惯性权重动态调整方法,文献[26]根据群体早熟收敛程度和个体适应值自适应地调整粒子的惯性权重,使群体在进化过程中始终保持惯性权重的多样性,文献[27]采用(0,1)均匀分布的随机惯性权重法来取代线性递减的方法等。这些基于惯性权重改进的算法被广泛应用于水库的优化调度中。

文献[28]在PSO算法速度更新公式中引入收缩因子来确保算法的收敛性,从而达到提高局部收敛速度的目的,可使粒子轨迹收敛,而不需限定粒子的速度,这是经典模型之一。邱林等[29]将这种引进收敛因子的微粒群优化算法用于水库优化调度计算,取得了比较满意的结果。

4.2 基于遗传算法进化机理的改进

受GA的启发,在PSO算法中加入选择算子、交叉算子、变异算子。将选择算子引入PSO算法中的混合PSO(HPSO),选择每次迭代后较好的粒子复制到下一代,以保证每次迭代的粒子群都具有较好的性能。实验表明这种算法对某些测试函数具有优越性。朱凤霞等[30]在基本算法中引入遗传算法的锦标赛选择算子,并将这种改进的算法应用到黄河上游梯级电站的长期调度中,证明了算法的可靠性和有效性。李崇浩等[31]通过引入遗传算法中的“杂交”算子对原算法进行改进,并将其应用于水库长期优化调度问题。文献[32]提出带变异算子的POS算法,通过引入变异算子来跳出局部极值点的吸引,从而提高全局搜索能力,同时又保持前期搜索速度快的特性,加快粒子的收敛速度,搜索精度也相对比较高,对一类非线性优化问题可以得到满意的结果。彭勇等[33]将算法引进了类似遗传算法的交叉和变异算子来提高搜索效率,并将其用于求解梯级水库群的优化调度,结果比较满意。

4.3 与其他算法的结合与改进

POS算法与模拟退火算法相结合,从一给定解开始采用模拟退火算法思想对粒子的更新位置作限制[34],从邻域中随机产生另一个解,接受准则允许目标函数在有限范围内变差,以一定概率接受新的解,克服了由于新位置变差引起收敛速度缓慢的缺点,提高了整个算法的可行性。王少波等[35]将其引入水库调度领域,设计了基于该算法的水电站水库优化调度问题的求解方法,具有较好的应用前景。

针对PSO算法早熟收敛现象并提高粒子群的多样性,把免疫系统的免疫信息处理机制结合到POS算法中,构成免疫POS算法[36]。免疫PSO算法引入疫苗接种等操作,对算法的进化过程进行选择性地指导,提高了收敛速度和精度。李安强等[37]在分析梯级电站短期优化调度数学模型及该算法特点的基础上,建立了基于免疫PSO算法的梯级电站短期优化调度数学模型,证明该算法可获得较优的优化调度方案。

针对PSO算法易陷入局部极值点、进化后期收敛速度慢等缺点而提出来的混沌思想[38],使混沌变量从混沌空间映射到解空间,然后对当前粒子群体中的粒子进行混沌寻优,使粒子群体的进化速度加快,从而改善了POS算法摆脱局部极值点的能力。文献[39]将这种混沌混合算法应用到水库防洪优化调度中,实例结果表明该方法具有一定的有效性。

5 结论与展望

PSO算法是一种简单易行的算法,在求解各种问题中展现了它的魅力和特点。笔者对粒子群在水库(群)优化调度中的应用进行了探讨,认为PSO算法无论从理论还是工程实际应用上都有很多问题值得进一步研究,具有广阔的应用前景。在该算法中加入各种改进措施和方法,可使其越来越完善,PSO算法在水库优化调度中将发挥更大的作用。

由于水库优化调度实际问题的多样性,需要研究者提出更多有效的PSO算法的改进算法;有根据地设置各种参数,保证解的收敛并有效地避免局部最优;结合水库群本身的结构和特点建立使用PSO算法及其改进算法的数学模型,确实有效地解决问题。随着PSO算法在水库优化调度领域进行广度和深度的应用拓展,并与其他算法和理论相结合,必将带动水库优化调度的进一步发展。

[1]畅建霞,黄强,王义民.水电站水库优化调度几种方法的探讨[J].水电能源科学,2000,18(3):19-22.

[2]KENNEDY J,EBERHART R.Particle swarm optimization[C]//Proc IEEE Int Conf on Neural Networks.Perth,Australia:IEEE Press,1995:1942-1948.

[3]杨道辉,马光文,过夏明,等.粒子群算法在水电站优化调度中的应用[J].水力发电学报,2006,25(5):5-7.

[4]马细霞,储冬冬.粒子群算法在水库调度中的应用分析[J].郑州大学学报:工学版,2006,27(4):121-124.

[5]芮钧,梁伟,陈守伦.基于粒子群算法的水电站中长期优化调度研究[J].水电能源科学,2007,25(5):99-101.

[6]袁鹏,常江,朱兵,等.粒子群算法的惯性权重模型在水库防洪调度中的应用[J].四川大学学报:工程科学版,2006,38(5):54-57.

[7]EBERHART R,KENNEDY J.A new optimizer using particle swarm theory[C]//Proc 6th Int Symposium on MicromAchine and Hum an Science.Nagoya:IEEE Press,1995:39-43.

[8]SHI Y,EBERHART R.A modified particle swarm optimizer[C]//Proceedings of the IEEE International Conference on Evolutionary Computation.Nagoya:IEEE Press,1998:69-73.

[9]曾建潮,介婧,崔志华.微粒群算法[M].北京:科学出版社,2004.

[10]谭明交,张红梅.粒子群优化算法及其在神经网络中的应用[J].计算机与信息技术,2009(1):6-8.

[11]袁晓辉,王乘,张勇传.粒子群优化算法在电力系统中的应用[J].电网技术,2004,28(19):14-19.

[12]SHI Y,EBERHART R C.Empircal study of particle swarm optimization[C]//Proceedings of the World Multiconference on Systemics,Cybernetics and Informatics.Orlando:FL,2000:1945-1950.

[13]李爱国,覃征,鲍复民,等.粒子群优化算法[J].计算机工程与应用,2002(21):1-4.

[14]李崇浩,纪昌明,缪益平.基于微粒群算法的梯级水电厂短期优化调度研究[J].水力发电学报,2006,25(2):94-98.

[15]钟建伟,杨俊杰.粒子群优化算法及其在水库优化调度中的应用[J].湖北民族学院学报:自然科学版,2006,24(3):239-241.

[16]杨道辉,马光文.粒子群算法在水电站日优化调度中的应用[J].水力发电,2006,32(3):73-75.

[17]程春田,唐子田,李刚.动态规划和粒子群算法在水电站厂内经济运行中的应用比较研究[J].水力发电学报,2008,27(6):27-31.

[18]芮钧,陈守伦.一种改进的水电站优化调度粒子群求解算法[J].水力发电,2008,34(3):97-99.

[19]武新宇,程春田,廖胜利,等.两阶段粒子群算法在水电站群优化调度中的应用[J].电网技术,2006,30(20):25-28.

[20]CLERC M,KENNEDY J.The particle swarm-explosion,stability,and convergence in a multidimensionalcomplex space[J].IEEE Transactions on Evolutionary Computation,2002,6(1):58-73.

[21]TRELEA I C.The particle swarm optimization algorithm:convergence analysis and parameter selection[J].Information Processing Letters,2003,85(6):317-325.

[22]CLERC M.Stagnation analysis in particle swarm optimization orwhathappens when nothing happens[R].London:Technical Report CSM-460,2006.

[23]涂启玉,梅亚东.遗传算法在水库(群)优化调度研究中的应用综述[J].水电自动化与大坝监测,2008,32(1):16-18.

[24]王丽,王晓凯.一种非线性改变惯性权重的粒子群算法[J].计算机工程与应用,2007,43(4):47-48.

[25]王启付,王战江,王书亭.一种动态改变惯性权重的粒子群优化算法[J].中国机械工程,2005,16(11):945-948.

[26]韩江洪,李正荣,魏振春.一种自适应粒子群优化算法及其仿真研究[J].系统仿真报,2006,18(10):2969-2971.

[27]延丽平,曾建潮.具有自适应随机惯性权重的PSO算法[J].计算机工程与设计,2006,27(4):4677-4679.

[28]CLERE M.The swarm and the queen:towards a deterministic and adaptive partical swarm optimization[C]//Proceeding of lntemational Confereneeon Evolutionary Computation.Washington D.C.:1999:1951-1957.

[29]邱林,肖琳.改进微粒群优化算法在水库防洪调度中的应用[J].人民黄河,2007,29(10):18-21.

[30]朱凤霞,熊立华,高仕春,等.改进微粒群算法在梯级电站长期优化调度中的应用[J].水文,2007,27(5):42-45.

[31]李崇浩,纪昌明,李文武.改进微粒群算法及其在水库优化调度中的应用[J].中国农村水利水电,2006(2):54-56.

[32]李宁,孙德宝,岑翼刚,等.带变异算子的粒子群优化算法[J].计算机工程与应用,2004,40(17):12-14.

[33]彭勇,梁国华,周惠成.基于改进微粒群算法的梯级水库群优化调度[J].水力发电学报,2009,28(4):49-55.

[34]高尚,杨静宇,吴小俊,等.基于模拟退火算法思想的粒子群优化算法[J].计算机应用与软件,2005,22(l):103-104.

[35]王少波,解建仓,汪妮.基于改进粒子群算法的水电站水库优化调度研究[J].水力发电学报,2008,27(3):12-15.

[36]高鹰,谢胜利.免疫粒子群优化算法[J].计算机工程与应用,2004,40(6):4-6.

[37]李安强,王丽萍,蔺伟民,等.免疫粒子群算法在梯级电站短期优化调度中的应用[J].水利学报,2008,39(4):426-432.

[38]高鹰,谢胜利.混沌粒子群优化算法[J].计算机科学,2004,31(8):13-15.

[39]纪昌明,吴月秋,张验科.混沌粒子群优化算法在水库防洪优化调度中的应用[J].华北电力大学学报:自然科学版,2008,35(6):103-107.