（水力学及河流动力学专业论文）改进蚁群算法和改进混合遗传算法在给水管网优化中的应用.pdf

改进蚁群算法和改进混合遗传算法在给水管网优化中的应用 摘要 城市供水管网是城市供水系统中重要的一环，它不仅是连接供水处理厂与 用户的“桥梁”，而且投资占整个供水系统的5 0 8 0 ，同时也占用供水系统 3 0 5 0 的能耗。随着水资源日益紧缺和水资源开发利用率的提高，新系统的 兴建和老系统的改扩建等所需的工程投入逐渐增大。因此，供水管网的规划、 设计和运行管理是否科学、经济、实用，直接影响工程的投资、运行管理费用 及系统的可靠性。因此，进行给水管网优化具有重要作用和意义。 本文应用改进蚁群算法，把其运用到给水树状管网的优化布置，可实现节 省投资、合理布局的目的，为给水管网的优化设计和给水管网优化调度提供了 前提条件，并用一个算例进行验证，可预计蚁群算法在此方面将有广阔的应用 前景。 在计算管网优化设计之前，需要进行管网水力计算以求解管段流量和节点 压力，本文选用了性能较好的水力模拟软件e p a n e t 进行计算。在进行经济性 计算之前必须知道经济性参数的取值，本文通过m a t l a b 编写程序进行最小 二乘法拟合。 通过对已有管网优化设计数学模型进行分析，提出了以经济性和可靠性为 目标函数的多目标优化数学模型。建模过程中，将系统可靠性定义为“节点富 余水头加权平均值”和“管网恢复力”，使对管网系统可靠性对评价更加直观和 定量化；同时将管网年费用作为经济性衡量指标 针对该优化数学模型为离散变量组合优化的实质，将改进遗传算法和水力 模拟软件e p a n e t 结合使用，形成“改进混合遗传算法”用于复杂给水管网的 优化设计计算，并编写了相应优化计算程序。最后，以一个具有典型代表性的 管网优化设计工程案例对该优化模型和改进混合遗传算法的理论、方法进行验 证，并将计算结果与常规设计方法得到的结果进行经济、水力性能和可靠性比 较，充分说明了改进混合遗传算法在给水管网设计中具有重要的理论和实用价 值。 关键词：改进蚁群算法；给水管网优化：多目标优化数学模型：管网系统可靠 性；改进混合遗传算法 t h ea p p l i c a t i o no fi m p r o v e da n tc o l o n ya l g o r i t h m sa n d i m p r o v e dh y b r i dg e n e t i ca l g o r i t h m so nt h eo p t i m i z a t i o no f w a t e rd i s t r i b u t i o ns y s t e m a b s t r a c t w a t e rd i s t r i b u t i o ns y s t e m ( w d s ) i s 锄i m p o r t a n tp a r to fu r b a nw a t e r s u p p l y s y s t e m ，w h i c hi sn o to n l yab r i d g el i n k i n gw a t e rt r e a t m e n tp l a n tw i t hc u s t o m e r , b u ta l s o a c c o u n t sf o r5 0 8 0p e r c e n to ft o t a li n v e s t m e n ta n d3 0 - - - 5 0p e r c e n to fe n e r g yc o n s u m p t i o i l o ft h et o t a lw a t e rs u p p l ys y s t e mb u d g e t t h ei n v e s t m e n ti nr e h a b i l i t a t i o ni sg r o w i n gw i t h t h ed e v e l o p m e n to fw a t e ru s e t h er a t o n a l i t yo fn e t w o r kp r o g r a m m i n g ，d e s i g na n d o p e r a t i n gc a na f f e c tt h ei n v e s t m e n ta n dr e l i a b i l i t yo fw a t e rs u p p l ys y s t e m t h e r e f o r e , i ti s v e r yi m p o r t a n ta n ds i g n i f i c a n tt 0m a k eo p t i m i z a t i o nf o rt h ew d s t h i sa r t i c l eu s ei m p r o v e da n tc o l o n ya l g o r i t h m sf o ro p t i m a ll a y o u tt ot h e 吮w a t e r - p i p e n e t w o r k , i tc a r ls a v em v e s l j n e ma n dl a y o i l ti nr e o n , a f f o r dp r e c o n d i t i o nf o rt h eo p t i m a ld e s i g na n d o p t i m a la t t e m p e ro fw a t e rd i s t r i b u t i o ns y s t e m , t h e nt 咖, h ta ne x a m p l et ov a l i d a t e , t h e r ei s av e r yw i d ea p p f i c a t i o ni no p t i m i z a t i o no f w a t e rd i s t r i b u t i o ns y s t e m i no r d e rt og e tp i p ef l o wa n dn o d ep r e s s u r e i ti sn e c e s s a r yt oh a v eh y d r a u l i ca n a l y s i s b e f o r et h eo p t i m a ld e s i g n , t h i sa r t i c l ec h o o s ee p a n e t ( ah y d r a u l i cs i m u l a t i o ns o f t w a r e ) t o c a l c u l a t e a n dt h ee c o n o m y p a 姗c t e rm u s to r d e rb e f o r ee c o n o m yc a l c u l a t i o n , t h i sa r t i c l eu s e t h el e a s ts q u a r em e t h o dt 0s i m u l a t eb ym a t l a b b ya n a l y z i n gt h ee x i s t e do p t i m a lm o d eo fd e s i g nt ow d s t h ea u t h o rp r e s e n t sa m u l t i - o b j e c t i v em o d e lb a s e do ne c o n o m ya n dr e l i a b i l i t y i nt h ep r o c e s so fs e t t i n gu pt h e m o d e l t h er e l i a b i l i t yo fw d si sd e f i n e d 罄 w e i g h t e dm e a no fn o d a le x t r ap r e s s u r e a n d i p en e t w o r kr e s i l i e n c e ”，w h i c hw i l lm a k ei te a s ya n dd i r e c tt oe v a l u a t et h er e l i a b i l i t yo f w d s ：a tt h es a n l et i m e , t h ea n n u a lc o s ti sl o o k e d 笛t h ee c o n o m i c a lc h a r a c t e r i s t i co f w d s a i m i n ga t m o d e l se s s e n c eo fc o m b i n a t i o n a lo p t i m i z a t i o n 稍md i s c r e t ev a r i a b l e c o m b i n ei m p r o v e dg e n e t i ca l g o r i t h mw i t l le p a n e tt of o r mi m p r o v e dh y b r i dg e n e t i c a l g o r i t h m s ( i h g a ) ，a n dw h i c hi su s e dt ot h ec a l c u l a t i o no fo p t i m a ld e s i g nf o rc o m p l i c a t e d w d s a tt h es a r f l et i m e ，t h ec o r r e s p o n d i n gp r o g r a m m ec o d ei sm a d et o o l a s t l y , at y p i c a l e x a m p l ei su s e dt op r o v et h ep r a c t i c a l i t ya n dv a l i d i t yo ft h eo p t i m a lm o d e la n di h g a ， w h e nc o m p a r et ot h et r a d i t i o n a ld e s i g nm e t h o d ，t h er e s u l ts h o w st h a tt h ei h g ah a v eg r e a t m e a n i n g a n dv a l u eb o t hi nt h e o r ya n di np r a c t i c e k e yw o r d s ：i m p r o v e da n tc o l o n ya l g o r i t h m s ；o p t i m i z a t i o no fw a t e rd i s t r i b u t i o ns y s t e m ； m u l t i - o b j e c t i v eo p t i m a lm o d e l ；r e l i a b i l i t yo fw a t e rd i s t r i b u t i o ns y s t e m ；i m p r o v e dh y b r i d g e n e t i ca l g o r i t h m s 表格清单 表3 ，l 管道价格2 7 表3 2 不同算法所得最优化方案比较2 8 表4 1 单位长管道造价表3 8 表5 1 钢筋混凝土管单位长度造价( 元米) 一4 9 表5 ，2 不同管材管线的海曾一威廉公式的c 值5 0 表5 3 改进混合遗传优化设计与传统设计方法节点水压比较5 l 表5 4 改进混合遗传优化设计与传统设计方法费用比较5 l 表5 。5 改进混合遗传优化设计与传统设计方法系统可靠性比较5 2 图2 ，1 图2 2 图2 3 图2 4 图2 5 图3 1 图3 2 图3 。3 图3 4 图3 5 图3 6 图3 7 图3 8 图4 1 图4 2 图4 3 图4 4 图4 5 图4 6 图4 7 图5 1 图5 2 图5 3 图5 4 插图清单 自然界中的蚂蚁觅食模拟1 0 基本蚁群算法的逻辑结构1 l 蚁群算法实现流程图1 2 遗传算法基本运算流程图一1 6 二进制单点交叉基本原理示意图1 8 简单的网络图2 6 最小生成树图2 6 管网初步连接图2 6 总长度最短管网优化布置方案2 7 k r u s k a l 算法优化布置方案。2 8 d 目k s 妇算法优化布置方案。2 8 s p o a 算法优化布置方案2 8 a c a 算法优化布置方案2 8 可靠性与费用关系图3 2 m a t l a b 运行效果图3 9 已知数据点连接成的曲线图3 9 拟合曲线图：3 9 算例管网水力分析计算4 l 节点计算结果 管段计算结果 管网优化设计的改进混合遗传算法流程图4 4 交叉算子示意图4 8 某城镇的给水管网图4 9 两种设计方法下各节点自由水头值分布折线图5 2 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕 士学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 主席： 导师： 剀磁孑从压 密绦蛹啦互向 毒王 删匆 岛 峰躲 3 鼍乳了呷 委 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果 也不包含为获得金胆互些走堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所做的任何贡献均己在论文中作了明确的说明井表示谢意。 学位论文作者繇稻谬字盹汶平脏月，咱 学位论文版权使用授权书 本学位论文作者完全了解盒月b 王些鑫堂有关保留、使用学位论文的规定，有权保留并向 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权盒目b 王些盘 堂可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位做者躲孀、导师始 签字日期渺p 月o 日签字日期：c l 龙 嚣主，鬣抵亏、寺瘾叶脚幅鹏聊f 通讯龇于寺兹聊崎南治撼蚴：l f j g 泖 致谢 衷心感谢我的导师王军教授对我的论文的选题、课题研究以及论文写作等 方面提出的宝贵意见。导师严谨的治学态度、刻苦钻研、兢兢业业的工作精神， 使我深受启迪，受益匪浅。在此我向导师致以最诚挚的敬意和深深的感谢! 在论文的完成过程中，中国社会科学院可持续发展研究中心的储诚山博士 后给了我很多的帮助和启发，并为本文的修改和校核提出了许多宝贵的意见； 广东广播电视大学南海校区的傅问莲老师，广东省佛山水泵厂有限公司的区国 惟副总经理，广东省佛山市城市规划勘测设计研究院的区广晖工程师，哈尔滨 工业大学的徐志标同学，合肥工业大学的覃华、李柱同学等为本论文的完成提 供了非常大的帮助，在此十分感谢他们! 最后感谢我的家人对我研究生学习和生活的关心，谢谢他们对我的培养和 鼓励l 潘永昌 2 0 0 7 年1 1 月7 日 第一章绪论 1 1 课题研究背景 城市给水系统整体主要是由取水构筑物、水处理构筑物、泵站、输水管线 及管网、调节构筑物等组成的一整套工程设施。而输配水管网是城市给水系 统的重要组成部分，它通过各级输配水管道把水安全可靠地输送到各个用水点， 并满足水量、水压和水质要求。在整个给水系统中管网部分的投资一般要占到 工程总投资的5 0 8 0 【2 l ，而且涉及到庞大的能耗和运行管理费用。同时，随着 水资源日益紧缺和水资源开发利用律的提高，新系统的兴建和老系统的修复、 改建和扩建等所需的工程投入逐渐增大。因此，给水管网系统的规划、设计和 运行管理是否科学、经济、实用，直接影响工程总投资、运行管理费及系统可 靠性在工程资金投入有限的情况下，进行管网系统优化设计，寻求能满足水 量和水压要求，且能使整个系统的造价最低、系统可靠性最高的设计方案，对 于节约投资、降低能耗、提高经济效益和社会效益，落实。科学发展观”、创建 “节约型社会”等有重要的现实意义 3 1 。 给水管网系统的优化研究主要是通过构造抽象或简化的管网优化设计模 型，借助于最优化理论和计算机技术，研究如何在管网工程规划设计中合理地 选择有关技术参数，从众多可行的设计方案中寻找出既能满足工程设计要求， 又能降低工程投资成本的最优或次优设计方案，作为工程建设施工和运行管理 的技术依据。 一个完整的给水管网系统设计过程包括规划、设计、运行管理三个阶段【2 】。 规划阶段主要进行管网干支线的布置，力求确定管网总长度最短或投资最小的 最佳管网结构形式。设计阶段以最优管网布置形式为依据，通过管网水力计算 确定有关技术参数，主要解决管径最佳组合问题，寻求系统造价最低的最优设 计方案。一个按最优设计方案施工建设的管网系统还必须通过水泵机组优化组 合、阀门开启优化组合、水源联合优化调度等优化运行研究，按最优运行策略 运行管理才能发挥系统最佳性能。 从管网系统的规划、设计到运行管理，每个阶段的设计任务均依赖于其他 阶段的设计结果，彼此之间具有一定的相互影响和制约关系。由于在不同阶段 对管网优化研究的对象和侧重点不同，采用的优化模型和算法也不同，故一般 来说仍按相对独立的阶段分别进行研究。因此，供水管网系统的优化研究工作 按照主要研究对象的内容不同，一般可分为管网优化布置1 4 l 、管网优化设计1 5 ，6 j 和管网优化调度1 7 j 三个方面。 1 2 管网优化研究现状 管网优化研究始于2 0 世纪6 0 年代末，最先在城市供水系统的规划设计中 引起工程设计人员们的重视j 。经过近4 0 年的发展和完善，管网优化模型和算 法在工程实践中得到了较为广泛的应用，成为提高系统设计水平和设计效率的 重要工具。而随着计算机的出现及其应用软件的发展，给水管网水力计算有了 很大飞跃，在理论和算法上日趋完善。同时，管网可靠性分析作为管网优化的 一个重要考虑因素，也有了大量的研究成果。下面将分别对给水管网的水力计 算研究现状、可靠分析研究现状、优化方法研究现状、优化布置研究现状和优 化设计研究现状进行概述。 1 2 1 给水管网水力计算研究现状 给水管网水力模型是优化设计中的水力约束条件，其求解的准确性直接影 响到优化设计计算过程的搜索时间和搜索效率。近年来，国内外众多学者进行 了大量研究，从不同角度和不同问题的需要出发，提出了不同的供水管网水力 模型及其求解方法。但总体而言，可将给水管网系统运行工况模型分为宏观模 型和微观模型。所谓宏观模型，就是在配水系统的大量生产运行数据基础上， 利用统计分析的方法，建立起来的有关管网的经验数学表达公式。它不考虑管 网各节点和各管段的所有状态参数和结构参数，从管网系统整体角度出发、直 接描述与调度决策有关的主要参数之间的经验函数关系。1 9 7 5 年r o b e r t d e m o y e rj r 首次提出管网宏观建模之后【9 l ，国内外学者进行了大量研究。 宏观模型所需数据少、建模快、计算效率高，但由于仅依靠管网中所设测 流、测压点建模，因而其输出量也只能是相应节点的压力及管段流量，无法了 解非测压点及非测流管段的信息。而微观模型就详尽地考虑了供水管网的网络 拓扑结构，从管网系统的基本组成元件的水力特性出发，用供水管网稳态方程 模拟管网系统的非线性特性所建立的模型。对配水系统来说，以供水网络分析 的连续性方程和能量方程或管段压降方程为基础，联立描述管网元件的特性方 程及边界条件等，求解可获取各点状态。通过调整节点绝对水压或调整环流量 或调整管段流量求解上述方程，解管网的任何问题总是联立求解连续性方程、 能量方程和压降方程，解管段方程是联立求解连续性方程和能量方程：解环方 程是联立能量方程和压降方程；解节点方程是联立压降方程和连续性方程。微 观模型需要己知管网拓扑关系、管径、管材、管段水力摩阻系数及节点流量等 参数所需输入数据多，需求解的变元多，因而占用较长的计算时间和较大的 存储容量o 】。 1 2 2 给水管网可靠分析研究现状1 2 1 许多研究者认为，只考虑一种用水情况的优化设计不能保证管网的可靠性， t e m o i e m a n ( 1 9 8 2 ) 的研究表明，管网优化设计的寻优过程是通过去除某些冗余条 件来实现的，这些冗余条件虽然在某一特定的用水情况是可以不予满足的，但 在管网实际运行的许多用水情况下，这些冗余条件是必须被满足的。也就是说， 这些优化设计中，投资的下降是以管网的可靠性的丧失为代价的。 2 t e m p i e m a n ( 1 9 8 2 ) 还指出，应把满足各节点消防水量、水压作为优化设计的约束 条件，通过这种方法可以使管网的可靠性得到保证。a l p e r o v i t sa n ds h a m i r 和 q u i n d r ye ra 1 在建立管网优化模型时，都考虑了多种用水情况。然而，这些方 法无法进行定量的描述和方案间的分析比较。 为了定量描述管网可靠度以利于各方案的分析比较，以及把可靠度因素合 并入管网优化模型，研究者做了大量的研究。w a g n e re ta 1 使用解析方法( 通过 模拟管网的水力条件确定管网中各水力参数的值) 来评价管网的可靠度，他们引 入图论中的可达性( r e a c h a b i l i t y ) 和连通性( c o n n e c t i v i t y ) 的概念，分析管网中各节 点间的连接的程度。h o b b sa n db i e m ，s h a m i ra n dh o w a r d 使用类似的解析方法， 应用频率期间分析( f r e q u e n c y d u r a t i o na n a l y s i s ) 和马尔科夫模型评价管网可靠 度。 d a m e l i ne ta 1 ，w a n g n e re ta 1 和b a oa n dm a y s 应用随机模拟分析方法分析 管网可靠度。w a g n e re ta 1 通过随机模拟拓展了他们的评价管网可靠度的解析方 法。b a na n dm a y s 把可靠度定义为供水管网系统满足用水用户水量和水压需要 的概率，使用蒙特卡罗模型( m o n t e c a r l os i m u l a t i o n m o d e l ) 求解管网可靠度。 a w u m a he ta 1 ，t t t a n y i m b o ha n da b t e m p l e m a n 把熵作为管网可靠性的 代用度量应用管网可靠性分析中。s h a m s ia n d q i u m p o 建立了一个基于时变连接 性( t i m e v a r y i n gc o n n e c t i v i t y ) 概念的可靠度分析模型。 从上述分析中可看到，研究者在管网可靠性方面还存在较多争论，特别是 在管网可靠性定义、度量方法、可靠度与总投资关系方面分歧较多。 1 2 3 给水管网优化方法研究现状 优化算法是研究给水输配水管网优化设计问题的理论基础和工具【l l l 。 2 0 世纪8 0 年代以来，一些新颖的优化算法，如人工神经网络、混沌、遗 传算法、蚁群算法、粒子群算法、鱼群算法、进化规划、模拟退火、禁忌搜索 及其混合优化策略等，通过模拟或揭示某些自然现象或过程而得到发展，其思 想和内容涉及数学、物理学、生物进化、人工智能、神经科学和统计力学等方 面，为解决复杂问题提供了新的思想和手段。这些算法独特的优点和机制。引 起了国内外学者的广泛重视并掀起了该领域的研究熟潮，并在诸多领域得到了 成功应用。在优化领域，由于这些新的算法构造的直观性及其与自然机理的一 直性，因而通常被称作智能优化算法( i n t e l l i g e n to p t i m i z a t i o na l g o r i t h m s ) ，或称 现代启发式算法( m e t a h e u r i s t i ca l g o r i t h m s ) 。 目前管网优化设计方法大致可分为确定性优化方法和随机优化方法两大 类。其中传统的确定性优化方法主要有枚举法、线性规划法、非法性规划法和 动态规划法i l2 2 0 j ；而随机优化方法主要是指神经网络算法、模拟退火算法、遗 传算法以及蚁群算法等，后者是管网优化设计方法的发展趋势1 2 卜2 3 1 。 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是随机优化方法的一个新的正在发 3 展的领域，它模拟达尔文的遗传选择和自然淘汰的生物进化的计算模型。1 9 7 5 年，由美国的h o l l a n d l 2 4 1 最先提出了g a 的系统概念和方法，之后的几十年时 间里该算法得到了迅速的发展，并广泛地应用于各种领域。1 9 8 7 年，g o l d b e r 9 1 2 5 】 等将这一理论应用于管网优化设计中来。这一方法采用离散的标准管径为决策 变量，并对其进行二进制或浮点式的编码，通过选择，交叉和变异等迭代操作 因子，进而求得满意的结果。目前，国内外学者已经将遗传算法成功应用在给 水管网设计中的技术经济计算等l z 6 。 蚁群算法( a n t c o l o n y a l g o r i t h m ，简称a c a ) ，是由意大利学者m d o r i g o l 2 7 】 等人于2 0 世纪九十年代提出的一种模拟进化算法，并将此方法用来求解t s p 问题、j o b s h o p 调度闯题、指派闯题。随后国外学者运用蚊群算法在给水管网 管径的优化上也做了大量的研究，其中m a i e r 2 8 】等人采用蚁群算法进行给水管 网的优化设计取得了较大的成功，并指出蚁群算法在给水管网管径的优化上优 于遗传算法，之后国内学者也开始将蚁群算法应用于给水管网中【2 9 l 。 1 2 4 给水管网优化布置研究现状 在管网布置优化研究的初期，国内外学者主要根据自己的实践经验和工程 的地形条件，提出管网布置的一些基本原则，作为确定管线走向和干支管布置 形式的依据。法国学者c l e m e m t ( 1 9 7 9 ) 等人提出用单位矢量法改进管网布置形 式【2 ”。直到8 0 年代国内外学者才开始研究管网最小费用布置和设计问题的结 合。m o r g a n 和g o u l t e r ( 1 9 8 5 ) 提出两阶段法，由两个相连的线性规划构成，一个 线性规划模型求解布置，另一个确定最小费用的元件大小设计【3 0 】l a n s e y 和 m a y s ( 1 9 8 9 ) 对两阶段方法进行了改进，在设计中考虑了泵、蓄水池、阀门以及 管径的大小及管线的位置口”，但该过程计算强度很大，需要在优化模型和模拟 模型之间进行大量迭代，每个步骤需要高维梯度项。 近年来国内学者也开始对管网布置优化进行了研究，林性粹等人( 1 9 9 3 ) 提 出一种简单实用的且同时考虑布置和设计的管网优化设计方法【“。该方法利用 正交试验设计原理确定若干个管网布置方案，并用微分法对每个方案进行优化 设计，通过对多个布置方案的优化设计结果进行比较，确定最优的管网布置形 式和优化设计方案。魏永耀等人( 1 9 9 5 ) 通过利用图论中最小生成树法确定管网 总长度最短的管网布置方案，然后采用动态规划法计算管网的最优管径，并利 用计算机绘制管网布置图，提出了一套比较完整的管网系统优化设计方法1 3 2 1 。 方永忠利用生成树变换法解决输配水系统最短供水路线问题，解决了多水源输 配水系统有一个以上节点流量为负值的最短供水路线问题。 已有的管网优化布置方法各具特色，为管网的拓扑结构优化提供了可选择 的具体方法，对管网工程的规划布局有一定的指导意义，但在实际应用中还存 在一定的局限性： ( 1 ) 经验性布置方法的合理性主要依赖于设计者的经验丰富程度，设计的主 4 观性太强，并且只适用于小型供水管网布置，当管网系统复杂度增大时，缺乏 科学依据的布置形式将会导致经济性的损失。 ( 2 ) 经典的图论方法仅以管线长度作为其管段权值，寻求的是管网总长度最 短的布置目标，并没有综合考虑流量、水泵扬程等各种因素对经济性的影响。 这就需要对管段权值有重新的定义，而不仅仅以管段长度作为经济性衡量指标。 在设计过程中，为了减少设计者的主观因素影响，使管网布置过程简单化、 实用化，这就使寻找一种管网优化布置的新方法成为管网优化设计研究中亟待 解决的问题。 1 - 2 5 给水管网优化设计研究现状 1 2 5 1 输水管线优化设计 输水管道系统优化设计方法主要有非线性规划模型、界限流量法等。 使用非线性规划法首先要根据管径与管道单价的关系，应用最小二乘法， 计算管线造价公式，以确定最优管径计算公式中的各项参数。这一方法计算简 单，但也存在一些问题，如应用这一方法计算出的最优管径往往与标准管径不 符，按按照标准管径对计算结果进行调整，结果偏离最优解；有时管径与管道 单价相关性较差，这对优化结果影响也较大；这一方法也没有考虑供水期间管 道流量变化和官衔地形的变化对设计方案选取的影响【1 6 】。 由于标准管径分档较少，因此每种管径不仅有相应的经济流量，并有其界 限流量【3 3 1 ，在界限流量内，用这一管径都是最经济的这就是界限流量的基本 出发点。确定界限流量的条件是相邻两管径的年费用相等。这一方法便于应用， 但仅适用于泵站加压输水管优化设计，同样这一方法也没有考虑供水期间管道 流量变化和管线地形的变化对管径选取的影响2 。王峪飞3 4 1 ( 2 0 0 1 ) 引入动态投 资的时间效应概念，用以改进界限流量法，应用改进后的界限流量法更加合理。 1 2 5 2 树状管网优化设计 从二十世纪6 0 年代末起，k a r m e l i i l6 】等人先后提出了树状管网优化设计的 线性规划模型。在树状管网布置形式和节点流量已定的情况下，用节点连续方 程就可以确定出各管段流量。如果事先选定管道允许采用的标准管径集合，以 标准管径的管段长度为决箢变量，则管道水头损失是管长的线性函数，节点水 压约束是决策变量的线性不等式，可构成树状管网的线性规划模型。这种线性 规划模型一般能保证得到一个全局最优解。 周荣敏、林性粹【2 , 4 1 等人应用人工神经网络法求解树状管网优化设计的非线 性规划模型，其基本原理是随着系统的不断演化，系统收敛到状态空间中的稳 定平衡点即计算能量函数的极值点，该点对应与原非线性规划问题的近似最优 解。这一方法首先用二次罚函数法构造出神经网络的计算能量函数，利用人工 神经网络的并行分步式计算结构和非线性动力学系统的动态演化机制，可求得 非线性规划模型的最优解。 5 周荣敏、林性粹1 2 ，4 1 等人提出了重力树状管网两阶段优化计算方法，第一阶 段将管径作为连续变量。用人工神经网络优化方法确定最优管径，由于求得的 最优管径往往与标准管径不符；于是根据第一阶段优化计算结果，用标准管径 的管长为变量，用线性规划法，确定各管段选用的标准管径最优长度。 以上成果大部分研究的是灌溉树状管网优化设计问题，而对给水树状管网 研究比较少，实际上，树状给水管网在水力联系上与灌溉管网并不完全相同， 如树状给水管网常采用水塔来调节管网流量和压力，而从掌握的文献来看，对 各种形式的有塔树状管网分级供水条件下优化设计问题研究还不够【l ”。 1 2 5 3 环状管网优化设计 s h a m i r i 】等人采用梯度技术进行求解，这一方法先采用n e w t o n r a p h s o n 方法获得管网稳定状态的水力解，然后用该解的j a c o b i a n 矩阵计算目标函数对 策变量的梯度，寻找减少管网设计费用的求解方向，模型中只考虑一种工况， 对节点水压和管段流量都没有约束 j o c o b y 3 1 采用一种数值梯度技术求解环状管网的非线性优化模型。饱先选 择一个初始设计点，在当前设计点周围做较小的移动，移动方向随机选择或者 根据前几个相对成功移动的“经验”确定，评价新设计点处的目标函数值，计 算目标函数对设计变量的近似梯度。重新确定能改进设计的优化搜索方向， j o c o b y 仅应用这种比较复杂的方法，进行了一个五条管道的双环管网优化设计， 但这一方法难以对更复杂的管网进行优化设计。 1 9 7 7 年，a l p e r o v i t s 和s h a m i r ”j 提出线性规划梯度算法( l i n e a r p r o g r a m m i n gg r a d i e n t l p g ) ，l p g 算法通过两个相互交替的优化模型，解决环 状管网优化设计问题，它认为管网费用是管网中各关段流量的函数，首先确定 出一个可行的初始管段流量分配方案，建立线性规划模型并求解，得到一组管 径组合方案和节点压力水头。根据当前l p 模型的优化结果，求目标函数对各 基环流量增量的梯度值，确定能使系统费用减少的基环流量增量，来修正初始 流量分配，然后用新的流量分配方案代入线性规划模型，反复进行该过程直至 收敛于一个局部最优解，也可能是全局最优化解，但这在很大程度上决定于初 始流量分配方案。l p g 酸法首次将环状管网中的流量分配问题与优化设计结合 起来，对管网的水力条件没有做任何假设，l p g 算法被公认是管网优化研究领 域取得的一个非常重要的进展，其研究环状管网优化设计问题的思路影响至今。 f u j j w a r a 和k h a n g 2 8 1 提出一种具有全局寻优能力的两阶段分解方法，能产 生一个改进局部最优解的过程。第一阶段中引入了非线性梯度法( n l p g ) ，比直 接应用一股的n l p 算法计算更有效。 s h e r a l i i i 等人提出另外一种具有全局搜索能力的分支定界算法，应用重构 线性化算法。构造一个线性松弛模型，以确定给定问题的下限值，以获得优化 问题的全局最优解。 6 进入二十世纪9 0 年代以来，m u r p h y 和s i m p s o n 3 6 】等人先后将遗传算法用 于解决管网优化设计问题，这些方法用标准管径作为优化变量，使用二进制编 码，寻求费用最低的管网优化设计方案。 越来越多的学者用智能优化算法进行给水管网优化设计计算，应用这些算 法进行管网系统优化研究，是给水管网优化研究的一个新方向，尚处于探索和 尝试阶段，许多问题有待于深入研究。 1 3 现行给水管网系统所需要解决的问题 对于现行的给水管网系统所需要解决的问题主要有： ( 1 ) 管网设计不合理 目前，我国对供水管网系统的设计方法仍采用常规模式，即按照已知的管 网布置路径，根据设计人员经验首先假定一种流量分配方案，由管段的界限流 量确定一组可能的管径组合并进行管网水力分析计算( 又称管网平差) ，确定该 组合方案是否能满足节点压力和其他约束条件的要求。在此基础上，通过反复 试算和不断调整管网布置方案，直至得到一组满意的管径组合方案为止，并计 算出管段流量、管段流速、管段水头损失、节点压力和水泵扬程。该设计思路 和方法实际上是优化方法中的枚举法，对于小型管网系统，将枚举法和传统试 算方法相结合，通过搜索和评价多个可能管径组合方案，一般能选出一组满足 设计要求且较合理的管径组合方案；但对规模较大或较复杂的管网，采用枚举 试算法计算工作量异常巨大，单凭人工方法很难找到较合理的管径组合方案。 ( 2 ) 管网运行管理费用高 由于管网设计不科学，容易造成局部地区水压过高而某些地区水压不足的 现象。但是，为了满足整个管网系统的供水要求，势必要通过增大泵站出水扬 程的方式来保证管网压力，这样就造成了不该发生的能源浪费。据计算，对于 一个总供水量为l 米3 秒的供水系统，假定水泵机组工作效率为8 0 ，若出 厂水压浪费一米，则该系统每年约浪费十万千瓦时电量，对于能源紧缺的社会， 我们应该杜绝这种现象在供水行业内出现【4 ”。 ( 3 ) 管网漏损和爆管现象严重 城市供水管网常因管材、施工质量、腐蚀等原因而在运行过程中易造成管 网漏损或爆管现象。同时，由于管网设计不合理，造成局部水头损失过大和水 头不足的现象。但是，为了满足运行，保证整个管网节点所需要的最小自由水 压的限量，就一味通过增大泵站出水扬程方式来增加管网中水压，这也在一定 程度上间接地增大了管网漏损率和爆管率。各种原因，使得我国城市供水管网 中的漏损率远高于发达国家，造成了无谓的水资源浪费1 4 7 1 。 ( 4 ) 城市供水管理水平落后 供水系统自动化程度低，供水器材、设备和仪表相对落后，产品开发滞缓， 缺乏创新，管理水平落后，造成供水过程中出现水质、水量和水压有时不能满 7 足用户要求的现象，供水安全可靠性差。与此相比，发达国家的供水企业已实 现现代化管理，特别是从规划的制定到生产运营实施中的各方面的统计、分析 已全面地应用计算机，水厂运营基本实现了自动化，有的已向智能化发展，实 现了企业的科学管理和高效运营。另一方面，在我国由于管网前期设计的不合 理性，对管网系统进行科学的运行管理也带来一定的制约。 1 4 本文研究的主要内容 本文在前人研究的基础上，根据本课题相关领域所需要解决的问题，确定 本课题主要研究内容为以下几个方面： ( 1 ) 简要介绍与管网优化相关的最优化方法，主要叙述遗传算法和蚁群算法的起 源与发展、基本原理与流程、设计与执行策略，分析它们的优缺点，并介绍 它们的应用。 ( 2 ) 对输水树状管网优化布置数学模型的研究，用图论法和改进的蚁群算法进行 输水管网优化布置求解，并讨论算法中各参数的数值设置，然后用v c + + 语 言编程，在算例中应用并和其他算法进行对比分析。 ( 3 ) 结合给水管网水力计算的基本方程，并对水力计算方程求解的方法进行较详 细的论述，利用水力模拟软件e p a n e t 进行管网水力计算。 ( 4 ) 建立给水管网多目标优化设计数学模型，分别将经济性条件、可靠性条件和 约束条件转化为公式进行定义和计算，并对其中的经济参数值用m a t l a b 语言编程进行最小二乘法拟合。 ( 5 ) 采用v c + + 语言针对改进混合遗传算法对所建模型进行编程和实例应用，并 详细分析计算的主要步骤、编码方式、目标函数和约束条件的处理、适应度 函数的设计和各遗传算子的设计等，然后将计算结果与传统设计方法所得结 果进行比较分析。 8 第二章蚁群算法和遗传算法概况 2 1 蚁群算法 2 1 1 蚁群算法起源与发展 根据蚂蚁“寻找食物”的群体行为，意大利学者d o r i g om 1 3 4 l 等于1 9 9 1 年 在法国巴黎召开的第一届欧洲人工生命会议( e u r o p e a nc o n f e r e n c eo na r t i f i c i a l l i f e ，e c a l ) 上最早提出了蚁群算法的基本模型；1 9 9 2 年，d o r i g om 又在其博士 学位论文中进一步阐述了蚁群算法的核心思想1 3 ”。 但自从d o r i g o m 等提出蚁群算法后的近5 年时间里，并没有在国际学术界 引起广泛关注，这段时期在蚁群算法理论及其应用上也没有取得突破性进展。 到了1 9 9 6 年，d o r i g om 等在i e e et r a n s a c t i o n so ns y s t e m s ，m a n ，a n d c y b e r n e t i c s p a r t b 上发表了“a n ts y s t e m ：o p t i m i z a t i o n b yac o l o n yo f c o o p e r a t i n g a g e n t s ”一文【3 9 1 。在这篇文章中，d o r i g om 等不仅更加系统地阐述了蚁群算法 的基本原理和数学模型，还将其与遗传算法、禁忌搜索算法、模拟退火算法、 爬山法等进行了仿真实验比较，并把单纯地解决对称t s p 拓展到解决非对称 t s p 、指派问题( q u a d r a t i ca s s i g n m e n tp r o b l e m ，q a p ) 以及车问作业调度问题 ( j o b - s h o ps c h e d u l i n gp r o b l e m ，j s p ) ，且对蚁群算法中初始化参数对其性能的影响 做了初步探讨，这是蚁群算法发展史上的又一篇奠基性文章。从目前公开发表 的蚁群算法相关论文来看，其中7 0 以上的论文将这篇文章或1 9 9 1 年d o r i g om 等在e c a l 上发表的“d i s t r i b u t e do p t i m i z a t i o nb ya n tc o l o n i e s ”一文列为参考文 献。自1 9 9 6 年之后的5