双层多种群PSO在水库群供水优化调度中应用

卿逸男，丁永生，2，曾献辉，2，郝矿荣，2

1.东华大学 信息科学与技术学院，上海 2016202.数字化纺织服装技术教育部工程研究中心，上海 201620

双层多种群PSO在水库群供水优化调度中应用

卿逸男1，丁永生1，2，曾献辉1，2，郝矿荣1，2

1.东华大学 信息科学与技术学院，上海 201620
2.数字化纺织服装技术教育部工程研究中心，上海 201620

1 引言

我国水资源时空分布不均，缺水问题严重影响着人民的生活生产以及生态环境，合理高效地利用水资源是目前亟待解决的问题。如何通过水库群联合水量优化调度，更好地调配有限水资源一直是研究的热点问题。水库群供水优化调度问题是一个具有各类约束条件的大型、动态的负载非线性系统的优化问题，国内外学者进行了广泛研究，其中包括：动态规划法、网络流法、大系统分解协调、人工神经网络法、遗传算法、模拟退火算法等[1]。

粒子群优化（PSO）算法是由Kennedy和Eberhart于1995年提出的一类基于群智能的随机优化算法[2]，其思想来源于对鸟群捕食行为的研究，PSO算法有着算法简单、容易实现，并且可调参数少等特点，适用于求解大量非线性、不可微和多峰值的复杂优化问题，已应用于多个学科和工程领域[3-5]。但通过研究发现基本PSO算法本身存在较强的“趋同性”，在进化过程中会导致多样性的大量丧失，常常会陷入到局部最优解中，全局搜索能力较差，求解精度不高；同时，在算法后期收敛速度较慢。如何保持群体的多样性，避免算法过早地陷入局部极值是改进粒子群算法的一个直接出发点。

本文在前人研究[6-11]的基础上提出一种带差分进化的双层多种群粒子群优化算法（DE-TMPSO），利用多个普通子群覆盖不同的解空间，加大粒子的多样性；同时利用精英种群重点进行局部搜索，添加差分进化操作有效地减少陷入局部极值的概率，具有更好的全局搜索能力和局部搜索能力，提高了算法的效能。

2 基本粒子群优化算法

其中，i=1，2，…，m，m为种群规模；d=1，2，…，n，n为粒子维数；c1和c2分别为认知部分和社会部分的加速常数，一般设定速度上限vmax；r1和r2为均匀分布于[0，1]之间的随机数；ω为惯性权重值，是一种控制群的搜索和挖掘能力的机制，大的ω值有利于全局探索，多样性增加，小的ω值促进局部的挖掘[12]，建议采用线性递减权策略：

其中，k为当前进化代数，kmax为最大进化代数，ωstart为初始惯性权值，ωend为进化至最大代数时的惯性权值（终止惯性权值）。

3 DE-TMPSO算法

3.1 思想与结构

DE-TMPSO算法分成上下两个层次：上层由具有问题较好解的粒子组成的精英种群，下层由N个普通子群构成，上下两层组成一个相互影响的闭环循环，如图1所示。

图1 DE-TMPSO算法结构图

下层的各个普通子群之间相互独立地进化，并从精英种群中得到优良信息指导自己的进化进程；各个基础种群将进化得到的优良粒子贡献出来，输送给精英种群。每个普通子群分别进行初始化和独立搜索。为了确保候选解的多样性以防止算法陷入局部最优解，每个子群分别设置不同的参数。具有粗粒度参数的子群负责搜索全局最优解，而其他种群用于细化局部搜索和增强求解精度。

上层的精英种群从每个子群选择较好的粒子来进行初始化，并在迭代过程中不断地选取每个子群中最好的粒子来替换自身较差的个体。为减少算法陷入局部最小值的可能，在精英种群中添加差分进化操作，有助于粒子跳出局部极值，同时差分进化操作不会出现因变异而产生的倒退，能够保证算法的整体最优值不受到影响。反过来，选取精英种群中前N（N为下层普通种群个数）个粒子随机分配到各个普通子群中指导它们进化更新。

