改进遗传算法在环状管网水力平衡计算中的应用

　2005年4月

灌溉排水学报

　第24卷第2期　

文章编号:1000646X (2005) 02005503

改进遗传算法在环状管网水力平衡

计算中的应用

缪海洋, 程吉林, 江建华, 阎玮

(扬州大学水利科学与工程学院, 江苏扬州225009)

摘　要:标准遗传算法不擅于局部微调, 在标准遗传算法的基础上, 利用传统的优化方法中坐标轮换寻优方法对个体进行局部微调, 寻优能力明显提高。把该算法用于环状管网水力平衡计算, 计算结果精度较高。关　键　词:改进遗传算法; 局部微调; 传统的优化方法; 环状管网水力平衡计算中图分类号:S 2　　文献标识码:A

1　标准遗传算法

标准遗传算法(又称简单遗传算法, 简称SGA ) , 至今仍是国内外遗传算法(GA ) 应用中常用的实施方案, 其步骤如下:

变量初始变化空间的离散和编码; 初始父代群体的随机生成; 父代个体串的解码和适应度评价; 父代个体的概率选择; 父代个体的杂交; 子代个体的变异; 进化迭代(演化迭代) 。由上步得到的n 个子代个体作为新的父代, 算法转入步 进入下一次进化过程, 如此循环往复, 以上7步构成SGA 。

SGA 自诞生以来, 在各个领域中得到了广泛的应用, 取得了一系列的重大成果, 但是, SGA 在应用的过程中也出现了一些新问题, 这些问题如下:

编码方案:SGA 采用二进制编码, 码长小, 难以满足精度要求; 码长取得大, 计算量大, 冗余多。采用二进制编码, 变量的取值范围变成离散的空间, 连续性差。

上位效应:上位效应排除了单个基因引起单个效应的可能性。虽然单个基因的变异可能导致某个特征发生改变, 但并不表明一个基因对应一个特征。同时上位效应使得判断某个基因是不是“好”基因变得更加困难, 因为此时一个基因在个体中所起的作用与个体中的其它基因有关。

SGA 的选择算子、杂交算子的寻优功能随进化迭代次数的增加而逐渐减弱, 在应用中常出现早熟收敛与不收敛现象。

SGA 控制参数的设置技术复杂, 目前尚无好的准则指导; 特别是当实际问题变量的变化区间很大时, 上述问题就十分突出。

[2]

2　改进遗传算法

编码上采用浮点数编码方案, 克服了二进制编码频繁的编码与解码过程, 解的连续性好; 选择算子采用De Jong 的“杰出人才模型”与Baker 、Whitley 等人提出的基于“排名”的选择方案, 一方面保留了每一代中的最优个体, 确保算法收敛, 另一方面减少了选择压力, 防止算法早熟收敛; 交叉算子采用“完全算术交叉”方案, 使得算法具有更好的稳定性; 变异算子采用“一致变异算子”与传统优化方法中“坐标轮换”法相结合, 使得算法具有局部微调的功能。通过对许多复杂函数的测试结果来看, 该算法效果很好。该算法的具体步骤如

收稿日期:2004

1213

基金项目:国家自然科学基金项目(NO. 70471090)

作者简介:缪海洋(1980, 男, 硕士研究生, 主要研究方向为水资源系统工程优化.

下:

(1) 编码

为克服二进制编码带来的问题, 与其它一些改进遗传算法一样, 本文采用实数编码。设第i 个变量x i 的取值范围为[a i , b i ], 则x i 可表示为x i =a i +(b i -a i ) r , 式中r 为[0, 1]上的随机数。

(2) 初始父代群体的随机生成

设每一个体由变量x 1, x 2, …, x n 构成, 则按如下方式即可生成某个个体的第i 个变量:生成一个随机数r , 取x i =a i +(b i -a i ) r , 重复n 次即可生成一个个体; 按照以上生成个体的办法, 重复p op 为群体规模, 本文的算例中其值取100) , 即可生成初始父代群体V 1, V 2, …, V pop

(3) 父代个体的适应度评价

适应度反映了个体对环境的适应情况, 适应度越高, 说明个体越优良。对于求目标函数极大值问题, 直接把目标函数值f (i ) 作为适度函数。

(4) 从父代群体V 中选择参与交配的群体V 1

一般来说, 较好的个体相互交配, 更有利于产生较好的后代。因此应该从父代群体中选择较好的个体, 本文采用概率选择, 做法如下:

将父代群体中每一个体的适应度f (i ) 按照由小到大的顺序(假设求极小值问题) 排序, 同时对相应的个体位置作调整, 计算出每个个体V i 的选择概率, 按照适应值的排名来计算选择概率p i 。 计算累计概率q (i ) 。 随机生成一随机数r , 若q (i -1)

(5) 由遗传算法产生一部分点

子代V 1中前5个个体都是适应性较好的个体, 称它们为“精英”。交叉操作的父亲来自于“精英”, 其选择方案采用概率选择, 适应性好的个体被选中的机会要大些; 母亲来自于除了“精英”以外的p o p 体, 采用随机选择。遗传算法产生点的具体步骤如下:

