调度算法解决梯级水库的需水模型

水库优化调度模型是通过建立水库调度的数学模型加以实现。水库优化调度模型根据径流描述方法可分为确定性模型、随机模型及隐随机模型；按目标的不同又可分为单目标模型和多目标模型。目前水库优化调度算法包括常规优化算法和智能优化算法两类，常规优化算法主要包括线性规划法、动态规划法、非线性规划法、逐步优化法和网络分析法；智能优化算法主要包括遗传算法、神经网络算法、模拟退火算法、蚂蚁算法、粒子群算法和模糊集算法等。

常规算法的优化调度理论已经比较成熟，在水库优化调度中已经进行了广泛研究，并取得了丰硕成果。常规优化算法大多是建立在对可能调度的部分枚举上，但随着水库优化调度问题的计算量急剧增加及计算精度要求的不断提高，常规算法在实际应用中一直不是很理想。为此，各国学者进行了大量研究，从各种角度对其进行改进。近几年来，随着新优化算法研究的不断深入和完善，遗传算法等智能优化算法开始在在水库调度中得到了应用，丰富和发展了水库优化调度理论。其中，常用于求解梯级水电站优化调度问题的算法主要有遗传算法、人工神经网络和蚁群优化算法。本节着重研究多目标遗传算法在水库优化调度中的应用。

3.3.4.1　基本遗传算法

遗传算法是进化算法中最有代表性的一种。遗传算法是一种全局随机寻优算法，近几年发展迅速，成为求解梯级水电优化调度问题最常用的算法之一。该算法以自然选择和遗传理论为基础，通过自然选择、遗传、变异等作用机制，实现各个个体适应性的提高，体现了自然界中“物竞天择、适者生存”的进化过程。与系统分析方法不同，遗传算法从多个初始点开始寻优，沿多个路径进行搜索，能以较大概率地搜索到全局最优解；由于求解过程具有隐含并行性，可以有效避免“维数灾”；同时，遗传算法用的是目标函数本身的信息来寻优，不需要传统算法所必需的连续和可导条件，适应性广。但遗传算法在接近全局最优时搜索速度会变慢，易产生“早熟”现象。与传统搜索算法不同，遗传算法从一组随机产生的称为 “种群 （population）”的初始解集开始搜索过程。种群中的每个个体是问题的一个解，称为“染色体 （chromosome）”。染色体是一串符号，比如一个二进制字符串。这些染色体在后续迭代中不断进化，称为遗传。在每一代中用 “适应度 （fitness）”来度量染色体的好坏，生成的下一代染色体称为后代 （offspring）。后代是由前一代染色体通过交叉（crossover）或者变异（mutation）运算形成的。在新一代形成过程中，根据适度的大小选择部分后代，淘汰部分后代，从而保持种群大小是常数。适应度高的染色体被选中的概率较高，这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定等5个要素组成了遗传算法的核心内容。GA的标准计算过程流程见图3-3。

3.3.4.2　多目标遗传算法

多目标决策问题都有一些共同的特点，其中最显著的是以下两点：目标间的不可公度性和目标间的矛盾性。所谓目标间的不可公度性是指各个目标没有统一的度量标准，因而难于进行比较。目标间的矛盾性是指如果采用一种方案去改进某一目标的值，可能会使另一目标的值变坏。

多目标优化技术可以分为两大类：①化多目标为单一目标；②Pareto支配技术，即非劣解生成技术。常用的多目标优化处理方法有：权重法、约束法、多目标线性规划的单纯形法、多维动态规划等[200]。基于Pareto非劣解概念进行排序方法主要优点就在于此方法对非劣解前沿的形状或连续性没有特殊的要求。该方法主要包括多目标遗传算法（MOGA）、非支配排序（Non-Dominated Sorting）遗传算法和小生境（Niched）Pareto遗传算法，其中以改进的非支配排序 （Non-Dominated Sorting）遗传算法 （NSGAⅡ）较为典型。