3.2 进化规则

（1）下层普通子群的进化规则

在普通子群的进化规则中添加向精英粒子飞行的速度分量，将基本粒子群中的粒子速度更新公式更改如下：

其中，c3是加速度常量，r3是[0，1]区间的随机数，Gbest为精英粒子位置，粒子位置按照公式（2）进行更新，惯性权值ω按照公式（3）进行更新。

（2）上层精英种群的进化规则

精英种群中的粒子通过式（1）（2）更新速度和位置，进一步用差分进化操作为精英粒子群增加一定的随机扰动，减少算法陷入局部最优解的可能[13-14]。差分进化（DE）利用3个随机选择的父代的算术交叉算子。令 x1(t)≠x2(t)≠ x3() t为从群中随机取出的3个粒子位置。粒子i的每一维根据下式进行计算：

如果U(0 ，1)≤Pc或j=U(1 ，n)：

其他情况：

其中Pc∈( ) 0，1为交叉概率，且β＞0为缩放因子。仅当新的个体位置取得更好的适应度值时，xi( ) t+1才被置为xi′(t +1)。

总结上述进化规则，可以得到DE-TMPSO算法的具体实现流程图，如图2所示。

图2 DE-TMPSO算法流程图

3.3 DE-TMPSO与基本PSO的对比测试

为了测试DE-TMPSO算法的性能，使用标准的Benchmar 和Rastrigin函数进行测试实验。它们在解空间内都有多个局部极值，是测试算法全局搜索性能较好的函数，如表1所示。

表1 测试函数

在测试中，维数取10，迭代200次，DE-TMPSO算法取3个普通子群和1个精英种群，种群规模均为30，基本PSO算法种群规模取120，运行30次测试，求平均最优值作为性能比较的依据，得到的进化曲线如图3和图4所示。

从测试结果可以看出，在粒子总体规模相同、迭代次数相同的情况下，DE-TMPSO算法取得的最优值明显优于基本PSO算法。测试结果表明DE-TMPSO算法具有更好的稳定性，并在一定程度上避免了“早熟”现象的发生，具有更好的全局搜索能力，同时收敛速度也得到了提高。

图3 求解Benchmark函数30次的平均最小值对比

图4 求解Rastrigin函数30次的平均最小值比较

4 DE-TMPSO算法在水库群供水优化调度问题中的应用

图5所示为我国赣江流域下游部分的网络系统概化图。

图5 流域网络系统概化图

图5中显示了1条干流与4条支流，流域上有5座大中型水库和5个水文站，以流域源头、水库和水文站作为节点，可将整条流域划分为15个河段，河段标号如图5所示。流域水库群水量调度是对干支流上的水库进行统一调度。为了协调上、中、下游和全年各月供水水量的矛盾，要求干支流水库联合调动，保证流域缺水量最小，由此建立流域水库群供水优化调度数学模型。

4.1 水库群供水优化调度问题的基本模型

目标函数：流域所有河段的最大供水缺水量最小。TW=min F() Q

约束条件：

4.2 带罚函数的水库群供水优化调度模型

水量调度基本模型中，水库水量平衡约束是一个复杂约束。复杂约束的处理问题是各种进化算法在实际应用过程中的难点。目前，进化算法处理约束优化问题主要有四种方法：抛弃不可行解法、修复不可行解法、改进进化因子法和惩罚函数法[15]。本文将惩罚函数法引入PSO算法中解决此复杂约束问题：粒子更新后，进行最大值最小值的约束判别，对于不满足约束的解，依照惩罚函数对该粒子的适应度值进行惩罚，设计惩罚函数如下：

最终问题的目标函数修正为：

4.3 问题求解

为保证算法公平性，基本PSO算法与DE-TMPSO算法的参数选取如表2所示，基本PSO算法的参数与DE-TMPSO算法中的精英种群一致。

表2 基本PSO算法与DE-TMPSO算法的参数选取

