（市政工程专业论文）基于改进蚁群算法的城市给水管网改扩建优化研究.pdf

中文摘要 摘要 城市给水管网是城市供水系统的重要一环，在保障经济建设和人民生活中发 挥着重要的作用。随着经济的持续发展、城市现代化建设的加快，用户对用水要 求不断提高，而城市给水管网由于使用年限的增加而导致水质变差，带来了许多 影响正常供水的问题，因此各发展中城市普遍面临着进行给水管网系统改扩建优 化问题。由于给水管网投资大、费用高， 投资，获得良好的经济效益和社会效益， 进行研究。 合理进行管网改扩建优化能够节省大量 本文结合某市给水管网改扩建实际工程 从给水管网改扩建的实际出发，进行城市用水量中长期预测是给水管网系统 改扩建优化的基础。首先对传统的用水量预测方法进行了分析，然后介绍了灰色 系统用水量预测模型及其实现过程，并针对灰色模型的缺点提出了改进的预测模 型，即等维新息灰色递补动态预测模型。通过实际资料对灰色模型和改进的灰色 模型进行了预测效果对比分析，结果表明：改进的灰色预测模型能够在数据较少 的情况下提高预测精度，可用于城市给水系统中长期用水量的预测。 接着，介绍了给水管网改扩建优化模型的经济效果指标及其经济评价的一般 程序，分析管网改扩建优化模型建立过程，并建立符合实际工程的管网改扩建优 化模型，将模型分解为管径优化、加压泵站扬程和流量优化、扩建水源流量分配 优化三个子系统，并对优化设计相关参数的确定方法进行了介绍。 针对给水管网改扩建优化问题为复杂非线性规划问题，其决策变量为离散变 量及其目标函数为多峰值函数的特点，采用了一种新型的仿生模拟算法一蚁群算 法进行求解。并针对基本蚁群算法有收敛速度慢、易陷入局部最优解的缺点，结 合遗传算法中杂交、变异操作和自适应思想提出一种改进的蚁群算法，即具有杂 交、变异特征的自适应蚁群算法。将基本蚁群算法与改进的蚁群算法分别应用于 某小区给水管网改扩建优化问题，优化结果表明：改进的蚁群算法更容易实现全 局最优解，且运算时间较短，优化效率高。 最后，通过工程实例来检验所采用的数学模型和求解算法的合理性。针对某 市给水管网改扩建实际工程，分别用传统设计方法和改进的蚁群算法进行优化， 结果表明：采用优化方案要比传统方案节省管网造价。 关键词：给水管网，改扩建，用水量预测，蚁群算法 英文摘要 a b s t r a c t u r b a nw a t e rn e t w o r ki sa “t a lp a r to ft h ew a t e rs u p p l ys y s t e m s a n dp l a y sa n i m p o r t a n tr o l ei ns e c u r i n ge c o n o m i cc o n s t r u c t i o na n dp e o p l e sl i v e s w i mt h es u s t a i n e d d e v e l o p m e n to f e c o n o m y , t h ed e v e l o p m e n to f t h ec i t ym o d e r n i z a t i o n , w a t e rd e m a n d so f c u s t o m e r si n c r e a s eg r e a t l y t h e r ea r el o t so fp r o b l e m st h a ti n f l u e n c et r a n s m i s s i o no f w a t e rr e g u l a r l y , a l o n g 、i t l ld e t e r i o r a t i n go f w a t e rq u a l i t yb e c a u s eo f i n c r e a s i n gf o ru s i n g t i m e s ot h ed e v e l o p i n gc i t i e sa r ef a c i n gt h ep r o b l e mo f u p g r a d i n ga n de x p a n s 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 b e c a u s eo ft h eh u g ei n v e s t m e n ta n dm a n a g e m e n tc o s t , o p t i m a lu p g r a d i n ga n de x p a n s i o nc a ns a v em u c hm o n e ya n da c t u a l i z eg o o de c o n o m i c a n ds o e i a ls i t u a t i o n b e g i n n i n gw i t hp r a c t i c a ls i t u a t i o no f t h eo p t i m a lu p g r a d i n ga n de x p a n s i o no f w a t e r d i s t r i b u t i o ns y s t e m t of o r e c a s t l o n g - t e r mw a t e rd e m a n di s t h ef o u n d a t i o na n d p r e p a r a t o r yw o r k f i r s t l y , t r a d i t i o n a lf o r e c a s tm o d e li sa n a l y z e d ，a n di m p r o v e dg r a y m o d e li sc o n s u u c t e db ya d d i t i o n a ld a t aa n dd y n a m i ce q u a ld i m e n s i o nn e wd a t ab a s e d o nt h es h o r t c o m i n go ft r a d i t i o n a lg r a ym o d e l b yc h e c k o u to fp r a c t i c a ld a t a , t h e i m p r o v e dg r a ym o d e lh a sab e t t e rf o r e c a s t i n ge f f e c tw i t l laf e wd a t at h a nt r a d i t i o n a l m o d e la n do a nb eu s e dt ot h ep r a c t i c a le n g i n e e r i n g t h e nt h ep r o c e s so f t h eo p t i m a lm a t h e m a t i c sm o d e li si n t r o d u c e d ，a n do p t i m i z a t i o n m o d e li sc o n s t r u c t e d ，w h i c hi n c l u d e s p i p co p t i m i z a t i o n , p r e s s u r ep u m ps t a t i o n o p t i m i z a t i o na n dw a t e rr e s o u r c eo p t i m i z a t i o n o w i n g t ot h ed i s c r e t ec h a r a c t e ro ft h ep i p ed i a m e t e rw i t ht h eo b j e c tf u n c t i o nb e i n g am u l t i m o d e lf u n c t i o n ，a n do p t i m a lu p g r a d i n ga n de x p a n s i o nb e i n gc o m p l e xn o n - l i n e a r m a t t e r , a n tc o l o n ya l g o r i t h m ( a c a ) i san e wt y p eb i o l o g i cs i m u l a t i n ga l g o r i t h ma n di s a d o p t e d ，b u ta c a h a sm u c hd e f i d e n c y , s p e c i a l yi ti se a s yt of a l li n t ot h el o c a lb e s ta n d i t sc a l c u l a t i o ni sc o m p l i c a t e d s oi m p r o v e da n tc o l o n yo p t i m i z a t i o na l g o r i t h mi sp u t f o r w a r dt oi m p r o v et h es h o r t c o m i n go fb a s i ca n tc o l o n ya l g o r i t h m t h e s et w o a l g o r i t h m sa r es e p a r a t e l ya p p l i e dt oas i m p l en e t w o r ko p t i m i z a t i o np r o b l e m a n dt h e r e s u l t ss h o wt h a ti m p r o v e da c ai ss u p e r i o rt h a nb a s i ca c a i m p r o v e da n tc o l o n y a l g o r i t h mh a se x c e l l e n tg l o b a lo p t i m i z a t i o np r o p e r t y e s s h o r t e ro p e r a t i o n 曲m ea n d h i g h e ro p t i m i z i n ge f f i c i e n c y i nt h ee n d ，a na c t u a le n g i n e e r i n gi su s e dt oc e r t i f yt h er a t i o n a l i t yo ft h em o d e la n d t h eo p t i m i z a t i o na l g o r i t h m t h eo p t i m i z a t i o na l g o r i t h ma n dt h et r a d i t i o n a la l g o r i t h ma l e 1 1 1 重壅盔兰堡主堂生堡苎一 a p p l i e dt od i s t r i b u t i o ns y s t e mu p g r a d i n ga n de x p a n s i o ne n g i n e e r i n gi ns o m ec i t y a n d m ec o m p a r i s o no fs o l u t i o ni l l u s t r a t e st h eo p t i m a lp l a nw h i c hi sd e s i g n e db yi m p r o v e d a n tc o l o n yo p t i m i z a t i o na l g o r i t h ms a v e st h ec o s to f w a t e r n e t w o r k s k e y w o r d s ：w a t e rd i s t r i b u t i o ns y s t e m ，u p g r a d i n g a n de x p a n s i o n ， f o r e c a s to f w a t e rd e m a n d ，a n tc o l o n ya l g o r i t h m 1 v 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文 中不包含其他人已经发表或撰写过的研究成果，也不包含为获得重麽太堂 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：张玉签字日期：力叮年牟月2 7 日 学位论文版权使用授权书 本学位论文作者完全了解重废太堂有关保留、使用学位论文的 规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许 论文被查阅和借阅。本人授权重庆太堂可以将学位论文的全部或部 分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段 保存、汇编学位论文。 保密() ，在年解密后适用本授权书。 本学位论文属于 不保密( 奶。 ( 请只在上述一个括号内打“4 ”) 学位论文作者签名：狱玉导师签名： 签字日期：2 叼年年月2 7 日签字日期：卿7 年年月刁日 1 绪论 1 绪论 1 1 课题的研究背景 给水系统是保证城市、工矿企业等用水的各项构筑物和输配水管网组成的系 统，它的任务是从水源取水，按照用户对水质的要求进行处理，然后将水输送到 用水区，并向用户配水【i 】。给水管网是城市供水系统的重要组成部分，一方面给水 管网是联系水源点和用户的“桥梁”，它通过各级输配水管道把水安全可靠地输 送到各个用水点，并满足水量、水压和水质要求；另一方面给水管网的投资大， 管网部分的造价比重约占5 0 7 0 ，同时给水系统运行中约3 0 a 0 - 5 0 2 的能耗 用于克服管网的阻力。所以，给水系统是重要的市政基础设施，一旦出现事故， 就直接危及社会生产和人民生活，甚至造成巨大损失，产生不良社会影响，是关 系社会生产和人民生活的生命线工程，在保障经济建设和人民生活中发挥着重要 的作用。 自我国第一座供水设施于1 8 7 9 年在旅顺建成后，到新中国成立。全国只有6 0 个城市有供水设施，日供水能力为1 8 6 7 万m m 3 1 。之后，随着社会的进步，经济的 发展，给水事业蓬勃发展，城市的供水状况得到了前所未有的改善。到目前为止， 全国几乎所有城镇均建立起了各自的给水系统，并且各地很多城市的给水系统已 初具规模，而且还在不断扩大。据统计，1 9 9 0 年，全国4 6 7 个城市设有水厂1 2 2 0 座，日供水能力达6 3 8 2 5 万m 3 4 1 ；到2 0 0 0 年，我国共有6 6 9 座城市。全年城市总 供水量为4 6 9 亿m m 卯。我国在“十五”计划期间城市日供水能力继续较快增长， 预计到2 0 1 5 年，全社会城市日供水能力将达到3 5 x 1 0 3 m 3 ，年供水量达到7 0 0 x 1 0 3 m 3 ，城市用水人口将达到4 4 亿人左右 6 1 。然而，随着我国城市化进程的加快，用 水量和城市格局的变化，以及一些自然因素和人为因素的影响，目前我国城市供 水状况不容乐观，现行给水系统所面临的主要问题有： 现有管网的供水安全性不高 由于供水管网系统规模越来越庞大，管网系统的拓扑结构也越来越复杂，经 验管理已难以保证用户在各个时段对水量与水压的要求，而且许多城市的现有给 水管网铺设年代久，管道材质差，腐蚀结垢严重，水流在管网中停留的时间较长， 微生物滋生繁殖的机会较大，造成了输配水管网二次污染严重。用户对永量、水 压和水质要求的提高要求对现有的给水管网进行优化设计。 供水效益亟待提高 能源紧张和水源危机是世界性问题，而这些矛盾在我国表现的尤为突出，节 能降耗已成为我国的一项基本国策。给水规模的不断扩大，使城市给水管网的电 重庆大学硕士学忙论文 耗也越来越大。有关资料统计表明 7 1 ，全国给水企业每年耗电超过4 0 亿度，各城 市水司为该市最大的用电单位之一。因此，改善管网运行状况，降低电耗是自来 水行业提高效益的一个重要环节，而且可以缓解国家能源紧张的局面。 供水系统布局和规划不合理 很多城市的给水管网年代已久，没有进行过管网系统的优化，布局和规划不 合理，管段连接复杂，敷设冗余，应逐步改善管网布局，使其合理化，以实现供 水系统的优化运行。 管道爆管频率高，漏损严重 我国供水管网漏失率非常高。在2 0 0 2 年，根据对全国4 0 8 个城市的统计，全 国城市公共供水系统的管网漏失率平均达2 1 5 t ”，全国城市供水年漏损量近1 0 0 亿立方米。造成问题的主要原因有：现有管网的输水能力难以满足实际用水量的 需求；现有管道抵抗内外压强冲击的能力较低，再加上过去大多数城市给水管网 都较缺乏合理的系统规划，供水分区不合理。 国内水务市场竞争日趋激烈 2 0 0 2 年3 月，国家计委公布的外商投资产业指导中将原禁止外商投资的 供、排水及其城市管网首次列入对外开放领域 9 】。外商投资产业指导的发布， 必将导致供水及排水领域投资主体的多元化，水务市场的竞争将会日趋激烈。现 代化的管理( 包括先进技术) 是投资主体在激烈的市场竞争中取胜的关键所在。 上述诸方面的原因说明，我国给水工程已进入加强管理和提高效益的改扩建 时期。给水管网系统改扩建优化不同于新建管网，其目标函数中包含现有管段 i o j l 】， 设计变量、约束边界条件增多，加上某些变量的不确知性，导致进行管网改扩建 设计的难度要比新建管网设计大得多，并且设计的方法、程序也不同。长期以来， 各地自来水公司在进行给水管网改扩建时，在仅凭经验确定管段走向和管径的基 础上，只拿出很少几个经验方案作比较，由于实际管网的计算复杂、工作量大， 难于找到经济合理的最优方案。由于给水管网投资额很大，缺乏科学依据地进行 建设，不仅浪费资金，而且投资效益也不理想，这些问题也一直困扰着供水企业。 因此需要运用现代科学知识进行给水管网改扩建优化，在满足用户对水量、水压、 水质要求的前提下，寻求经济合理的改扩建方案，实现生产的科学化、合理化和 现代化，并且对于节约投资、降低能耗、提高经济效益和社会效益，落实“科学 发展观”、创建“节约型社会”等有着重要的现实意义。 1 2 国内外城市给水管网改扩建优化研究概况 优化是任何工程设计的主要目标，它指工程设计者找到经最少的人力、物力 和财力取得以工程投资、工程质量、运行可靠性等一些标准衡量的最佳的工程效 2 1 绪论 果的过程。当前，优化越来越专指一个特定的领域，即应用数学模型、系统分析、 优化理论和计算机技术对工程方案进行求解。虽然优化设计并不意味着要寻求一 个新的设计目标，但是，它确实已经把原先以感性、经验、静态分析与手工式劳 动为基础的传统设计方法进行扩展和取代，形成以动态化、最优化和计算机化为 特征的，有着严格的程序与科学内容的优化设计。 从1 9 3 6 年哈代克罗斯( h a r d y c r o s s ) 提出的两个迭代法为标志以来，给水管网 设计理论及方法发展迅速，现已成为给水工程学领域的一个重要分支，并在实际 的给水工程设计中得到了大量应用【。其发展进程大致可分为四个阶段，即经典 的模拟设计( 传统设计) 阶段、技术经济计算阶段、应用系统分析阶段和可靠度分析 及评价阶段。2 0 世纪4 0 年代，前苏联学者b p 洛巴乔夫、兀q 莫什宁f 2 】等人首次 将经济观点引入到给水管网设计领域，从而开了给水管网技术经济计算的先河， 著名的莫什宁法就是在这个时候提出来的。 优化模型均与一定的求解方法相对应，与当时的数学发展水平是密切相关的。 自提出给水管网优化课题以来，前人已在这一领域做了很多研究和探索工作，取 得了大量的研究成果。其中代表性的优化方法有： 1 2 1 确定性优化方法 枚举法 枚举法是一种全局搜索算法，它对目标函数要求低，优化原理简单可靠。它 是从用户指定的各组管径序列中对各个管段进行最优管径组合，从中选出最符合 优化目标的方案，从而达到最优化设计的目的。枚举法需要存储每一管段所有可 能用到的标准管径，形成标准管径解空间，再进行逐个试算，所以该方法所需存 储空间大，计算效率很低，只能解决管段数量很少的给水管网优化问题，优化结 果不是很理想。 线性规划方法 线性规划模型是管网优化设计中应用较早的数学规划模型之一。 2 0 世纪6 0 年代末，& 哪c l i 【l 纠和g u p t a u 4 等人先后提出了进行树状管网优化 设计的线性规划模型，这些模型没有考虑类似阀门的附属物，仅用于树状管网系 统，没有线性规划法的计算优势，不能得出比较好的结果。 2 0 世纪7 0 年代末，a l p e r o v i 乜和s h 锄一”j ，q u i n d r y m 6 等相继提出线性规划 模型，至今仍有广泛的影响，但管网的规模受到了限制。1 9 7 7 年a l p e r o “t s 和 s h 锄一”j 提出了一个基本线性规划公式的、能引入任何理论和产生实际兴趣的第 一个环状系统模型，该模型是以管线建造费用构成一线性目标函数，同时满足水 力关系的约束，避免了求解管段费用回归式，所得结果直接为商用尺寸。这说明 线性规划法具有强大的实用性，奠定了两阶段法的基础，但该模型没有考虑泵站 重庆大学硕七学位论文 的运行费用及管网的可靠性。在1 9 7 9 年q u i n d r y t ”对模型进行了修正，用“两阶 段法”设计给水管网，代表了管网优化设计计算技术进入了一个崭新的阶段，也 意味着人们已经意识到管网优化课题的复杂性，单纯靠简单的单一阶段的方法是 解决不了该问题的，但该模型没有考虑管网可靠性。在该阶段，r o w e l l 【1 7 】用两阶 段法来确定管网布置及管道尺寸。 1 9 8 5 年，m o r g a n 和g o u l t e 一”】基f 线性规划方法提出了一个两步试探步骤， 第一步通过模拟管网中多种用水情况求出管网的各种水力条件；第二步搜索新的 水力条件使管网投资下降，通过不断迭代上述两个步骤求出最优解。该模型将 h a r d y - c r o s s 网络解算器和优化布置、新系统的设计及规划系统扩建结合起来。把 每一管线视为由两根管段所组成，以管段建造费用构成最低费用目标函数；对各 管段引入权重概念，反映各管段尺寸变化对节点压力的影响，同时在迭代求解过 程中多次应用水力计算，以此满足水力约束。该模型只能日j 接地考虑管网可靠性 要求，同时未考虑泵站运行费用对最优方案的影响。 同时，俞国平教授【1 9 】提出了以管长为决策变量的线性规划模型，主要是在满 足节点方程的条件下分配管段流量，然后在每根管段上划分若干区段，根据管段 流量，在这些区段上适宜地选定若干规格管径，但各区段长度未知，于是目标函 数就变成了以区段长度为变量的线性规划问题。这种以管长为决策变量的线性模 型不必调整管径，避免了调整管径后偏离最优解的情况，而且便于求解，运用单 纯形法求解即可。 非线性规划方法 1 9 8 9 年l a n s e y 和m a y s l 2 0 】应用 e 线性规划方法求解管网优化模型，考虑了优 选和布置泵站、蓄水池和阀门的情况，将一般降阶法和一个现存的给水模拟模型 结合起来优化管网、估计泵站及水箱尺寸，该法计算集中，更加准确地反映了管 网实际运行情况。该模型是对以前优化模型的一个概括，能适用于枝状、环状管 网。但其缺点是优化模型和模拟模型之间需要大量的迭代运算，而且每一步都要 考虑梯度项，并且没有考虑管网的可靠性。 王彤、赵洪宾1 2 1 】等针对我国城市给水管网改扩建过程中遇到的实际问题，提 出采用混合离散变量的直接搜索法，是在综合非线性规划中的“爬山”策略思想 和组合优化中的“查点”策略思想的基础上提出的一种约束非线性优化设计方法， 可确定出最优管径和各水源最优水量分配，经管网工况复核，改扩建优化方案合 理可行。 目前非线性规划模型一般都为复杂的不等式约束非线性规划问题，常用的计 算方法是广义简约梯度、法【2 2 2 3 1 ( g e n e r a l i z e dg r a d i e n tm e t h o d ，简称o r o ) ，基本思想 是把变量分成自变量和因变量两个部分，将因变量由约束条件解出，以自变量表 4 i 绪论 示，在利用简约梯度直接构造一个使目标函数改善的可行方向，沿此方向进行搜 索，从而找到一个新点，逐步逼进原问题。根据管网系统的特点，将管径作为非 基本变量，节点水压作为基本变量，直接以管径作为优化对象，以管网水力计算 方程作为约束条件，建立起不需要预先假定管段流量分配的管径优化数学模型。 该法，收敛速度较快，具有很强的局部收敛能力，但全局搜索能力欠差，对于多 峰值的规划问题，很容易陷入局部最优解。 动态规划方法 动态规划( d y n a m i cp r o g r a m m i n g ，简称d p ) ，是一种求解多阶段决策过程最优 化的方法，在管网设计优化中也有一定的应用。动态规划法以年费用折算值为目 标函数，以节点连续性方程、节点自由水压大于最小自由水压以及管线隆起处水 压非负为约束条件构成管网主干管线管径优化设计数学模型。该法直接以标准管 径为变量，求得的最优结果无需进行调整。 l i a n 一2 4 】应用动态规划法进行供水系统最优设计，将系统内的每个管段作为动 态规划的阶段，以每个管段入口和出口处的压力为输入和输出状态变量，以连续 变化的管径为决策变量，以所用费用项和整个系统效率为优化目标函数。k w a n g 2 5 采用动态规划法对一个单压力水源且有多个分支管道的发散性树状供水管网进行 优化设计，以标准管径为决策变量，以系统内的水力关系为动态规划的状态传递 关系，确定系统的最优管径组合。我国学者口6 2 7 1 对动态规划技术在树状管网和环 状管网优化设计中的应用也进行了探讨和研究。 从动态规划模型的性能及应用来看，对于单个的串联管道和小型树状管网， 动态规划能得到全局最优解和一组次优解。对于简单的环状管网，需要预先假定 管径，进行初始流量分配，化环状网为树状网，进行迭代计算。当其应用于复杂 管网时，该法需要的计算机内存和计算机运行时间都很大，甚至得不到最优解。 此外，动态规划技术没有统一的标准，也没有构造模型的能用方法，甚至没有判 断一个问题能否构成动态规划模型的准l l j 2 引。因此，在实际应用中只能根据问韪 的不同类型，进行具体分析，构造具体的模型。对于复杂问题，在选择状态，确 定状态转移规律等方面，需要丰富的想象力和灵活的技巧性，使动态规划技术的 应用范围受到限制【2 9 】。 界限流量法 界限流量法是一种近似优化算法。把每一管段看作是管网中与其它管段无关 的单独工作管段。对于每种标准管径不仅有相应的最经济的流量，而且有其经济 的界限流量范围，在此范围内用这一管径都是经济的，超出界限流量范围就必须 采用大一号或小一号的标准管径。根据相邻两标准管径d 。和见的年费用折算值 相等的条件，可以确定界限流量。这时相应的流量吼即为相邻管径的界限流量， 5 重庆大学硕十学伊论文 也就是说既是d 。的上限流量，又是d 。的下限流量【3 0 】。 1 2 2 随机优化方法 目前的给水管网优化设计课题随着计算机技术不断更新、发展而不断向纵深 发展，并已出现优化设计理论与工程实际相结合的软件化趋势，一些新型算法开 始介入管网设计理论领域并表现出了强大的生命力。 模拟退火算法 模拟退火算法( s i m u l a t e da n n e a l i n g ，简称s a ) 是将统计物理学中的物理退火过 程与组合优化相结合的一种随机迭代寻优算法。最早是由m e t r o p o l i s 3 l 】等人在1 9 5 3 年提出，k j r k p a t r i c k 挖】等人在1 9 8 3 年将优化问题与统计动力学中的热平衡作类比， 研究发展了模拟退火算法的理论，成功地应用在组合优化问题中，从而开辟了求 解优化问题的新途径。在随后的几十年中国内外学者将其应用于管网优化中【3 3 - 3 5 ， 实践证明用s a 来解决管网优化可以取得令人满意的结果。它从任意一个标准管径 初始可行解开始，并用某一机制( 交换、查找、逆转) 产生邻域解，用水力约束条件 控制计算流程是否由m e i t r o p o l i s 准则判定，如此迭代下去直到得出一满意解。s a 算法的收敛速度依赖于初始温度、降温速率及整个算法过程的其他随机操作。由 于理论最小迭代次数无法确定，s a 法的计算效率偏低，仍需要作进一步研究。 神经网络算法 神经网络算法( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) 求解优化问题的关键思想 是将问题映射到一个神经网络动力系统，写出相应的满足问题约束条件的能量函 数表达式和动力学方程，选取适当的参数值以保证网络的稳态输出，在网络动力 学方程自动演化到平衡位置后，即可搜索到相应的( 局部) 最优解。 人工神经网络这一理论起源于2 0 世纪4 0 年代，到6 0 年代末进入了低潮，后 来由于神经网络具有较好的非线性映射、智能化学习以及较好容错性的特点，于 8 0 年代重新得到了重视，h o p f i e l d l 3 6 1 将人工神经网络成功地应用在组合优化问题 中，掀起了一股遍及各个学科的神经网络热潮。由于神经网络采用了微分方程这 样的数学工具，因而开启了用动态方法求解静态问题的大门。在具体实现上不仅 可用软件模拟，而且可以制成硬件电路，因而拥有广泛的应用前景。之后国内外 学者 3 7 , 3 8 1 将人工神经网络应用于给水管网中。 遗传算法 随着生物工程的蓬勃发展，随之而起的遗传学算法开始介入各个工程领域。 遗传算法( g e n e t i ca l g o r i t h m ，简称g a ) 是随机优化方法的一个新的正在发展的领 域，其基本思想是基于达尔文的生物进化论和蒙德尔的遗传学说，是模拟生物在 自然环境中的遗传和进化过程而形成的一种自适应全局优化概率搜索算法。 美国的h o l l a n d 3 9 1 于1 9 7 5 年最先提出了g a 系统的概念和方法，之后的几十 6 l 绪论 年时间里该算法得到了迅速的发展，广泛地应用于各种领域。近些年来，国内外 不少学者已经将遗传算法成功应用于给水管网的设计计算中，其中包括管径的技 术经济计算等 4 0 - 4 2 1 。遗传算法主要有三种编码方式：二进制编码、实数编码和自 然数编码。其中自然数编码在给水管网的优化计算中是最方便的。其过程为：对 离散型的标准管径进行自然数编码，随机产生一组初始群体，通过解码操作将个 体的基因信息译为管网优化的决策变量，经过管网水力计算求得水头损失、节点 水压等变量值，代入管网优化问题的目标评价函数，并计算出个体的适应度；通 过评价，按照适应度大小，优胜劣汰，组成优良亲本群体用于繁殖新一代，一对 对亲本的染色体及基因以一定的变换概率和变异概率经过随机地交换，变异生成 新一代群体；不断重复上述过程，使得群体适应度的平均水平逐代提高，直至产 生最优个体。 遗传算法的优势在于f 4 l 】：1 ) 算法思路简单，不受规划问题要求的可微、可导、 连续等限制，避免了线性规划解的“瓶颈”问题：以离散的标准管径为决策变量 也避免了非线性规划最后对连续管径进行“圆整”带来的麻烦与偏差；2 ) 由于遗 传算法从一组方案出发，扩大了搜索寻优的范围，减少了传统规划方法线性寻优 产生局部最优解与全局最优解差距较大的风险；3 ) 遗传算法的搜索一次性遍布整 个解空间，所以得出全局最优解的机会大大增加。不足之处在于耗机时太多、过 早收敛等。 此外，将遗传算法与其它一些方法结合使用，也是9 0 年代以来的新趋势，典 型的就是与模拟退火法结合的所谓遗传退火算法。胡卫权【4 3 】用模拟退火算法及遗 传算法编制了城市给水管网优化设计的计算程序，并作了适合管网优化设计的算 法改进，算例表明该方法收到了良好的经济效果。 蚁群算法 蚁群算法( a n tc o l o n ya l g o r i t h m ，简称a c a ) 是由意大利学者m d o r i g o h 4 5 1 等 人于2 0 世纪9 0 年代初首先提出来的一种崭新的求解复杂优化问题的启发式算法， 用此方法求解t s p 问题4 6 4 刀、j o b s h o p 调度问题档，4 9 】、指派问题m l 。它是继模拟 退火算法、遗传算法、禁忌搜索( t a b us e a r c h ) 算法、人工神经网络算法等之后的又 一种应用于组合优化问题的启发式搜索算法。 算法不仅能够智能搜索、全局优化，而且具有稳健性( 鲁棒性) 、正反馈、分布 式计算、易与其它算法结合等特点。就算法本身而言，可概括为算法实验性能和 算法的理论基础研究两个方面。在算法的性能上，蚁群算法存在着以下缺点：1 ) 当 规模较大时，算法效率下降得很快，需要较长的搜索时间。2 ) 容易出现停滞现象， 即搜索到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行 搜索，不利于发现更好的解，从而容易陷入局部最优。 7 重庆大学硕十学付论文 许多学者对此进行了研究，并提出了许多改进的蚁群算法。g a m b a r d e l l a 和 d o r i g ”1 提出了蚁群学习算法，该算法建立了蚁群算法( a c a ) 与学习算法( q l e a r n i n g ) 的联系，简称a n t q 算法，其信息素更新采用两种计算方法：一种是全局最好( g l o b a l b e s t ) 更新算法，另一种是每个循环内最好( i t e r a t i o n b e s t ) 更新算法。m d o r i g o 5 1 】在蚁 群算法以及a n t - q 的基础上提出了蚁群系统( a n tc o l o n ys y s t e m ，简称a c s ) ，其特 点是在蚂蚁探索路径的过程中应用局部更新，同时只对构成最好环游的弧集进行 全局更新，并采用二交换法【2 ，o p t ) 和三交换法( 3 o p t ) 局部搜索算法对蚂蚁构造的 解进行改进，得到了很好的求解效果。s t u t z l e 和h o o s i5 2 】提出了最大最小蚁群系统 ( m a x m i na n ts y s t e m ，简称m m a s ) 。其基本思想是：1 ) 每次循环结束后，只有 最优解所属路径上的信息量被更新，以此来加快收敛速度；2 1 为了避免搜索时出 现停滞现象，各路径上的信息量被限制在范围 r 。，r 。】内；3 ) 初始时刻，各路径 上的信息量取最大值r 。o 。b u l l n h e i m e r ，h a r d 和s t r a u s s i s 3 提出了a s ，对。采 用延迟更新方法，首先对全部蚂蚁构造的解依目标函数值由小到大排序，并选择 排在前边的盯只蚂蚁对f 。进行更新，排序越小，更新贡献量越大。d o r i g o 和c a g o t 5 4 】 把此前各种基于蚁群系统演化而得的算法归结到一个统一的框架中，称为a c o 元 启发算法( a n tc o l o n yo p t i m i z a t i o n ，简称a c o ) ，该启发算法近年来受到了广泛关 注。l e e ，j u n g 和c h u n g 5 5 l 主要提出了一种相遇算法。其基本思想是在求解旅行商 问题( t s p 问题) 中，用两只蚂蚁共同完成对一条路径的搜索，以提高搜索速度。 t s m ( 5 6 】提出了一种变异策略，其核心思想是采用逆转变异方式，随机地进行变异， 以增大进化时所需的信息量，此变异机制充分利用了二交换法简洁高效的特点， 具有较快的收敛速度。 国内一些研究者也对蚁群算法作了一些研究。吴庆洲”等从遗传算法中变异 算子的作用得到启发，在蚁群算法中采用了逆转变异机制，进而提出了一种具有 变异特征的蚁群算法，这是国内学者对蚁群算法所作的最早改进。覃刚力【5 8 】提出 了一种基于自适应调整信息素的改进蚁群算法。该算法根据人工蚂蚁所获得解的 情况，动态地调整路径上的信急素，从而使得算法跳离局部最优解。谢剑英【5 9 】通 过自适应地改变算法的挥发度等系数来克服蚂蚁算法易陷于局部最优点的缺陷， 并能够在保证收敛速度的条件下提高解的全局性。吴斌f 6 0 】先在蚁群算法的基础上 提出了相遇算法，提高了蚁群算法中蚂蚁一次周游的质量，然后将相遇算法与采 用并行策略的分段算法相结合，提出一种基于蚁群算法的t s p 问题分段求解算法。 近十年来，蚁群算法在许多不同的n p 一难的组合优化问题中的应用都显示了算 法的有效性，但是极少有理论来解释蚁群算法成功的原因。o u t j a “6 1 】给出基于图 的蚂蚁系统算法的收敛性证明，但该算法的性能有待于实验验证。s t u t z l e 6 2 】给出了 蚁群算法收敛性的简单证明，证明了两个定理，可以应用到两个应用最成功的a c o 1 绪论 算法：a c s 和m m a s 。 之后国外学者运用该算法在给水管网管径的优化上也做了大量的研究，其中 m a i e r t 6 3 l 等人采用蚁群算法进行给水管网的优化设计取得了较大成功，并指出蚁群 算法在给水管网管径的优化上优于遗传算法，随后国内学者也开始将蚁群算法应 用于给水管网中【叫。 随着研究者在这一领域的不懈努力，给水管网优化设计理论与方法日趋丰富， 涉及问题的深度与广度也日趋加强。但是给水管网可靠性问题还没有很好地解决。 在近几十年时间里，如何采用有效的方法解决给水管网可靠度的问题一直是工程 技术人员不懈努力的方向之一。给水管网可靠性的研究集中在两个方面，一是如 何将管网可靠性数值化，另外就是如何提高管网可靠性，即采取何种措施和何种 计算方法。一个合理的可靠度值，应是易于理解、物理意义实际且在计算上是可 行的。但是，尽管近十年来研究者们提出了多种可靠度值，但能够同时满足这三 项要求的可靠度值还没有。s u 等人【”】提出的可靠度值定义为管线破损条件下供水 量与正常供水量的比值，物理意义合适，但是在计算上却是不可行的，特别是在 优化过程中考虑可靠性几乎是不可能的，利用s u 等人的优化模型分析三环管网， 在兼容机上耗时2 0 0 5 分钟。f u j i w a r a 等人脚】将可靠度定义为管线破损条件下预期 最大供水量与总需水量的比值，同样，该可靠度值由于需要求多个最大供水量优 化模型，从计算的可行性上亦是不足取的。而那些能够融入优化计算过程，计算 上可行的可靠度值【6 7 】却又不能对管网运行提供真实的描述。o r m s b e e 和k e s s l e r 6 8 】 所提出来的考虑可靠度要求的管网优化设计方法是一种有价值的方法。该方法核 心思想是为每一用水节点选择两条独立的路径，然后求得对应的较少费用系统。 可是，按照现行设计规范，这种设计方法所设计出的管网1 0 0 可靠，但却投资大， 似无必要。当发现管网可靠性不足时，就必须采取措施提高管网可靠性，如为某 些管线添加平行管段，这就面临着如何选择添加位置，添加平行管段直径的大小 使提高管网可靠性所耗费用尽可能低。由于给水管网可靠度问题涉及到管网模型 中的诸多方面( 甚至包括施工、管理、材料等) ，而对可靠度的理论定义也无统一形 式。从用户角度来说，可靠性是在任何时间都能保证应有的水量和水压；从管理 角度，主要是指管网所需的修理、维护和更新费用最小。基于此，本文考虑从用 户角度出发，可靠性指能使所有用户都能维持足够的水压和水量。因此，基于可 靠度的优化设计是当前及今后一段时间内管网优化设计问题的一个重点和难点。 具体地说，如何在考虑管网可靠性的情况下，利用原有的线性或非线性的方法， 或者采用遗传算法、蚁群算法之类的新型智能方法进行优化设计，使之更接近城 市供水管网的工程实际，并进一步开发相应的软件，是今后研究者所关注的课题。 9 重庆大学硕+ 学位论文 1 3 课题的提出、研究目的和意义 近年来，学术界在给水管网优化技术领域进行了大量研究，取得了丰硕的成 果，促进了给水事业的发展。但是，这些研究大多局限于新建或扩建管网的优化， 相比之下，给水管网改扩建优化方面的研究未能得到足够的重视，管网改扩建优 化与新建或扩建管网优化不同，有着自己独特的一些性质，有必要在这方面进行 详细的研究。 在我国，大多数给水管网在建设初期就缺乏系统的合理规划，更谈不上合理 的改扩建，还有一些供水企业的供水管网现状图都是不完整的，为确保供水基础 设施可持续发展，对城市给水管网系统进行改扩建优化显得愈来愈重要。进行给 水管网系统改扩建优化设计，就是在符合城市发展规划要求前提下，即在城市供 水规模、城市的功能和布局、人口分布已知的情况下，从工程应用角度，在对现 有管网系统工况科学分析的基础上，根据对城市未来发展用水需求的预测，确定 系统中需要改造的管段及管径、新增管道的位置和参数。在充分发挥现有管网系 统设施功能的条件下，以管网的各项运行参数符合规范要求为约束条件，以最少 的投入保证供水，满足用户对水量、水压、水质的要求，提高供水效益。 根据重庆大学与四川省某市自来水公司的横向科研项目“某市给水管网改扩 建工程方案优化研究”的要求，在王圃教授的指导下，以改进的蚁群算法在城市 给水管网改扩建优化中的应用为硕士毕业论文的研究方向，对城市管网优化的整 个过程进行了系统的研究和阐述，并在此基础上研究城市给水管网的优化。利用 提出的研究方法，结合四川省某市城市供水管网改扩建工程实例，提出了经济合 理的优化方案。 随着我国经济发展的加速，国家对城市基础设施( 包括供水行业) 的投入不断增 加，大批资金彼用于城市的给水系统的改扩建项目。因此，研究给水管网改扩建 优化是一个具有较高经济效益和社会效益的课题。 1 4 课题的研究内容 给水管网改扩建优化是一个十分复杂的系统工程，随着用户对水质、水压、 水量要求的提高、供水规模的