（模式识别与智能系统专业论文）基于改进模拟退火算法的给水管网改扩建优化规划.pdf

基于改进模拟退火算法的给水管网改扩建优化规划 摘要 当原有的城市供水系统无法满足城市日常用水要求时，需要对给水管网进行改扩 建。给水管网改扩建优化设计的目标，就是以有限的建设资金投入，最大限度地提高 管网供水的综合效益。给水管网优化设计方法有多种，其中模拟退火算法作为一种有 效的全局最优算法，在解决大规模组合优化问题等领域得到了广泛的应用，同时它还 具有描述简单、使用灵活、运行效率高和较少受初始条件限制等优点，因此本文引入 模拟退火算法作为管网改扩建的优化算法。 模拟退火法是一种模拟金属退火的全局优化随机方法。本文对模拟退火算法进行 了详细的论述，并从缩减运行时间和提高解的质量这两方面考虑，对算法进行改进。 并以工大南区给水管网改扩建优化设计为例，分别采用模拟退火法、有记忆的模拟退 火法、回火退火法和快速回火退火法进行优化设计比较，从而得出满足水量、水压和 经济性要求的最优解及最优算法。 关键词：给水管网改扩建；优化设计；模拟退火算法；回火退火法 o p t i m a lr e h a b i l i t a t i o np l a no fw a t e rs u p p l yn e t w o r ku s i n g i m p r o v e ds i m u l a t e da n n e a l i n ga l g o r i t h m a b s t r a c t w h e nt h eo r i g i n a lu r b a nw a t e r s u p p l ys y s t e mc a n n o t m e e tt h ed a i l yd e m a n d r e q u i r e m e n t so fc i t y , w en e e dt or e h a b i l i t a t et h ew a t e rs u p p l yn e t w o r k t h eo b j e c t i v eo ft h e o p t i m a lr e h a b i l i t a t i o nd e s i g no ft h ew a t e rs u p p l yn e t w o r ki st om a x i m u mt h eg e n e r a b e n e f i to ft h ew a t e rs u p p l y 、析t ht h el i m i t e dc o n s t r u c t i o ni n p u t s t h e r ea leav a r i e t yo f m e t h o d si no p t i m a ld e s i g no ft h ew a t e rs u p p l yn e t w o r k ，i n c l u d i n gs i m u l a t e da n n e a l i n g a l g o r i t h m ，a ne f f e c t i v eg l o b a lo p t i m i z a t i o na l g o r i t h m ，w h i c hh a sb e e nw i d e l yu s e di n s o l v i n gl a r g ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m s s ai se a s yt od e s c r i b ea n dh a sh i 曲 o p e r a t i n ge f f i c i e n c ya sw e l la sf l e x i b i l i t y m e a n w h i l e ，i ta l s oc a no v e r c o m et h ed e p e n d e n c e o nt h ei n i t i a ls o l u t i o n t h e r e f o r ew ei n t r o d u c es aa so p t i m i z a t i o na l g o r i t h mf o rt h e r e h a b i l i t a t i o no ft h ew a t e rs u p p l yn e t w o r k s ai sag l o b a lo p t i m i z a t i o nr a n d o ma l g o r i t h mw h i c hs i m u l a t e st h ea n n e a l i n go fm e t a l i nt h i sp a p e r , s ai sd i s c u s s e di nd e t a i la n di m p r o v e di nt w oa s p e c t sh o wt or e d u c et h e r u n n i n gt i m ea n di m p r o v et h eq u a l i t yo fs o l u t i o n s t h e nac a s eo f t h eo p t i m a lr e h a b i l i t a t i o n d e s i g no fw a t e rs u p p l yn e t w o r ki nt h es o u t hc a m p u so fh e f e iu n i v e r s i t yo ft e c h n o l o g yi s g i v e na sa ne x a m p l ei nw h i c hw ea d o p tf o l l o w i n gm e t h o d si n c l u d i n gs a ，s a 谢lm e m o r y , t e m p e r - s aa n df a s t - t e m p e r - s a b yc o m p a r i n gt h er e s u l to ft h e s em e t h o d s ，w eo b t a i nt h e o p t i m a ls o l u t i o na n dt h eo p t i m a la l g o r i t h mt h a tm e e tt h er e q u i r e m e n to fw a t e rd e m a n d ， w a t e rp r e s s u r ea n de c o n o m i c a le f f i c i e n c y k e y w o r d s ：r e h a b i l i t a t i o no fw a t e rs u p p l yn e t w o r k ；o p t i m a ld e s i g n ；s i m u l a t e da n n e a l i n g a l g o r i t h m ；t e m p e r - s a 图2 1 图4 1 图4 2 图4 3 图5 1 图5 2 插图清单 哈代一克罗斯连续校正法平差计算框图1 2 给水管网改扩建计算流程框图2 8 模拟退火算法计算流程框图2 9 回火退火算法计算流程框图3 0 求管线建造费用公式中的系数a 值4 l 求管线建造费用公式中的系数b 、口值4 2 表5 1 表5 。2 表5 3 表5 - 4 表5 5 表5 - 6 表5 7 表5 。8 表5 9 表5 1 0 表5 1 1 表格清单 合肥工业大学南校区部分用水大户最高日用水量情况3 4 管段的编号、管长和管径3 7 住宅最高日生活用水定额及小时变化系数3 8 公共建筑的生活用水定额及小时变化系数3 9 水泵技术参数4 0 球墨管价格4 1 不更换管段编号以及管径4 3 有记忆的模拟退火法与无记忆的模拟退火法优化结果比较4 4 两种判断式的模拟退火法优化结果比较4 6 回火退火法与快速回火退火法优化结果比较4 9 三种算法的计算结果比较5 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 金肥王些太堂 或其他教育机构的学位或证书而使 用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说 明并表示谢意。 学位论文作者签字：割观甍签字日期：x 川年年月f2 日 学位论文版权使用授权书 本学位论文作者完全了解 金旦墨工业太堂 有关保留、使用学位论文的规定，有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人 授权 金筐王些太堂可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：刳观鼋 签字日期：) 川年印月j 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名： 泐新巧 签字日期：1 年年月f 、日 电话：| 6t s 易。啸。 邮编： 致谢 论文完成之际，也是我两年半的研究生学习阶段的结束，同时也是我告别 生活了近七年的工大校园的时候。回顾七年的点点滴滴，不论是生活，还是学 习，这段记忆都将永驻心底。 我要感谢我的导师徐得潜教授，本论文是在徐老师的悉心指导下完成的。 在两年半的研究生学习和撰写学位论文过程中，无论是课程学习、论文选题， 还是资料收集、论文成稿，都倾注了徐老师的大量心血。徐老师不仅在学业上 给予我关心和指导，在生活方面也给了我无微不至的关怀和照顾。在此，我向 徐老师表示由衷的感谢。徐老师广博的知识、严谨的治学态度和精益求精的工 作作风，对我影响深远，必使我在今后的学习、工作和生活中受益终身。 感谢李柱师兄，他在论文撰写过程中提供了大量帮助和指导。感谢我的同 学高慧慧、张丽丽、王莉莉、孟翔宇和许一，他们在生活和学习上给予我很大 帮助，让我体会到如兄弟姐妹般亲切的友谊。 感谢我的父母和弟弟，他们对我的无私奉献和默默支持，是我完成学业的 精神动力。我不会辜负他们的期望。 再次感谢徐老师和所有帮助过我的老师、同学和家人。 感谢对本论文进行评审和出席论文答辩的专家们，感谢他们在百忙之中为 我提出宝贵的意见和指导。 作者：刘晓莹 2 0 0 9 年3 月2 0 日 第一章绪论 一个城市给水系统在建成的一定时期内，即在预定的规划期限内，其供水 能力是可以满足用户要求的。随着社会经济的快速发展，用水人口的不断增加 和人民生活水平的日益提高，城市用水量急剧增长，给水管网的供水能力逐渐 不能适应用水量增长的需要。同时，由于给水管网规模的不断扩大，不少城市 在管线改造、铺设等方面缺乏统一规划，给水管网系统在管线连接、构筑物设 置等方面存在诸多不合理之处，增大了供水能耗，并使部分供水区域水量欠缺、 低压区面积不断扩大、供水可靠性降低。这时除了设法提高现有管网的输水能 力和设备的生产能力外，还须及时进行改建和扩建。 给水管网改扩建是在原有管网系统的基础上进行，既要充分发挥旧管网系 统的功能和作用，又要根据增大用水量、扩大供水范围的扩建要求对旧管网进 行改建，并同时扩建新管网，使新旧管网共同工作，满足城市的日常用水要求。 1 1 管网改扩建的要求 在给水管网改扩建时，既要充分利用现有构筑物，使其发挥应有的作用， 又要全面考虑技术、经济和环境等问题。故在管网改建和扩建时，应满足下列 要求： 以最低费用保证供水，满足用户对水量、水质和水压的要求； 给水系统的建造应不破坏环境的生态平衡； 构筑物施工时，尽可能采用先进的施工方法； 管网系统各项构筑物应做到应用方便、管理简单、发生故障的次数和漏 失的水量为最小； 考虑今后发展的可能性。 1 2 管网改扩建优化设计的目标 在给水管网的优化设计中，要考虑以下四个问题：水压、水量的保证性， 水质的安全性，可靠性和经济性。给水管网改扩建优化设计是一个复杂的系统 工程，既要充分发挥现有设施的作用，又要综合考虑技术、经济、供水安全、 管理和环境等问题。因此，给水管网改扩建优化设计的目标，就是以有限的建 设资金投入，最大限度地提高管网供水的综合效益。主要考虑以下几个方面的 内容【1 】： 使管网系统水压线密度分布趋于合理化，减少爆管频率，降低供水漏耗， 增强供水安全可靠性； 改善管网、泵站和水塔水池等的联合工作条件，减少供水时的电能浪费， 使管网年费用折算值达到最小； 改扩建后的管网，工作状况得到改善，整体结构趋于合理，供水成本有 所降低。 1 3 给水管网优化设计方法1 2 - 1 0 l 管网优化设计是组合优化设计问题，其优化设计方法主要有两大类：传统 的确定性优化方法和随机性优化方法。自提出给水管网优化课题以来，前人已 在这一领域做了研究和探索工作，取得了大量的研究成果，并发展了不少的优 化方法。其中代表性的优化方法有： i 3 i 枚举法1 2 j 用枚举法进行管网优化设计计算，是从用户指定的各组管径序列中对各个 管段进行最优管径组合，从中选出最符合优化目标的方案，从而达到最优化设 计目的。 枚举法是一种全局搜索算法，它对目标函数要求低，优化原理简单可靠， 搜索到的结果是全局最优解，但枚举法的最大缺点是在优化过程中计算机的消 耗时间多，对大型管网系统，甚至难以完成计算。现在有学者提出了基于改进 枚举技术的优选管径法，它通过管段分组、管径现在范围验证、投资验证、水 压验证等手段提高了枚举法优化速度，但其庞大的计算量仍是枚举法技术无法 得到广泛应用的主要原因。 1 3 2 线性规划法 2 0 世纪7 0 年代末，a l p e r o v i t s 和s h a m i r ，q u i n d r y 相继提出线性规划模型， 至今仍有广泛影响，但管网的规模受到了限制。俞国平教授提出了以管长为决 策变量的线性规划模型。主要是在满足节点方程的条件下分配管段流量，然后 在每根管段上划分若干区段，根据管段流量，在这些区段上适宜地选定若干规 格管径，但各区段长度未知，于是目标函数就变成了以区段长度为变量的线性 规划问题。这种以管长为决策变量的线性模型不必调整管径，避免了调整管径 后偏离最优解的情况，而且便于求解，运用单纯形法求解即可。 1 3 3 广义简约梯度法【3 】 广义简约梯度法( g e n e r a l i z e dg r a d i e n tm e t h o d ，简称g r g ) 的基本思想是 把变量分成自变量和因变量两个部分，将因变量由约束条件解出，以自变量表 示，再利用简约梯度直接构造一个使目标函数改善的可行方向，沿次方向进行 搜索，从而找到一个新点，逐步逼进原问题。 给水管网优化设计的目标函数及约束条件属于非线性约束下的非线性规划 问题，广义简约梯度法( g r g ) 是目前求解此类问题较为有效的方法。采用该法 需要解决的主要问题是如何将自变量区分为基本变量和非基本变量。根据管道 系统的特点，当管径确定以后，管网中的管段流量及水头损失可通过水力计算 方程得出，当控制点的水压已知时，管网内其它节点水头也就随之确定，即管 径d 与节点水压h 之间存在非线性函数关系。因此可将管径作为非基本变量， 节点水压作为基本变量，直接以管径d 作为优化对象，以管网水力计算方程作 为约束条件，建立起不需要预先假定管段流量分配的管径优化数学模型。 1 3 4 遗传算法 4 - 5 j 遗传算法( g e n e t i c a l g o r i t h m s ，简称g a ) 是随机优化方法的一个新的正在发 展的领域，它继承了达尔文的进化论思想。19 7 5 年，美国的h o l l a n d 等提出了 g a 系统的概念和方法。1 9 8 7 年，g o l d b e r g 等将这一理论应用于管网优化设计 中。这一方法采用离散的标准管径为决策变量，并对其进行一定进制的编码， 通过选择、杂交和变异等迭代操作因子，进而求得满意的结果。基因算法主要 有三种编码方式：二进制编码；实数编码；自然数编码。其中，自然数 编码在给水管网的优化计算中是最方便的。其过程为：对离散型的标准管径进 行自然数编码，随机产生一组初始群体，通过解码操作将个体的基因信息译为 管网优化问题的决策变量，经过管网水力计算求得水头损失、节点水压等变量 值，代入管网优化问题的目标评价函数，并计算出个体的适应度；通过评价， 按照适应度的大小，优胜劣汰，组成优良亲本群体用于繁殖新一代，一对对亲 本的染色体及基因以一定的变换和变异概率经过随机地交换、变异生成新一代 群体；不断重复上述过程，使得群体适应度的平均水平逐代提高，直至产生最 优个体。虽然g a 的搜索方式具有很大的随机性，可实践已证明对于任何管网 的系统优化设计，都能得到全局最优解或趋于全局最优的解。这种方法也存在 着一些缺陷，如计算效率低( 与非线性规划模型相比) 、过早收敛等。 1 3 5 模拟退火算法【6 d j 模拟退火法( s i m u l a t e da n n e a l i n g ，简称s a ) 是由s k i r k p a t r i c k 于2 0 世纪8 0 年 代初提出的一种模拟金属退火的全局优化随机方法。模拟退火算法的得来是基 于对物理退火过程的分析。在金属退火处理过程中，常将它加热熔化，使其中 的离子可以自由运动，然后逐渐降低温度，使离子形成低能态的晶体。不同的 冷却过程，可以使得离子达到不同等级的能量状态，这一过程与金属的初始状 态无关，如果冷却速度足够慢，则金属将达到最低能量的基态。模拟退火算法 通过采用随机模拟物体退火过程来完成问题的求解。也就是在控制参数( 温度) 的作用下，对参数的值进行调整，直到所选取的参数值使能量函数达到全局极 小值。它结合了统计物理学和局部搜索的方法和原理求解问题的全局解。理论 己证明在连续情况下可将概率1 收敛到全局最优点。用s a 来解决管网优化这样 复杂的问题，实践证明可以取得令人满意的结果。它从任意一个标准管径初始 可行解开始，并用某一机制( 交换、查找、逆转) 产生邻域解，用水力约束条件 控制计算流程，用m e t r o p o l i s 准则进行判定，如此迭代下去直到得出满意解。s a 算法的收敛速度依赖于初始温度、降温速率及整个算法过程的其他随机操作。 与g a 法类似，由于理论最小迭代次数无法确定，s a 法也存在着计算效率偏低 的问题，仍需要作进一步研究，可它的优势也是显然的。首先，以离散的标准 管径为空间搜索点，管径不必调整。其次，随机产生领域解及m e t r o p o l i s 准则的 引入，都避免了陷入局部最优解的发生。 该方法在求解组合最优化问题时，理论上已被证明在满足一定条件的某种 问题函数下，模拟退火法可收敛到问题的最优解。因此它可以用于求解各种优 化问题，在大系统优化方面更是引起人们极大的关注。 1 3 6 神经网络方法i l o 】 神经网络方法( a r t i f i c i a ln e u r a ln e t w o r k ，简称a n n ) 求解优化问题的关 键思想是将问题映射到一个神经网络动力系统，写出相应的满足问题约束条件 的能量函数表达式和动力学方程，选取适当的参数值以保证网络的稳态输出， 在网络动力学方程自动演化到平衡位置后，即可搜索到相应的( 局部) 最优解。 自h o p f i e l d 和t a n k 在8 0 年代中期给出第一个求解优化问题的神经网络， 并在货郎担问题( t s p ) 上取得了成功以后，就掀起了一股遍及各个学科的神经网 络热潮。由于神经网络采用了微分方程这样的数学工具，因而开启了用动态方 法解静态问题的大门。在具体实现上不仅可用软件模拟，而且可以制成硬件电 路，因而拥有广泛的应用前景。 1 4 本课题研究内容 ( 1 ) 在给水管网改扩建优化设计中，模拟退火算法作为一种有效的全局最优 算法，在解决大规模组合优化问题等领域得到了广泛的应用，同时它还具有描 述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制等优点，因 此本课题采用模拟退火算法作为管网改扩建的优化算法。 ( 2 ) 在优化算法中，最重要的就是运行时间和解的质量，因此，本课题从这 两个方面考虑，通过提高各环节的时效和增大控制参数来跳离“陷阱”，以缩减 运行时间和增加解的质量，从而对算法进行优化。 ( 3 ) 在管网改扩建的优化设计中，主要是管径的优选，因此本课题主要针对 给水管网改扩建中的管径优化，采用模拟退火算法进行优化计算，并提出几个 改进的方法，同时对其进行计算比较，从而得出满足水量、水压和经济性要求 的最优解以及最优算法。 第二章给水管网改扩建计算 给水管网是一个由管线、二级泵站、加压泵站、水库、水塔等部分组成的 系统。管网改扩建是在已有管网的基础上，决定如何经济合理增敷新管，挖掘 现有旧管网的输水能力，协调新旧管网的功能。与新建管网优化设计相比，旧 管网的存在使改扩建有自己独特的性质。因为优化问题的目标函数中也包含了 旧有管段的不合理存在，这些往往由经验设计的旧管段，大大影响整个管网的 运行费用。从节能的角度，在扩建管段寻优的同时，要对不合理的旧管段进行 改造。那么旧管段的改造需要解决两个问题：( 1 ) 在什么地方敷设新增管道；( 2 ) 增敷管线的经济管径怎么确定。扩建与新建的区别是：扩建设计中新旧管道交 错，流量分配的作用非常复杂，因此如何对改造管道的布局寻优，如何在充分 利用原有供水管道供水能力的情况下，对需改造、扩建的管网进行优化，比新 建设计更为复杂。 给水管网改扩建时，要进行水力计算和技术经济计算。前者是求出各管段 的流量和水头损失，以及各节点水压；后者是确定新铺管线或拟更换管线的最 优路径和经济管径。由于给水管网的改扩建设计与新建管网设计相比，设计变 量、约束边界条件增多，加上某些变量的不确定性，故导致进行管网改扩建设 计的难度要比新建管网设计大得多，设计的方法、程序也不同。 2 1 管网水力计算 2 1 1 管网计算基础方程【1 , 1 1 - 1 3 】 管网计算的目的在于求出各水源点的供水量、各管段流量和管径以及全部 节点的水压。管网计算的基本原理是基于质量守恒和能量守恒。其基础方程为 连续性方程、能量方程、压降方程和虚环方程。设尸为管网中的管段总数，s 为 配水源数，为节点数，包括配水源节点，三为环数，则未知量为p 个管段流 量q 盯和水头损失h f ，s 个配水源供水量和，个节点水压日f ，共计p + ，+ s 个未 知量。 连续性方程，是指对任一节点来说，流向该节点的流量必然等于流出该 节点的流量，即要满足节点流量平衡的条件，方程如下： q j ，+ q f = o ( 2 一1 ) 式中，q f 为节点f 的流量；q 打表示与节点f 相连接的各管段流量，f ，为其起、 止节点编号。对于节点数为，配水源数为s 的管网，可以写出，一s 个节点连 续性方程。 能量方程，是指管网每一环路中各管段水头损失之和必等于零。因为任 一环都形成封闭的环路，故取顺时针方向为正，逆时针方向为负，能量方程为： h 一胡七= 0 ( 2 - 2 ) l 式中，h f ，为基环k 的各管段水头损失；a - 意为基环k 的闭合差或增压和减压装 置产生的水压差。在单水源管网中，埘七= 0 ；若脯七不等于零，则在环的方 向上，水压增高时取正值，水压降低时取负值。在多水源管网中，肼七为两个 配水源的水压差。 压降方程，是指管段的水头损失与该管段两端节点水压的关系。根据能 量守恒定律，该管网两端节点水头损失之差，应等于该管段的压降。同时在管 网计算中，一般不计局部阻力损失，则流量g 和水头损失h 的关系，可用指数 型公式表示如下： h u = h i h j = i s r g 孑 ( 2 _ 3 ) 式中，h f ，h ，分别为管段两端节点f ，的水压高程；h | ：为管段水头损失，m ；s v 为管段摩阻；9 f ，为管段流量，m 3 s 。玎= 1 8 5 2 - - - 2 ，根据所采用的水头公式不同 而定，对于海曾威廉公式( 适用于较光滑的钢管) ，n = 1 8 5 2 ；对于舍维列夫 公式( 适用于旧钢管和铸铁管) ，n = 2 。 如考虑水流方向，并假定各管段的h 和g 的符号相同，可以写成： h = s 舻1g ( 2 4 ) 虚环方程，是指有关管线的水头损失与配水源之间的关系，可用下式表 示： f ( q ) l f ( q ) k = ( 2 h ) 1 - k ( 2 _ 5 ) 式中，f ( q ) 表示配水源的流量和水压特性。 2 1 2 水头损失计算 在管网计算时需要确定管线的水头损失，包括沿程水头损失和局部水头损 失。前者是克服管线摩擦阻力而损失的水头，它随着管线长度的增加而增加， 所以又称长度损失。后者是水流通过弯管、渐缩管、分流管、阀门或其它附件 时产生的水头损失。由于在给水管道中，局部水头损失和沿程水头损失相比， 其值很小，因此，在管网分析计算中，局部水头损失通常忽略不计。 在管网优化计算中，常因管线材料的使用不同，而导致管网水头损失计算 公式也不尽相同，本文列出在管网计算过程中常用的四种水头损失公式j 。 ( 1 ) 舍维列夫公式 适用于旧铸铁管和旧钢管的水头损失计算。 v 扎2 m s 圳o o l 。7 斋 ( 2 - 6 ) 1 ， 1 2 m s 圳o o 嗍2 斋( + 半) 0 3 7 ， 式中：1 ，流速，m s d 水管的计算内径，m 。 ( 2 ) 巴甫洛夫斯基公式 适用于混凝土管、钢筋混凝土管和渠道的水头损失计算。 v=c4m(2-8) 式中：矿流速，m s ； ，水力坡度； r 水力半径，n l 。 c ：= ! r y 门 式中：c 谢才系数，( m 1 陀s ) ； 聆管壁粗糙系数，一般为 ( 2 9 ) 0 0 13 o 0 1 4 ，水