《1 引言》

1 引言

遗传算法 (Genetic Algorithm, 简称GA) 是美国密执安大学的著名科学家J.H.HoIIand教授于20世纪70年代中期提出来的一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术[1,2]。遗传算法提供了一种求解复杂系统优化问题的通用框架, 它不依赖于问题的具体领域, 对所求解问题的种类具有很强的鲁棒性, 它以决策变量的编码作为运算对象, 直接以目标函数值作为概率搜索的基本信息, 可同时使用多个搜索点的信息, 并且占用计算机内存少, 尤其适用于求解一些非线性、多模型、多目标和多参数的复杂系统的全局总体优化问题。水电站优化调度是一个典型的全局优化问题, 将遗传算法应用于水库优化调度中, 可解决应用动态规划等算法时出现的“维数灾”问题, 考虑到标准遗传算法在应用中存在的问题, 本文通过改进提出一种改进遗传算法并将其应用于水库优化调度领域, 改变通常采用的随机水位变化序列为基础的个体编码方法, 通过合理的编码, 不仅使遗传算法在水库优化调度中体现了强大的适应性, 同时也简化了水库优化调度中遗传算法的实现过程。

《2 遗传算法的改进》

2 遗传算法的改进

基于对自然界生物在遗传和进化过程中选择、交叉、变异机理的模仿, Goldberg提出了标准遗传算法 (Standard Genetic Algorithm, 简称SGA) 的实现过程。SGA以随机方式产生一个对应于优化问题可行解的初始群体后, 采用三种遗传算子, 即选择算子、交叉算子和变异算子[2], 通过在进化过程中对各代群体中的个体进行优胜劣汰来寻找问题的最优解。其中, 选择算子用于对群体中的个体进行优胜劣汰;交叉算子则是产生新个体的主要手段, 它决定了遗传算法的全局搜索能力;变异算子是产生新个体的辅助手段, 它决定遗传算法的局部搜索能力[3,4,5]

SGA提供了一个遗传算法的基本框架, 同时也解决了一些简单的函数优化问题, 但对于复杂的系统优化问题, SGA在使用时出现了一些困难和问题, 首先, SGA收敛于最优解的概率小于1, 其应用的可靠性值得怀疑[2,3]。其次, SGA在使用选择算子对种群根据适应度评价函数进行优胜劣汰时, 要求个体的适应度均大于零, 因此需考虑个体的目标函数向适应度评价函数的转化, 当无法确定个体目标函数的正负上限时, 这种转换通常很不方便。

基于以上问题考虑, 研究人员提出了各种改进方法, 如在进化过程中保留最佳个体, 这种改进虽使遗传算法收敛于最优解的概率为1, 但却未能解决第二个问题。本文提出一种改进遗传算法 (Advanced Genetic Algorithm, 简称AGA) , 在遗传算法的实现过程中, 认为自然界中生物的适应度不仅与个体自身有关, 同时与个体所处的环境等外在条件有关, 因此, 生物的适应度通常也应当是一个随机量[6]。遵循这一思想, 以个体的随机得分作为个体的适应度, 同时吸取SGA的优点, 采用与SGA相同的交叉算子和变异算子提高遗传算法的全局和局部搜索能力, 并主要依靠交叉算子产生新的个体, 进化过程由交叉、变异、选择三步组成, 对于选择算子, AGA作以下定义:

a. 将大小为M的父代群体P (t) 和经过一次交叉、变异算子作用后产生的子代群体P″ (t) 合并, 得到大小为2M的子代群体P (t) =P (t) ∪P″ (t) ;

b. 对于P (t) 中的每一个体Xk, 再从P (t) 中随机取出其他q个个体 (其中q≥1, 为选择因子) , 比较这q个个体和个体Xk之间的函数值大小, 以其中函数值不优于个体Xk的个体的数目作为个体Xk的得分Sk (k=1, 2, 3, …, 2M, Sk=0, 1, 2, …, q) ;

