《1 引言》
1 引言
遗传算法 (Genetic Algorithm, 简称GA) 是美国密执安大学的著名科学家J.H.HoIIand教授于20世纪70年代中期提出来的一种基于生物遗传和进化机制的适合于复杂系统优化计算的自适应概率优化技术
《2 遗传算法的改进》
2 遗传算法的改进
基于对自然界生物在遗传和进化过程中选择、交叉、变异机理的模仿, Goldberg提出了标准遗传算法 (Standard Genetic Algorithm, 简称SGA) 的实现过程。SGA以随机方式产生一个对应于优化问题可行解的初始群体后, 采用三种遗传算子, 即选择算子、交叉算子和变异算子
SGA提供了一个遗传算法的基本框架, 同时也解决了一些简单的函数优化问题, 但对于复杂的系统优化问题, SGA在使用时出现了一些困难和问题, 首先, SGA收敛于最优解的概率小于1, 其应用的可靠性值得怀疑
基于以上问题考虑, 研究人员提出了各种改进方法, 如在进化过程中保留最佳个体, 这种改进虽使遗传算法收敛于最优解的概率为1, 但却未能解决第二个问题。本文提出一种改进遗传算法 (Advanced Genetic Algorithm, 简称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的应用提供了理论保障
《3 水库优化调度》
3 水库优化调度
关于水库优化调度问题, 过去通常采用动态规划法 (DP) , 将多维非线性问题转化为多阶段决策问题, 通过增加状态数目来满足各阶段的可分解性和单调性, 但是, 随着状态数目的增加, 所需计算机存储容量迅速增加, 即所谓的“维数灾”问题, 使动态规划法只能解决一些精度要求不高的水库优化调度问题。因此, 本文考虑将改进遗传算法应用于水库优化调度中。在水电站优化调度中, 水电站的运行策略一般用发电引用流量序列 (Q1, Q2, …, Qn) 来表示, 将遗传算法应用于水电站优化调度中, 通常把发电引用流量序列转换为水位变化序列, 并以水位变化序列为基础进行编码等遗传寻优操作
该电站是以发电为主、兼顾防洪和灌溉的水利枢纽。水库最高蓄水位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个月) 。以年发电量最大为目标函数, 数学模型如下
约束条件有:
水量平衡约束
库容约束
水轮机过流量约束
水电站出力约束
同时对于年调节水库, 在一个调度年末库容为零, 即
式中: A为水电站出力系数; Hi为水库i时段内的平均水位 (m) ; ti为i时段内的小时数; 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。因此所求问题为约束优化问题, 为便于遗传算法的求解, 可采用惩罚函数法将其转变成无约束优化问题。惩罚函数法分为定量惩罚法、变量惩罚法。在定量惩罚法中, 解的质量严重地依赖惩罚系数值, 当惩罚系数太小时, 算法可能收敛于不可行解;而惩罚系数太大时又会使算法较早地收敛于某个局部最优解
式中:M (g) 为进化代数相关的惩罚因子;g为进化代数;α, β为调节惩罚因子大小的系数, 其中α取值确保水量与发电量具有相同的量级。
对于约束优化调度问题, 由于惩罚项的影响, 使个体对应的目标函数值有正有负, 同时随着进化代数的增加, 个体目标函数的正负上限难以确定, 采用SGA, 由目标函数向适应度函数的转化相当不便。AGA仅根据个体目标函数值的相对大小来确定个体的适应度, 个体目标函数的正负对适应度的求解无影响, 因此, 对水库优化调度等约束优化问题, 采用AGA具有更强的适应性。
《3.3遗传算子》
3.3遗传算子
在AGA寻优过程中, 需经过交叉算子、变异算子不断地产生新的个体, 并通过选择算子进行优胜劣汰操作, 采用单点交叉及单点变异方法, 交叉概率取0.8, 变异概率取0.05。选择算子根据个体目标函数大小打分的办法来进行个体的优胜劣汰操作, 从而产生新一代群体, 选择因子q取10。
《3.4AGA优化调度结果》
3.4AGA优化调度结果
选择不同的进化代数, 经过多次试算, 得水库优化调度结果如表1所示。
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.20 | 0 | 0 |
1967 | 8 | 3.3 | 3.959 | 54.42 | 24.37 | 796.26 | 0 |
1967 | 9 | 6.3 | 4.63 | 59.88 | 33.18 | 1 192.70 | 0 |
1967 | 10 | 6.3 | 1.05 | 37.00 | 37.0 | 821.91 | 0 |
1967 | 11 | 6.3 | 0.79 | 27.39 | 37.0 | 608.48 | 0 |
1967 | 12 | 6.3 | 0.53 | 17.39 | 37.0 | 386.33 | 0 |
1968 | 1 | 6.0 | 0.92 | 43.84 | 36.68 | 965.21 | 0 |
1968 | 2 | 5.3 | 0.81 | 55.47 | 35.50 | 1 182.00 | 0 |
1968 | 3 | 4.0 | 0.37 | 61.80 | 32.97 | 1 223.04 | 0 |
1968 | 4 | 2.1 | 0 | 70.46 | 28.22 | 1 193.81 | 0 |
1968 | 5 | 0.6 | 0 | 55.47 | 21.66 | 721.21 | 0 |
1968 | 6 | 0 | 0 | 21.74 | 15.58 | 203.39 | 0 |
注:年发电量为9 294.34×104 kW·h
《3.5动态规划法求解》
3.5动态规划法求解
为了验证水库优化调度结果的正确性, 同时便于AGA与动态规划法在水库优化调度应用中的比较, 本文采用动态规划法在对以上水库优化调度问题进行求解, 由于库容离散点为64时动态规划法所需内存太大, 在微机上难以实现, 因此取库容离散点为10, 优化调度结果如表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 | 8 | 3.5 | 3.959 | 42.83 | 24.38 | 626.77 | 0 |
1967 | 9 | 6.3 | 4.63 | 67.55 | 33.48 | 1 224.00 | 0 |
1967 | 10 | 6.3 | 1.05 | 37.00 | 37.0 | 821.90 | 0 |
1967 | 11 | 6.3 | 0.79 | 27.39 | 37.0 | 608.48 | 0 |
1967 | 12 | 5.6 | 0.53 | 44.55 | 36.20 | 968.17 | 0 |
1968 | 1 | 5.6 | 0.92 | 32.51 | 35.40 | 690.87 | 0 |
1968 | 2 | 4.9 | 0.81 | 55.64 | 34.50 | 1 152.45 | 0 |
1968 | 3 | 3.5 | 0.37 | 65.86 | 31.78 | 1 224.00 | 0 |
1968 | 4 | 2.1 | 0 | 51.31 | 27.55 | 848.74 | 0 |
1968 | 5 | 0.7 | 0 | 51.56 | 21.98 | 680.25 | 0 |
1968 | 6 | 0 | 0 | 25.54 | 15.90 | 243.84 | 0 |
注:年发电量为9 089.47×104 kW·h
《3.6AGA与动态规划法的比较》
3.6AGA与动态规划法的比较
通过以上分别采用AGA及动态规划法进行水库优化调度分析, 经过比较发现两者计算结果相差不大, 由于AGA可采用更高的计算精度, 因此计算结果更优于动态规划结果, 年发电量可增加204.87×104 kW·h。同时, AGA所需计算时间与动态规划法相差不大, 但它们所需的计算机存储容量却相差极大, 应用动态规划时, 当水库库容离散点为64时, 需存储6412个状态点在计算机中
《4 结论》
4 结论
本文以标准遗传算法 (SGA) 为基础, 提出了一种改进遗传算法 (AGA) , 并将其应用于水库优化调度研究中, 通过实例计算可得:
1) 通过对SGA的改进, 特别是选择算子的改进, 使AGA从理论上以概率1收敛于最优解, 这为AGA的实现提供了理论保证。
2) AGA根据个体目标函数值的相对优劣, 采用选择因子打分的办法确定个体的适应度, 使AGA在个体适应度的求解方面更加简便, 对解决水库优化调度等约束优化问题具有更强的适应性。
3) 综合数组存储理论, 以存储库容状态的数组下标为基础, 采用下标变化范围内的下标变化序列进行个体编码, 由于库容状态数组与其相应的水面面积、水位数组一一对应, 因此个体编码序列不仅表征水库库容变化序列, 同时也表征其相应水位及水面面积变化序列, 增加了个体编码中的信息量, 使个体解码后目标函数的求解变得极其方便, 此个体编码方法对其他水库优化调度遗传算法的个体编码具有一定的参考价值, 同时本文采用以库容序列对应的个体编码方案, 与水位变化序列为基础的编码方案相比, 对于相同的状态点具有更好的计算精度。
4) 通过AGA与动态规划法在水库优化调度实例上的应用比较可得, AGA原理简单, 易于编程实现, 能非常有效地实现概率意义的全局搜索, 同时占有内存少, 为高精度、多水库联合调度等优化调度解决“维数灾”问题提供了一个新的途径。