粗粒度并行自适应混合粒子群算法及其在梯级水库群优化调度中的应用

王 森，马志鹏，李善综，熊 静

(1.珠江水利科学研究院 a.资源与环境研究所；b.水利部珠江河口动力学及伴生过程调控重点实验室，广州 510611；2.水利部 珠江水利委员会技术咨询中心，广州 510611)

粗粒度并行自适应混合粒子群算法及其在梯级水库群优化调度中的应用

王 森1a,1b，马志鹏1a，李善综2，熊 静1a

(1.珠江水利科学研究院 a.资源与环境研究所；b.水利部珠江河口动力学及伴生过程调控重点实验室，广州 510611；2.水利部 珠江水利委员会技术咨询中心，广州 510611)

为了充分利用现今普及的多核配置计算机，提高大规模梯级水库群优化调度问题的求解效率，提出了梯级水库群优化调度的粗粒度并行自适应混合粒子群算法。该方法以自适应混合粒子群算法为求解基础，采用粗粒度并行设计模式，利用Fork/Join多核并行框架的分治策略，将其初始种群递归划分为多个子种群，平均分配到不同的内核逻辑线程中实现并行计算，并在各子种群优化结束后，合并优化结果集从而输出全局最优解。以澜沧江下游梯级水库群发电优化调度为例，利用该方法进行计算。结果表明，该方法能充分发挥多核配置的计算性能，在4核环境下最大加速比达到3.97，缩短计算耗时1 787.2 s，计算效率显著提高，为我国不断扩张的大规模梯级水库群优化调度提供了一种切实可行的高效求解途径。

梯级水库群；优化调度；粗粒度；多核并行；Fork/Join；粒子群算法

1 研究背景

随着我国水电开发迅速发展，各大流域已规划或已建成具有电站级数多、装机容量大等特点的大规模梯级水库群，其优化调度凸显非线性、高维数、动态多阶段、约束强耦合等特点[1]。采用传统的优化方法求解大规模梯级水库群优化调度问题非常困难[2]，如动态规划方法在求解时易造成“维数灾”问题，甚至可能因内存溢出导致无法计算；逐步优化算法对初始解敏感度高，求解易陷入局部最优。随着智能算法的兴起和发展，涌现出如遗传算法[3-4]、粒子群算法[5-6]、蜂群算法[7]、蚁群算法[8]等多种具有计算速度快、全局收敛性好等优点的群体算法。这些算法有效地克服了传统优化算法求解的不足，并成功应用于梯级水库群优化调度，是我国当前大规模梯级水库群优化调度建模求解的可行方法。但是，群体算法的求解精度与计算规模存在一定竞争关系，即种群规模或迭代次数越大，在解空间搜索到全局优化解的概率越大，求解精度越高，但是同时也意味着计算耗时越多，求解效率越低。因此，在保证群体算法求解质量的同时，研究其高效计算方法，具有非常重要的科学意义。

并行计算一直是计算机科学领域的研究热点，在多核处理器已成为现今普及配置的背景下，并行技术已成功应用于众多科学领域，是一种原理清晰、操作简单且易于实现的高效求解技术[9-10]。本文以笔者前期研究成果自适应混合粒子群算法[11](adaptive hybrid particle swarm optimization，AHPSO)为代表群体算法，采用初始种群递归划分为多个子种群的粗粒度并行设计模式，利用Java编码的Fork/Join多核并行框架[12]，提出并行自适应混合粒子群算法(parallel adaptive hybrid particle swarm optimization，PAHPSO)，并应用于澜沧江下游梯级水库群发电优化调度。结果表明，方法的并行化求解能够有效提高求解效率，且其粗粒度的并行化设计可为其他群体算法提供参考和借鉴。

2 库群发电量最大模型

2.1 目标函数

梯级水库群发电量最大模型可描述为：充分利用调度期内各电站的预报或情景径流，在考虑水库水量平衡、蓄水量、出力、出库等约束条件的前提下，制定水库群联合优化调度方案，使调度期内总发电量最大。目标函数数学表达式为

(1)

2.2 约束条件

水量平衡约束为

(2)

蓄水量约束为

(3)

发电流量约束为

(4)

出库流量约束为

(5)

出力约束为

(6)

始末水位约束为

(7)

水电系统总出力约束为

(8)

3 并行自适应混合粒子群算法

3.1 自适应混合粒子群算法