c. 按群体P (t) 中个体的得分大小对全部2M个个体作降序排列, 对于得分相同的个体, 根据其出现的前后随机选择其排列顺序。选择前M个个体作为进化过程的下一代群体P (t+1) 。

AGA将父代群体及子代群体合并之后进行选择, 增加了群体的多样性, 而且, 选择算子实质上仅根据个体目标函数值的相对优越性来决定个体的适应度 (即个体的得分) , 这样由个体对应的目标函数向适应度函数转化就相当简单。同时在进化过程中, 每代群体中的最佳个体在比较适应度大小时始终被赋予了最大得分, 使最佳个体总能保留到下一代中, 从而确保了AGA收敛于最优解的概率为1, 这为AGA的应用提供了理论保障[2,3,4]

《3 水库优化调度》

3 水库优化调度

关于水库优化调度问题, 过去通常采用动态规划法 (DP) , 将多维非线性问题转化为多阶段决策问题, 通过增加状态数目来满足各阶段的可分解性和单调性, 但是, 随着状态数目的增加, 所需计算机存储容量迅速增加, 即所谓的“维数灾”问题, 使动态规划法只能解决一些精度要求不高的水库优化调度问题。因此, 本文考虑将改进遗传算法应用于水库优化调度中。在水电站优化调度中, 水电站的运行策略一般用发电引用流量序列 (Q1, Q2, …, Qn) 来表示, 将遗传算法应用于水电站优化调度中, 通常把发电引用流量序列转换为水位变化序列, 并以水位变化序列为基础进行编码等遗传寻优操作[7,8]。然而, 由于水库地形的影响, 不同初始水位条件下, 相同的水位变化时, 引用流量相差极大, 这样, 在高水位时, 水位的微小变化即可导致引用流量的较大变化, 这必然影响遗传算法的寻优过程, 同时也降低了计算结果的精度。本文采用以库容变化序列对应的个体编码方法, 具体过程如下:将水电站运行过程中库容变化范围内的水库库容状态存储于一维数组中, 根据数组存储时水库各库容状态与数组下标的对应关系, 在数组下标变化范围内, 随机选取n组下标变化序列组成初始种群, 根据预先设计的编码方案进行个体编码, 同时根据个体解码后所对应的库容变化序列 (V11, V21, …, Vn1) , (V12, V22, …, Vn2) , …, (V1n, V2n, …, Vnn) , 在水量平衡、水库允许泄流量、水轮机过水流量、水电站出力等约束条件的制约下求解个体的适应度值, 通过交叉、变异、选择等遗传算子, 逐步迭代, 最终达到最优值。在算法运行过程中, 根据优化调度目标函数确定的适应值是评判库容变化序列优劣的标准, 适应高的遗传到下一代的概率就大, 反之, 就相对低一些。以库容变化序列为基础进行遗传算法操作, 库容变化与引用流量一一对应, 提高了计算结果的精度。现以华北某发电为主的年调节水库为例, 说明AGA在水库优化调度中的应用过程。

该电站是以发电为主、兼顾防洪和灌溉的水利枢纽。水库最高蓄水位149 m, 相应兴利库容6.3×108 m3, 死水位125 m, 相应兴利库容0.0。装机容量17 000 kW, 最大过机流量71.1 m3/s, 最小发电流量10.0 m3/s, 发电水头13~37 m。将水库调度年划分成12个时段 (即12个月) 。以年发电量最大为目标函数, 数学模型如下

Ρ=maxi=112AqiΗiti(1)

约束条件有:

水量平衡约束

Qi=Vi-1-Vi+Di-Fi-Li(2)

库容约束

0Vi6.3(3)

水轮机过流量约束