按概率选择交叉操作的父亲, 随机选择母亲, 配成对。 进行交叉操作。 以较小的概率P m 对V (i ) 重复 ～ , 直到产生的点数达到int (p op 体总点数的比例, 本文取0. 8。

(6) 由局部微调算法产生另外一些点

传统的优化方法中, 有一种所谓坐标轮换的优化方法, 即对每一变量进行优化, 所有的变量优化完就称为一个轮回。吸收该思想, 但对某一变量的优化并不一定要找到其最优解, 只要找到比现有解更好的解即停止对该变量进行优化, 转入到下一个变量的优化。采用此法主要基于以下二点考虑:第一, 搜索到最优解的计算量将大大增加, 使得算法的运行速度很慢; 第二, 只要二个较优解分布在最优解二侧, 通过算术交叉就可以使解的质量大大改善。由局部微调算法产生另外一些点的步骤如下:

从V 1中随机选择变异的个体, 设P t =(x 1, x 2, …, x k , …x n ) 是第t 代种群中的一个被选择的个体, 对P t

的第k 个基因x k 作微小的扰动, P t 的左右二个点分别为P t 1与P t 2, 其中P t 1=(x 1, x 2, …, x k - , …x n ) , P t 2=(x 1, x 2, …, x k + , …x n ) 。若f (P t 1) f (P t ) , 则从x k 从UB 开始向左搜索, 直到新点的函数值小于f (P t ) , 以新点代替P t , UB 、L B 表示x k 的最大值与最小值。重复n 次, 即完成一个轮回, 产生一个新的点。重复以上操作p op (6) 二步产生的新点的个数为p op siz e , 这些点记为子代V 2。(局部siz e -int (p op siz e ×p g ) 次, 那么由(5) 、微调的精度由 控制) 。

(7) 计算V 1与V 2中个体的适值, 并按照适应度的大小进行排序。V 1与V 2中的个体按照位置形成一一对应的关系。前5个个体选择适值大的个体直接进入V ; 后面的个体选择适值与该点到“精英”距离的比值大的那个个体进入V 。判断是否满足算法迭代的终止条件, 若不满足, 进入步(3) 循环。

遗传算法迭代的终止条件一般采用启发式方法判断, 例如:是否到了预定算法的最大代数; 是否找到了某个较优的染色体; 连续几次迭代后得到的解群中的最好解是否变化等。[3]

′

size

siz e 次(p op

siz e

。

siz e -5个个

进行“一致变异”, 即用[a i , b i ]上的随机数代替V (i ) ′上的某个基因。 检查新点是否与“精英”有明显距离。

siz e ×p g ) 为止, 其中, p g 反映了由遗传算法产生的点占群

3　应用实例

将遗传算法用于环状管网的水力平衡计算中, 计算结果精度较高, 效果很好。在图1所示的管网中, 已知各节点的“节点消耗”, 管段编号与节点编号如图, 又知第一个节点的水头值为H 1=40. 00m , 第i 个节点的水头值相应地记为H i 。各管段的编号、管长、管径及粗糙系数见表1。

表1　管网管段编号、管长、管径、粗糙系数对应关系表

管段编号

管长/m [***********][1**********]0

管径/m 0. 40. 40. 30. 30. 20. 20. 30. 30. 30. 3

粗糙系数n 0. 01090. 01090. 01270. 01270. 01370. 01370. 01270. 01270. 01270. 0127

　　由质量守衡定律, 对任意一个节点, 流入该节点的流量之和应该等于流出该节点的流量之和, 环状管网水力平衡计算的目的就是平衡各节点的

水头, 使得流入该节点的流量之和应该等于流出

8/3

该有Q 8+Q 10-Q 9-0. 075=0, Q 8=0. 3121/2

nl

1/2

( H 8) , H 8=H 5-H 4, 记f 5=Q 8+Q 10-Q 9-0. 075, 表示由于水头分配不合理而引起的流量不平衡程度。同理可以用各节点的水头值表示出各管段的流量, 从而求出第i 个节点的流量不平衡度f i 。因此, 要进行

8

图1　管网布置示意图

该节点的流量之和。以第5个节点为例, 平衡时应

水力平衡, 只要求一组H =(H 1, H 2, …, H 8) , 使得f =

i =1

f i 取得最小值。参数取值p op

-6

-7

siz e =100, N gen =

50, P m =0. 1, 将f 作为评价函数, 控制精度的参数 取10, 求解结果H 2=33. 771, H 3=30. 144, H 4=34. 094, H 5=30. 830, H 6=29. 439, H 7=32. 440, H 8=27. 282, f =2. 43×10。

参考文献:

[1]　金菊良. 遗传算法用于水科学优化问题中的理论和应用研究[J ]. 系统工程, 2000, 17(3) . [2]　王正志, 薄涛. 进化计算[M ]. 长沙:国防科技大学出版社, 2000.

[3]　杨荣富, 等. 与局部微调方法相结合的遗传算法[J]. 水科学进展, 1999, 10(2) .

Application of an Improved Genetic Algorithms in

Hydraulic Distribution Calculation of Loop Pipe Network

M IAO Hai-yang , CHENG Ji-lin, JIAN G Jian-hua, YAN Wei

(Water Science and Engineering College, Yangzhou Univ er sity, Yangzho u 225009, China)

Abstract :SGA(sim ple genetic algorithm) is no t w ell suited to per for m finely tuned lo cal searches. Based on SGA, in this paper , w e find another w ay of local tuning m ethod co mbined w ith traditional optim ization w ay , and it turns o ut efficient . T his metho d is applied to hydraulic distribution calculatio n of loop pipe netw ork , and the results are finer .

Key words :im pro ved g enetic algo rithms; lo cal tuning; traditio nal optimization; hydraulic-distribution calculation o f loop pipe netw or k