（市政工程专业论文）改进的遗传算法在给水管网优化设计中的应用.pdf

改进的遗传算法在给水管网优化设计中的应用 摘要 由于给水管网优化设计在给水工程中占有重要地位。国内外学者对其进行了 广泛而深入的研究，提出了多种优化方法，诸如禁忌搜索、模拟退火、遗传算 法和人工神经网络算法。但这些方法在实际应用中均存在一定的局限性。文中 首先阐述了给水管网优化设计的内容和意义。简要介绍了已有的优化方法，分 析比较了各种优化方法并指出其存在的不足，归纳总结了影响给水管网优化设 计结果的各种因素：接着，介绍了遗传算法的基本原理，然后在标准遗传算法 的基础上，通过对选择算予、交叉算子、变异算子以及部分参数的设置采取改 进措施，并以年费用折算值为目标函数，建立了给水管网优化设计的遗传算法 模型；最后，通过工程实例验证了该模型具有一定的理论和应用价值。 关键词：给水管网优化设计遗传算法年费用折算值 t h e a p p l i c a t i o no fi m p r o v e dg e n e t i ca l g o r i t h m s o nt h eo p t i m a l d e s i g n o fw a t e r s u p p l y n e t w o r k s a b s t r a c t t h eo p t i m a ld e s i g no fw a t e rs u p p l yn e t w o r k sh a sb e e nb r o a d l ya n dd e e p l y s t u d i e db ym a n yd o m e s t i ca n df o r e i g ns c h o l a r sb e c a u s eo fi t s i m p o r t a n ts t a t u s i n w a t e rs u p p l ye n g i n e e r i n g t h es c h o l a r sa d v a n c e dm a n yk i n d so fo p t i m a lm e t h o d s ， s u c ha st a b us e a r c hm e t h o d ，s i m u l a t e da n n e a l i n gm e t h o d ，g e n e t i ca l g o r i t h m sm e t h o d ， a r t i f i c i a ln e u r a ln e t w o r k sm e t h o d t h e s em e t h o d sa l lh a v es o m el i m i t a t i o no n p r a c t i c e t h i sp a p e r ，f i r s t l y , e x p a t i a t e st h ec o n t e n ta n ds e n s ea b o u to p t i m a ld e s i g no fw a t e r s u p p l yn e t w o r k s ，b r i e f l yi n t r o d u c e sa l lo p t i m a lm e t h o d sw h i c hh a v eb e e na d v a n c e d ， a n a l y z e st h e s em e t h o d s a n dp o i n t so u tt h e i rl i m i t a t i o n ，s u m m a r i z e st h ef a c t o r sw h i c h i n f l u e n c et h er e s u l t si n o p t i m a ld e s i g n o fw a t e r s u p p l yn e t w o r k s ；s e c o n d l y , i t i n t r o d u c e st h ep r i n c i p l eo fg e n e t i ca l g o r i t h m s i tt a k e sy e a r l ye x p e n d i t u r ec o n v e r t i n g v a l u ea st a r g e tf u n c t i o na n ds e t su pt h eg e n e t i ca l g o r i t h m sm o d e lo no p t i m a ld e s i g no f w a t e rs u p p l yn e t w o r k sb a s e do ns i m p l eg e n e t i ca l g o r i t h m sb ym e a n so ft a k i n gs o m e e f f e c t i v em e a s u r e so ns e l e c t i o no p e r a t o r , c r o s s o v e ro p e r a t o gm u t a t i o no p e r a t o ra n d s o m ep a r a m e t e r ss e t t i n g ；f i n a l l y , t h eg e n e t i ca l g o r i t h m sm o d e li s v e r i f i e d b y i t s a p p l i c a t i o n o n e n g i n e e r i n gp r o j e c t k e y w o r d s ：t h e o p t i m a ld e s i g no f w a t e rs u p p l yn e t w o r k s ，g e n e t i ca l g o r i t h m s ，y e a r l y e x p e n d i t u r ec o n v e r t i n gv a l u e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得台肥工业太堂或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签名： j o 青朽签字日期：刎年1 日 学位论文版权使用授权书 本学位论文作者完全了解金肥王业太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权盒肥工业太堂可以将学位论文的全部或部分内容编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名 签字日期砖年6 月节日 学位论文作者毕业后去向：) 斩1 乙 工作单位：i 奸喜芸簪产乞 通讯地址： 导师签名 训习w 儡 签字日斌i , j 1 1 日 电话：8 9 弓如7 0 3 ，- 邮编： 致谢 本人在研究生学习、生活期间，自始至终得到导师王国明老师无微不至的 关怀。在文献检索、资料收集、调研考察、论文选题和论文撰写过程中，导师 给予了具体悉心的指导，提出了许多宝贵的意见和建议。导师严谨的治学态度 刻苦钻研、兢兢业业的工作精神和平易近人的作风，使我深受启迪，受益匪浅。 在此我向导师致以最诚挚的敬意和深深的感谢 在本文写作过程中，得到了娄健、汪忠明、潘金锋等许多同学的帮助，在 此向他们表示深深的谢意! 感谢我的家人对我学习的支持与鼓励，感谢所有在我生活、学习期间，支 持和帮助过我的老师、同学。 况青松 二零零三年五月 第一章缳论 l 。1 国内外绘水管网的计罄理论及电舅应用的发展壤提f h 4 】 给水工程总投资中，输水管和管网所占费用是很大的，一般约7 0 一8 0 ， 鞠诧，输配永系统静饶纯设计在给求工程中占有重要的蓖位，要达到投资少、 能耗低、可靠性高的目标，必须进行多种方案的计算和比较，以褥到经济、 合理的满足j 蠢期和遮期用水的最佳方案。但越，给水管网的设计面临着巨大 的困难，牵涉到很多方恧。其主要困难表现在以下几个方鳆：f 1 ) 管径鲍离教 化；( 2 ) 费用函数难以确定；( 3 ) 环状管网可靠性的评估；( 4 ) 设计中涉及多种需 水量形式。 给水管网的设计从手算到电簿，从凭经验设计到优化设计是与计算方法 及诗算工其赘发展_ i 毫程糖逡应懿。 最早使用的管网水力分析方法是众所周知的哈代克罗斯法。它是以能 鹫方程西鼹f 环) 豹承头损失平衡为准粥，并引逶校正流潼的概念来求解。 方程的欲求变基是环的校正流量，方程的个数就是管网的綦环数。由于这一 方法采稍的是迭代方法，舅迭代公式简单硬予手工计算，所以在无计算机的 年代，遮方法占有绝对蛉统治地位。7 0 年代以后，随着鼹终技术的应鼹发 腿，便于用图论来构造给水管网的节点方程和环方程，这魃方程都是以矩阵 来攒述豹，方撰影式麓法明了，健人髓对系统、方程本身戆蕊矮及其庭霆有 了更直观、更深刻的认识。而且，求解这些方程的各种方滋易于在计算机上 实现。应躅较多豹蹩葶l 薅牛顿迭代法来求解节点方稳和环方程，由于应弼牛 顿法求解时所形成的雅可比矩阵慰一个对称正定、带状的稀疏矩陟，可利用 效率极离豹平方禳注来求解籀应静线往方程组。这秘方法收敛袄、精度商、 储存量小，目前，即使在微机上也可对大型给水管网进行水力分柝计算。 管两的水力计算是管翮设计的基础，随着系统工程、最优化瓒论的发展， 管网的优化设计也相应的开展起来。早在5 0 年代初，苏联学者就把古典拉格 朗日条件极值的理论应用到给水管网的技术经济计算中，并巧妙的应用虚流 量的概念，使褥其计冀方法鼗过纛与管阙水力平差一楼，莠最终嚣出经滂管 径的解析表达斌。而欧美一些学者则把管网优化设计描述成非线性规划问题， 邋两结合绘水蓉疆懿特点秘实际寻求这一# 线形簌糍阉霆鹣解法。 线经筑 划的数学模型比较真实、完整地反映了管网优化设计问题的实质，但求解起 来往往缀困难，焉量得羁的鬻誊慧简部激饶解。 很多研究结果表明，对环状管网来说，没有最优的流量分配，也就是说， 在流量未分配的情况下，流量优化分配潮题是一夺酗观鞠阏题，它的最优解 出现在约束区域的边界上。如果对管段餐径、流量没有下限约束，则优化的 缔采是菜些管段的流量等予零，致使环状网变成树状网，从而导致供水的可 靠性大大降低。因此管网的优化设计大多是在流量已分配的情况下进行的。 显然，不同的流量分配就会有不同的优化结果，所以，近年来，许多学者对 流量分配问题做了大量的研究。 1 1 1 国内外给水管网的计算理论i 2 j 从2 0 世纪6 0 年代人们就开始用系统分析方法设计给水管网，并将优化 程序应用于其中。最早的绘水管网设计模型是为树状网设计的，如k a r m e l ie t a i ( 1 9 6 8 ) 、s c h a a k e 和l a i ( 1 9 6 9 ) 。这些模型没有考虑类似阀门的附属物，但 根据水力特性说明了其影响。其它非线性模型在当时也被提出，如s c h a a k e 和 l a i ( 1 9 6 9 ) 。以上这些模型仅用于树状网系统，不能得出比较好的结果。1 9 7 7 年a l p e r o v i t s 和s h a m i r 提出了一个环状网系统模型，其中使用了保证环状网 水力连续性的附加约束条件( 如围绕环的水头损失代数和等于零) 。 自从2 0 世纪7 0 年代以来，大量的管网优化设计技术被相继提出。w a l s k i ( 1 9 8 5 ) 、w a l t e r s ( 1 9 8 8 ) 、以及g o u l t e r ( 1 9 9 2 ) 在他们的论文中进行了详细 的讨论。a l p e r o v i t 和s h a m i r ( 1 9 7 7 ) 应用梯度搜索法得出给水系统中满足最 小总费用的流量形式，用两阶段法设计给水管网，在优化结构中，两阶段法 在模型中的使用代表了管网优化设计模型研究的一个新阶段。在该阶段， r o w e l l 和b a r b e s ( 1 9 8 2 ) 用两阶段法来确定管网布置及管道尺寸。 m o r g a n 和g o u l t e r ( 1 9 8 5 ) 将h a r d y - - g r o s s 网络解算器和优化布置、新 系统的设计及规划系统扩建结合起来。1 9 8 9 年l a n s e y 和m a y s 将一般降阶法 和一个现存的给水模拟模型结合起来优化管网、估计泵站及水箱尺寸，浚法 计算集中，但在优化模型和模拟模型之间需要大量的迭代运算，而且每一步 都要考虑梯度项。1 9 9 4 年e i g e r e ta l 扩充了该法，用广义二元法计算普通优化 解的下限值。 研究给水系统可靠性是必不可少的。l9 8 6 年g o u l e r 和c o a l s 提出了两种 定量法来评估管网可靠性。1 9 8 7 年s u e ta l 将一个稳定可靠的模拟模型与个 优化模型结合起来阐明基于风险性上的管网设计。l a n s e y e ta l ( 1 9 8 9 ) 使用随 机约束模型进行设计，其中包括需水量、水压力以及管道强度系数的不确定 性。 在环状给水管网设计系统中选择优化法进行灵活量化是非常必要的。 h e e k y u n gp a r k 和j o nc l i e r m a n 把个别管道损坏引起的缺水作为测量可靠性 的一种方法，该法与管道损坏频率k 、周期及其严重性相结合。在此基础上他 们研究了改变梯度的线性规划模型，该模型控制管网中的每个管网的缺水不 大于指定的需水量指标。 1 9 9 1 年z i c k 将g e o s q l 及a u t o c a d 合并入给水系统分析器w a d l s o ( w a l s k ie ta 1 1 9 9 0 ) 来给用户提供改变给水管网后影响的瞬息反馈。后来人 们提出了一种典型的决策支持系统w a d s o p ( 给水系统优化程序) ，该系 统为承担给水工程规划设计提供了一种灵活且又价值的工具。 我国给水管溺伉纯设计研究近些年也取得了校大进震。方永忠用生成树 变换法求解输配水系统最短供水路线，船决了多水源输配水系统中有一个以 上节点流量为负值的最短供承路线问题；王浆和、颥国维等编制的h y p n w 和p c a d 软串系统，建立了青岛高科鼓开发因区绘承管网优化设计模型，该 模型属地形起伏大、水源多、分区供水的大型给水管网优化设计模型，并对 羧入、竣出数摆述露特殊处理，建立霪澎菜攀积数据库，绘制水力计算残鬃 图、等压线圈，并且在给定平面图的情况下自动生成纵剖面施工图。 绘承譬嘲系统怒城枣泰政工程基破设戆静主要豁分，楚耨兴城市戴新建 开发区的重要工程项目之一。同时，给水系统投资大，投资偿还期长，有很 大静可鍪穗，透过橇仡设计可疆节省大蕊工程投资。 给水管网是供水系统的重要部分，必须提高其安全可靠性，在规划设计 中进行风险分析，辩串连、并联及复杂的给水环节，需要进行可靠性分析。 利用计算机对管网番管段损坏时的供水影响避 亍程度分析，采用双管供承并 在适当位置加以连通，通过技术经济手段因地制宜的选用适当方式。 为搜绘承罄网优化设计充分反映实际，劳裁广泛镬鼹，必须对给求蛰网 现状进行深入细致的调查，掌握准确的原始资料，并对其进行科学的加工处 璎。管丽雯瑟改遥燕提裹绘末安全哥靠瞧，终 莲瀑东量耧改善管霹东袋鹃重 鞭途径，更新改造的方法爨因地制宜合理使用，可根据资料和技术经济比较， 建立评价管道模式，嗣露檄据经济效益及实舔条件逸择更薪改造的优先颓序。 l 。2 瑗代优化技术口冉7 1 最优化是人们农工程技术、料学研究和经济管理等诸多领域中经常遇到 的问题。铡如结构设计要在满足强度要求等条件下使所用的材料芯重量鼹轻： 资源分配要使锫用户剥用有限资源产生的总效益最大。解决实际生活中优化 问题的乎段大致有以下几种：一是靠经验的积累，凭主观作判断：二魁做试 骏选方案，比较优劣定凌策；三怒建立数学模型，求鳃最谯策晦。虽然出于 建立模型时要作适当简化，可能使结果不一定非常完善，但是它基于客观数 搭，袁孵润憨楚霞、灵活、经济，蠢墨筑模可淤缀大。入们还胃戳啜牧姨经 验得到的规则，用实验来不断校砸建立的模型。随澍数学方法和计算机技术 懿进步，瘸建篌帮数佳模按解决往纯海遂这手段，穗会越来越嚣示盘它的 效能和威力。显然，在决策定量化、科举化的呼声嘲益高涨的今天，优化方 法的攥广应掰是符含时代潮流和形势发聪需要的。p 随麓2 0 世纪8 0 年代初期禁忌搜索、模拟退火、遗传熨法和人工神经网 络算法薄优化簿法的兴起，人们对这些算法的模型、理论和应用技术等一系 列问题进行了深入的鼹究，并将这些算法称为现代优化算法。现代优化算法 的主要应用对象是优化问题中的难解问题。 1 2 1 禁忌搜索算法 禁忌搜索算法是局部邻域搜索算法的推广，是人工智能在组合优化算法 中数袋功应瘸，g l o v e r 在1 9 8 6 年首次提出这一概念，遂瑟形残一套完整算法。 禁忌搜索算法的特点是采用了禁忌技术。所谓禁忌技术就是禁止重复前面的 工终。为了隧运焉帮邻域援索陷入屡帮最饶鼢主要不足，禁忌攘索翼法嗣一 个禁总衷记录下已经到达过的局部最伐解，在下一次搜索中，利用禁思表中 的信息不再戴有选择静搜索这些点，戳既来懿出曷酃最恍点。 l ，2 ，2 摸掇退火算法 模拟退火算法是局部邻域搜索算法的扩展。它不同子局部邻域搜索算法 之出怒它以定的概率选择邻域中费嗣值大的状态。理论上来说，它是个 全局最优算法。模拟退火算法最早的愚想是啦m e t r o p o l i s 在1 9 5 3 年提出， k i r k p a t r i c k 在1 9 8 3 年成功地应用在组合最优化问题中。 1 2 3 入工神经两络算法 天王穆经霹终斡早麓王 睾可以遑臻至1 9 4 3 年m c c u l l o c h 帮p i t t c 建立斡第 一个模型，靥被扩展为认识模型。认识模型的第一个功效可以用来解决简单 静分类闯题。2 0 爱= 纪8 0 年代，h o p f i e l d 将入工静经溺络成功静应用在组合 优化问题中。人工神经网络的模型要求发展神经网络型计算系统来替代传统 的计算视。这种 嘻# 系统不再怒传统计算梳顺序执行命令的运行过程，而怒 希望对输入系统进程平 亍处理：这种计算系统不再是只包含一个或几个复杂 的计算设备，而是由众多简单设备有机组合在一起；这种计算系统处理信息 时，不要是将信息存继在一个糕确的饺霆， 嚣是逶过毒孛经愿的内部提涟关系 达到信息存储的目的。 1 2 4 遗传葬弦 遗传算法是基予鑫然迷撵耪遗传撬剿，袭诗算梳上模数生物进纯辍刳懿 寻优搜索算法，它把搜索空间( 解空间) 映射为遗传空间( 即将可行解编码 为个商量染色藩) ，n 个染色体鞫戚一个群体p ，并按颈定翡添数( 适合发 函数) 对每个染色体进行评价，根据“适者生存”的原则保存优者，淘汰劣 者，筏群体逐步收敛于最优解。本文的研究对象帮为遗传箨法。 1 , 3 选惩戆嚣戆器淘窖 l 。3 1 选题的目的 城市给水管网优化设计中的变量是离散的标准管径，故相应的目标函数 瑟费，甏函数毪为离散的函数。良往豹优纯方法大多采蠲控格翡毯法，甄将管 径看作连续的变量，相应的目标函数也为连续函数，然后采用偏导数的方法 4 取极值。由于这种方法不能保证所得管径为标准管径，最后必须列管径进行 处理，但这样做必熬会影响经济霸标函数。 近年来，随着最优化理论和计算枫的发展，已经有越来越多的耨方法应 用于各个工程领域，在电力、交通、机械、能源等领域有了很成功的应用。 霹黠，绘零管霹夔谯忧设计选嚣戆运爱这些瑟数算法，荠黢示了较好懿效暴， 但同时也暴露出不少缺点。 本文静鏊懿在予对此遴行搽喜薯，主要磅究将遗传算法零| 入城市管蠲优化 遮一课题中，并针对标准遗传算法应用于给水管网优化时出现的问题进行分 弄，撵密解决方案。丽露穗希望褥虱大家的指点。 l 。3 。2 零文熬掰究工传 本文以黄山市给水管网优化设计为研究背景，威用改进的遗传算滋对不 同参戮条件下的优化结采进行分析和研究，得出遗传算法在应用于给水管网 优化计算时主要运行参数的取值。 ( 1 ) 如何将遗传算法应用到城市给水管网设计中，进行新建管网的优化设计。 f 2 ) 应用标准遗传算法进行管网优化设计，解决算法实现的一系列技术问题， 主要包旗：染色钵熬编玛方式、逶应度蘧数懿构造、嚣钵援模数大小、耱嚣 的产生、选择算子、遗传变异方式、交换方式、罚函数的选择等。 ( 3 ) 分析遗传算法的运算过程，对其主簧参数所起的作用避行分析，并针对标 准遗传算法的缺点，提出解决方察，加以改进。 ( 4 ) 对提出的方案进行验证。 5 第二章管网优拖设计的数学摸垒 2 1 绘水管网的设计层标l 对于给水管网优化这样一个复杂的问题，由于包含了太多的变量，故难 以仅孺数学方法来绉述。邋年来，淹着数学规翔、计算技术、系统工稔等其 它学科的引入，给水管网优化这课题得到了迅速的发展，给水管网的优化 设计，应考虑到4 个方面，即保证供水所需的水量和水压、水质安全、可靠 憾和经济性。管网技术经游计算就是以经济性为目标函数，两姆其余的馋为 约束条件，掇此建立目标函数和约束条件的表达式，以求出最优管径或水头 损失。瞧于水矮安全牲不容易定爨的进行评价，正攀时帮撰坏霹耀水鬓会发 生变化，二级泵房的运行和流量分配等有不同方案，所有这些因素都难以用 数学式表达，嚣l 龟警鼹技零经济计算主要是瓷考意备释设计鑫栋静兹鬟下， 求出一定设计年限内，管网建造费用和管理费用之和为最小时的管段直径或 承头损失，也就是求鑫经济管径躐羟济承头损失。l l l 管网问题是很复杂的，管网布置、调节水池容积、泵站工作情况等都会 影晌技术经济指标。在进行技术经济计算之前，事先必须完成下剐工作：确 定水源位置，完成管网东鬟。拟定泵站工作方案，选择控制点所霈的最小服 务水头。 绘水管潮设诗懿一般激慰是：在警耀毒髯己定，保证供瘩量秘末压懿裁 提下，计算求得年折算费用值最小情况下的管径。 2 2 给水管两优化设计的数学模型 蠛赘绘永管溺我诧设诗中，一般按最高辩溺承量遴行管阏援拳经济计算。 城市设计用水量主要是居住区生活用水和由城市给水系统供给的工业生产用 零稻职互生活糟水，还应考虑全市往静公共建筑璃水、浇洒道路和大面积绿 化用水及消防时的用水。 管潮建造费用中主要怒管刚豹费用，包括水管费用和绝沟埋管等施工费 用。出于泵站、水塔、水池豚占费用很小，一般忽赡不计。 目前在管网技术经济计算时，常先避行流凝分配，然后采用优化的方法， 笃出以浚量、管径表示故费震遗数，鞋褥最傀瓣。 2 2 1 目标函数 管网年费用折算值是按年计的管网建造费用和管理费用，它是管阉技术 缀济诗舞时熬瓣蠡番数，霹震下式表示： 吲志1 f ) 域a ) l y + 0 0 t x8 7 6 - 触掣 1 ) 6 式中符号意义如下： a ，b a 单位长度管线造价公式中的系数和指数，随水管材料和当地旎工 条件丽异； d “一一管径，m ； e 邀费，分k w h ； q 一一输入管网的总流量，l s ： | 。二缀采菇扬程，m ； n 一一泵站效率，一般为o 5 5 0 8 5 ，水泵功率小的泵站，效率较低； p 一一每年指除懿褥 西费稻大穆爨，越篱丽造价兹计； l i j 镣段长度，m ； 蛳管段瀛璧，l s t 投资偿还期， 8 一一供水能量变化系数。中型城市可参照：网前水塔管网的输水管或无水 塔的管阚为0 。l o 4 ；霹浆水塔的承管为0 。5 o 。7 5 ： p 一一水的密度，p = 1 k g l ； g 耋力热遽凄，g = 9 。8 1 m j s 2 ； h o 水泵静扬程。m ； h i 。一一藏瞽两超点爨控制点静经条篱线静承头损失总和，m 。 将式( 2 1 ) 简化，只取其变量部分，得年费用折算值或目标函数如下； ：k 半1 蟛n p 匹( 2 - 2 ) 式中p = 8 7 6be pg r l ，q = i l s ，h p = l m 时的每年电费( 分) 。 2 2 2 约束条件： ( 1 ) 节点连续方程 盆+ 譬，= o 0 2 i ，2 ， ( 2 - 3 ) 式中：q 为管段流鼙，m 为与节点j 相连的管段数： 锚为节患滚鬟，n 受繁点数： ( 2 ) 环能量方程 ( h i i ) 1 。0 式中：h 。，为管段水头损失( m ) ， i 为环号，1 为环数： ( 3 ) 节点自由水压约康 h h m m f l = l ，2 ，l ) i ，j 为节点号； 7 ( 2 4 ) ( 2 - 5 ) 式中：h 为节点i 的自由水压： r 为节点i 允许的最小自由水压 ( ) 对管线隧起楚青纂受压力约窳： h j o ( 2 - 6 ) 对簪拣函数w 送行稷餐分耩可知，当流量分配已知时，可以谣明管径的优 化设计是凸规划课题，有唯一的最优解，即目标函数w 存在极小值。目前绘 承管两优纯设计大多是以式( 2 一i ) ( 2 - 6 ) 为基础，采用各种数学方法进行管 网优化计算柬求出经济管经。 8 第三章绘水管鼹优亿计算 3 1 拳头损失计算 绘水管嘲任一管段鼹端节点的水压和管段水头损失之涮有下列关系： h j h j = h q 0 3 - 1 1 式中h 。h j 一驭莱一基准面算超的管段起端i 和终点j 的水压，m ； h 。一管段的水头损失，r f l 。 在箭网计算中，主要考虑沿管线长度的水头损失。配件和附件如弯管、 灏壤譬萋爨阕f l 等懿翳龆承头损失，匿i i 漤线长发螅拳头损失掇魄校夸，通誊 忽略不计，产生的误差很小。 壤撂均匀漉凌逮公式： v = c q r ： 鼓；= 岳= 函2 9 专= 孬8 9 蓦= 考王2 9 p ：， 式中v 一一鹫农的平均滚逮： c 一一谢才系数： 爻水管鹳水力半径( 鬣管为索= 等) i 一一单位管段长度约表头损失，残承力坡度4 d 一一水管内径； , k - - - - 隧力系数( 五：警) ： g 羹力攘速度。 式( 3 - 2 ) 用流量q 表示时为： ；考彘2 参8 9 茄。而6 4 弘明2 ( 3 - 3 ) 式中群茹i 而6 4 为院疆e 水头损失公式一般表示为： 冉= 肼告= 嘶”= s q “ ( 3 - 4 ) 式中k ，r l ，m 常数和指数； i 管段长度； 9 s 水管摩阻。 目前国内外使嗣较为广泛的些水头损失公式介绍如下，其中，舍维列 夫和巴甫洛夫斯基公式为幽内常用，海磐一一威廉和柯尔勃洛克公式在疆方 国家应用较多。 ( 1 ) 舍维列夫公式 适用于旧铸铁管和旧铜管，水温l o ”c 时 f _ 0 0 0 1 0 7 乓 d 1 3 ( 3 5 ) 0 0 0 9 1 2 毒l + 半) 0 3 v l 触 ( 3 1 6 ) 式中v 一一流速，m so d 一水管的计算内径，m 。 ( 2 ) 巴甫洛夫鬏基公式 适用于混凝土管、钢筋混凝土管和渠道的水头损失计算。 式( 3 3 ) 中戆湔君系数c 篷必： c = 二剧( m “2 s ) f 3 7 ) 式中巴甫洛夫斯基公式的指数y 等于： y = 2 ，5 4 n 一0 。1 3 一o 7 5 x ( 4 n o 。1 0 ) x 露( 3 8 ) n 一警壁糨糙系数，混凝蛰秘锶簸混凝管般妥妫o ，0 1 3 0 0 1 4 ： r 水力半径。 对子漫凝管瑟钢麓滢凝土绘求管，当n x = ( x i ，x 2 ，x n ) ( 4 _ i ) 把每一个x 看作个遗传基因，它的所有可能取值称为等位基因，这样 2 0 x 就可看作是由n 个遗传基因所组成的一个染色体。一般情况下，染色体的长 度n 楚函定豹，毽对一些润题r l 瞧可以是交纯静。遗传算法中，决策交量x 组成了问题的解空间。生物的进化是以集团为主体的。与此相对应，遗传算 法静运算对象是由m 个个体组成的集合，称为群体。与生物一代一代的自然 进化过程相类似，遗传算法的运算过程也是一个反复迭代过程，第t 代群体记 馓p ( t ) ，经过一代遗传和邋化后，得到第t + l 代群体，它们也是由多个个体组 成的集合，记做p ( t + 1 ) 。这个群体不断的经过遗传琴强进化操作，共且每次都按 照优胜劣汰的规则将适应魔较高的个体厘多的遗传到下一代，这样最终在群 体中将会褥到一个锐良的令体x ，宅所对应的表现型x 将达到或接近予润题 的最优解x 。u 4 2 0 j 生物的进化过程主要是通过染色体之间的交叉和染色体的变异来完成 的。与此相对应，遗传算法中最忧解的搜素过程也模镑，土物的进化过程，蠖 用遗传算子作用于群体p ( t 1 中，进行下述遗传操作，从而得到新- - 4 2 群体 p ( t + 1 ) e 4 + 2 遗传算法的运行过程及对主要参数醺熊的分析 自然界中通过基因机制，一系列具有智能、自组织、自修整的器官在不 断产生衣进诧羞。遗传算法就是这样一类利用自然选择帮群体逶传机制在高 维空间寻优的方法，它不一定能寻得最优点，但是它可以找到更优点。因此， 遗传算法可鼗会哲对停留在某些非最优点上，直到变异发生使它迁移到另一 更优点上。遗传算法的整体行为是复杂的，但它的运行过程较为麓单。遗传 算法随编码方式、遗传算予操作的不同丽表现为不同形式，因此难以从形式 上给以明确定义，它的识别标志在于它是否具有模拟生物的自然选择秘群体 遗传机理这一内在特征。遗传算法将要优化的问题转化为某个适应值函数的 极大化阏题，标准遗传算法使用弱定长度螅二遴刳棼号串对令俸避嚣编码， 初始群体中各个个体的值使用均匀分布的随机数来产生，并按个体适应度大 小来决庭当藜群体中每个令体遗铸到下一 弋群俸中豹撬会中蛇多少，然螽复 复进行选择、交叉和变异等遗传算子操作，直到满足停止条件为止。 2 0 - 2 3 4 2 1 编码 在遗传算法中，优化闯题的所有参数( 或者称为决策变量) 郄被编码， 形成一个有限长的字符串，称之为染色体或个体。每个个体都对成于优化问 题的一个可行解。组个体组成一代种群，它描述了遗传算法的搜索空间。 标准遗传算法用二进制串来模拟染色体，用数量极大的数字串表示优化闽题 可行域内的试探解。编码怒应用遗传算法时要解决的首要问题。常用的编码 方法奄二进铡缡玛、浮点数编码、铤号缡码、巍然数编码等。 2 1 遗传算法的操作对象怒数字审，而不是优化问题的解形式，这为遗传算 法成为种通用的优化方法奠定了基础。遗传算法从某一点开始寻优，若一 个小的变动能改善解褥质量，则浍该方向继续搜索，否则向其它方向搜索。 但是若问题较复杂，则解空间也余随之增大，搜索效率随之下降。 当逡择繁咯确定箱彩确遗传算法浚敛往静主要函豢是杂交和变舜算子。杂交 和变异算子对于遗传算法收敛性的影响在编码方式确定后邋过杂交率和变异率 采体现。杂交率的高低将决定解群体的更新和搜索速度的快馒。p 。太大会使 离适应值的结构很快被破坏掉，若p c 太小搜索会停止不前。变异率对于保持 解群体结构多样性，防止过早收敛是一种重要手段。p 。太小时不会产生新的基 因块，p m 太大又会使遗传爨洼变成随机搜索，肤瑟失去其线嶷特惶。由此霉知 杂交率和变异率对于遗传算法的收敛性有蘑要影响。另一方面，只要分析一下杂 交算子耱变异算子豹结梅毒翅：在不嚣编竭方式下杂交酾交雾算子蕊结构笺杂程 度不同，进行杂交和变异的方法不同，进行杂交和变异后对于适应度值的影响程 浚不磊。出魏可鞋撵凝，采鲻不嗣的编码方式执于亍杂交帮变异操作鹾对于遗传算 法收敛性能的影响不同。编码方式影响遗传算子的结构、操作及性熊，而遗传算 予静结构、操作及往能又直攘影响遗传算法的收敛往和收敛逮度。因此不同的编 码方式，对于遗传算法的收敛性和收敛速发有着重大影响。事实上，人们在实践 中已经发现采用二进制编码方式的遗传算法缺乏微调功能，对于复杂问题或高维 阅题由于个体串长过大使闷题无法诗算以及收敛蓬旱等问题。为了鼹决上述缺陷 人们己对编码技术进行了一系列的改进，如为使算法县有微调功能采用动态编 码，为了镬算法能蠲来解决笈杂或褰维问惩采用实数编码。睇+ ” 4 2 2 初始种群的产生 遗传算法是对群体进行的进化操作，需要给其准备一些表示起始搜索点 豹窃始瓣体数攥，熬螽壹它 f j 亲垒成后幸。一般都采霜缱秘法尘裁拐始群体， 也可以自己设定初始群体。群体规模的大小和遗传算法中选择操作密切糨关。 群体藏模越大，遗传操 笮掰处理的模式就越多，群体的多祥性就越好，越容 易出现好的结果。但是。隧着群体规模的增大，计算量会迅速增大。另方 面，若群体规模太小，会造成遗传算法搜索空间狭窄，群体还未成熟搜索却 已停止，引起“早熟”收敛现象。通常在遗传算法的运褥过程中t 群体娥模 保持不变，为保持群体多样性，群体规模较大。 4 2 。3 适合度 适合度是毽掭豳数毽经过一定戆修改爱俸为个谚对巧境酶适应能力。适 合度是判别个体优劣的标准，故它必须能够进行比较。适合度值总是非负的， 露且总怒越大越好。在具体鹤计葵中，遥应度灞数l 搀设诗癸结合求勰麓趣事 身的要求而定。 2 2 4 2 4 评价 先将个体解码，把被编码的参数还原成实际管径，然后进行管网平差， 憋乎羞结果代入基橼运数，可睾卡葵塞管潮费瓣，稷掇费用溺数诗算出适合瘦， 弭通过选择将适合度高的个体保存下来，组成新的种群，摄后再利用交换、 变异等手段使这些溪熬狰群酶挠楚褥瞧得班遗传帮保留到下一代。如诧“选 择交换变异褥选择”的不断重复，使备代种群的优良基因成分 逐渐积蔡，静群的平均适合度和最饶个体适合度不断上升，矗到迭代过程趋 于收敛。 4 2 5 选择运算 选择运算( 或称为复制运算) 把当前群体中适成度较高的个体按某种规 则或模型遗传到下一代群体中。一般要求适应度较高鲍个体壤有更多蛉规会 遗传到下一代群体中。群体中选择优秀的个体，淘汰劣质的个体。选择的目 款是把傥饯爱携个体( 或熬) 壹接遗传裂下一代或透过配瓣交叉产生赣戆令 体再遗传到下一代。选择的标准就是各个体的适应度值大小，个体的适应度 壤越嘉，它羧选中懿概率熬大。秘翦邃传算浚中最鬻矮豹选择髯予是院翻复 制法。 3 0 】 4 2 6 交叉运算 交叉运算怒遗传箨法孛产生新个体的主要操作过筏。在标准遗传算法中，它 以某一概率相曩交换綮两个个体之间的部分染色体。把甄个父代个体的部分结构 加以替换重组而生成新个体。通过交叉，可以大大提高遗传算法的搜索能力，交 叉翼予农遗传冀法中起惹核心的传思。 4 2 6 1 交叉算予的作用 交叉运算怒遗传算法区别于其它进化算法的个重瑟特征，在遗传算法中起 关键终耀，是产生囊令葵的疑主要方法，它壹接影嚷蓉算法懿最终实瑷积攥链， 在一定稳度上决定着遗传算法的发展前景。遗传算法模拟自然界优胜寓汰的生物 遴纯撬澍。其选择、交叉囊交异算孑分裂对应于螽然赛中饶薤劣汰静生存竞争季亍 为、有性繁殖以及遗传性状变异现象，特别是早期基于二进制编码的遗传算法更 燕对这黧生命蠛蒙在分子生物学永平上癣释酶一耱壹接映射。正确理耱选择、交 叉和变异算子教遗传算法中的作用，对设计高效遗传算法有着重要的指导意义。 选择算子是引警遗传算法走向全局鬣优解的关键，它让适应度商的个体以较大的 概率参与生成下一代的遗传操作，从丽淘汰适应发低的不良个体，使嚣体自搜索 空间更优的解鹾域移动。变异算子怒一种无方向随机搜索，它可以起到保持群体 多样性，防止擞现末成熟收敛褒象，及增趣局部搜素能力的l 乍爆。 3 t 3 3 1 遗传算法中，交叉算子因其全局搜索能力而作为主要算子，变异辣子因其局 2 3 部搜索能力而作为辅助算予。遗传舆法通过交叉秘变募这一对相互醚台又蝴互竞 争的操作而使其具备兼顾全局和局部的均衡搜索能力，这也是使遗传算法获得良 好收敛性熊的藩提条牛。实际上，交叉运箨是遗传算法区裂予其它逡位葵法粒根 本所在，在遗传算法中起关键作用，是产生新个体的最主要方法，它决定了遗传 舞法的全局搜索能力。但爨选择程交叉佟瘸后保器了逶应度蠢筑令体，便会产生 封闭竞争，导致“近亲繁殖”，从而引起“早熟”现象。变异操作可增加新的搜 索空闻，改善遗传算法蛉蜀豁搜索靛力，维撩群体的多样往，防丘蹬现“荦熟” 现象，但会降低收敛速度。因此在对遗传算法的实际应用过稷中，必须使交叉算 予藕变异算子紧密结合，共问完成对全局和局部的搜索，这也是使遗传算法获得 良好收敛性能的前提条件。p 4 3 1 4 2 6 2 交叉算子的方式 杂交算予一般随编码方式的不同而不同。标准遗传算法只采用一点杂交算 予。杂交操 乍方式与编码方式毒关，采用不目的缠码方式提应的杂交搡 乍也不屈。 在二进制编码方式下是点式杂交。进行一次杂交操作后所得子代改变了父代串的 菜些基雕，于是父 弋个体鼹疲豹逶疲值与予代令体对应的适应值不弱。从寻饶的 角度看，第k 代个体通过杂交变为k + 1 代个体时存在盲目性，故杂交虽然能产生 耘煞个体，毽不能保证子代令体一定院父代好，也就是说这耱全局搜索存在膏蟊 性。这种盲目搜索对于遗传算法的收敛性及收敛速度显然有重要影响。采用自然 数编码对煮算术杂交和离敬杂交。这类杂交本质上是修改父代的某些分量丽得到 予代，这样一米可以根据当前结果通过杂交有目的的修改某些分量，使子代比父 代优越。因此这类杂交可以沿着有利于算法收敛的方向进行，结果将导致遗传算 法收敛性能的改善、收敛速度的提高。1 3 8 1 杂交操作是把两个父代个体的部分结构加以交换重组生成新个体的操作。杂 交撩终鸯奄鼙的建麓了在下一代产生新静个体。杂交操作酌西翡跫饺遗传算法其有 全局搜索功能。杂交算子常采用点式杂交。点式杂交又分为单点式、多点式翮均 匀式杂交。 ( 1 ) 荤点式杂交是摆在甄个父 弋串中随机懿曩选取一| 拿杂交点，然后交换其对应予 串。 父代串l 011 1lo0予代串1 01011 10 父代串2 0 0 0 ll0予代串20 0 l 1 l0o f图4 1 单点式杂交示意图 f 2 ) 两点式杂交是随机选取两个杂交位置，使两个父代串在选取的两个杂交位置 之间的对应位相互交换，得予代串。采用两点式杂交可以将嬲个赢遁应性模式 结合在一个子代串中。多点杂交就照两点杂交的推广。 2 4 父代串1 1 l01101 父代串2 0 010l 1 1 子代串1 il 10101 子代串2 000l101 lf 图4 2 嬲点式杂交示意图 ( 3 ) 均匀杂交是通过设置模块来决定子代的基因如何继承父代个体中相应熬因。 竣蠢戆接头与父代事矮有胡同豹长疫，其中0 表示不交换，l 表示交换。撒据模 块对两个父代串进行杂交产生子代。 父代串l 00l0j】010ll0予代串101l l0l 父代串2 0l l10 0模块 + 予代串20 0l010 图4 0 均匀杂交示意图 4 2 6 3 交叉算子的设计弘9 4 。 交叉箨予豹设计通常应键括两个方面的内容，邵如何确定交叉点的位置和如 何进行部分基因交换。交叉算子的设计一般与所求解的具体问愿有关，但无论设 计何种交叉算予均应满足其评估准则，即让前一代中优秀的性状能在后一代的新 个体中尽可能得到遗传和继承。交叉算予设计和编码设计也需协调操l 莹。对卷用 的二迸制编码而言，成从由选择操作形成的配对库中，对个体随机配对并按预先 设定的交叉摄率寒决定每对是否霰瑟进行交叉操 睾，鄹时设定配对令体的交叉 点。交叉算子的设计和实现与所研究的问题密切相关，般要求它既不要太多的 破j ；l = 个体编码审中表示优良校状的模式，又要能够有效的产生出一些较好的凝个 体模式。单点交叉是常用的交叉算予。在实际应用中，研究者往往以单点交叉为 出发点对葵经能进行研究，艇很多情况下其它交叉方法的往嚣t 优于单点交叉算 子。 交叉概率p c 的大小也直接影响着遗传算法的性能，较大的交叉概率可增强 逮传算法秀舞颞瓣援索区域静能力，餐毫秣赣豹模式遭舞破坏鹃霹辘毪增大；若 交叉概率太低，遗传算法搜索可能陷入迟钝状态。因而，鼓计合适的交叉概率是 算法获褥蘸驽佼能静条件之一。一般建议酌p c 敬值范围是o 5 o 9 9 之闯。 4 。2 。7 变异运算 变异的目的有两个方面：提高遗传算法的局部搜索能力：维持群体的多样性， 防止早熟。变异算子使个体的基因竣一定的概率发生变化，它是扩大遗传算法搜 索区域的一种重要手段。变异概率过大将g 起遗传算法的振荡，过小则影嚷冬进 化迭代搜索区域的范围。变异算子主要模拟生物个体的随机变异现象。对个体串 的某些基照位的健进行髓枫改变，冀俸用楚增强遗传算法运行中群体憨多样蠖， 是对有效基因缺失韵一种补救措施。同时也对因选择操作失去的多样牲的恢复具 毒漤在鳇馋，霹l ，是实瑗遮转雾法全弱爨纯瞧憝戆耋要算予之一。出于变异算予在 标准遗传算子中只是以很小的变异概率p 。对个体串进行运算，所以变异算予在 2 5 标准遗传算法中的作用远不如杂交算子。变异算予一般随编码方式的不同而不 嗣。对二进翩编筠，变异算予可取一点变舜( 个体每次变异只有一个二迸铡值的 德发生改变) 、两点变异( 个体每次变异有两个随机选取的二进制位的值发生改 变) 、多点交辩、均匀变异( 以菜概率随机选取个体审中每一位置谶行变舜) 。 变异算予其功能就是以很小的概率p 。随机地改变群体中个体的某些基因。变异 搽作是一种局部随机搜索。它与选择策略，杂交算子结合应用就能避免由于选择 策略和杂交操作两使某些售息永久挞丢失，从藤保证遗传算法躯有效性。交买擐 作也是保持群体多样性，防止出现算法“早熟”的重要手段。 在标准遗倦算法中，变羿一般被看作为辅韵算法。它作蠲在染色体上，以较 小的概率p m 随机的改变染色体上的每个慕因。在通常的二进制编码方式下，变 辩算子只是简单的将蒸因值取反，即“0 “变为”1 “，或者”1 “变为”0 “。在 实际操佟中，每次要辩染色体上的纂困位i 生成一个p ，l 】闻她随掇数r ；：船栗 r i p 。( 变异可发生的概率) ，变异位的基因将被新的基因所代替，否则第i 位的 基因缳簿不变。变异缓率p 。魏篷一般