AHPSO算法以粒子群算法(PSO)为基础算法，优化步骤主要为：①初始化种群；②计算粒子适应度、个体最优解及全局最优解；③更新粒子位置和速度。AHPSO与PSO相比，其改进策略主要有：①利用混沌算法的遍历性优点生成初始种群，提高初始解的质量；②定义了粒子能量、粒子能量阈值、粒子相似度，以及粒子相似度阈值4个参数，以提高初期全局搜索和后期局部精化能力；③算法进化后期引入了基于邻域的贪心随机搜索策略提高局部搜索能力。文献[11]对该算法的详细改进策略及应用方法作了深入研究与介绍，并将其成功应用于梯级水库群优化调度。AHPSO算法迭代寻优过程为：

(1) 参数初始化。设定种群规模、混沌迭代次数、最大迭代次数、飞行加速度、惯性因子、粒子能量上下限以及粒子相似度上下限等参数。

(2) 种群初始化。采用混沌映射公式初始化粒子个体位置及飞行速度。

(3) 计算粒子适应度、粒子个体最优解以及种群全局最优解。

(4) 计算粒子能量以及粒子能量阈值，判断是否对粒子位置与速度执行变异操作。

(5) 计算粒子相似度以及粒子相似度阈值，判断是否对较差粒子的历史最优位置执行变异操作。

(6) 引入基于邻域的贪心随机搜索策略对粒子的个体最优位置进行更新。

(7) 更新粒子种群。

(8) 判断迭代是否结束。

3.2 Fork/Join框架简介

Fork/Join多核并行框架最早由学者Lea[12]在2000年提出，其汇编语言为Java，并已集成于Java版本7及其以上版本中作为语言标准库。框架特点主要有：

(1) 集成了线程池并行技术，默认生成的子线程数等于硬件配置的逻辑线程数。

(2) 采用“分治法”策略将父任务递归分解为多个相互独立、规模更小且计算任务相同的子任务，再汇总每个子任务的解从而获得父任务的解。图1为“分治法”策略框架图。

图1 “分治法”策略框架图Fig.1 Frame diagram of divide-and-conquer strategy

(3) 在“分治法”策略划分子任务的过程中，子任务的最大规模由设定的阈值进行控制，即当子任务规模≤阈值时，“分治法”停止运行，子任务开始在子线程中执行。图2为阈值控制框架图。该阈值的实质是子任务规模的上限，若阈值过小，划分子任务数越多，造成更大的管理消耗；若阈值过大，划分子任务数越少，不利于子线程的充分利用。因此，在需保证多核资源充分利用的前提下，可设置阈值大小使分解的子任务数等于逻辑线程数，则阈值的计算公式为

(9)

式中：符号「 ⎤表示取上整数；β，α，w分别为阈值、父任务计算规模、CPU的逻辑线程数。其中，具有“超线程”技术的硬件配置每个核心可以开启2个逻辑线程。

图2 阈值控制框架图Fig.2 Frame diagram of threshold controlling

(4) 设计了“工作窃取”算法，即当某个线程处于闲置状态时，可从其他线程中“窃取”任务执行，减少线程闲置时间。

3.3 PAHPSO并行方法设计

AHPSO方法的初始种群由不同的个体粒子组成，粒子的个数即为种群的计算规模。由于每个粒子代表解空间的一个候选解，采用划分初始种群为多个规模更小子种群的粗粒度并行设计，并不影响每个粒子在其子种群中的搜索寻优。因此，子种群之间的优化搜索是相互独立的，具有天然的并行性。图3为PAHPSO方法并行设计框架示意图。

图3 PAHPSO方法并行设计框架示意图Fig.3 Schematic diagram of parallelism design framework for PAHPSO

其并行步骤主要为：

(1) 划分子种群。从主线程中获取初始种群的计算规模作为父任务规模，采用Fork/Join阈值计算公式(式(9))将父任务划分为多个规模更小的子任务，且每次递归分解将父任务规模对半划分为2个规模相同的子任务，直至子任务规模小于或等于阈值，停止分解。

(2) 子线程同时计算各自分配的子任务。每个分配到子线程的子任务的种群规模相同，并且设置相同计算参数的AHPSO方法计算各子任务的最优解。

(3) 输出最优解。当各子线程完成所有子任务的计算，合并所有子任务的最优解并筛选出全局最优解，返回主线程。

4 实例应用

4.1 基础信息