NSGA是由Srinivas和Deb[201]提出的，这种方法对个体做很多层次的分类。在进行选择前，整个种群先根据非劣解性进行排序，所有的非劣解个体都被归为一类，同时指定一个虚假的适应度（适应度的值可以根据这些个体占种群个体数的比例来给出）。为了保证种群的分布，这些个体都具有相同的适应度。然后这一部分个体被取出，其余的个体再采用相同的方法进行分类，直到所有的个体都被分类完毕。然后采用随机的方法选出个体，因为在最前沿的个体具有最大的适应度，所以被传递到下一代的可能性也就越大。这种方法可以搜索非劣解区域，而且可以使种群很快收敛到这一区域。本算法的效率集中在那个虚假的适应度上，可以解决目标函数为任意数量的问题，无论是最大化还是最小化。同时由于是在变量空间进行比较，所以可以允许具有相同目标函数的不同点的存在。这种算法的主要缺点是相对MOGA而言效率较低 （不仅仅是计算速度，也包括所生成Pareto非劣解前沿的质量）。

NSGA Ⅱ是在NSGA的基础上加上了精英策略、密度值估计策略和快速非支配排序策略，是对NSGA算法的改进，在很大程度上改善了NSGA的缺点。NSGA Ⅱ[202]具有以下优点：①提出新的基于分级的快速非支配排序算法，将计算复杂度由O（m N 3）降到O（m N 2），其中m表示目标函数的数目，N 表示种群中个体的数目；②为了标定分级快速非支配排序后同级中不同元素的适应度值，也为使准Pareto域中的元素能扩展到整个Pareto域，并尽可能均匀遍布，提出了拥挤距离的概念，采用拥挤距离比较算子代替需要计算复杂的共享参数的适值共享方法；③引入了保优机制，扩大了采样空间，经选择后参加繁殖的个体所产生的后代同其父代个体共同竞争来产生下一代种群，因此有利于保持优良的个体，迅速提高种群的整体水平。

下面介绍一下NSGA Ⅱ中相关理论概念及其算法流程。

图3-3　遗传算法流程图

（1）NSGA Ⅱ相关概念。

1）群体排序：在选择运算之前，根据个体的非劣解水平对种群分级。具体方法为：将当前种群中所有非劣解个体划分为同一等级，并令其等级为1；然后将这些个体从种群中移出，在剩余个体中找出新的非劣解，再令其等级为2；重复上述过程，直至种群中所有个体都被设定相应的等级。

2）确定拥挤距离：把种群中的每一个体与同级别相邻两个体间的局部拥挤距离称为该个体的拥挤距离，用id表示，它指出了在个体周围包含个体i本身但是不包含其他个体的最小的长方形。拥挤距离大的个体参与繁殖和进化的机会较多，从而维持种群的多样性。

3）拥挤距离比较：拥挤距离比较是确保算法能收敛到一个均匀分布的Pareto曲面。经过排序和拥挤距离计算，群体中的每个个体i都得到两个属性：非支配序ir；拥挤距离id。则定义偏序关系≥n为：i≥nj，表示ir＞jr的情况，或者表示ir=jr时id＞jd的情况。上式的意义为：如果两个个体的非支配排序不同，取序号低的个体（分级排序时，先被分离出来的个体）；如果两个个体在同一级，则取周围较不拥挤的个体。

4）精英保留：首先产生一个组合的种群Rt=Pt∪Qt，种群Rt的个数为2N。然后种群Rt根据非支配关系排序，新的父代种群由当前的第一级非支配个体填充，直到个体数量达到N 就形成了新的父代种群Pt+1，然后在此基础上进行遗传操作，形成子代种群Qt+1。

（2）NSGA Ⅱ算法流程。NSGA Ⅱ算法基本步骤可以分为以下5个步骤。

1）随机生成一个父代种群P0，并置代数计数器t=0。种群成员根据非劣法则进行排序，每一个解都计算其适应度值，并归于不同的级别，1级代表最好，2级次之，以此类推。然后运用常规的二进制锦标赛选择方法，并通过交叉和变异操作产生一个大小为N的子代种群Q0。

