并行动态规划和改进遗传算法在水库调度中的应用分析

0 引言

水库优化调度是典型的多维非线性优化问题，求解方法显得尤其重要。动态规划是由Bellman提出的用于解决多阶段决策过程最优化问题的一种数学方法[1]。它是最优化领域中一个重要分支，是一种研究多段决策过程的递推最优化方法。它可以将复杂的初始问题划分为若干个阶段的子问题，逐时段求解，而水库调度正是一种与时间过程相关的典型动态多阶段决策过程，决策具有无后效性，也是水库调度中应用最多的方法之一。但是采用动态规划等传统算法[2]在实际应用中常常会遇到维数灾的问题，由于动态规划法求解时，随着计算精度的提高，计算所需时间成指数倍增长，计算效率明显降低。人们又提出了不少改进的传统优化算法，但在某些方面仍有其缺陷。如逐次逼近动态规划难以保证收敛到全局最优解等;毛睿[3]等提出了基于并行分布式计算方法进行库群优化调度，可大大降低计算时间。

针对水库调度优化问题，人们在实践中提出生物进化算法。遗传算法最初由美国Michigan 大学 J.Holland 教授于 1975 年首先提出来的，但是经典的遗传算法不是完全遍历的马尔可夫过程，收敛速度慢、接近全局最优解时很难收敛，且容易早熟。特别对于复杂非线性问题，更容易发生局部收敛。许多学者从编码方式的角度改进遗传算法，马光文等人[4]采用二进制编码的遗传算法在水库优化调度中得到应用;畅建霞等人[5]采用了十进制编码的优化方法改进遗传算法;陈立华和梅亚东等人[6]采用超立方体浮点编码遗传算法对遗传算法有一定的改进。采用自适应的交叉率和变异率可以改进遗传算法的收敛性[7~8];但是在交叉和变异过程中随机性较大，随机初始种群多样性较差，随着种群适应度提高而局部收敛，初始种群优劣一定程度上决定了算法全局收敛性。

水库优化调度从基本的动态规划算法和遗传算法两种求解方法出发，并在动态规划算法加入并行模块，提高计算效率，在一定程度上缓解了维数灾采用分层自适应遗传算法，改善了初始种群的多样性，提高了收敛速度，改善了调度效益;结合三峡水库实际调度，并采用改进的算法求解水库优化调度模型。

1 水库调度模型

1.1 目标函数

对于水库优化调度决策，一般来讲都是多目标决策问题，目标包括防洪、发电、航运以及下游用水效益等。

2 算法的改进

2.1 动态规划算法应用

1) 基本的动态规划算法

适用动态规划的问题必须满足最优化原理和无后效性。动态规划法适用于求解水库优化调度模型，具体求解步骤如下：

① 阶段变量：由于水库优化调度是按照时间过程进行的，属于多段决策过程，阶段变量按时间段选取。

② 状态变量：状态变量选取水库对应变量，例如水位、库∞容等。其水库水位和库容反应了调度过程的演变，并满足无后效性要求。

③ 决策变量：时段末的水库状态对应一个决策，即决策变量。

④ 状态转移规律：根据决策变ฟ量从而得到时段末的一个状态，作为下一时段的起始状态。

2) 并行算法设计

