算结果表明，CGGA 能够有效地提高求解质量和求解速度，从 收 敛 性 能 看，CGGA 由 于 种 群 隔 离 保 证 了 种 群 间 的 个 性 ，能
够在整个计算过程中不断进化，避免总群体趋于同化； 从并行性能看，CGGA 加速比 远 大 于 线 性 加 速 比，说 明 CGGA 能 够

充 分 地 利 用 各 计 算 进 程 ，提 高 并 行 效 率 ，避 免 资 源 浪 费 。
摘 要： 巨型水库群实时优化 调 度 涉 及 大 规 模、高 维 及 非 线 性 问 题，庞 大、动 态、复 杂 的 搜 索 空 间，采 用 传 统 遗 传 算 法
（ GA） 求解该类问题几乎不可行，并行遗传算法（ PGA） 除具有 GA 的优势外，还能充分利 用 并 行 计 算 机 的 计 算 能 力 、有 效
0 引言
水库优化调度研究的基本内容是，根据水库来流过程，遵照调度准则，运用优 化 方 法，寻 求 能 使 水 库 发 电、防 洪 、灌 溉 、供 水 等 各 部 门 在 整 个 分 析 期 内 的 总 效 益 最 大 的 调 度 方 案 ，其 本 质 上 属 于 对 高 维 、非 线 性 问 题 的 求 极 值 运 算。国内外学者对水 库 调 度 问 题 进 行 了 大 量 的 研 究 工 作，应 用 线 性 规 划 （ LP ） 、非 线 性 规 划 （ NLP ） 、动 态 规 划 （ DP） 、智能优化算法等方法进行水库优化调度模型求解。智能优化算法由于其鲁棒性及普适性已被成功应 用到 水库优化调度问题中，如遗传算 法 （ GA） 、粒 子 群 算 法 （ PSO） 、蚁 群 算 法 （ ACO） 、人 工 神 经 网 络 （ ANN） 等，其 中 遗
水 库第 t 时段的出库流量； ZUi，t 为第 i 水库在第 t 时段的上游水位； ZUL 为 i，t 第 i 水库在第 t 时段允许的最低水位，一
般为死水位； ZUU 为 i，t 第 i 水 库 第 t 时 段 允 许 的 最 高 水 位，一 般 在 非 汛 期 为 正 常 蓄 水 位，汛 期 为 防 洪 限 制 水 位；
第 31 卷 第 4 期 2012 年 8 月
水力发电学报 JOURNAL OF HYDROELECTRIC ENGINEERING
Vol． 31 No． 4 Aug． ，2012
粗粒度并行遗传算法在水库调度问题中的应用
李 想，魏加华，傅旭东
（ 清华大学 水沙科学与水利水电工程国家重点实验室，北京 100084）
并行计算程序使用 C + + 语言进行编程，在 Windows 7 64-bit 操作系统平台搭建 Microsoft Visual Studio 2010 开发环境，计算数据的存取通过 Oracle 11G 数据库完成，利用 MPI （ Message Passing Interface） 实现进程间消息传 递。计算过程在 DELL T5500（ 24 核处理器） 高性能工作站完成。
本文以三峡-葛 洲 坝 梯 级 水 库 为 例，将 基 于 双 向 环 迁 移 拓 扑 的 粗 粒 度 并 行 遗 传 算 法 （ coarse-grain genetic algorithm，CGGA） 应用于水库调度模型求解，分析了 CGGA 的计算结果、收敛性能、并行性能，通过该例计算证明 将 CGGA 应用于水库优化调度问题能够取得很好的效果。
地提高求解质量和求解速度，在解决巨 型 水 库 群 优 化 调 度 问 题 方 面 具 有 广 阔 的 应 用 前 景。 本 文 采 用 PGA 粗 粒 度 模 型
（ CGGA） ，引入迁移算子，以三峡-葛洲坝梯级水库为例，将基 于 双 向 环 迁 移 拓 扑 的 CGGA 应 用 于 水 库 调 度 模 型 求 解。 计
关键词： 并行遗传算法； 水库调度； 粗粒度模型； 三峡-葛洲坝梯级
中图分类号： TV697. 1
文献标识码： A
Application of coarse-grained genetic algorithm to reservoir operation
LI Xiang，WEI Jiahua，FU Xudong （ State Key Laboratory of Hydroscience and Engineering，Tsinghua University，Beijing 100084，China）
29
传算法是应用最早也是最广泛的一种优化算法。 1975 年，Holland 提出了遗传算法（ genetic algorithm，GA） ，其基本思想是 Darwin 的进化论及 Mendel 的遗传学
说在人工智能上的应用。GA 最早在国外被应用于求解经典四水库调 度 问 题 并 取 得 成 功［1，2］，国 内 学 者 研 究 的 工 作逐渐由单目标 水 库 优 化 调 度 问 题 发 展 为 多 目 标 水 库 优 化 问 题，在 算 法 性 能 和 计 算 效 率 上 都 取 得 了 一 些 进 展［3 － 5］。在科技不断进步的背景之下，不断扩大的问题规模及高度复杂的搜 索 空 间 对 GA 赋 予 了 新 的 使 命，即 如 何提高求解质量和求解速度。并行遗传算法有效利用遗传算法天然的并行性，一方面由于 并 行 计 算 机 的 高 速 并 行性从而加速了遗传算法的搜索过程，一方面由于种群规模的扩大和各子种群的隔离从而提高了求解质量 ，降低 了早熟的可能性。自 20 世纪 80 年代，GA 被应用 到 并 行 机 上，此 后 并 行 遗 传 算 法 理 论 研 究 得 到 不 断 发 展，90 年 代以来，并行遗传算法更是广泛应用 于 各 个 实 践 领 域。 一 些 学 者 将 并 行 遗 传 算 法 应 用 于 水 资 源 领 域： 武 新 宇［6］ 将基于双向环迁移拓扑的并行遗传算法应用于新安江模型参数率定 ； Tang 等［7］用 主 从 式 和 粗 粒 度 式 两 种 并 行 模 型改进 e-NSGAII 多目标遗传算法，将其用 于 水 资 源 领 域 的 三 个 问 题 并 讨 论 了 两 种 并 行 模 型 在 三 个 问 题 中 的 效 果； 陈立华［8］将基于单向环迁移拓扑交流局部最优解策略和 基 于 解 的 多 样 性 自 适 应 地 调 节 信 息 交 流 周 期 策 略 的 并行遗传算法应用于雅砻江梯级水库群优化调度。
Abstract： Real-time optimal operation of giant reservoirs is characterized by large-scale，high-dimensional and nonlinear problems． Large，dynamic and complex search space makes it almost impossible to solve such problems with a simple genetic algorithm． In addition to the advantage of simple genetic algorithm，parallel genetic algorithm can make full use of the computing power of parallel computers in improving solution quality and increasing solution speed，showing a promising prospect in resolving these difficult problems． This paper applies a coarse-grained genetic algorithm based on bi-directional ring topology to optimal operation of the Three Gorgest-Gezhouba cascade reservoirs． Results show that this algorithm can effectively improve the solution quality and increase the solution speed． In terms of convergence performance， it ensures the personality of each population through population isolation and allows populations to evolve constantly throughout the calculations，thus avoiding assimilation of the populations． In terms of parallel computing efficiency，the speedup of CGGA is much greater than the linear one，indicating its full use of calculation processes with less resources waste． Key words： parallel genetic algorithm； reservoir operation； coarse-grained genetic algorithm； the Three Gorges project and Gezhouba project cascade reservoirs
（ 4）
4） 出力约束
N Li，t "N i，t "N Ui，t
（ 5）
5） 边界条件
Z = Z i，0
i，start
Z i，0 = Z i，end
（ 6）
式中： Vi，t － 1 、V 分 i，t 别为第 i 水库在第 t 时 段 初、末 的 蓄 水 量； QINi，t 为 第 i 水 库 在 第 t 时 段 入 库 流 量； QOUTi，t 为 在 第 i