为了验证PAHPSO方法的并行效率，采用澜沧江下游梯级水库群年发电量最大模型作为计算实例。梯级自上游而下分别为小湾(多年调节)、漫湾(季调节)、大朝山(年调节)、糯扎渡(多年调节)和景洪(季调节)水库，水库群梯级拓扑结构见图4，水库特征属性见表1。用于测试的计算机CPU配置为Intel Xeon E31245@3.30GHz (4核)，测试状态分别设置“超线程”开启和关闭状态进行对比分析。

图4 水库群拓扑结构

表1 各计算水库特征属性

4.2 并行性能指标

加速比Sp和效率Ep是衡量并行算法性能的2个常用指标[13]，其数学表达式分别为：

(10)

(11)

式中：T1为串行环境下算法执行时间(s)；Tp为p个内核环境下算法执行时间(s)。

4.3 测试方案

AHPSO方法的可行性和计算精度已在文献[11]中的梯级水库群优化调度中得到了验证，本文重点研究PAHPSO方法的并行效率。由于PAHPSO方法采用种群分解的粗粒度并行设计模式，为了测试不同种群规模条件下算法的并行性能，设置4组种群规模大小不同的方案进行仿真测试。各方案种群规模大小设置见表2。另外，其他参数设置与文献[11]中相同。

表2 4组仿真方案种群规模大小

4.4 并行结果

表3为PAHPSO方法在不同并行核数、超线程启闭状态下的并行结果。从表3中可以看到，PAHPSO方法的计算时间随着核数的增加大幅缩减，并行效果非常明显。

表3 PAHPSO算法测试结果

对于同一方案，算法在不同并行环境下的并行性能有所不同。以方案1计算结果为例，随着并行核数增加，在1核、2核、4核环境下的加速比分别为1.00，1.98，3.84，计算加速比逐渐提高。而且在相同核环境下，在“超线程”开启状态下获得了更佳的加速效果，主要是因为“超线程”技术能够在1个核心上模拟出2个逻辑线程，减少硬件CPU的闲置时间，更好地发挥CPU的计算效率。但是随着并行核数增加，在“超线程”启闭相同环境下，1核、2核、4核且“超线程”开启状态下的效率分别为100.0%，99.0%，96.0%，呈逐渐下降趋势，主要原因是并行核数越多，则执行线程数越多，资源管理消耗、线程间通信时间、内存占用等因素也相应提高，直接导致了并行效率的下降。

对于不同方案，算法的种群规模越大，并行性能的优势越明显。4组仿真方案在4核“超线程”开启状态下的缩减时间分别为486.6，926.3，1 381.0，1 787.2 s，并行效果非常明显。在相同的并行环境下，以4核“超线程”开启为例，随着种群规模增大，计算加速比、效率逐渐增加，且计算加速比越来越接近理想加速比。主要原因是计算任务规模越大，线程处于闲置状态的时间越少，线程利用率更加充分。另外，方案3和方案4在2核环境“超线程”开启状态下的计算加速比大于理想加速比，发生“超线性”加速比现象，主要原因有2点：①“超线程”技术能够有效提高线程利用率；②Fork/Join是一种基于内存共享的并行框架，实现了内核中缓存共享，而且Fork/Join具有独特的队列设计，其“窃取”算法能够有效减少物理缓存的占用和争夺，减少线程闲置时间，提高线程利用率。

5 结 论

目前，我国大水电开发格局已初步形成，梯级水库群优化调度势必面临求解维数高、计算规模庞大等难点问题，因此，研究合理高效的梯级水库群求解方法具有非常重要的科学意义。本文结合计算机科学领域的并行计算思想，利用种群算法子种群之间的天然并行性特点，以自适应混合粒子群算法为代表群体算法，采用流行的Fork/Join多核并行框架，提出了粗粒度并行自适应混合粒子群算法，并应用于澜沧江下游梯级水库群优化调度，结果表明：

(1) 并行自适应混合粒子群算法能够充分利用多核资源大幅度缩减计算时间，且在4核环境下基本能缩减75%的计算耗时，计算效率显著提高。

(2) 随着并行核数的增加，并行自适应混合粒子群算法的加速比逐渐增加，但效率逐渐下降。

(3) 在相同并行环境下，随着计算规模的增加，并行自适应混合粒子群算法的加速比逐渐增加，效率逐渐提升。

(4) “超线程”技术的开启能够提高硬件配置的利用率，进一步提高算法的并行效率。

(5) 并行自适应混合粒子群算法采用的粗粒度并行设计模式可为其他种群算法的并行化提供参考和借鉴。

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

[2] LABADIE J W. Optimal Operation of Multireservoir Systems: State-of-the-art Review[J]. Journal of Water Resources Planning and Management, 2004, 130(2): 93-111.