2）合并父代Pt和子代Qt生成新种群Rt，则Rt大小为2N。

3）从Rt中选择N 个个体组成新一代种群Pt+1，步骤为：①对Rt按照非劣排序，由于它包含了当前和以前世代的所有成员，所以最优解也包含在内，假设生成的序列集合分别为λ1，λ2，λ3，…；②如果λ1的大小大于N，则对λ1进行拥挤度计算，通过拥挤度比较算子对个体进行排序，取出前N 个个体组成Pt+1；如果λ1的大小等于N，则直接用λ1组成Pt+1；如果λ1的大小小于N，那么就从序列λ2中补足，如果还是不够，则从序列λ3补足，以此类推，直到找到N 个体。特别注意：如果所有选定的序列集合的个体总和等于N，则用它们直接组成Pt+1；如果所有选定的序列集合的个体总和大于N，则对最后入选的序列进行拥挤度计算并排序后，抛弃其中多余的个体。

4）t=t+1，如果t大于算法规定的最大迭代代数，则算法结束，否则继续步骤4）。

5）对Pt通过拥挤联赛选择、交叉操作和变异操作得到子代种群Qt，跳到步骤2）。其中拥挤联赛的选择步骤如下：①对所有个体进行非劣排序，并计算每个个体的拥挤度；②利用拥挤度比较算子，对所有的个体进行联赛选择。NSGA Ⅱ算法流程图如图3-4所示。(www.xing528.com)

3.3.4.3　水库优化调度模型求解的遗传算法

根据上述优化调度数学模型的目标函数呈非线性，约束条件多，属于复杂的多目标非线性优化问题，用传统的优化算法进行求解比较复杂而且效率不高。本节采用基于实数编码的遗传算法进行求解。

1.遗传编码设计

图3-4　NSGA Ⅱ算法流程图

式中 Znt，min，Znt，max——第n个有调节能力水库在时段t的水库水位最小值和最大值，由于水库汛期和非汛期水库控制水位不同而分别进行处理；

l——精度控制整数；

Nrand——随机产生的实数。

2.种群初始化

3.适应度计算

本节以水库优化调度的目标函数作为适应度函数来判定个体优劣程度，目标函数计算是根据水库的初始水位（或库容）、水量平衡方程式、水位-库容曲线以及下游水位流量关系曲线，计算各级电站的各时段水头、各时段的最大最小允许流量，最后确定各时段目标函数值。

4.遗传操作

遗传操作主要包括选择、交叉和变异操作。选择操作采用轮赛制方法，具体计算过程为：①计算群体中所有个体的适应度总和∑Fitness；②计算每个个体的相对适应度大小，即每个个体i被遗传到下一代群体中的概率Pi=Fitness（i）/∑Fitness；③根据每个个体的概率大小进行轮赛制选择。

5.遗传算法终止判断

遗传算法迭代的终止条件一般采用以下准则：①是否达到预期算法的最大代数；②是否找到了某个较优染色体；③连续几代迭代后得到较优解是否变化等。本节采用拟定最大进化代数和评价最优解的标准方差，作为遗传终止的判断条件。

根据以上计算步骤，可以看出对于水库优化调度的遗传算法可以理解为：在水位的可行变化范围内，随机生成m组染色体，在满足一定的约束条件下，按预定的目标函数评价其优劣。通过一定的遗传操作（选择、交叉和变异），将适应度低的个体淘汰，使得适应度高的个体有更大机会被遗传到下一代，如此反复，直至满足一定的收敛准则。

应用遗传算法解决水库调度优化问题还需注意以下问题：个体在交叉和变异操作之后将影响本时段下游水库的入流和出流，需修正直至最后一个梯级的入流和出流，还可能影响下一时段直至最后一个时段的水位搜索空间，需校核交叉和变异之后的水位是否在可行范围内，进而可能需修正下一时段直至最后一个时段所有水库的决策水位和出流，以免生成不可行解。