水库优化调度模型的求解过程具有一定的并行性，有利于并行ฑ计算的实施。多核处理器的日益普及为并行机制的实现提供了必要的硬件基础。为了防止单线程计算而导致计算资源的浪费;在动态规划算法中嵌入并行模块。并行计算是指，将一个目标问题分解成多个子任务，分配给不同处理结构，各个结构之间相互协同，在同一时段内，并行地的执行子任务，从而达到加速求解速度，或者减少目标问题的规模程度。OpenMP 采用共享存储的编程模式，所谓共享存储，是指各个处理器[8]可以对共享存储器中的数据进行存取，数据对每个处理器而言都是可以访问到的，不需要在处理器之间进行传递，即数据通信是通过读或写共享存储单元来完成。 OpenMP 是基于线程的并行编程模型，并采用了Fork-Join 的并行模型。所有 OpenMP 程序开始于一个主线程，并一直串行执行，直到遇见第一个并行域才开始并行。即①Fork：主线程创建一行并行线程，并行域中代码在不同线程队中运行;②Join：当所有的并行域执行完之后，它们或被同步或被中断，最后回到主线程的运行。所有的 OpenMP 的并行化，都是通过嵌入到源代码中的编译制导语句来实现并行化的，衡量算法效率指标是计算任务所使用的时间和空间资源。在水库调度动态规划计算中，计算量最大的部分就是重复计算决策变量对应的适应度值。假设电站水位离散个数为 k，除了起始和终止蓄水状态，其余阶段始末各有 k 个组合状态，需进行 k2次计算。若时段数为 T，每轮寻优需要 2k+k2次计算，时间复杂度为 O，所以比较容易遭遇维数灾。加入并行设计后，假设 CPU 核数为 P，并行后会分成 P 个线程同时计算，则每轮迭代时需要计算 [2k+k2]/P 次。由于线程与主线程之间的通信是在临界区，效率较高[9]，因此并行后复杂度应为 O+P)。可见并行算法的设计能够在相同的时间内能够完成更多的工作。

3) 动态规划实现并行化的具体步骤：

① 在并行域前，首先主线程计算水库的各个时段的所有的决策方案，并用并行化嵌套语句设置多个子线程。

② 每个子线程从对应共享内存中获取计算数据，包括电站的基础属性数据、各类特征曲线和约束条件等。每一个线程由一个 CPU 内核处理，同时每一个子线程只允许与主内存进行通信和数据交互，核与核是相互隔离的，从而保证各个线程独立工作。

③ 子线程通过与共享内存的通信得到数据，计算当前时段的一个决策方案的发电量和目标适应值，并将结果返回到主内存中，从而达到了汇合。

④ 当所有子线程执行完成后，结束并行计算，回到主线程，回到主线程环境中。

2.2 改进遗传算法应用

遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，通过种群交叉变异进化寻优的启发式的搜索算法。在自适应遗传算法寻优过程中，用适应度函数评价每一代个体的优劣，通过对整个参数空间编码得到待处理种群，再对其检测并选择ฝ优良个体进行随机交叉得到下一代种群，新一代种群中优良个体的性状得以保留，同时适应度低的个体将被淘汰。 改进的自适应遗传算法分两层，第一层采用无搜索策略的广度搜索算法寻找种群的多样性，通过外部存档的方式储存精英个体[10]，增加种群多样性，从而增强起初母体的鲁棒性;第二层采用第一层外部存档的初始种群，并嵌套广度搜索的变异模块，通过合理判定条件进入随机变异，防止陷入局部最优，并采用自适应遗传算法进行全局搜索。分层收敛算法具体设计步骤如下

3 实例应用

三峡工程是治理开发长江的关键性工程，水库正常蓄水位 175m，防洪限制水位 145m，枯期消落低水位 155m，具有巨大的防洪、发电、航运和枯期向下游补水等综合利用效益，三峡水库防洪库容 221.5 亿 m3，兴利库容 165.0 亿 m3，有巨大的调蓄能力。 由于三峡水库可进行年调节，而汛期基本保持汛限水位不变，所以对供水期进行优化调度更加合理，即从开始蓄水到翌年的汛前进行优化调度，采用旬为计算时段。以典型枯水年供水期作为研究对象，选取三峡坝址宜昌水文站的天然来水 95%保证率的 1972 年的径流系列作为研究依据。

4 结论

基于动态规划算法，嵌入并行计算模块;在自适应遗传算法基础上，采用外部存档的方式，提出了改进的分层遗传算法，并将改进算法应用到三峡水库实际调度中。实验算例的应用情况表明，并行动态规划算法相，比于串行计算，提高了算法计算效率;与其它两个算法相比较，分层遗传算法提高了收敛速度并改善了调度效益，而长系列的计算结果进一步验证了改进算法的有效性。改进的算法从不同的角度提高了求解速度并改善了求解质量，为水库优化调度问题的求解提供了一定的参考。