[3] 刘心愿，朱永辉，郭小虎，等. 水库多目标优化调度技术比较研究[J]. 长江科学院院报，2015，32(7)：9-14.

[4] 陈 瑞，陈求稳，陈 进. 基于改进遗传算法的生态友好型水库调度[J]. 长江科学院院报，2012，29(3)：1-6.

[5] 罗军刚，张 晓，解建仓. 基于量子多目标粒子群优化算法的水库防洪调度[J]. 水力发电学报，2013，32(6)：69-75.

[6] 冯雁敏，张雪源，梁年生. 松江河梯级水电站短期优化调度数学模型分析[J]. 长江科学院院报，2012，29(4)：1-6.

[7] 张德发，周建中，卢 鹏，等. 变尺度混沌蜂群算法在梯级库群优化调度中的应用[J]. 水电能源科学，2014，32(4)：46-50.

[8] 原文林, 曲晓宁. 混沌蚁群优化算法在梯级水库发电优化调度中的应用研究[J]. 水力发电学报, 2013, 32(3): 47-54.

[9] 王丽萍，孙 平，蒋志强，等. 并行多维动态规划算法在梯级水库优化调度中的应用[J]. 水电能源科学，2015，33(4)：43-47.

[10]张忠波，吴学春，张双虎，等. 并行动态规划和改进遗传算法在水库调度中的应用[J]. 水力发电学报，2014，33(4)：21-27.

[11]王 森，武新宇，程春田，等. 自适应混合粒子群算法在梯级水电站群优化调度中的应用[J]. 水力发电学报，2012，31(1)：38-44.

[12]LEA D. A Java Fork/Join Framework[C]∥Proceedings of the ACM 2000 Conference on Java Grande. San Francisco, California, June 3-5, 2000：36-43.

[13]蒋志强，纪昌明，孙 平，等. 多层嵌套动态规划并行算法在梯级水库优化调度中的应用[J]. 中国农村水利水电，2014，9(9)：70-75.

(编辑：罗 娟)

Coarse-grained Parallel Adaptive Hybrid Particle Swarm OptimizationAlgorithm and Its Application to Optimal Operation ofCascaded Reservoirs

WANG Sen1,2, MA Zhi-peng1, LI Shan-zong3,XIONG Jing1

(1.Resources and Environment Department, Pearl River Water Conservancy Science Research Institute,Guangzhou 510611, China; 2.Key Laboratory of Pearl River Estuarine Dynamics and Associated Process Regulation of the Ministry of Water Resources, Pearl River Water Conservancy Science Research Institute,Guangzhou 510611, China; 3.Technical Advisory Center of Pearl River Resources Commission of the Ministry of Water Resources, Guangzhou 510611, China)

To improve the computing efficiency of optimal operation of large-scale cascaded reservoirs, a coarse-grained parallel adaptive hybrid particle swarm optimization (PAHPSO) algorithm is proposed in full use of the popular multi-core computers. The method is based on adaptive hybrid particle swarm optimization (AHPSO) algorithm, and adopts the coarse-grain model and divide-and-conquer strategy of Fork/Join multi-core parallel framework to divide the initial population into multiple small-scale subpopulations, which are assigned to different logical threads averagely for parallel computing. After the optimization computation for all subpopulations, the optimization result sets are merged to obtain the globally optimal solution. The proposed algorithm is applied to the generation and operation of cascaded reservoirs located on the lower stream of Lancang River. Results show that the method gives full play to multi-core computer performance, and the maximum speedup in 4-core parallel environment reaches 3.97 with the time-consuming cutting down by 1 787.2 s. The computing efficiency has improved significantly and it provides a feasible and efficient solution for the optimal operation of increasingly expanding large-scale cascaded reservoirs in China.

cascaded reservoirs; optimal operation; coarse-grain; multi-core parallel; Fork/Join; particle swarm optimization algorithm

2015-12-03

国家重点研发计划资助项目(2017YFC0405905);水利部公益性行业科研专项(201401013，201501010)

王 森(1986-)，男，江西万载人，工程师，博士，主要从事水库群联合优化调度及水利信息化等研究，(电话)020-87117637(电子信箱)wangsen19861227@163.com。

马志鹏(1979-)，男，江苏江都人，高级工程师，博士，主要从事水文水资源系统分析等研究，(电话)020-87117019(电子信箱)zhipengma@163. com。

10.11988/ckyyb.20151020

2017,34(7):149-154

TV697.1

A

1001-5485(2017)07-0149-06