论文部分内容阅读
摘要：以广东省某水电站为研究对象， 建立了以年发电量最大为目标，兼顾其他综合用要求的单库优化调度模型，分别利用遗传算法、粒子群算法和SCE-UA算法进行求解， 并对它们的计算结果进行比较。计算结果表明， 在水库优化调度中，三种算法都能得到较满意的解，其中，遗传算法和粒子群算法比SCE-UA算法具有更好的效率和得到更令人满意的解。
关键词：遗传算法；粒子群算法；SCE-UA算法；水库优化调度
0引言
水库优化调度是一个比较复杂的问题，具有离散性、非线性等特点[1]。目前已经有很多方法运用在这方面的求解，比如动态规划法、逐步优化算法、蚁群算法及遗传算法等。在本文中，笔者采用比较流行的遗传算法、粒子群算法和SCE-UA算法[2，3]分别对此问题进行求解，目的在于探讨它们的可行性和算法间在此问题上的优劣性比较。
1 水库优化调度模型的建立
假设研究的对象是一个以发电为主，并适当考虑其他综合利用要求的水库。建立的水库优化调度数学模型如下：
目标函数：
（1）
上式中：T为年内总月数，即T=12；A为水电站出力系数；Qt 为水电站的发电流量（m3/s）；
Ht 为水电站的平均水头（m）；Mt为第t时段小时数。
约束条件：
水量平衡约束
（2）
水库泄流量约束 （3）
水库蓄水量约束 （4）
水轮机过水流量约束 （5）
水电站出力约束 （6）
上述约束式中：Ft为水库入库流量（m3/s）；Qt为水电站发电的流量（m3/s）；St为水库弃水流量（m3/s）；Vt为时段初水库蓄水量（m3）；Vt+1为时段末水库蓄水量（m3）；Δt为第t时段的秒数；Vt，min为水库最小允许蓄水量（m3）；Vt，max为水库最大允许蓄水量（m3）；qt，min为水库下游综合利用要求的最小下泄流量（m3/s）；qt，max为下游河道安全泄流量；Q，min为水电站最小引用流量（m3/s）；Q，max为水电站最大引用流量（m3/s）；Nmin为水电站保证出力（kW）；Nmax为水电站装机容量（kW）。
3算法介绍
3.1 遗传算法介绍
遗传算法是一种通过模拟自然进化过程搜索最优解的方法，在求解很多优化问题上已显示出强大的能力，应用的范围也比较广泛。目前，已经有很多学者将其应用在水库优化调度中，本文中的遗传算法[4]设计如下：
3.1.1染色体编码：本文采用基于十进制的编码方法，在十进制编码中，必须保证基因值在整个区间范围内搜索。即
（7）
上式中：Zt为水位值；Zt，min为时段水位的最小值；Zt，max为时段水位的最大值；n为整数；m为基因段数。
3.1.2 染色体适应度函数：
本文采用目标函数加惩罚函数的方式构造适应度函数，式子如下：
（8）
上式中f（Z）为目标函数，M（g）为与进化代数相关的惩罚因子，g为进化代数，Wj为与第j个约束有关的违约值，P为违约数目。
3.1.3选择运算
选择的方法很多，本文中采用基于排名的选择策略。即假设群体规模为PA，先根据适应度值对个性进行排序，然后以某个概率P，从中选择PA*P个适应度值高的个体，而另外的（1-P）*PA个个体由适应度值高的个体代替。
3.1.4交叉运算
交叉運算，就是对两个相互配对的个体按某种方式相互交换部分基因，从而形成两个新的个体。本文采用的是单点交叉法进行交叉运算。
3.1.5变异运算
变异的方法有很多种，本文中采用的是非均匀变异。
3.2粒子群算法介绍
粒子群优化算法[5]是模拟鸟类捕食行为的群体智能算法，由美国的Wberhart和Kennedy于1995年提出的。基本粒子群算法模拟的是一群鸟在随机搜寻食物，而在这个范围内只有一块食物，所有的鸟都不知道食物在哪，但它们知道自己的位置离食物还有多远。我们可以通过搜寻目前离食物最近的鸟的周围来找到食物，这就是基本粒子群算法的思想[6]。在一个优化问题中，我们需要搜寻的是空间中的一只鸟，我们称之为“粒子”。所有的粒子都有一个函数适应度值，每个粒子还有一个决定它们飞翔方向和距离的速度，粒子追随目前的最优粒子在空间搜索。由于粒子群算法需要调整的参数比较少，并且比较容易實现，所以应用范围很广。本文中粒子群算法步骤如下：
第一步：在水电站运行过程中的水位变化范围内，随机选取n组水位变化序列（Z11，Z12，…，Z1n），（Z21，Z22，…，Z2n），……，（Zn1，Zn2，…，Znn），随机生成n组时段末水位涨落速度变化序列（V11，V12，…，V1n），（V21，V22，…，V2n），……，（Vn1，Vn2，…，Vnn），即初始化n个粒子。粒子i的坐标Pi设置为粒子当前的位置，即Pi=Zi，并由此计算出其相应的个体极值E（i）。找出n个个体极值中最大的一个使全局极值Eg=max{ E（i），i=1，2， …，n}，记录下最好粒子的序号g，则Pg= Zg。
第二步：计算各粒子的适应度值， 如果好于该粒子当前的个体极值E（i） ，则将Pi设置为该粒子的位置，并更新个体极值. 如果所有个体极值中最好的好于当前的全局极值Eg，则将Eg 设置为该粒子的位置， 并更新全局极值。
第三步：更新各粒子的速度和位置：
（9）
（10）
第四步：检查是否满足迭代终止条件。如果当前迭代次数达到了预先设定的最大迭代次数，或者达到最小误差的要求，则迭代终止，记录下的全局极值点的位置，即为水库的的调度最优值，否则转到第二步继续迭代。 3.3 SCE-UA算法介绍
SCE-UA算法是由段青云教授等人提出的一种进化算法，该算法结合了随机搜索、单纯形法和基因算法等优点，具有很强的全局寻优能力。[1]本文中的SCE-UA算法步骤如下：
第一步：初始化 假设研究的是n维问题，这里优化调度的计算时段为月，那么n=13。选取参与进化的复合形个数p（p>=1），每个复合形包含m个顶点（每个顶点就是一组水位变化序列）。计算样本数目为s=pm。
第二步：产生样本点 在可行域内随机产生s个样本X1，…，Xs即（Z11，Z12，…，Z1n），（Z21，Z22，…，Z2n），……，（ZS1，ZS2，…，ZSn），计算样本Yi=（S1（Xi），S2（Xi）），得到样本点（Xi，Yi），i=1，…，s。
第三步：样本点排序 把s个样本点按适应度函数值排序，排序后仍记为（Xi，Yi），i=1，…，s，其中Xi优于Xi+1，记D={（Xi，Yi），i=1，…，s }。
第四步：划分为复合形群体 将D划分为p个复合形A1，…，AP，其中，每个复合形包含m个点，其中
（11）
第五步：复合形进化 按CCE分别进化各个复合形。
第六步：复合形混合 将进化后的所有复合形的顶点组合成新的点集，再次按适应度函数值排序，排序后仍记为D。
第七步：终止判断 如果满足收敛条件则停止，否则返回第四步。
其中CCE算法的步骤为：
第一步：初始化 分别选择，这里2<=q<=m，，。Pi=2（m+1-i）/m（m+1），i=1， …， m。
第二步：分配权重 对第Ak个复合形中的每个点分配概率，这样较好的点就比较差的点有更大的概率形成子复合形。
第三步：选取父辈群体 从Ak中按照形成子复合形的概率随机地选取q个不同的点u1， …，uj，并记录q个点在Ak中的位置L。计算每个点的Yi=（S1（Xi），S2（Xi）），将q个点及其相应的Yi放到变量B中。
第四步：进化产生下一代 ，其中可以分为六个小步：
①对q个点按适应度函数值排序，计算除最后一个点外的形心：。
②计算最差点的反射点 r=2g-Uq 。
③如果计算的r在可行域内，则计算其二维向量值Yr，转到④。否则，计算包含Ak的可行域中随机抽取可行点z，计算Yz，以z代替r，Yz代替Yr。
④如果Yr大于Yq，则以r代替最差的点Uq，转到⑥，否则计算c=（g+Uq）/2和Yc。
⑤如果Yc大于Yq，则用c代替最差的点Uq，转到⑥；否则，计算包含Ak的可行域中随机抽取可行点z，计算Yz，以z代替Uq，Yz代替Yq。
⑥重复①到⑤次。
第五步：取代 把B中进化产生的下一代中的所有点，即q个点，全部放回到Ak中原来的位置L，并重新排序。
第六步 迭代 重复前边五步次，即进化了代。
4计算实例
以广东省某水电站为例，该电站是以发电为主，兼有防洪和其他功能的枢纽，水电站出力系数为8.5，保证出力为3.3MW，装机容量为22.5MW，多年平均发电量为4.77亿度。水库是不完全年调节水库，死水位为290米，正常蓄水位为300米，最高蓄水位为303米，为保证水库运行安全，现要求水库在7，8月份水位不超过300米，9月初以后才允许超蓄，直到最高蓄水位303米。三种算法的调度结果如表一和图1所示：遗传算法的总发电量为5.572亿度，粒子群算法的总发电量为5.576亿度，SCE-UA的总发电量为5.447亿度。
5 结论
在本文的水库优化调度中，采用遗传算法、粒子群算法和SCE-UA算法都能得到较满意的解，其中，遗传算法和粒子群算法的平均运行时间都不到1秒，SCE-UA算法的运行时间大约为2秒。结果表明，粒子群算法和遗传算法能够较快速和准确的找到全局最优解，而SCE-UA算法在初始种群规模更大的情况下反而得到更不满意的解。这与王建群等人得到的结论是一致的[7]，即SCE-UA算法在求解具有区间约束的非线性约束优化问题时一般都能够得到全局最优解，但对于本文中的例子，其求解的效率和精度还有待提高。
参考文献
[1]林剑艺，程春田，顾妍平，武新宇.水库优化调度的Pareto强度值SCE-UA算法[J].中国工程科學.2007（10）.
[2] Duan Q Y ，Gupta v K， Sorooshian S. Shuffied complex evolution approach for effective and efficient minimization[J].Jorrnal of Optimization Theory and Applications，1993，76（3）：501-521.
[3] Duan Q Y， Sorooshian S， Gupta v K.Optimal use of the SCE-UA global optimization method for calrbrating watershed models[J].Journal of Hydrology，1994，158（1）：265-284.
[4] 王大剛，程春田，李敏；基于遗传算法的水电站优化调度研究[J].华北水利水电学院学报；2001，（01）.
[5]杨道辉，马光文，严秉忠，左幸；粒子群优化算法在水电站日优化调度中的应用.[J].水利发电，2006（3）.
[6]刘波.粒子群优化算法及其工程应用[M].电子工业出版社，2010，29-30.
[7]王建群，卢志华，哈布哈琪.求解约束非线性优化问题的群体复合形进化算法[J].河海大学学报.2001（3）.
关键词：遗传算法；粒子群算法；SCE-UA算法；水库优化调度
0引言
水库优化调度是一个比较复杂的问题，具有离散性、非线性等特点[1]。目前已经有很多方法运用在这方面的求解，比如动态规划法、逐步优化算法、蚁群算法及遗传算法等。在本文中，笔者采用比较流行的遗传算法、粒子群算法和SCE-UA算法[2，3]分别对此问题进行求解，目的在于探讨它们的可行性和算法间在此问题上的优劣性比较。
1 水库优化调度模型的建立
假设研究的对象是一个以发电为主，并适当考虑其他综合利用要求的水库。建立的水库优化调度数学模型如下：
目标函数：
（1）
上式中：T为年内总月数，即T=12；A为水电站出力系数；Qt 为水电站的发电流量（m3/s）；
Ht 为水电站的平均水头（m）；Mt为第t时段小时数。
约束条件：
水量平衡约束
（2）
水库泄流量约束 （3）
水库蓄水量约束 （4）
水轮机过水流量约束 （5）
水电站出力约束 （6）
上述约束式中：Ft为水库入库流量（m3/s）；Qt为水电站发电的流量（m3/s）；St为水库弃水流量（m3/s）；Vt为时段初水库蓄水量（m3）；Vt+1为时段末水库蓄水量（m3）；Δt为第t时段的秒数；Vt，min为水库最小允许蓄水量（m3）；Vt，max为水库最大允许蓄水量（m3）；qt，min为水库下游综合利用要求的最小下泄流量（m3/s）；qt，max为下游河道安全泄流量；Q，min为水电站最小引用流量（m3/s）；Q，max为水电站最大引用流量（m3/s）；Nmin为水电站保证出力（kW）；Nmax为水电站装机容量（kW）。
3算法介绍
3.1 遗传算法介绍
遗传算法是一种通过模拟自然进化过程搜索最优解的方法，在求解很多优化问题上已显示出强大的能力，应用的范围也比较广泛。目前，已经有很多学者将其应用在水库优化调度中，本文中的遗传算法[4]设计如下：
3.1.1染色体编码：本文采用基于十进制的编码方法，在十进制编码中，必须保证基因值在整个区间范围内搜索。即
（7）
上式中：Zt为水位值；Zt，min为时段水位的最小值；Zt，max为时段水位的最大值；n为整数；m为基因段数。
3.1.2 染色体适应度函数：
本文采用目标函数加惩罚函数的方式构造适应度函数，式子如下：
（8）
上式中f（Z）为目标函数，M（g）为与进化代数相关的惩罚因子，g为进化代数，Wj为与第j个约束有关的违约值，P为违约数目。
3.1.3选择运算
选择的方法很多，本文中采用基于排名的选择策略。即假设群体规模为PA，先根据适应度值对个性进行排序，然后以某个概率P，从中选择PA*P个适应度值高的个体，而另外的（1-P）*PA个个体由适应度值高的个体代替。
3.1.4交叉运算
交叉運算，就是对两个相互配对的个体按某种方式相互交换部分基因，从而形成两个新的个体。本文采用的是单点交叉法进行交叉运算。
3.1.5变异运算
变异的方法有很多种，本文中采用的是非均匀变异。
3.2粒子群算法介绍
粒子群优化算法[5]是模拟鸟类捕食行为的群体智能算法，由美国的Wberhart和Kennedy于1995年提出的。基本粒子群算法模拟的是一群鸟在随机搜寻食物，而在这个范围内只有一块食物，所有的鸟都不知道食物在哪，但它们知道自己的位置离食物还有多远。我们可以通过搜寻目前离食物最近的鸟的周围来找到食物，这就是基本粒子群算法的思想[6]。在一个优化问题中，我们需要搜寻的是空间中的一只鸟，我们称之为“粒子”。所有的粒子都有一个函数适应度值，每个粒子还有一个决定它们飞翔方向和距离的速度，粒子追随目前的最优粒子在空间搜索。由于粒子群算法需要调整的参数比较少，并且比较容易實现，所以应用范围很广。本文中粒子群算法步骤如下：
第一步：在水电站运行过程中的水位变化范围内，随机选取n组水位变化序列（Z11，Z12，…，Z1n），（Z21，Z22，…，Z2n），……，（Zn1，Zn2，…，Znn），随机生成n组时段末水位涨落速度变化序列（V11，V12，…，V1n），（V21，V22，…，V2n），……，（Vn1，Vn2，…，Vnn），即初始化n个粒子。粒子i的坐标Pi设置为粒子当前的位置，即Pi=Zi，并由此计算出其相应的个体极值E（i）。找出n个个体极值中最大的一个使全局极值Eg=max{ E（i），i=1，2， …，n}，记录下最好粒子的序号g，则Pg= Zg。
第二步：计算各粒子的适应度值， 如果好于该粒子当前的个体极值E（i） ，则将Pi设置为该粒子的位置，并更新个体极值. 如果所有个体极值中最好的好于当前的全局极值Eg，则将Eg 设置为该粒子的位置， 并更新全局极值。
第三步：更新各粒子的速度和位置：
（9）
（10）
第四步：检查是否满足迭代终止条件。如果当前迭代次数达到了预先设定的最大迭代次数，或者达到最小误差的要求，则迭代终止，记录下的全局极值点的位置，即为水库的的调度最优值，否则转到第二步继续迭代。 3.3 SCE-UA算法介绍
SCE-UA算法是由段青云教授等人提出的一种进化算法，该算法结合了随机搜索、单纯形法和基因算法等优点，具有很强的全局寻优能力。[1]本文中的SCE-UA算法步骤如下：
第一步：初始化 假设研究的是n维问题，这里优化调度的计算时段为月，那么n=13。选取参与进化的复合形个数p（p>=1），每个复合形包含m个顶点（每个顶点就是一组水位变化序列）。计算样本数目为s=pm。
第二步：产生样本点 在可行域内随机产生s个样本X1，…，Xs即（Z11，Z12，…，Z1n），（Z21，Z22，…，Z2n），……，（ZS1，ZS2，…，ZSn），计算样本Yi=（S1（Xi），S2（Xi）），得到样本点（Xi，Yi），i=1，…，s。
第三步：样本点排序 把s个样本点按适应度函数值排序，排序后仍记为（Xi，Yi），i=1，…，s，其中Xi优于Xi+1，记D={（Xi，Yi），i=1，…，s }。
第四步：划分为复合形群体 将D划分为p个复合形A1，…，AP，其中，每个复合形包含m个点，其中
（11）
第五步：复合形进化 按CCE分别进化各个复合形。
第六步：复合形混合 将进化后的所有复合形的顶点组合成新的点集，再次按适应度函数值排序，排序后仍记为D。
第七步：终止判断 如果满足收敛条件则停止，否则返回第四步。
其中CCE算法的步骤为：
第一步：初始化 分别选择，这里2<=q<=m，，。Pi=2（m+1-i）/m（m+1），i=1， …， m。
第二步：分配权重 对第Ak个复合形中的每个点分配概率，这样较好的点就比较差的点有更大的概率形成子复合形。
第三步：选取父辈群体 从Ak中按照形成子复合形的概率随机地选取q个不同的点u1， …，uj，并记录q个点在Ak中的位置L。计算每个点的Yi=（S1（Xi），S2（Xi）），将q个点及其相应的Yi放到变量B中。
第四步：进化产生下一代 ，其中可以分为六个小步：
①对q个点按适应度函数值排序，计算除最后一个点外的形心：。
②计算最差点的反射点 r=2g-Uq 。
③如果计算的r在可行域内，则计算其二维向量值Yr，转到④。否则，计算包含Ak的可行域中随机抽取可行点z，计算Yz，以z代替r，Yz代替Yr。
④如果Yr大于Yq，则以r代替最差的点Uq，转到⑥，否则计算c=（g+Uq）/2和Yc。
⑤如果Yc大于Yq，则用c代替最差的点Uq，转到⑥；否则，计算包含Ak的可行域中随机抽取可行点z，计算Yz，以z代替Uq，Yz代替Yq。
⑥重复①到⑤次。
第五步：取代 把B中进化产生的下一代中的所有点，即q个点，全部放回到Ak中原来的位置L，并重新排序。
第六步 迭代 重复前边五步次，即进化了代。
4计算实例
以广东省某水电站为例，该电站是以发电为主，兼有防洪和其他功能的枢纽，水电站出力系数为8.5，保证出力为3.3MW，装机容量为22.5MW，多年平均发电量为4.77亿度。水库是不完全年调节水库，死水位为290米，正常蓄水位为300米，最高蓄水位为303米，为保证水库运行安全，现要求水库在7，8月份水位不超过300米，9月初以后才允许超蓄，直到最高蓄水位303米。三种算法的调度结果如表一和图1所示：遗传算法的总发电量为5.572亿度，粒子群算法的总发电量为5.576亿度，SCE-UA的总发电量为5.447亿度。
5 结论
在本文的水库优化调度中，采用遗传算法、粒子群算法和SCE-UA算法都能得到较满意的解，其中，遗传算法和粒子群算法的平均运行时间都不到1秒，SCE-UA算法的运行时间大约为2秒。结果表明，粒子群算法和遗传算法能够较快速和准确的找到全局最优解，而SCE-UA算法在初始种群规模更大的情况下反而得到更不满意的解。这与王建群等人得到的结论是一致的[7]，即SCE-UA算法在求解具有区间约束的非线性约束优化问题时一般都能够得到全局最优解，但对于本文中的例子，其求解的效率和精度还有待提高。
参考文献
[1]林剑艺，程春田，顾妍平，武新宇.水库优化调度的Pareto强度值SCE-UA算法[J].中国工程科學.2007（10）.
[2] Duan Q Y ，Gupta v K， Sorooshian S. Shuffied complex evolution approach for effective and efficient minimization[J].Jorrnal of Optimization Theory and Applications，1993，76（3）：501-521.
[3] Duan Q Y， Sorooshian S， Gupta v K.Optimal use of the SCE-UA global optimization method for calrbrating watershed models[J].Journal of Hydrology，1994，158（1）：265-284.
[4] 王大剛，程春田，李敏；基于遗传算法的水电站优化调度研究[J].华北水利水电学院学报；2001，（01）.
[5]杨道辉，马光文，严秉忠，左幸；粒子群优化算法在水电站日优化调度中的应用.[J].水利发电，2006（3）.
[6]刘波.粒子群优化算法及其工程应用[M].电子工业出版社，2010，29-30.
[7]王建群，卢志华，哈布哈琪.求解约束非线性优化问题的群体复合形进化算法[J].河海大学学报.2001（3）.