基于遗传算法的新建给水管网优化设计
栾志玲,纪志凤
(烟台职业学院 计算机与信息工程 山东 烟台264000)
摘要:遗传算法是一种较新的工程优化算法，将其引入给水管网优化设计,增强了管网设计方案的经济合理性。对给水管网优化设计的数学模型建立，遗传算法的基本原理、实数编码技术、评价函数的建立进行了分析，并用实例验证了其有效性。
关键词:给水管网优化设计;遗传算法;数学模型;算例
中图分类号:TU991.02 文献标识码:A 文章编号:1673-5382(2007)03-0047-06
供水工程总投资中，输配水管网大约占总投资的70%-80%，可见，管网是输配水系统设计的重要组成部分，其投资大，投资偿还期长，有很大的可塑性。一般通过优化设计计算，可以节省工程投资的10%左右。管网优化设计是在建立数学模型和提出多个约束条件后，通过一定的数学算法，得出经济合理的管径和水泵扬程的[1]。近年来，遗传算法在给水管网优化设计中研究取得了一定的研究成果。本文将遗传算法引入了新建环状管网的优化设计中，增强了管网设计方案的经济合理性。
1 给水管网优化设计和遗传算法
给水管网的计算简图是有向图，将供水管网中的管段概化成一条线段(即图中的边)，边与边由节点相连。即把给水管网看作是一个由若干顶点（节点）和边（管段）组成的有向图。
图1中箭头表示各条边的方向，即管段中水流方向。
图1 环状管网图例
顶点与边的关系（即管网的拓扑结构）可用两个基本关系矩阵来描述 环-节点矩阵KL(I,J)[2]，环-管段矩阵LG(I,J)。首先，给管网各管段编上总体号，给管网各节点编号，给管网各环编号，然后写出矩阵KL(I,J)和LG(I,J)。KL(I,J)中的行号与环编号相对应，其值是环上的各个节点，对于图1管网有KL(I,J)=
给水管网优化设计的一般原则是：在管网布置已定、保证供水量和水压的前提下，计算求得年折算费用值最小情况下的管径。
管网优化设计是组合优化设计问题，其优化设计方法主要有两大类：传统的确定性优化方法，主要有枚举法、线性规划法和非线性规划法，还有一类随机性优化方法，主要是遗传算法和模拟退火算法。
遗传算法(Genetic Algorithms,简称GA)是随机优化方法的一个新的正在发展的领域，它继承了达尔文的进化论思想。1975年，有美国的Holland等提出了GA的系统的概念和方法[3]，1987年，Goldberg等将这一理论应用于管网优化设计中来。这一方法采用离散的标准管径为决策变量，并对其进行一定进制的编码，通过选择，杂交和变异等迭代操作因子，进而求得满意的结果。近年来实践已证明了GA的有效性和可靠性，越来越受到人们的广泛重视。GA具有传统优化方法无法比拟的优势；首先，GA的搜索一次性遍布整个解空间，所以得出全局最优解的机会大大增加。其次，以离散的标准管径为决策变量，可以不进行圆整近似优化而直接得出可能解。再有，用GA进行管网优化设计，一次可以得出几种不同的接近最低造价的方案，可再根据其他不同的要求选取合适的方案。
2 给水管网优化设计的数学模型
管网设计应该保证供水所需的水量和水压、水质安全、可靠性和经济性。管网优化设计的数学模型以经济性为目标函数，将其余的作为约束条件，据此建立目标函数和约束条件表达式。
2.1 目标函数
目标函数包括管网造价年折算值、送水泵站年平均动力费用和水厂新建的年折算值。由于新建水厂所占费用很少，在优化过程中其值无变化，因此目标函数可仅考虑前两项，可用下式表示：
式（2-1）中符号意义如下：
a,b,α 单位长度管线造价公式中的系数和指数，随水管材料和当地施工条件而异；
Di 第i个管段的管径，m;
E 电费，分/kw.h；
Q 输入管网的总流量，L/s；
Hp 二级泵站扬程，m；
η 泵站效率，一般为0.55-0.85，水泵功率小的泵站，效率较低；
p 每年扣除的折旧费和大修费，以管网造价的%计；
Li 第i个管段管段长度，m;
t 投资偿还期；
i 为利率;
β 供水能量变化系数。
ρ 水的密度，ρ=
g 重力加速度，g =
H0 水泵净扬程，m；
从管网起点到控制点的任一条管线的水头损失，m；
将式（2-1）简化，只取其变量部分，得年费用或目标函数如下：
式中,P =8.76
2.2 约束条件
⑴节点连续方程:所谓连续性方程，就是对任一节点来说，流向该节点的流量必须等于从该节点流出的流量。规定流出节点的流量为正，流向节点的流量为负，则节点i的连续性方程可表示为：
其中φ为与节点i相邻的节点号集合，Qij为管段ij的流量，qi 为节点i的流量。
⑵环能量方程：能量方程表示管网每一环中各管段的水头损失之和等于零。一般规定水流顺时针方向的管段，水头损失为正，水流逆时针方向的管段，水头损失为负。则第j环的能量方程可表示为：
其中ψ为组成环的管段号集合，hl 为管段l的水头损失。
⑶节点自由水压约束：即任一节点的自由水压应不小于最小服务水头。
其中，
⑷管段流量约束：管段流量应大于最小允许流速时的流量。
其中qmin为管段最小允许流速时的流量。
⑸管径约束
其中W为所有可选管径的集合。
3 遗传算法在给水管网优化设计中的实现
遗传算法的关键技术主要包括编码、选择运算、交叉运算、变异运算适应度评价等问题[4]。在给水管网优化设计中，笔者主要采用了如下的具体操作：
⑴编码：目前应用遗传算法进行管网优化设计，普遍采用的都是二进制编码，用此编码表示管径规格会存在编码冗长的问题。同时，由于标准管径规格数目有限且不连续，势必也会增大遗传操作的难度。为了改进和提高遗传算法的可操作性和实用性，本文采用实数编码[5]。同时为了解决管径必须采用标准管径的问题，可先根据标准管径规格建立数组，例如Di={100，150，200，300，400，500，600，700，800，1000}，假设标准管径系列有T种可选择的标准管径，那么将随机数rand()%T(C++中)所产生的值i分别对应标准管径Di（i=0，1,2,…(T-1)）。由于个体的基因信息就是管径，可直接用于管网水力计算，进行个体的适应度评价十分方便，不必反复进行编码、解码操作。
⑵适应度函数：遗传算法中使用适应度这个概念来度量群体中的各个个体在优化设计中可能达到最优解的优良程度。适应度函数的定义一般与求解的具体问题有关。通常，适应度函数F是目标函数的一种数学变换。为调节遗传算法的性能可以对适应度函数做线性比例变换[6]，
F0 变换后的适应度函数；
F 变化前的适应度函数，F= ;
W 为广义目标函数；
f0 群体平均适应度；
fmin 群体中最小适应度。
⑶罚函数：在求解有约束优化问题时，遗传算法必须将其转化为无约束优化问题，一般采用罚函数方法实现。给水优化模型中，除了能量平衡和流量平衡约束通过水力计算部分纳入目标函数之外，经济目标函数还应满足最小服务水头等约束条件，以罚函数形式纳入目标函数。Dragan A.Svaic和 Godfrey A.Waiters 提出了如下罚函数：
M=W0+Kxmax{max[0,(Hmin-H)]}
其中，H为对于1组管径优化方案所计算出的管网节点压力列向量;Hmin为管网允许的最低节点列向量；max{max[0,(Hmin-H)]}表示所有节点欠压值的最大值；K为惩罚因子，K的选择应保证使欠压管网的广义目标函数大于不欠压管网的广义目标函数。
课题中为简便起见，设计当管中流速v∈(0.1, 2.5)(m/s),节点自由压力H≥16(m)，管道承压P≤100(m)时，M=W0；否则考虑惩罚因数，M=2W0。
⑷选择技术：遗传算法中使用选择运算来实现群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大，适应度低的个体被遗传到下一代群体中的概率小。常用的选择方法有赌盘选择法、随机联赛法、最优个体保留法等。在随机联赛选择操作中，只有个体适应度之间的大小比较运算，而无个体适应度之间的算术运算。
⑸交叉和变异运算：所谓交叉运算是指对两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉是最主要的遗传运算，是遗传算法区别于其它进化方法的重要特征，遗传算法的性能在很大程度上取决于采用的交叉运算的性能。
所谓变异运算，是指将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。变异运算决定了遗传算法的局部搜索能力。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。
4 实例
烟台市某新建小区单水源给水管网，经过调查分析、需水量预测、管网定线、比较选择水源的位置后，考虑供水可靠性的要求，采用环状管网设计。配水系统采用二级泵站供水，二级泵站通过输水管接入1号节点。管网节点编号与管段编号如图2所示。
管材全部使用新的球墨铸铁管，其价格参见表1所示，海曾系数C=130。管网每年扣除的折旧和大修理费用为管网造价的5%，系统运行方式为24小时连续供水，最高日最高时用水量为
图 2 算例简图
表1 球墨铸铁管段造价参考表
(注：参考数据来源于烟台自来水公司)
用遗传算法优化后的管网年折算费用值为1 020 308元，比用经典优化法优化的管网年折算费用值1 085 362元节省大约6%，二者的优化结果比较如表2所示。
表2 遗传算法优化结果与经典优化法优化结果比较
遗传算法应用于给水管网优化计算的特点如下：
⑴全局优化：遗传算法从问题解的串集开始嫂索，而不是从单个解开始。这一方面增加了全局寻优的能力，另一方面也给了设计者更大的选择余地。
⑵通用性：遗传算法求解时使用特定问题的信息极少，容易形成通用算法程序。
由于供水运行工况环境的变化而造成目标函数变化，对大多数依赖目标函数的其它优化算法就可能完全不能适用了。而遗传算法具有很强的鲁棒性，只需要适应度信息，不需要导数等其它辅助信息，对问题的依赖性较小，能够得到一组直接以市场规格管径表示的满足要求的优化解，更能适应管网计算要求。
⑶概率搜索：遗传算法中的选择、交叉和变异都是随机操作，同时它在一定的约束条件下采用启发式搜索，而不是盲目的穷举，因而兼顾了搜索的广度和方向性，搜索效率高。
总之，遗传算法能方便地处理管网优化设计中的离散变量，求得的管径为标准管径，避免了管径调整；遗传算法不会在狭窄区收敛，形成局部最优解；遗传算法形成了多个接近最优解的方案，使研究者能够方便地进行多方案间的比较。
参考文献：
[1]葛琳,许仕荣.基于遗传算法的给水管网优化设计[J].湖南大学学报,2003,30(3):167.
[2]王国明,颜高锋.环状给水管网计算的一种数据转换方法[J].合肥工业大学学报,2004,26(4):582.
[3]王小平,曹立明.遗传算法[M].西安:西安交通大学出版社,2002:1.
[4]郑立平,郝中孝.遗传算法理论综述[J].计算机工程与应用,2003,21:50.
[5]葛琳.给水管网优化设计及其CAD的研究[D].湖南大学硕士学位论文,2003,11:34.
[6]况青松.改进的遗传算法在给水网优化设计中的应用[D].合肥工业大学硕士学位论文,2003,5:30.
The Optimal Design of New Water Supply Networks Based
on Genetic Algorithms
LAN Zhi-ling, JI Zhi-feng
(Departerment of Computer and lnforncation Engineering, Yantai Vocational College,Yantai 264000,
Abstract: Genetic Algorithms is a new engineering optimal algorithm applied in the optimal design of water pipe network, and it also increases the economical rationality of network design plan. We analyze the form of math model in the optimal design of water pipe network supply, the theory of Genetic Algorithms, real number encoding method and the establishment of evaluation functions in the paper. At last, the application of Genetic Algorithms illustrates its effectiveness.
Key words: the optimal design of water supply networks; Genetic Algorithms; math model;example
(责任编辑 侯中岩)
收稿日期:
作者简介:栾志玲(1972- ),女,山东栖霞人,烟台职业学院计算机与信息工程系讲师.
联系客服