粒子的维数由水库数与时段数决定，即维数=水库数×时段数。本问题中考虑7～11月每个月的水库下泄流量，则粒子为25维。水量调度中涉及到的各河段需水流量、耗水流量、区间来水流量及水库库容等相关数据都来自于江西省赣江流域。运行20次后，求平均值并作图进行比较。从图6可以看出DE-TMPSO算法在收敛速度和求解精度上都优于基本PSO算法，两种算法求解的最优值比较如表3所示。由DE-TMPSO算法和基本PSO算法分别求解得到的各水库每个月的下泄流量如表4所示，各河段每个月的缺水流量如表5所示。需要说明的是，表4中未列出河段1、3、4、10，因为这些河段在流域的源头处，不能通过水库的调节影响其水量分配。

图6 水量调度问题运行20次平均最优值对比

表3 2种算法运行20次的各项指标对比

表4 2种算法计算得各时段各水库下泄流量对比

从以上结果可以看出，DE-TMPSO算法取得了较好的调度效果，特别是能够在7月至9月这些用水高峰期，通过增大各大出库的出库流量来满足需求。算法在时段上有很好的均衡效果，例如调度方案中不会因为7月水量需求较大，过大地增加放水量，导致需求量依旧很大的8月份缺水很大，这样不仅满足了当月的需求量，还兼顾到了下一个月的水量分配。调度结果将所有河段在所有调度时段内的缺水都控制在150 m3/s以内，实现了在缺水情况下全流域联动、等跨破坏的调度要求。同时，注意到基本PSO算法计算得到的所有河段在所有调度时段内的最大缺水量为160.84 m3/s，较此数据，DE-TMPSO算法将最大缺水量降低了7%左右。可见，应用DE-TMPSO算法求解水库群水量调度问题结果更合理，更能够满足实际应用的要求。

表5 2种算法计算得各时段各河段缺水流量对比

5 结语

本文提出了一种带差分进化的双层多种群粒子群算法，算法由多个普通子群和1个精英种群组成，普通子群采用不同参数增加粒子群的多样性，精英种群加入了差分进化操作，减低了算法陷入局部极值的概率。实验证明这种DE-TMPSO算法具有更好的全局搜索能力，求解精度提高，收敛速度加快。将该算法应用于水库群水量调度问题中，得到了库群最优下泄水量策略和河段的供缺水情况，计算表明，本文提出的DE-TMPSO算法可以求解具有各类约束条件的大型、动态的负载非线性系统的优化问题，能缓减水库群水量调度中的“维数灾”问题，为水库群供水优化调度提供了一种新途径。

[1]郭生练，陈炯宏，刘攀，等.水库群联合优化调度研究进展与展望[J].水科学进展，2010，21（4）：496-500.

[2]Eberhart R C，Shi Y H.Particle swarm optimization：developments，applications and resources[C]//Proceedings of the IEEE Congress on Evolutionary Computation.Piscataway，USA：IEEE Service Center，2001：81-86.

[3]谢晓峰，张文俊，杨之廉，等.粒子群算法综述[J].控制与决策，2003，18（2）：129-134.

[4]王大志.面向实际工程问题的粒子群优化算法应用技术的研究[D].沈阳：东北大学，2009.

[5]邓显羽，彭勇，叶碎高，等.粒子群算法在水库（群）优化调度研究中的应用综述[J].水利水电科技进展，2010，30（5）：90-94.

[6]罗德相，周永权，黄华娟，等.多种群粒子群优化算法[J].计算机工程与应用，2010，46（19）：51-54.

[7]吕林，罗绮，刘俊勇，等.一种基于多种群分层的粒子群优化算法[J].四川大学学报：工程科学版，2008，40（5）：171-176.

[8]Van den Bergh F，Engelbrecht A P.A study of particle swarm optimization particle trajectories[J].Information Sciences，2006，176：937-971.

[9]Alba E，Luna F，Nebro A J，et al.Parallel heterogeneous genetic algorithms forcontinuous optimization[J].ParallelComputing，2004，30：699-719.

