（模式识别与智能系统专业论文）城市雨水管网系统优化设计研究.pdf

城市雨水管网系统优化设计研究 摘要 随着城市化进程的高速发展，作为城市重要基础设施，雨水管网的建设取 得了重大进展。但是，由于雨水管网具有短时流量大的特点，所以相应的管网 系统的投资费用在市政投资中占了相当大的比例。因此，对雨水管网进行最大 限度的优化设计，将会减少大量的投资费用，取得最佳的经济效益。而近年来， 随着应用数学和计算机技术的不断发展，使得这种最优化设计成为可能。 本文首先分析了雨水管网费用函数各主要影响因素和目标函数的非线性 特性，推求出新的雨水管网费用函数形式，通过使用m a t l a b 遗传算法工具 箱( g a d s ) 对造价目标函数的非线性参数拟合，验证了新的造价目标公式的精确 性和使用遗传算法进行参数拟合的可靠性。 因为城市雨水管网的最优布局为树状结构，所以对于雨水管网可以用图论 中的树形结构理论来描述。本文从雨水管网的网络特性分析入手，结合图论的 原理和方法，在以上分析的基础上，选择f r a n k w o l f e 算法为求解算法对方程组 进行求解，在求解过程中以f o r d 算法进行最短路径的选择，形成排水管网规划 优化设计的一整套解决方法，同时，用m a t l a b 计算机语言编写了排水管网规 划优化设计的计算机程序，使所提出的规划方法具有更好的实用性。 最后，将该优化设计方法应用到罗河新区的雨水规划的实例中，验证了基 于图论法编写的程序可行性，并将程序计算结果和简单水力计算结果进行费用 函数对比分析，验证了该方法的工程价值。 关键词：雨水管网；遗传算法；m a t l a b ；非线性参数拟合；图论 o p t i m i z a t i o nd e s i g nf o ru r b a nr a i n w a t e r p i p e n e t w o r k ss y s t e m a b s t r a c t w i t ht h e r a p i dd e v e l o p m e n to f u r b a n i z a t i o n ，a sa ni m p o r t a n tu r b a n i n f r a s t r u c t u r e ，c o n s t r u c t i o no fr a i nw a t e rp i p en e t w o r kh a sm a d e s i g n i f i c a n t p r o g r e s s b e c a u s eo ft h eh i g hp e a kf l o wo fs t o r md r a i n a g ep i p e s ，s ot h es c a l eo f s t o r md r a i n a g en e t w o r k sm o r ei n v e s t m e n ti s r e q u i r e d t h e r e f o r e t h eo p t i m i z e d d e s i g no fs t o r md r a i n a g en e t w o r k sw i l lr e d u c ec o s ta n dg e tt h eb e s te c o n o m i c p e r f o r m a n c e r e c e n t l y , w i t ht h ed e v e l o p m e n to fa p p l i e dm a t h e m a t i c sa n dc o m p u t e r t e c h n o l o g y ，t h eo p t i m i z e dd e s i g no fs t o r md r a i n a g en e t w o r k sb e c o m e sf e a s i b l e a tf i r s t ，t h i st h e s i sa n a l y z e dt h en o n l i n e a rc h a r a c t e r i s t i c so ft h eo b i e c tc o s t l u n c t i o no fs e w e rn e t w o r ka n d s t u d y i n gt h eu s u a lm e t h o d so fo p t i m i z i n gt h e h y d r a u l i cp a r a m e t e r s ，a n dt h em e t h o df o rt h en o n l i n e a rp a r a m e t e r se s t i m a t i o nb y t h em a t l a b g e n e t i ca l g o r i t h ma n dd i r e c ts e a r c ht o o l b o x ( g a d s ) i s p r o p o s e d ，a n d i tc a no b t a i no p t i m i z a t i o nw i t hi t sm e r i to fu n i v e r s a la n da c c u r a t er e s u l t b e c a u s et h eb e s tl a y o u to fas t o r md r a i n a g en e t w o r k si s u s u a l l yt r e e s h a p e d ， t h et h e o r yo f t r e e 。s h a p e ds t r u c t u r ec a nb ea p p l i e dt os t o r md r a i n a g en e t w o r k s i n s u c c e s s l o n ，o nt h eg r o u n d so fa n a l y z i n gt h en e t w o r kc h a r a c t e r i s t i co fs t o r m d r a i n a g en e t w o r k s ，c o m b i n i n gw i t ht h eg r a p ht h e o r ya n dt o o l s ，b a s e do nt h ea b o v e d i s c u s s i o n ，t h e nt h ef l o wd i s c h a r g ed i s t r i b u t i n gm e c h a n i s ma n dt h em a t h e m a t i c a l p r o g r a m m i n gm o d e li so f f e r e da n dt h ef r a n k - w o l f ea l g o r i t h mi ss e l e c t e da st h e s o l v i n ga l g o r i t h m ，i no r d e rt of o r ds h o r t e s tp a t ha l g o r i t h mf o rt h ec h o i c eo ft h e s o l u t i o np r o c e s s t h e r e b y ，t h ec o m p l e t es e to f s o l v i n gm e t h o di sf o r m e d a d d e dt o t h i s ，t h ec o m p u t e rp r o g r a mo ft h es e w e rs y s t e mp l a no p t i m i z a t i o ni sd e s i g n e db y m a t l a b ，w h i c hm a k et h em e t h o di n t r o d u c e dt a k eo nt h eb e t t e rp r a c t i c a b i l i t v f i n a l l y , t h i sm o d e li sv e r i f i e db yi t sa p p l i c a t i o no ne n g i n e e r i n gp r o j e c to ft h e l u o h ed i s t r i c ts t o r md r a i n a g en e t w o r k sa n dv a l i d a t e dm e t h o db a s e do ng r a p h t h e o r y p r o c e d u r e sf o rt h ep r e p a r a t i o no ft h ef e a s i b i l i t y c o m p a r et ot h et r a d i t i o n a ld e s i g n m e t h o di n e c o n o m y , t h er e s u l ts h o w st h a tt h i sm e t h o dh a sc e r t a i np r a c t i c a lv a l u e k e yw o r d s ：s t o r md r a i n a g en e t w o r k s ；g e n e t i ca l g o r i t h m s ；m a t l a b ；n o n l i n e a r p a r a m e t e re s t i m a t i o n ；g r a p ht h e o r y 插图清单 图2 1 图和有向图8 图2 2 具有一个交汇点的雨水管网1 1 图3 1 为管沟挖深与断面积关系曲线图2 3 图3 2 鱼刺式( 双侧平行布管) 2 3 图3 - 3 木梳式( 单侧布管) 2 4 图3 4 篦子式( 双侧布管) 2 4 图3 5 分离的木梳式( 双侧布管) 2 5 图3 6 管道对接方式有管顶平接、管中接、管底平接、跌水接一2 6 图4 1 遗传算法g u i 参数拟合计算结果图3 4 图4 2 最佳适应度值和平均距离图3 4 图5 - 1 节点并编号图4 5 图5 2 生成树及初始流量分配图4 6 图5 - 3m a t l a b 程序计算结果图4 6 图5 - 4 矩阵f 转化图4 7 图5 - 5 优化方案雨水管布线图4 8 图5 6 原方案雨水管布线图4 9 表3 - 1 表4 - 1 表5 - 1 表5 - 2 表5 - 3 表5 - 4 表5 - 5 表格清单 管沟挖深与断面积的关系表( 单式边坡) 2 2 不同管径与埋深对造价的影响单位：元1 0 0 m 3 3 规划用地汇总表4 1 径流系数一览表4 3 重现期一览表4 3 雨水干管投资估算表5 0 原设计方案雨水干管投资估算表5 0 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。 据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰 写过的研究成果，也不包含为获得 佥照互些太堂 或其他教育机构的学位或证书 而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意。 学位论文作者签名： 签字日期：z d l o 年斗月2 7 日 学位论文版权使用授权书 本学位论文作者完全了解盒壁王些太堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金罡王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名。 岔诅 签字日期：洲d 年坪月刁日 学位论文作者毕业后去向：辱眺 工作单位： 通讯地址： 导师签名： 签字日期：l 年矿月7 日 电话：i 麒o l 秘妒 邮编： 致谢 在本论文完成之际，首先感谢合肥工业大学给我的这个学习和提高的机会， 本文凝聚了我的导师沈致和教授和同学们的关心与帮助，在此向他们表示衷心 的感谢! 导师渊博的专业知识、严谨的治学风范和敏捷的思维能力使我获益匪浅， 永生难忘! 在论文撰写过程中，导师从论文的选题、资料的搜集整理到论文的 构思、总体框架的设计、参考文献的推介直到论文的格式都进行了精心的指导， 并提出许多宝贵意见。在此，谨向恩师表示衷心的感谢和最美好的祝愿! 在研究生学习阶段和论文选题的过程中，还得到了王军教授、陈慧副教授、 祝健副教授等老师的精心指导和帮助，感谢各位老师在学术活动中提出了许多 建议和思路，使我的论文得以顺利完成，在此，对他们表示诚挚的谢意! 同时， 也向本论文的评阅人和答辩委员们表示衷心的感谢，感谢各位专家和教授在百 忙之中给予的指导和建议! 在论文的撰写工作中，得到了汪宏学长、李晓琪、吴空、余轶鹏等的帮助， 此外我的同学和朋友们给予我莫大关心和鼓励，尤其是刘彦涛、刘天伟、郑昊 等在此真诚的祝愿他们学业有成，工作顺利，生活幸福! 最后，我要感谢我的家人和潘红对我学习的支持和鼓励，再次感谢在学习 和生活中所有对我支持和帮助过的老师、同学和朋友们! 李阳 2 0 1 0 0 4 于合肥 第一章绪论 1 1论文研究背景 人类社会在创造文明的同时产生了城市。近年来，由于经济的高速发展， 全球加快城市化进程。随着城市化进程的发展和大都市的出现，人口密度不断 增加，城市开发规划范围不断扩大。城市化是一个国家现代化水平的重要标志， 是人类文明进步的必然结果，是人类社会发展的必然趋势。 自2 0 世纪8 0 年代以来，随着我国改革开放力度的加强，社会经济的飞速 发展，我国的城市化也迈入了快速发展时期。我国的城市由3 2 4 个增加到6 7 0 个；城市化水平也由2 3 7 1 增长到2 9 0 4 。根据相关预测，2 0 1 0 年中国城镇 人口将达6 5 亿左右，城市化水平将达到4 7 ，平均年增长速度为o 8 个百分 点。城市人口的增加，将导致城市的用水量的剧增，对城市的给水排水工程设 施的需求也将要提高【2 】。 由于社会财富不断向城市集中，城市生产力不断扩大，人类在世界上制造 了一种新的生态系统一一人工城市生态系统。城市化的发展影响着城市的水文 效应、水文环境和排水系统，给城市的内涝排泄、城市环境、城市防洪等带来 系列新问题，一般来说，城市化对水文情势的影响主要表现在以下几个方面： ( 1 ) 在降水方面 通过对上海市水文总站在上海老市区1 4 9 k m 2 内设置的1 3 个雨量点和原有 分布在郊县的5 个雨量站平行观测，以研究城市化对上海市区降雨影响的程度 和范围【3 】。得出的结论主要有一下几个方面： ( a ) 市区降雨量要比郊区降雨量大，平均增雨量为6 ； ( b ) 时空分布不均趋势明显，以市区为中心向外依次减小： ( c ) 对不同量级降水雨日发生频次的影响：具体为城市化使暴雨雨日增多， 故当雨量达暴雨级后，市区雨日不再增加。 ( 2 ) 在蒸发方面 在城市化条件下，蒸发的变化较为复杂 4 - 6 一方面，因为城市的受热量和蒸 发表面积较大造成了蒸发能力提高；另一方面，随着城市化、市政工程建设的 完善植被覆盖率的逐步减少，地表的滞水能力降低，城区可供蒸发的水量减少， 局地蒸发量减少，绝对湿度也比非城市化地区低。 ( 3 ) 在产流方面 由于城市化的加深天然流域下垫面已经变为楼屋顶、道路、街道、高速公 路、公园等不透水地表，这使不透水面积大大增加，从而使地面下渗能力减弱， 造成地下水位降低，壤中流和基流减少，而地表径流系数、径流总量、洪峰流 量显著增加强l 。 ( 4 ) 在对汇流方面 影响流域汇流的下垫面因素主要是水系形状、坡度及河道的比降与糙率等。 城市地区不透水地表坡度增大、糙率减少，地面汇流速度加快；再者城市排水 系统管网化，且多数采用混凝土管道，管道坡度大，糙率小，相对来说水力半 径增大，使径流的汇流时间缩短，因此，对于一场相同时空分布的净雨，由于 流域汇流速度随着城市化程度而加快，其所形成的洪水过程线将越来越尖瘦， 峰现时间将越来越提前瞵j 。 由于城市化的建设和路面普及率的提高，地面的保水、滞洪能力的下降， 雨水的径流量变大，通过贮留系统的建立，即可以避免水淹之害又可以以雨水 作为城市水源，缓解供水压力紧张。 1 1 1雨水管道系统的组成及特点 雨水来自两个方面，一部分来自屋面；一部分来自地面。屋面的雨水通过 天沟和立管流至地面，然后随地面雨水一起排除。地面上雨水通过雨水口流入 街坊( 庭院) 雨水管道或街道上的管渠。雨水管网系统由下列几个主要部分组 成： 1 、室内雨水管道系统及设备。 2 、室外雨水管道系统。主要分布在室外的道路上，依靠重力流输送雨水至 泵站、或受水体管道系统称室外雨水管道系统。室外雨水管道系统又可以分为 居住小区管道系统和市政道路雨水管道系统。 ( a ) 居住小区雨水管道系统。敷设在小区内，连接建筑物出户管的雨水管 道系统。 ( b ) 市政道路雨水管道系统。敷设在市政道路下，用以排除居住小区管道 流来的雨水。它由雨水支管、干管、主干管等组成。 ( c ) 管道系统上的附属构筑物。有雨水口、雨水连接管、检查井、跌水井、 倒虹管、雨水提升泵站等。 3 、雨水泵站及压力管道。雨水一般以重力流排除，但往往由于受到地形等 条件的限制而发生困难，这时就需要设置泵站。泵站分为局部泵站、中途泵站 和总泵站等。 4 、出水口及事故排除口。 ( a ) 雨水排入水体的渠道出口称出水h ，它是整个城市雨水排水系统的终 点设备。 ( b ) 事故排出口是指在某些易于发生故障的组成部分面前，所设置的辅助 性出水渠，一旦发生故障，雨水就通过事故排出口直接排入水体。 1 1 2雨水管网系统优化设计的必要性 2 雨水管网系统是给水排水工程的一个重要组成部分，由于雨水管网的管径 埋深相对于污水系统都比较大，在整个排水系统投资中占有的比例也很大。同 时雨水管网系统又是现代化城市重要的基础设施，是城市防洪的骨干工程。城 市排水管网规划优化问题研究的主要就是通过优化计算方法寻找最优的用于排 水管网新建或改造的建设投资方案，即研究如何能用最少的资金投入达到使整 个排水管网系统中某种指标最优的目的，这些指标可以是使整个排水管网的工 程建设投资最小，也可以是使整个排水管网所能服务的区域最大等，从而为市 政建设决策部门和有关人员提供科学、合理、有效的方案和数据，使政府的有 限资金投入能取得最佳的投资收益【5 】。 如今，随着计算机技术的发展，计算机己渗透到人们生活和工作的各个方 面。通过编制程序和软件来对大型工程建设进行设计和优化，已经得到广泛的 应用并被人们所认可。 1 2 研究的目的和意义 计算机技术的发展和优化理论的不断完善，如何利用计算机和优化理论在 排水管渠系统设计中己成为市政工程设计中十分关注的课题。传统的排水管网 设计方法中，设计者往往能根据以往设计经验进行初步的优化选择，并且尽量 设计达到技术上先进、经济上合理，其技术条件经济分析一般都要考虑几个不 同布置形式的方案比较。雨水管网系统是一个庞大和复杂的系统，其优化设计 一般包括两个方面：雨水管网系统平面定线优化设计和雨水管网己定线时管径 和埋深及泵站设置的优化设计。作者主要研究前者，即雨水管网系统平面定线 优化设计。 雨水管网的优化设计，其主要目标是使雨水管网费用最小，而雨水管网系 统的造价主要受设计管段管径和埋深的影响。对于己定线的雨水管网系统，管 网造价的主要影响因素是设计管段的管径和埋深。而在水力模型中管径和埋深 是计算的核心，因此通过水力模型和目标函数之间的函数关系，就可使在利用 优化算法优化水力参数的同时，使雨水管网费用函数最小，即实现用数值计算 方法解决雨水管网系统设计优化的问题。 管网的布局方案比较的基础是费用函数，而费用函数又取决于管段参数的 设计问题，管段的优化设计可为管网布局方案的比较提供可靠的依据。 1 3国内外研究的现状和发展 1 3 1 国外研究的现状 根据国内外近年来的研究和发展趋势，雨水管网系统设计方法的研究大 致可分为三个方面： ( 1 ) 雨水管网系统的设计流量； ( 2 ) 管道平面布置方案拟定情况下管径、埋深和提升泵站位置的优化设计 研究。 ( 3 ) 管线平面布置方案的最优选择 对雨水设计流量的研究，国外己经有了很多研究成果，例如s a i n t v e n a n t 方 程组，s v 方程组是国际上公认的反应水流非恒定特性的较理想的方程组，但 s v 方程组至今尚无解析解，常用的近似求解方法有动力波模拟法、运动波模 拟法、弥漫波模拟法、半稳定动力波近似法。美国的b e nc y 教授对确定非稳定 流状态的管道中的峰值流量也提出了一种新的方法【7 】。 对排水系统( 包括雨、污水) 平面设计的研究，由于计算过程中不确定因素 很多，求解方程较为困难。j g l i e b m a n 在研究中就抛开了水力因素，仅考虑挖 方费为优选依据，先假定初始方案然后用试算法逐个调优。后来y a r g a m a n 和 l w m a y s 等引入排水线的概念，将所有可行的管线敷设路径组成的图分割成多 个阶段，用一多阶段的决策过程表示管线平面设计方案的优选课题，并用动态 规划求解，该模型考虑了水力因素，但由于排水线的引入，寻优过程的搜索范 围被限制在平面布置方案可行域的很小一部分内，所以不能保证寻优的结果是 最优的。g a w a l t e r 将此法稍事简化后应用于市政道路排水系统的优化设计中， 并取得一定的成果。为了解决上述问题p r b h a v e 和l ，f b a r l o w 将网络图论中的最 小生成树算法引入到排水管道系统平面布置优化中，但对于排水管道系统所有 可能的管线敷设路径组成的图，各边的权值在平面布置方案确定之前是未知的， 因此，排水管道系统平面设计方案的优选是图论中的变权问题，尚无有效的解 决办法。在上述文献中将平面布置方案的优选课题简化为图论中的定权问题来 求解并假定一套管径和坡度，从而避开了水力因素。s t e k e l i 和h b e l k a y a 贝l j 采用 三种权值：( 1 ) 以各管段道路坡度的倒数为权，( 2 ) 管长为权，( 3 ) 在满足最小覆 土约束条件下按最小坡度设计所对应的挖方量为权，然后对这三种权值运用最 短路径生成树算法求管线平面布置方案，再分别对求得的管线平面布置方案进 行管径、埋深和提升泵站位置进行优化设计，取投资费用最小的设计方案为最 优方案。 1 3 2 国内研究的现状 自7 0 年代起，在给排水管道和处理工程系统方面，我国同美国、日本和欧 洲的一些发达国家一样，在方法学和计算机程序上取得了各种研究成果，为全 面展开优化设计奠定基础。目前大多数研究都是基于管网定线下的优化，常用 的解决这一问题的基本方法有：线性规划、非线性规划、动态规划和遗传算法 等。相比之下，动态规划的应用较为成功，其主要原因是该法对对目标函数和 4 约束条件的要求比较低。动态规划法主要是由同济大学的杨钦、陈霖庆和俞国 平教授最先提出来，但是动态规划计算时并没有充足的证据能够证明阶段状态 的“无后效应”以及计算过程中所需要的存储量大和计算时间长的缺点。为了 解决这些缺点同济大学的张景国博士在前人的基础上提出以拟差动态规划法进 行雨水管网的优化设计，在计算过程中逐步求精，减少了存储量需求，取得了 比较成功的结果，其理论已经在实践中有所应用。同样李贵义博士提出把解有 约束的非线性凸规划问的简约梯度法引入到给排水管网系统优化设计中，该方 法考虑到了水力因素，取得了较为满意的结果，但给排水管网系统优化并非严 格的凸规划问题，在求解过程也有缺陷。 另外杨钦教授和刘遂庆教授、彭永臻教授等分别对给排水管网系统展开了 定量优化的研究。 近年来，对排水管网布线布置形式的研究与应用日益增多，张景国拟差动 态规划法和简约梯度法求解f 9 】。陈森发讨论了单汇出点排水管网的最优结构， 从理论上证明了单汇出点排水管网的最优结构应为枝状网，并提出了获得优化 树的修正逐步生成法l l 0 1 。 5 第二章雨水管网优化设计的方法 2 1 雨水管网优化技术的意义 城市雨水管网系统是保证城市生产活动和人民生活的重要基础设施，是城 市防洪和保护环境的保障体系，也是维护和促进国民经济发展的重要手段。随 着城市化进程的加快，雨水管网系统的建设规模和速度也是前所未有的，将会 有大量的资金投入到城市雨水管网系统中，如何合理有效的来利用这些资金， 届时将会对市政建设的决策者提出更高的要求。 由于雨水产生的特点可知，相应的雨水管网系统的规模要比污水系统大得 多，因此雨水管网系统的建造、维护及运行费用在市政工程项目的费用支出中 占了相当大的比重。一般一个路段的雨水管道投资就达千万元左右，这对于正 处于社会主义初级阶段的我国来说，是一个不小的投资，如何科学、合理、有 效的利用这些资金，使政府的有限资金投入能取得最佳的投资收益，就要保证 每一分投资都能发挥最大的作用，所以进行雨水管网的优化设计研究有着十分 重要的现实意义。 2 2 其方法的简介 2 2 1 动态规划法 动态规划是解决多阶段决策过程最优化问题的一种有效方法。国外学者首 先把动态规划法引入到排水管网系统优化设计中，目前该方法在国内外仍得到 广泛的应用。它在应用中分为两支： 一支是以各节点埋深作为状态变量，通过坡度决策进行全方位搜索，其优 点是直接利用标准管径，优化约束与初始解无关，却能控制计算精度。 另一支是以管径为状态变量，通过流速和充满度组合进行优化搜素。由于 标准管径数目有限，比以节点埋深为变量的方法在计算存储和时间上有显著优 势。 动态规划的基本思想是把待解决的问题划分为个相互独立的阶段，从只 含第一个阶段的子问题出发，对该子问题进行优化求解，并将求得的解传入下 一个阶段，作为下一阶段的输入条件，然后对只含下一阶段的子问题进行优化 求解，其解的结果也传入下一阶段，如此不断反复，直至求得第个子问题的 解，此解即为原问题的最优解。 动态规划的函数方程【9 】一般可用下列的递推公式表示： 厶( s ) = m i n d ( s ，( s ) ) + 厶一1 k ( s ) ) ) ，x n ( s ) n ( 2 1 ) 式中：s 一一状态变量，表示某一阶段所处的某一状态。 ) 一一决策变量，表示第n 阶段中当状态处于s 时可采取的决策。 6 力一一可行决策的集合。 d ( s ，( s ) ) 一一第1 1 阶段中，当状态处于s 时采用决策h ( s ) 所得到的效益。 厶一1 ( h ( s ) ) 一一采用决策( s ) 得到的从过程开始到第n 1 阶段的总效益。 厶( s ) 一一在状态为s 时，从过程开始到第n 阶段所得到的总效益。 2 2 2 神经网络方法 神经网络算法l f l 2 】是模拟生物神经进行信息处理的一种数学模型。它以对 大脑的生理研究成果为基础，其目的在于模拟大脑的某些机理与机制，实现一 些特定的功能。目前，神经网络已应用到各个领域。其求解问题的关键是将原 问题映射到一个神经网络动力系统，写出相应的满足问题约束条件的能量函数 表达式和动力学方程，选取适当的参数值以保证网络的稳态输出，在网络动力 学方程自动演化到平衡状态后，即可搜索到相应的最优解。 2 2 3 模拟退火法 模拟退火法的思想是模拟了一个热平衡的物理体系逐渐降温的过程，在整 个过程中，随着温度的下降，体系的能量逐渐降至最低，从而原问题取得最优 解。解组合优化问题的模拟退火算法：由初始解i 和控制参数初值t 开始，对 当前解重复“产生新解一计算目标函数差一接受或舍弃 的迭代，并逐步衰 减t 值，算法终止时的解即为所得近似最优解，这是基于蒙特卡罗迭代求解法 的一种启发式随机搜索过程。 2 3图论与遗传算法的概况 2 3 1图论的基本概念 2 3 1 1 图和有向图1 1 3 - 1 4 1 图的定义：图是由点、边实体组成的，可以用点、边和点与边关联函数与三元 组表示，即g = ( v ，e ) 图g = ( nf ) 常简记为图g ，并以坎g ) 或v f ( g ) 或f 分别表示图g 的顶点 集、边集。设s 是一个集合，则以isi 表示集s 的基数或元素个数，于是i 坎g ) l 或iyl 、le ( g ) l 或le1 分别表示图g 的顶点数、边数。由定义，边 是顶点的无序对，若边是顶点u 和y 的无序对，则记e = ( u ，叻，或e - ( vu ) 。 有1 1 个顶点条边的图称为( n ，n 1 ) 图；( 0 ，0 ) 图叫做空图；( 刀，0 ) 图称为 零图1 1 是正整数：当n - - 1 ，( 1 ，o ) 图叫做平凡图；没有环与平行边的图称为简 单图；任意相异两顶点都相邻的简单图称为完全图；有n 个顶点的完全图记为 k 。： 7 有向图的定义：v 是一个非空有限集合，e 是v 中元素的有序对所组成的有限 集合，称g = ( v 即为有向图， 并把y 中的元素叫做图的顶点，e 的元素叫做图的有向边或边。 设g 是有向图，e - - 化叨e e ，则称u 为e 的起点或尾，e 为u 的出边； 并称y 为e 的终点或头，e 为v 的入边；又称u 为y 的前趋，y 为u 的后续。 若二条或二条以上的边有相同的头和尾，则称这些边为平行边。 v 1 a 简单图 v 5 v 2 图2 1 图和有向图 b 简单有向图 v 5 对于无向图，边e = 杪) 也可以记为e = ( 奶u ) ，因为无向图的边是顶点的 无序对。而有向图的边是顶点的有序对，故对有向图，( u ，叻与( 矿，u ) 是不同 的二条边。 设g 是有向图，若略去边的方向，则得到一个无向图，称为图g 的基础图。 如果g 是无向图，给所有的边任意定一个方向，则得到一个有向图，称为图g 的定向图。容易看到，有向图的基础图是唯一的，而没有环的无向图却有 2f 1 个。 设g 是有向图，如果对任意的u ，ve v ( 回，以u 为起点y 为终点的边数， 与矿为起点u 为终点的边数相同，则称图g 是对称的。如果对任意的u ，ye v ( g ) 时，则( u ，叻睡e ( g ) ，则称g 为反对称的。任意二顶点u ，y 都有二条边( h ， 叻，和( eu ) 的简单有向图称为完全有向图。基础图是完全图的有向图称为竞赛图。 一个竞赛图可完全看作是完全图的定向图。 2 3 1 1 图的连通性及加权图 图的连通性：如果图d 中存在聊一聊路径，则顶点聊和v j 是连通的。在图d 中每对顶点之间都存在一条路径，则图d 是连通的。 加权图：赋有权的图称为加权图或称网格图 为了表示这些路径联通的强弱程度，这时就要给图的边赋以某一数值或函 8 数( 称为权重) ，给顶点赋以某一数值或函数( 称为点权) 。 r 1 1 0 0 1 0 1r 1 1 100 0 1 i1 01 0 0 1ii 一1 10100i 100 1 1 1 0 l10 01011i t o1 0 1 01 j 1 0 0 0 111 j | 1 | 的邻接矩阵比关联矩阵小，而且还可将矩阵的元素定义为边或弧的权，因而在 存储和计算时用的较多。 2 3 1 3 树和生成树 树是图论以及图论基础上发展起来的网络分析方法，是一种非常重要的非 线性结构。一方面对于计算机应用中常出现的嵌套数据，树形结构可以提供自 然的表示：另一方面在解决各种算法中，树形结构有广泛的应用。连通的无圈 图称为树。若图的树包括图的所有顶点，则称树为图的一颗生成树或支撑树。 ( 1 ) 生成树的基本性质 对于图g = ( y ，f ) ， lyi = 1 1 ，ji ，i = 刀2 ，则： ( a ) g 的任意两顶点间有且仅有一条道路； ( b ) g 是连通的，且仇- - 7 i 一1 ( c ) g 不包含回路，且m = 7 l 一1 ( d ) g 不含回路而且在不相邻接的两顶点间增加一条边则有且仅有一条回 路。 ( 2 ) 最小生成树 已给一连通图g = ( nf ) ，其中v = ( 吼，吃，1 7 3 ) ，g = ( p 1 ，e 2 ，e 3 ) 其边权 w = 舢1 ，w 2 ，w 3 w h ) ，丁是g 的生成树，且记其各边权的总权为： w ( 丁) = 毗( 2 2 ) 若生成树t + 的总权w ( t + ) 有 w ( r = c ) = m i n w ( t ) ( 2 3 ) 则称树丁事为图g 的最小生成树，简称最小树。 2 3 1 4 图模型的建立 排水管网规划的图模型应包括三个方面的信息：( 1 ) 各节点之间的关系；( 2 ) 各节点流量；( 3 ) 各条弧的权函数。下面将对这三个方面信息的表达作详细论述。 ( 1 ) 地理信息的表达 排水管网系统及其附属设施与城市的地形、地貌、河流、湖泊以及市政道 路、工业企业、居民生活区的规划密切相关。前面已提到雨水主要依靠自身重 力流动，排水管网的走向应符合地形的倾斜趋势，生成的有向图应该由高位节 点指向低位节点，按照这个原则，对道路网的路段联系进行修正，即可生成排 水管网的图模型的初始结构，在进行管网布线的优化时，每个节点的排水量就 可根据每条可行路径的弧函数的大小选择流经的管路，从而产生雨水流量在图 模型上的最优分配，使管道系统的建设费用最小。 l o k y 1 2 3 睡 4 图卜2 具有一个交汇点的雨水管网 设个管段服务面积上的本段汇水面积为： ，f 2 ， ， ，用向量表示如下： 厂= 魄，f 2 ， ， ) 丁( 2 - 5 ) 卜一笺肛厶 ( 2 - 6 ) 【三一呈一。1 10 1 0 0001 0 。】x 【萎】= 匡】 i 一1 1 一iif ，2il 厶i il “iblf 厶i ljl r jl 丘j 3 ，4 ) 。根据计算出的各设计管段的汇水面积，按照下式可求出各设计管段的雨 水设计流量为： q s i = ( p q o f i( 2 - 7 ) 式中q o 一一雨水单位面积上的比流量； 妒一一径流系数。 结合管网的水力计算的进行，可逐步的计算确定整个管网的设计流量。 ( 3 ) 各条弧的权函数 图模型中各条弧的权函数以该条弧的管道建设费用函数来表示。 管长为，的管道的建设费用就为： q = f o c d l ( 2 8 ) 每一条弧的弧函数就为该条弧上各管径的管道的建设费用的总和，即： c = g( 2 9 ) 到此，排水管网规划的图模型就建立起来了，下一步的工作就是根据最优 化的工作程序，利用图模型进行计算，求出排水管网规划的最优方案。 2 3 。2遗传算法 遗传算法是基于进化论的原理发展起来的一种广为应用的、高效的随机搜 索机技术与优化方法，也是生命科学与工程科学的相互交叉、相互渗透和相互 促进的结果。一种通过模拟自然进化过程搜索最优解的方法。 遗传算法的发展过程基本上分为三个阶段：2 0 世纪7 0 年代的起步阶段， 8 0 年代的发展阶段，9 0 年代的高潮阶段。进入9 0 年代后，遗传算法已发展成 为一种实用、高效、鲁棒性强的优化技术。所谓的鲁棒性是指能在许多不同环 境中通过概率及功能之间的协调平衡以求生存的能力，人工系统很难达到如生 物系统那样的鲁棒性。 遗传算法是一种更为宏观意义下的仿生算法，它模仿一切生命和智能的产 生与进化，并通过模拟达尔文的“优胜劣汰，适者生存”的原理，激励并保持 良好的结构；通过模拟孟德尔遗传变异理论在迭代过程中保持已有的结构，同 时寻找更好的结构。生物进化的基础是生物体的遗传和变异的对立统一，而决 定生物进化方向的是外界环境对生物体的选择。遗传和变异是相互对立，而又 相互联系的，它们构成了生物体内的一对矛盾。生物就是在这种矛盾的斗争和 转化中不断向前发展。 遗传算法最早是由美国m i c h i g a n 大学的j o h nh h o l l a n d 教授及其同事和学 生受到生物模拟技术的启发，创造出一种基于生物遗传和进化机制的适合于复 杂系统优化的自适应概率优化技术。l9 7 5 年j o h nh h o l l a n d 教授出版了 1 2 “a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s 一书，给出了遗传算法的基本定 理和大量的数学证明，是遗传算法的经典之作；2 0 世纪8 0 年代他的学生d a v i d e g o l d b e r g 教授在“g e n e t i ca lg o r i t h m si ns e a r c h ，o p t i m i z a t i o na n dm a c h i n e l e a r n i n gk i d ，则系统的对遗传算法的主要研究成果，全面完整地论述了遗传 算法的基本原理及其应用。1 9 9 2 年，k o z a 将遗传算法应用于计算机程序的优 化设计及自动生成，提出遗传算法编程的概念。在控制系统的离线设计方面遗 传算法被众多的使用者证明是有效的策略。 目前遗传算法的主要应用在如下领域函数优化：如非线性、多模型、多目 标的函数优化；生产调度问题：如单件生产间调度、流水线生产车间调度，生 产规划，任务分配等；自动控制：如航空控制系统的优化、设计空间交汇控制 器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨认、利用 遗传算法进行人工神经网络的结构优化设计和权值学习、生产过程优化控制等； 机器学习：学习模糊控制规则、学习隶属度函数以及分类器控制。遗传算法在 给排水工程领域的设计计算雨管理中也得到广泛的应用，如排水管网的优化布 置和设计，给水管网优化设计雨水经流模型的校准，水资源管理，以及水质管 理等。 9 0 年代，遗传算法的研究和应用在我国开始了起步，我国刊登有关遗传算 法方面的杂志主要有信息与控制，控制与决策，计算机科学等【1 6 。8 1 。 2 3 2 1遗传算法的基本原理 遗传算法( g e n e t i ca l g o r i t h m ，简称( g a ) t 1 9 2 1j 是一种借鉴生物界自然选择和 自然遗传的随机搜索方法，是模拟达尔文的遗传选择和自然淘汰的生物进化论 的计算模型。它与传统的算法不同，大多数古典的优化算法是基于一个单一的 度量函数( 评估函数) 的梯度或较高次统计，以产生一个确定性的实验解序列； 遗传算法不依赖于梯度信息，而是通过模拟进化的过程来搜索最优解它利用某 种编码技术，作用于被称为染色体的数字串，模拟这些数字串组成的群体的进 化过程。遗传算法从任意初始种群出发，通过随机选择、交叉和变异操作，使 群体进化到搜索空间中越来越好的可行域。选择使群体中适应性好的个体保留 下来，交叉是将父代的信息结合在一起并将它们传送到子代个体中，变异在群 体中引入新的物种，从而适应新的环境而不断的向前发展1 2 卜2 4 1 。 基本遗传算法是其他遗传算法的雏形和基础，它从一组随机产生的初解称 为种群，将每个可能的解看作是群体中的一个个体，并将每个个体编码成字符 串的形式，按照给定的目标函数给出一个适应度值。开始时，总是随机地产生 一些初始个体，然后根据这些个体的适应度利用遗传算子一一选择、交叉、变 异，对它们重新组合，得到一群新的个体。这一群新个体由于继承了上一代的 1 3 一些优良特性，明显优于上一代，综上所述遗传算法是通过一系列的选择、交 叉、变异以及适应度函数评价来产生新的子代，从而完成整个随机搜索的进化 过程。 2 3 2 2 遗传算法的基本方法 生物遗传物质的主要载体是染色体，在遗传算法中，染色体通常是串数 据( 或数组) ，用来作为优化问题的解的代码，其本身不一定是解。遗传算法一 般经过这样几个过程： 1 、编码 针对不同的问题，为改进遗传算法的效率，很多学者设计了多种不同的编 码方法，其中最主要的有两种编码方式：二进制向量和浮点向量。由于二进制 编码法使用的是真实值，向量的长度依赖于要求的精度，在求解复杂优化问题 时，二进制向量表示结构有时不太方便。另一种表示方法是浮点向量，即每个 初始个体均由一个浮点向量表示，其向量的长度与解向量一样。例如最优化问 题的解是刀维数的，则相应的染色体也是n 维的。 2 、处理约束条件 合理的约束条件是解决计算高效和正确的前提。关键在于：( a ) 为了保证判 断过程正确进行，对于约束条件中的等式予以去除；( b ) 确保所有新产生的染色 体在可行域中。 3 、初始化过程 初始化过程用来产生适当数量的满足约束条件的个体，而且要保证产生的 个体符合随机性分布。 4 、适应度评价 遗传算法按与个体适应度成正比的概率来决定当前群体中各个个体遗传到 下一代的机会多少。为了正确评估这个概率，要求所有个体的适应度必须为非 负数。适应度函数雨目标函数的转换是因实际求解问题而异的，但两者的转换 方式或函数是遗传算法能够获得全局最优解的关键。在利用遗传算法求解实际 问题时可采用不同的转换函数，将目标函数转换成适应度函数。具体的转换方 法有两种：。 第一种方法，设初始代中的染色体班，可以