qi={71.1qi71.1Qi/ti,71.1Qi/ti100Qi<10(4)

水电站出力约束

AqiΗi17000(5)

同时对于年调节水库, 在一个调度年末库容为零, 即

V12=0(6)

式中: A为水电站出力系数; Hi为水库i时段内的平均水位 (m) ; tii时段内的小时数; qi为水电站i时段内的发电引用流量 (m3/s) ; Qi为水电站i时段的放水量 (108 m3) ; Vi为水库i时段的库容 (108 m3) ; Di为水库i时段的入库水量 (108 m3) , 由代表年的天然年径流过程减去相应的需水过程而得; Fi为水库i时段的蒸发量 (108 m3) ; Li为水库i时段的渗漏量 (108 m3) 。

采用AGA对以上年调节水库进行优化调度研究, 同时考虑水量平衡、水库库容、水轮机过流量、水电站出力等约束条件。AGA设计如下:

《3.1AGA的编码》

3.1AGA的编码

将水库库容离散成64个状态, 通过水库特性曲线可得相应水面面积及水库水位。采用一维数组从小到大依次存储水库各库容状态, 数组下标0~63与水库库容0~6.3的各离散值一一对应, 将各水库库容值对应的水面面积及水库水位同样以一维数组存储时, 则以水库库容数组下标编码为基础的个体设计, 不仅与水库库容离散值一一对应, 同时对应于各库容相应的水面面积及水库水位, 增加了个体编码中的信息量, 使个体适应度相关的年发电量的计算变得极其方便。对各库容数组下标, 采用6位串长的二进制编码, 优化调度的库容精度为0.1, 对于群体中的每个个体, 包含12个库容状态, 个体串长为72位, 取群体大小为100。

《3.2适应度函数》

3.2适应度函数

本文采用AGA进行水库优化调度, 通过个体解码得到的水库调度库容变化序列, 必须满足水量平衡中用水量非负约束, 即Qi≥0, 同时应满足一个调度年末库容为零约束, 即V12=0。因此所求问题为约束优化问题, 为便于遗传算法的求解, 可采用惩罚函数法将其转变成无约束优化问题。惩罚函数法分为定量惩罚法、变量惩罚法。在定量惩罚法中, 解的质量严重地依赖惩罚系数值, 当惩罚系数太小时, 算法可能收敛于不可行解;而惩罚系数太大时又会使算法较早地收敛于某个局部最优解[8,9]。因此, 本文采用变量惩罚法, 使惩罚系数随着进化代数的增加而动态增大。考虑以上水量平衡及库容约束, 惩罚函数表达式如下

Ρ(VΜ)=Ρ-Μ(g)(i=112[min(0Qi)]2+[max(0V12)]2)(7)Μ(g)=αgβ(8)

式中:M (g) 为进化代数相关的惩罚因子;g为进化代数;α, β为调节惩罚因子大小的系数, 其中α取值确保水量与发电量具有相同的量级。

对于约束优化调度问题, 由于惩罚项的影响, 使个体对应的目标函数值有正有负, 同时随着进化代数的增加, 个体目标函数的正负上限难以确定, 采用SGA, 由目标函数向适应度函数的转化相当不便。AGA仅根据个体目标函数值的相对大小来确定个体的适应度, 个体目标函数的正负对适应度的求解无影响, 因此, 对水库优化调度等约束优化问题, 采用AGA具有更强的适应性。

《3.3遗传算子》

3.3遗传算子

在AGA寻优过程中, 需经过交叉算子、变异算子不断地产生新的个体, 并通过选择算子进行优胜劣汰操作, 采用单点交叉及单点变异方法, 交叉概率取0.8, 变异概率取0.05。选择算子根据个体目标函数大小打分的办法来进行个体的优胜劣汰操作, 从而产生新一代群体, 选择因子q取10。

《3.4AGA优化调度结果》

3.4AGA优化调度结果

选择不同的进化代数, 经过多次试算, 得水库优化调度结果如表1所示。

表1 AGA优化调度结果

Table 1 Optimal operation result of AGA

《表1》




水库库容
/108 m3
入库水量
/108 m3
发电流量
/m3·s-1
水头
/m
出力
/104 kW
弃水流量
/m3·s-1
1967 7 0.8 0.839 0.51 16.200 0

1967
83.33.95954.4224.37796.260

1967
96.34.6359.8833.181 192.700

1967
106.31.0537.0037.0821.910

1967
116.30.7927.3937.0608.480

1967
126.30.5317.3937.0386.330

1968
16.00.9243.8436.68965.210

1968
25.30.8155.4735.501 182.000

1968
34.00.3761.8032.971 223.040

1968
42.1070.4628.221 193.810

1968
50.6055.4721.66721.210

1968
60021.7415.58203.390

注:年发电量为9 294.34×104 kW·h

《3.5动态规划法求解》

3.5动态规划法求解

为了验证水库优化调度结果的正确性, 同时便于AGA与动态规划法在水库优化调度应用中的比较, 本文采用动态规划法在对以上水库优化调度问题进行求解, 由于库容离散点为64时动态规划法所需内存太大, 在微机上难以实现, 因此取库容离散点为10, 优化调度结果如表2所示。

表2 动态规划法优化调度结果

Table 2 Optimal operation result of DP

《表2》




水库库容
/108 m3
入库水量
/108 m3
发电流量
/m3·s-1
水头
/m
出力
/104 kW
弃水流量
/m3·s-1
1967 7 0.7 0.839 4.40 15.90 0 0

1967
83.53.95942.8324.38626.770

1967
96.34.6367.5533.481 224.000

1967
106.31.0537.0037.0821.900

1967
116.30.7927.3937.0608.480

1967
125.60.5344.5536.20968.170

1968
15.60.9232.5135.40690.870

1968
24.90.8155.6434.501 152.450

1968
33.50.3765.8631.781 224.000

1968
42.1051.3127.55848.740

1968
50.7051.5621.98680.250

1968
60025.5415.90243.840

注:年发电量为9 089.47×104 kW·h

《3.6AGA与动态规划法的比较》

3.6AGA与动态规划法的比较

通过以上分别采用AGA及动态规划法进行水库优化调度分析, 经过比较发现两者计算结果相差不大, 由于AGA可采用更高的计算精度, 因此计算结果更优于动态规划结果, 年发电量可增加204.87×104 kW·h。同时, AGA所需计算时间与动态规划法相差不大, 但它们所需的计算机存储容量却相差极大, 应用动态规划时, 当水库库容离散点为64时, 需存储6412个状态点在计算机中[10], 如此庞大的数据存储需要使动态规划法求解高精度的水库优化调度问题难以实现, 而采用AGA, 则无需存储这些状态点。可见, 对同一问题, 采用AGA可大大节约了计算机的内存需求量, 为高精度、多水库联合优化调度克服“维数灾”问题提供一条新途径。

《4 结论》

4 结论

本文以标准遗传算法 (SGA) 为基础, 提出了一种改进遗传算法 (AGA) , 并将其应用于水库优化调度研究中, 通过实例计算可得:

1) 通过对SGA的改进, 特别是选择算子的改进, 使AGA从理论上以概率1收敛于最优解, 这为AGA的实现提供了理论保证。

2) AGA根据个体目标函数值的相对优劣, 采用选择因子打分的办法确定个体的适应度, 使AGA在个体适应度的求解方面更加简便, 对解决水库优化调度等约束优化问题具有更强的适应性。

3) 综合数组存储理论, 以存储库容状态的数组下标为基础, 采用下标变化范围内的下标变化序列进行个体编码, 由于库容状态数组与其相应的水面面积、水位数组一一对应, 因此个体编码序列不仅表征水库库容变化序列, 同时也表征其相应水位及水面面积变化序列, 增加了个体编码中的信息量, 使个体解码后目标函数的求解变得极其方便, 此个体编码方法对其他水库优化调度遗传算法的个体编码具有一定的参考价值, 同时本文采用以库容序列对应的个体编码方案, 与水位变化序列为基础的编码方案相比, 对于相同的状态点具有更好的计算精度。

4) 通过AGA与动态规划法在水库优化调度实例上的应用比较可得, AGA原理简单, 易于编程实现, 能非常有效地实现概率意义的全局搜索, 同时占有内存少, 为高精度、多水库联合调度等优化调度解决“维数灾”问题提供了一个新的途径。