[10]李爱国.多协同粒子群优化算法[J].复旦大学学报，2004，43 （5）：923-925.

[11]高芳.智能粒子群优化算法研究[D].哈尔滨：哈尔滨工业大学，2008.

[12]Shi Y，Eberhart R C.A modified particle swarm optimizer[C]// Proceedings of the IEEE Congress on Evolutionary Computation.Anchorage，AK：[s.n.]，1998：69-73.

[13]刘建平.基于混沌和差分进化的混合粒子群优化算法[J].计算机仿真，2012，29（2）：208-212.

[14]辛斌，陈杰.粒子群优化与差分进化混合算法的综述与分类[J].系统科学与数学，2011，31（9）：1130-1150.

[15]吴茜，郑金华，宋武.改进的粒子群算法求解非线性约束优化问题[J].计算机工程与应用，2007，43（24）：61-64.

QING Yinan1,DING Yongsheng1，2,ZENG Xianhui1，2,HAO Kuangrong1，2

1.College of Information Sciences and Technology,Donghua University,Shanghai 201620,China
2.Engineering Research Center of Digitized Textile&Fashion Technology,Ministry of Education,Shanghai 201620,China

Aiming at the problem of optimal water supply dispatching for multi-reservoirs,it presents a Two-layer Multi-swarm Particle Swarm Optimal algorithm with Differential Evolution（DE-TMPSO）.The DE-TMPSO realizes the swarm size expansion and the dual parallel-running mechanism,so it can purposefully enhance the global search ability.Meanwhile the different granularity in multi sub-swarms parallel mechanism,dual direction optimal information flow between sub-swarms and differential evolution strategy also increase the local search ability.The DE-TMPSO can avoid the premature problem and increase the stability and the convergence rate.The DE-TMPSO is applied to optimal multi-reservoir water supply dispatching of a river in the south China.Results show that the DE-TMPSO is reasonable,and it provides a new approach for multi-dimensional and complicated optimization of multi-reservoir water supply dispatching.

optimal water supply dispatching;multi-reservoir;multi-swarm Particle Swarm Optimization（PSO）;differential evolution

针对水库群供水优化调度问题，提出了一种带差分进化的双层多种群粒子群算法（DE-TMPSO）。该算法实现粒子群优化算法的群体拓展和双并行运行机制，针对性地提高粒子群算法的全局搜索能力，同时采用不同粒度的多子群并行机制、种群间的双向最优信息流动以及引入差分进化策略也提高了该算法的局部搜索能力，在一定程度上避免了“早熟”现象的发生，具有较好的稳定性，收敛速度也得到了提高。该算法应用于我国南方某流域的水库群供水优化调度问题中，调度结果合理，为求解高维、复杂的水库群供水优化调度提供了新的思路和方法。

供水优化调度；水库群；多种群粒子群；差分进化

A

TP391

10.3778/j.issn.1002-8331.1208-0076

QING Yinan,DING Yongsheng,ZENG Xianhui,et al.Two-layer multi-swarm particle swarm optimal algorithm with application to optimal water supply dispatching of multi-reservoirs.Computer Engineering and Applications,2013,49 （5）：263-267.

国家自然科学基金重点项目（No.61134009）；国家自然科学基金（No.60975059）；教育部高等学校博士学科点专项科研基金（No.20090075110002）；上海市优秀学术带头人计划项目（No.11XD1400100）；上海领军人才专项资金；上海市科学技术委员会重点基础研究项目（No.11JC1400200）；中央高校基本科研业务费专项资金。

卿逸男（1988—），女，硕士研究生，从事智能系统、优化调度等研究；丁永生（1967—），男，博士，教授，博士生导师，从事智能系统、网络智能、物联网等研究；曾献辉（1974—），男，博士，副教授，从事智能系统、数字化纺织等研究；郝矿荣（1964—），女，博士后，教授，博士生导师，从事机器视觉、模式识别等研究。E-mail：ysding@dhu.edu.cn

2012-08-06

2012-12-05

1002-8331（2013）05-0263-05