（模式识别与智能系统专业论文）基于改进遗传算法的供水管网多工况优化设计.pdf

j，1_ill，j一 f ? i o p t i m a ld e s i g no fw a t e r d i s t r i b u t i o nn e t w o r kf o rm u l t i p l e o p e r a t i o n sb a s e do ni m p r o v e dg e n e t i ca l g o r i t h m b y l iw e n j u a n b e ( w u h a nu n i v e r s i t yo f s c i e n c ea n de n g i n e e r i n g ) 2 0 0 8 at h e s i ss u b m i t t e di np a r t i a ls a t i s f a c t i o no ft h e r e q u i r e m e n t sf o rt h ed e g r e eo f m a s t e ro fe n g i n e e r i n g l n m u n i c i p a le n g i n e e r i n g i nt h e g r a d u a t es c h o o l o f l a n z h o u u n i v e r s i t yo ft e c h n o l o g y s u p e r v i s o r p r o f e s s o rs e n i o re n g i n e e rl iz u p e n g ，a s s o c i a t ep r o f e s s o rl ih u i l i m a y , 2 0 1 1 脚0 删6m 5啪5 舢8 舢81脚y ，嶝、 r。 兰州理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名塘蠲日期：1 0 1 1 年6 月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即： 学校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许 论文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文 收录到中国学位论文全文数据库，并通过网络向社会公众提供信息服 务。 作者签名：虏交锔 导师签名：艿历乱哟 力弘粕 日期：瑚“年6e7 e 1 日期：细【1 年6 月7 e l 硕士学位论文 目录 摘要1 a b s t r a c t i i 第l 章绪论一l 1 1 课题研究背景及意义1 1 2 国内外研究进展l 1 2 1 给水管网优化设计模型综述2 1 2 2 供水管网模型的求解算法综述3 1 3 供水管网系统现状及需要解决的问题一6 1 3 1 管网设计的不合理性6 1 3 2 供水管网运行管理的高费用一7 1 3 3 管网严重的漏损率和爆管率一7 1 4 论文的研究主要内容7 第2 章供水管网多工况优化设计模型：9 2 1 供水管网水力计算分析9 2 2 管网优化设计模型目标函数的构建1 0 2 2 1 管网造价1 0 2 2 2 折旧费和大修费。10 2 2 3 泵站年运行电费1 1 2 2 4 费用函数1l 2 3 供水管网优化设计的影响因素1 2 2 3 1 管道造价公式经济参数的影响1 2 2 3 2 供水能量变化的影响1 2 2 3 3 水质因素的影响1 3 2 4 供水管网单目标多工况优化模型的建立1 3 2 4 1 单目标多工况优化设计的提出1 4 2 4 2 优化模型多工况的选择1 5 2 4 3 多工况优化模型的建立1 6 2 5 多工况优化设计的优势1 9 2 6 本章小结2 0 第3 章多工况优化模型的求解算法2 l 3 1 遗传算法概述及其原理2 l 3 2 遗传算法的特性2 l 3 3 遗传算法基本原理和算法2 2 3 3 1 编码设计2 3 j 基于改进遗传算法的供水管网多工况优化设计 3 3 2 初始群体的生成2 4 3 3 3 适应度值评价检测2 4 3 3 4 j 盘择2 5 3 3 5 交叉2 6 3 3 6 变异2 6 3 3 7 控制参数的确定2 6 3 3 8 约束条件的处理2 7 3 3 9 终止条件2 8 3 4 改进遗传算法的设计2 8 3 4 1 选择操作的改进2 8 3 4 2 约束条件的处理2 8 3 4 3 适应度值的设计与标定2 9 3 4 4 群体多样化2 9 3 5 本章小结3l 第4 章工程案例。3 2 4 1 工程概况3 2 4 2 多工况的设计选择3 4 4 2 1 最高日最高时工况3 4 4 2 2 平均时工况3 4 4 2 3 消防时工况3 4 4 2 4 事故时工况3 4 4 3 改进遗传算法运算操作的设置3 4 4 4 管网相关参数设置3 5 4 5 不同算法优化结果比较3 6 4 6 本章小结4 2 结论与建议4 4 结论4 4 建议4 4 参考文献4 6 致 射4 9 附录a 攻读学位期间所发表的学术论文5 0 硕士学位论文 摘要 随着城市的扩大化发展以及供水管理水平的不断提高，供水管网系统的规划 设计相比之前也有了高的起点和要求，因此正急需新的规划设计方法或优化设 计。 针对现有的供水管网优化模型，通常是基于最高日最高时单一工况，忽略其 他工况如平均时、消防时、事故时等运行工况的约束条件，不属于全局优化的结 果。在已有的研究基础上，考虑到现有的多目标函数中的水质目标、安全可靠性 目标的量化很含糊和不成熟性，本文提出了在满足管网各个用水工况不同的约束 条件基础上，以管网造价和泵站运行费用之和的管网年费用折算值最低为单一目 标的给水管网多工况优化设计数学模型，该模型中多工况的选择包括最高日最高 时、平均时、消防时、事故工况时等四个工况，且模型中引入了不同工况条件下 水泵机组运行时间占全年运行时间的比例。 在选用模型求解算法时仔细分析研究了常用的求解算法，如拉格朗日函数 法、界限流量法、线性规划算法、非线性规划法、动态规划法、遗传算法等。最 后考虑到管网优化模型中管径这一决策变量的离散性，以及多工况优化模型的研 究还比较不成熟，本文暂时在比较成熟的遗传算法的基础上做了简单的改进得到 的改进的遗传算法，并将其运用到实际工程中的多工况优化设计模型中。论文使 用m a t l a b 编制供水管网优化算法的求解程序。最后通过一个实际工程的供水 管网优化设计实例，进行传统遗传算法和改进遗传算法优化结果比较，证实了改 进遗传算法优化结果的优越性，同时也验证了多工况优化模型的优势。 关键词：供水管网；多工况优化设计模型；遗传算法 一一 a b s t r a c t a st h ec i t y e n l a r g e m e n ta n ds u p p l ym a n a g e m e n tl e v e lo fd e v e l o p m e n to f u n c c a s l n ge n h a n c e m e n t ，w a t e rs u p p l yn e t w o r ks y s t e mp l a n n i n gd e s i g nb e f o r ea l s o h a dh i g hc o m p a r e dt ot h e s t a r t i n gp o i n ta n dr e q u i r e m e n t s ，t h e r e f o r ea r eu r g e n t l y n e e d e dn e w p l a n n i n gm e t h o d so ro p t i m i z a t i o nd e s i g n c u r r e n tn e t w o r ko p t i m i z a t i o nd e s i g na r eu s u a l l yb a s e do na s i n g l em o d e so ft h e s i n g l eo b j e c t i v eo rm u l t i o b j e c t i v eo p t i m i z a t i o nm o d e l ，i g n o r i n go t h e rc o n d i t i o n s s u c ha sa na v e r a g e ，f i r e ，s u c ha st h eo p e r a t i o nc o n d i t i o no fa c c i d e n t sc o n s t r a i n t s s o t h a tt h o s eo p t i m i z a t i o nm o d e l sd o n o tb e l o n gt o g l o b a lo p t i m i z a t i o nr e s u i t s m o r e o v e r , t h es o m et a r g e to fe x i s t i n gm u l t i o b je c t i v ef u n c t i o no p t i m i z a t i o nm o d e l s s u c ha s s a f e t ya n dr e l i a b i l i t yo ft h eq u a n t i f i c a t i o nt a r g e t ，a r ev e r ya m b i g u o u sa n d i m m a t u r i t y b a s e do nt h ee x i s t i n gr e s e a r c h ，t h i sp a p e rp u t sf o r w a r dt h e m u l t i p l e o p e r a t i o n so p t i m a ld e s i g nm o d e lo fw a t e rd i s t r i b u t i o nn e t w o r k ，w h i c hs e l e c tt h es u m o fn e t w o r kc o s ta n do p e r a t i o nc o s to ft h ep i p e l i n ep u m pf e e s f o ras i n g l et a r g e t c o n v e r s i o nv a l u et h el o w e s tw a t e rn e t w o r k sw o r k i n g s i n g l et a r g e t ，c a nm e e td i f f e r e n t c o n s t r a i n to fd i f f e r e n tw a t e rc o n d i t i o n s t h i sm o d e lt h i n ka b o u tf o u rc o n d i t i o n sa n d a c c o u n tf o rp u m pu n i tr u n n i n gt i m er u n n i n gt i m es c a l e f o u rc o n d i t i o n s a r ep e a k c o n d i t i o n s ，a v e r a g ec o n d i t i o n s ，f i r ec o n d i t i o n ，a c c i d e n tc o n d i t i o n t h i sp a p e r a n a l y z e da n ds t u d i e dc a r e f u l l yu s e dc o m m o ns o l v i n ga l g o r i t h m ，s u c h a sl a g r a n g ef u n c t i o nm e t h o d ，b o u n d a r i e sf l o wm e t h o d ，l i n e a rp r o g r a m m i n g m e t h o d ， n o n l l n e a rp r o g r a m m i n gm e t h o d ，t h ed y n a m i cp r o g r a m m i n g ，g e n e t i ca l g o r i t h m s ，e t c f i n a l l yc o n s i d e r i n gt h ed i s c r e t e n e s so f p i p ed i a m e t e r , t h i sp a p e rt e m p o r a r i i yd os o m e 1 m p r o v eb a s e do nm a t u r eg e n e t i ca l g o r i t h mt og e tt h ei m p r o v e dg e n e t i ca l g o r i t h m w h i c hw a sa p p l i e dt ot h ep r a c t i c a l e n g i n e e r i n gw o r k i n go p t i m i z a t i o nd e s i g nm o d e l b yu s i n gm a t l a bc o m p i l i n gw a t e rs u p p l yn e t w o r k o p t i m i z a t i o na l g o r i t h mo f s o l v i n g p r o g r a m f i n a l l y , t h r o u g hap r a c t i c a l e n g i n e e r i n ge x 锄p l eo fw a t e r d 1 8 t r i b u t i o nn e t w o r ko p t i m i z a t i o nd e s i g n ，w i t ht h e c o m p a r i s o no ft h eo p t i m i z a t i o n r e s u l t sb e t w e e nt h et r a d i t i o n a lg e n e t i ca l g o r i t h ma n di m p r o v e dg e n e t i c a l g o r i t h m c o n f i r m e dt h e i m p r o v e dg e n e t i ca l g o r i t h m ，a n dt h e o p t i m i z e dr e s u l t sv e r i f i e d s u p e r i o r i t ya n dt h ea d v a n t a g eo fw o r k i n go p t i m i z a t i o nm o d e l k e yw o r d s ：w a t e rs u p p l yn e t w o r k ；w o r k i n go p t i m i z a t i o nd e s i g nm o d e l ：g e n e t i c a l g o r i t h m 硕士学位论文 1 1 课题研究背景及意义 第1 章绪论 水是人类生活、工农业生产和社会经济发展的重要资源，科学用水和捧水是 人类社会发展史上最重要的社会活动和生产活动内容之一，特别是在近代历史 中，随着人类居住和生产的城市化进程，给水排水工程是已经发展成为城市建设 和工业生产的发展命脉，成为人类生命健康安全和工农业科技与生产发展的基础 保障【l j 。随着农村城市化，城市化扩大化、经济快速的发展，国内外都致力于 追加投资在城市供水基础设施，提高城市供水设施的建设。就最近这几年来，我 国的用水规模直线上升，同时供水领域也出现了新的特征：( 1 ) 国内城市工、企 业构造的整顿，促使需水量大的企业做到水的反复利用，减少排放和水资源的浪 费，同时限制新起的高新技术的需水量，而这些原因导致最近几年的供水量没有 上升而呈现下降的趋势：( 2 ) 用户以及工企业的用水结构也有所改变，工企业生产 用水从1 9 9 1 年的8 2 下降至4 3 ，居民、工企业的生活用水则从2 8 增加到5 7 【7 1 o 在实际工程中，供水工程中供水管网都是一铺到位的，而仅仅管网的建造费 就占了整个工程的7 0 一8 0 ，管网中管径组合和水泵的选择的经济性、合理科 学性直接影响着整个工程的投资 2 - 3 1 。要想贯彻节约资源( 人力，物力，财力和土 地资源) ，务必要做详细管网的规划设计和优化设计，通常情况下管网经过合理 的优化设计后工程投资能减少s 1 0 4 - 6 l 。因此，在工程资金投入一定的情况 下，管网优化设计结果的合理、经济、可靠性对于贯彻“科学发展观一、创建“节 约型社会一等有重要现实意义。由此可见，管网的优化设计是顺应局势而逐渐成 为研究热点。 供水管网优化设计发展至今，始终是围绕着四个方面，满足供水管网所需的 水量和水压、水质安全、可靠和经济性目标。至于水质安全性目标虽然已有以控 制管网末端余氯值为目标，但是经分析该目标可以转换为经济性目标，可靠性的 定义也较模糊可信度不高。所以，管网优化设计的目的是在满足各种设计目标的 情况下，求出在设计使用年限内，管网年费用折算值为最小的管径组合或水泵的 扬程。 1 2 国内外研究进展 纵览所查文献，在供水管网优化设计这方面的研究，过去的几十年里，研究 l 基于改进遗传算法的供水管网多工况优化设计 者们提出了形式多样的供水管网优化设计数学模型和相应求解算法。将其逐步的 运用在工程实践中，并取得了一定应用价值和工程价值方面的。 1 2 1 给水管网优化设计模型综述 供水管网优化模型的大致有单目标单工况、多目标单工况、单目标多工况、 多目标多工况等四类。管网优化设计模型的依据主要有管网基建费用、管网年折 算值和管网安全可靠性，总之管网优化设计模型的目标函数不外乎从经济性和可 靠性两方面进行考虑和设计。迄今为止，供水管网多目标多工况优化设计模型的 研究和应用尚不多见。下面介绍下前三种优化设计模型的研究进展。 1 单目标单工况优化模型 在管网的单目标单工况优化设计数学模型中一般只满足供水的经济性目标， 仅仅以管网最高日最高时单一用水工况为研究对象。k a r m e l i 8 】在1 9 6 8 年第一次 提出了树状管网优化设计模型：数学目标函数是管网投资费和决策变量为具有标 准管径的管长；k a r m e l i 紧接着又将目标函数改为管网造价和泵站的运行费用之 和最小，决策变量增加了水泵扬程。k a r m e l i 提出的这两种模型都只适合树状管 网。k a l l y 列在1 9 7 2 年同样以具有标准管径的管长为决策变量，以管网投资最小 为目标函数，提出了环状供水管网优化设计的模型。a l p e r o v i t s 和s h a m i r 1 0 】在 1 9 7 7 年提出了在环状管网优化设计中的环状系统模型，该模型有两个阶段：( 1 ) 在初分流量情况下，进行管网的最优化设计；( 2 ) 进行费用目标对流量分配的求 导，逐步靠近管网最优的流量分配，转到( 1 ) 继续优化，如此反复以致不能再继 续优化。在供水管网优化设计领域中单目标单工况优化设计模型的研究是最早、 最多、最成熟的。 2 单目标多工况优化模型 多种供水工况主要是指设计使用年限内管网中存在的最高日最高、消防时、 最大转输时、平均供水时、事故时、现状供水工况以及各节点的压力和流量不同 要求的工况。纵览所查文献，在供水管网单目标多工况优化数学模型中总是最先 满足供水管网系统的经济性目标。 单目标多工况优化设计数学模型是s h a m i r 】在1 9 7 4 年第一次提出的，该模 型里的决策变量选择有管径、自由水头和流量；目标函数为管网系统的投资和多 种工况下的泵站运行费用之和，约束条件中除了传统的约束条件一一管径约束、 压力约束、流速约束等，该模型中的约束条件还包括多种工况下的系统性能约束。 通过计算机编程的实现和应用研究表明，证实了该模型是可行的。王荣和【1 2 】在 1 9 9 9 年将该模型应用于工程实例中，将优化结果与采用单目标单工况的优化结 果做了比较，结果表明单目标多工况优化设计模型具有很高的可靠性和可信度。 在此基础上刘守亮将多工况模型运用到单水源的管网系统中进行优化设计，模型 2 硕士学位论文 中满足了三个工况一一最高日最高时、最大转输时和平均时工况，同样也证实了 该模型的正确实用性。在这之后，吕谋、董深【1 3 0 4 】等在2 0 0 7 年也建立了满足供 水系统中最高日最高时和平均时两种工况的单目标多工况优化设计数学模型。该 模型的约束条件做了相应的改进一一加入流速约束条件并用该约束替换了最小 管径约束，经过工程实例优化结果的比较，验证了改进后的多工况数学优化模型 具有良好的供水安全性和经济性。 3 多目标单工况优化模型 随着单目标优化模型的不够全面性，研究学者逐渐开始提出多目标优化设 计。迄今为止，供水管网的多目标模型的目标通常选用经济性目标、管网可靠性 或水质安全性、配水均匀性。 t a n y i m b o t h 1 5 1 在2 0 0 2 年提出两个目标的优化设计数学模型一一只考虑管网 建造费用的经济目标和可靠性目标。模型中的通过管网信息熵来体现管的可靠性 目标，因为管网信息熵可以表示管网的布局，管网信息熵越大管网布局也合理， 而管网布局的好坏直接影响着管网的可靠性的，但是经济性目标只包含管网建造 费忽略了管网系统年运行费用，缺乏说服力。 k l e b b e 1 6 】在2 0 0 3 年在t a n y i m b o t h 研究的基础上，提出了管网三目标优化设 计模型：经济性、可靠性目标和流量比率目标。该模型存在两个缺陷：( 1 ) 与 t a n y i m b o t h 提出模型一样，经济性目标只包含管网建造费忽略了管网系统年运 行费用，缺乏说服力；( 2 ) 模型中管网的各个节点的熵值是单独计算的，忽略了 节点之间的相互影响作用。这些缺陷导致限制了该模型的使用推广。 蒋怀德【1 7 l 在2 0 0 7 年提出了三目标的优化设计数学模型：经济性目标、可靠 性目标、配水均匀性目标。不同之前的研究，该模型中的可靠性目标是通过管网 的熵值来表示的管网流量分配均匀程度，忽略了节点的相联管段管径以及节点的 水压，不够合理。同年，吕谋、董深【1 4 】等也研究了供水管网的多工况优化设计， 其研究过程是：首先应用计算机编程对最高日最高时单一工况优化设计出一组最 优管径下的管段流量分配，然后对管段流量已分配的管网进行平均时工况的优化 设计，该优化设计缺乏安全性。 1 2 2 供水管网模型的求解算法综述 随着供水管网优化模型的建立，相应的求解算法相继出现，得到模型的较优 解或最优解。供水管网优化模型的求解算法经历了数学规划优化法( 线性规划法、 动态规划法和非线性规划法) 和随机搜索算法三个主要阶段。 1 界限流量法 界限流量法是基于近似优化算法的前提提出的。该法的理论基础就是将管网 中的各个管段假定是互不影响的独立工作。市面上所售的管道标准管径是离散的 3 基于改进遗传算法的供水管网多工况优化设计 而非连续的，根据相邻两个标准管径q 、见一。的年费用折算值相等的条件，可以 确定界限流量。界限流量的表达式为： 州c 筹争； t ， 式中，包括多种经济指标的综合参数； 4 、6 一一单位长度管线造价公式中的系数和指数； 刀一一输水管分段数。 对于不同的地区和城市，供水工程的管网造价、压降公式中的参数以及电费、 用水规律等均有差别，导致其管道的界限流量有差别，不能任意套用。即便对于 同一地区，管网建造费用和泵站运行管理费等也是不一样的，必须根据当时当地 的经济指标和压降公式，求出各值，再确定界限流量。或者查表求得，但是如果 当地经济因素厂不等于l 时，必须将该管段流量化为折算流量后，再查表求得。 单独管段折算流量公式为：、 = 3 岛 1 1 2 ) 根据上式求得的折算流量吼，查表即得经济的标准管径。 表1 1 界限流量表 管径( m m )界限流量( l i s )管径( m m )界限流量( l s ) 1 0 0 4 0 0 时为o 9 1 4 m s 速2 、设计中可采用平均经济流速来确定管径，一般大管径 可取较大值，小管径则取较小值 理论上流速的选择可以按上述选择，但是在实际工程中，管径的确定不是单 一因素能决定的，而是综合近远期流量、各工况条件、水头损失、经济流速、界 限流量表以及工程造价等多个因素确定的。 ( 6 ) 水泵特性曲线： q = 4 一易g q 式中： 一一水泵的扬程； ( 2 2 8 ) 硕士学位论文 q ，一一水泵歹的流量； 4 ，乃，q ，一一水泵，的特性曲线参数。 ( 7 ) 流量约束： 吼= 瓴i 吼2 ，吼，3 ，吼，。 式中： ( 2 2 9 ) 吼一一供水工况s 下管网节点流量集； g “一一供水工况s 下节点f 流量。 综上所述，给水管网多i 况优化设计的模型可以表达为式： 口批r ：矽= 幽c 吾+ 蹦，倭c c 蹦缁粥妻姜学) c 2 珈， 。蚴：矽= 酬器+ 麟，胁li = l 叫+ s s 粥妻姜学亿3 ， ( 劬) + g = o t = 可1 0 6 场7 万 s 5 2 b 伊 ( 2 3 2 ) d 5d k h j = a j b 噬j 吼= 缸i ，吼，2 ，吼 3 ，以一 继续通过常规的人工计算方法来确定管网的管径组合和水泵型号，很明显 已不再满足当下的供水管网的设计要求了一般由于供水管网数学模型及单一 供水工况的限制，导致经典的标准优化法或者由界限流量所得结果比常规的人 工算法强和快捷，但结果缺乏安全可靠性，可行度不高。 上一章节中式( 2 3 0 ) 、( 2 3 1 ) 、( 2 3 2 ) 所示的供水管网的多工况优化数学模 型，正是模拟了工程中管网存在的各种工况运行情况和泵站实际运行情况，对后 期管网调度工作有了明确的指导作用，同时也解决了传统的标准优化法所碰到的 各种难题。在进行多工况优化计算时，一种管径组合必须进行所有存在的供水工 况下的水力计算，才能计算出这种管径组合时各种工况下水泵出水扬程和流量， 进而计算出整个管网系统的年折算费用值。并以此作为管网调度的依据，是水泵 在各个工况下都能高效的运行。 2 5 多工况优化设计的优势 与供水管网单工况优化模型相比，多工况优化模型具有如下的优势： 1 、后者能保证设计的管径组合和泵站的特性系数在保证满足其各种运行工 况前提下，是管网投资年费用最低，是一个全局优化结果。 一 基于改进遗传算法的供水管网多工况优化设计 2 、后者含有水泵特性曲线的优化设计，这是单工况优化设计模型中所欠缺 的。 3 、后者引入了水泵机组在不同的供水工况下的运行时间占全年运行总时间 的比例这一值直观的反应了水泵机组每年的运行情况，对供水管网的后期 运行管理调度有很明确的指导作用。 2 6 本章小结 本章节简单介绍了常用的三种供水管网水力计算方法：详细阐述供水管网设 计模型的构造，并分析了其影响因素。最后仔细介绍了本文的供水管网多工况优 化设计模型的推导过程及其优势。 硕士学位论文 第3 章多工况优化模型的求解算法 3 1 遗传算法概述及其原理 遗传算法( g e n e t i ca l g o r i t h m s ，简称g a ) 是由进化论原理一一自然选择和基 因遗传机制，演变发展起来的一种具有应用性广泛、快捷方便的随机搜索技术和 优化算法，是生命科学与工程科学的相互融合、促进的产物。该算法是宏观意义 上的仿生算法，它模仿生物生命与智能的产生和演变过程，通过模拟达尔文“优 胜劣汰、适者生存 的机理，激励并保存好的基因，通过模拟孟德尔遗传变异原 理在迭代过程中保持已有的基因，同时寻找更好的基因。遗传算法已成为人工智 能研究的一个重要领域，同时也成为了解决困难的组合优化问题和复杂的函数优 化问题的有效工具，并引起了各学科研究人员的普遍重视。发展过程基本上分为 三个阶段： ( 1 ) 2 0 世纪7 0 年代起步时期，主要由美国m i c h i g a n 大学的j o h nh o l l a n d 教 授最初尝试从生物进化机理中发展出适合现实世界复杂优化问题的模拟进化算 法。随后d ej o n g 3 4 】基于遗传算法的思想在计算机上进行了大量的纯数值函数优 化计算实验。 ( 2 ) 8 0 年代的兴起时期，在大量研究工作的基础上，g o l d b e r g 3 s 归纳总结出 了遗传算法的基本流程。1 9 8 5 年在美国卡耐基梅隆大学召开的第一届国际遗 传算法会议( i n t e r n a t i o n a lc o n f e r e n c eo ng e n e t i ca l g o r i t h m s ：i c g a 85 ) ； ( 3 ) 9 0 年代的兴旺时期，1 9 9 7 年5 月i e e e 的t r a n s a c t i o n so ne v o l u t i o n a r y c o m p u t a t i o n 创刊，再到2 0 0 5 年遗传算法国际年会一一遗传算法的基础 ( f o u n d a t i o no f g e n e t i ca l g o r i t h m s ) 。遗传算法作为一种实用、高效、鲁棒性强的 优化技术，发展极为迅速，已引起国内外学者的高度重视，其研究渐趋成熟。 3 2 遗传算法的特性 与传统的优化方法相比，遗传算法具有以下特点【3 6 l ： ( 1 ) 不同于其他优化方法，遗传算法先将待处理的对象进行编码设计，即遗 传算法不是直接处理问题本身而是处理算法能识别的编码； ( 2 ) 供水管网系统的优化设计模型中决策变量，约束条件和管网系统建造费 等中不乏离散性的问题，遗传算法的搜索过程不受这个影响； ( 3 ) 具有高效的并行性，搜索效果显著； ( 4 ) 遗传算法在搜索过程中不容易陷入局部最优，该算法能高效的寻求到全 2 1 基于改进遗传算法的供水管网多工况优化设计 局最优解，不会因为适应度函数的离散与否、规则与否等而受到影响； ( 5 ) 遗传算法采用自然进化机制来表现复杂的现象，对于很复杂的问题也能 够快速可靠地解决： ( 6 ) 扩展性比较强，可以与其他的技术混合使用。 遗传算法作为一种优化方法，也存在自身的局限性如容易出现早熟现象，优 化方法低、编码设计的不规范性，以及算法结果的精度、可行性等无法定量分析 等。 3 3 遗传算法基本原理 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任意 初始种群( p o p u l a t i o n ) 出发，通过遗传算子( 随机选择、交叉和变异) 操作，产生一 群更适应环境的个体，使群体进化到搜索空间中越来越好的区域，这样逐代地不 断繁衍进化，收敛到一群最适应环境的个体( i n d i v i d u a l ) ，求得问题的最优解。传 统的遗传算法运算流程可以用图表示： 图3 1 遗传算法运算流程 硕士学位论文 如图3 1 所示，遗传算法的主要运算过程如下： 3 3 1 编码设计 编码是应用遗传算法是首要解决的问题，也是设计遗传算法时的关键步骤之 一。在遗传算法执行过程中，对不同具体问题进行编码，编码的好坏直接影响遗 传算子的操作。编码就是将问题的可行解从其解空间转换到遗传算法所能处理的 搜索空间的转换方式，与之相反的是解码，即遗传算法解空间向问题空间的转换。 针对具体问题，怎样设计出一套完美的编码方案一直是遗传算法研究的重点 之一。由于遗传算法应用的广泛性，迄今为止人们已经提出了许多种不同的编码 方法，总的来说，常用的有：二进制编码、十进制编码、符号编码和浮点数编码。 1 、二进制编码 二进制编码是遗传算法中经典常用的编码方式，该方法是将问题的求解变量 转换为遗传空间的二进制符号0 和l 组成的二值符号集 0 ，1 ) 。该编码的优点有： ( 1 ) 比较满足编码设计中最小字符集的要求；( 2 ) 编码、解码操作简单易行，便于 进行交叉、变异等遗传操作，且物理概念清晰；( 3 ) 便于用模式定理进行分析和 预测。因为模式定理就是以二进制编码为基础建立起来的，二进制提供了各个位 信息最大的模式数。但是由于该算法不能直接反映出所求问题的本身结构特征导 致其在应用时受到限制。 2 、自然数编码 自然数编码也就是整数编码，是指直接以一个自然数( 整数) 来表示某一种管 径，比如0 表示管径1 0 0 ，1 表示管径1 5 0 ，以此类推，2 0 表示管径2 0 0 0 。管网 的管径组合可以用一个自然数串来表达，如 0 ，3 ，5 ，1 2 ，1 9 ，在自然数串空 间上进行遗传操作。相应地，在解码时，按照一一对应的关系，将自然数还原成 管径，进行管网的年费用折算值计算。相比二进制编码，其主要的优势是避免了 编码问题的繁冗。 3 、格雷码编码 格雷码编码是二进制编码方法的一种变形，该编码方法弥补了之前的二进制 编码不能直接反映所求问题的结构特征的局限性；当优化问题是连续函数，也能 使遗传运算即使具有随机特性也能避免其局部搜索能力较差的缺点。格雷码编码 特点是连续的两个整数所对应的编码之间仅只有一个不同，其余都相同。其主要 优点有：( 1 ) 便于提高遗传算法的局部搜索能力；( 2 ) 便于实现遗传算法的操作 算子交叉、变异等；( 3 ) 满足编码方式中最小字符集编码要求。 4 、浮点数编码 浮点编码也叫真值编码，是指个体的每个基因值用某一范围内的一个浮点数 表示，个体的编码长度等于决策变量的位数。该编码方法是针对多维、高精度要 基于改进遗传算法的供水管网多工况优化设计 求的连续函数优化问题提出的。 其他常用的编码技术有浮点数编码、多参数级联编码、多参数交叉编码、一 维染色体编码、二维染色体编码、可变染色体长度编码和树结构编码。 目前尚无一套严格完整的指导理论及评价标准来帮助我们设计编码方案，必 须具体问题具体分析，采用不同的编码方法。评估编码常采用三个策略：完备健 ( c o m p l e t e n e s s ) 、健全性( s o u n d n e s s ) 、非冗余性( n o n r e d u n d a n c y ) 。在具体问题的 设计中，这三个策略一般是不可能同时满足的，不过完备性是必须要满足的。 3 3 2 初始群体的生成 由于遗传算法是从一个群体开始寻优，而不是从单一的一个个体进行寻优， 所以在初期必须对种群进行初始化。种群内的每一个个体表示染色体的基因编 码，相应地代表了一种设计方案。初始化完毕后的种群定义为第0 代种群。 3 3 3 适应度值评价检测 适应度函数是的作用就是表明个体或解的优劣性。不同的问题适应度函数的 定义方式不同。根据具体问题，计算群体中各个个体的适应度。 在遗传算法中，适应度函数的主要目的就是对染色体的优劣进行评价，因此， 适应度函数的函数值是选择运算的最主要的依据，由于进化的准则是“优胜劣汰， 适者生存一，所以目标函数的寻优方向应该和适应度函数值增加的方向一致，这 是适应度函数设计的先决条件。另外，为了理论分析的方便，最好保证适应函数 值非负。有时适应度值为负的情况，要进行适当的转换。 将目标函数转换成适应度函数的设计一般要遵循下面四个基本原则。 ( 1 ) 单值、连续、非负、最大化； ( 2 ) 适应度值反映对应解的优劣程度，这个原则的符合往往难以衡量； ( 3 ) 计算量小。适应度函数的设计力求简单，从而提高计算在时间和空间的 效率，降低计算成本； ( 4 ) 通用性。适应度对同一类具体问题尽量通用，最好不用改变适应度函数 的参数。 l 、适应度函数的种类 对于最小值问题，常用转换有如下几种： ( 1 ) f i t ( f ( x ) ) = - f ( 力( 3 1 ) 此法的不足之处有：当某些带求解的函数在函数值分布上相差很大时，此种 方法得到的平均适应度值也许阻碍了种群的平均性能，影响算法结果的优劣。同 时此法不满轮盘赌选择中概率非负的要求。 ( 2 ) 界限构造法，该算法引入c 哪，即是厂( 曲的最大估计值。 2 4 硕士学位论文 。聊( 咖 八誓 ( 3 2 ) 该转换方法存在c 眦很难准确的预先估算，所以精确度不高。 ( 3 ) 与第二种转换方法相似，c 为目标函数界限的保守估计值。 砌( ( 曲) 2 赢，c 0 抖厂( 曲o 。( 3 3 ) 2 、适应度尺度的变换 纵览所查文献，比较通用的变换方法主要有三种：线性尺度变换、乘幂尺度 变换、和指数尺度变换【3 6 1 。 ( 1 ) 线性尺度变换 线性尺度变换公式为：f t - a f + b( 3 4 ) 式中，f 为原函数；，为尺度变换后的新适应度；a 和b 为系数。a 和b 的 确定直接影响到这个尺度的变换的大小，所以对其选取有一定的要求。 ( 2 ) 乘幂尺度变换 乘幂尺度变换时新的适应度是原适应度的某个指定乘幂。乘幂尺度变换的公 式为： f = f 量 ( 3 5 ) 式中，幂指数k 与所求解的问题有关，且在算法的执行过程中需要不断对 其进行修正才能使尺度变换满足一定的伸缩要求。 ( 3 ) 指数尺度变换 指数尺度变换时新的适应度是原适应度的某个指数。指数尺度变换的公式为 f = e x p ( 一胴 ( 3