（环境工程专业论文）遗传算法在周口沙北污水管网改扩建工程优化设计中的应用.pdf

摘要 为了探求污水管网最优化设计的计算方法，国内外学者进行了大量的工作，并随着 系统分析方法、计算技术和电子计算机的发展，遗传算法作为一种新的全局优化搜索算 法，因简单易用，对很多优化问题能够较容易给出令人满意的解，适用于并行分布处理 和对目标函数与约束条件没有特殊要求等特点，在工程最优化领域中展现出独特魅力。 本论文基于标准遗传算法和污水管网计算方法，针对管网结构形式已定情况下的污 水管网参数优化问题进行了如下的工作： 1 在满足污水管网一般约束条件的情况下，通过选择较小的设计流速和较大的设计 充满度来实现污水管网参数优化；针对不同污水管径以不同的最大流速限制：d n 3 0 0 1 0 0 0 m m ，h i o r e s t d n l l 0 0 1 2 0 0 m m ， k 1 i r a s ：d h l 3 0 0 1 6 0 0 m m , 缸d 1 2 m s 。 2 通过采用自然数编码的遗传算法得到可行管径组合群体，直观的反映遗传算法编 码和市售标准管径一一对应的关系；并采用代同竞争和群体单一化策略对遗传算法进行 改进；经过大量的计算机模拟试验，得到针对污水管网参数优化设计的改进遗传算法参 数组合：群体规模2 0 ，最大迭代数2 0 0 代，交叉概率尼= 0 8 和变异概率岛= o 4 。 3 利用改进遗传算法对周口沙北污水管网改扩建工程进行优化。通过与传统算法所 得管网参数组合进行比较得出：在满足污水管两一般约束条件和采用相i 司施工方法与 费用函数的情况下，利用遗传算法所得污水管网的管径、充满度和埋深的组合优于传统 的水力计算，可节省工程投资1 4 ；利用遗传算法进行优化，只需事先输入所需的流 量和地面高程数据，程序运行1 3 分钟就可以方便快速的得到最优的结果，比传统算法 省时省力；遗传算法在进化的过程中，产生大量的可行方案，为方案评价和决策提供 了更大的选择空间。 论文工作表明：通过选择较小的设计流速和较大的设计充满度及针对不同污水管径 以不同的最大流速限制可以得到更加合理的可行管径集合，利用自然数编码与采用代问 竞争和群体单一化策略的改进遗传算法可高效率地完成污水管网参数优化，为污水管网 结构优化提供了很好的优化基础，也为遗传算法在污水管网优化中的应用开辟了新的途 径。 关键词：排水管网污水管网优化设计遗传算法 g ai no p t i m i z i n gt h ea u x i l i a r ys e w e r a g ep i p en e t w o r kp r o j e c t s o fs h a b e is e w a g et r e a t m e n tp l a n to fz h o u k o uc i t y a b s t r a c t i no r d e rt os e e kt h em e t h o d so fo p t i m i z a t i o no fs e w e r a g ep i p en e t w o r k , b o t hh o m ea n d o v e r s e a se x p e r t sh a v eb e e nw o r k i n gh a r d l y a n dw i t ht h ed e v e l o p m e n to fs y s t e m a t i ca n a l y s i s m e t h o d s ，c a l c u l a t i o nt e c h n i q l | e sa n dc o m p 嗽, g e n e t i ca l g n f i t h m s ( g a ) ，w h i c hi sb e c o m i n ga n e ws e a r c ha l g o r i t h mf o rg l o b a lo p t i m i z a t i o n , h a si t so w n u n i q u es u p e r i o r i t yi ne n g i n e e r i n g o p t i m i z a t i o nf i e l db e c a 嘲i ti ss i m p l ea n de a s yu 辩g a l lg e ts a t i s f i e dr e s u l t sf o rm a n y o p t i m i z a t i o np r o b l e m s ，s u i t sf o rp a r a l l e ld i s p o s a la n dh a sn os p e c i a lr e q u i r e m e n t sf o rt h e o b j e c t i v ef u n c t i o na n d t h eb o u n d sf o ri t b a s e do ns y s t e m a t i cs t u d y i n gt h es i m p l eg aa n dt h ec a l c u l a t i o nm e t h o d so ft h es e w e r a g e p i p en e t w o r k , t h ea r t i c l ed o e st h ef o l l o w i n gw o r i 【sf o ro p t i m i z i n gt h ep a r a m e t e rp r o v i d i n gt h e l a y o u to f t h es e w e r a g ep i p en e t w o r k ： 1 b e i n gs a t i s f i e dt ot h en o r m a lc o n s t r a i n tc o n d i t i o n s , t h ea r t i c l es e t t l e ss e w e r a g ep i p e n e t w o r ko p t i m i z a t i o nb yc h o o s i n gl i t t l ed e s i g nv e l o c i t ya n dl a r g e rd e s i g ns u f f i c i e n tf u l l n e s s a n dt h ea r t i c l eg i v e sd i f f e r e n tl r f f t x i m u md e s i g nv e l o c i t yl i m i tf o rd i f f e r e n tp i p ed i a m e t e r ： d a r 3 0 01 0 0 0 m m ，1 0 m s ；d n l l 0 0 1 2 0 0 m m ，1 1 m s ；d n l 3 0 0 1 6 0 0m m ， 1 2 m s 2 t h ea r t i c l eg e t sa v a i l a b l ep i p ed i a m e t e rp o p u l a t i o nb yn a t u r a ln u m b e rc o d i n g , w h i c h d i r e c t l ye x p r e s s e st h ec o r r e s p o n d e n c er e l a t i o n s h i pb e t w e e ng e n e t i cc o d ea n ds t a n d a r dp i p e d i a m e t e r si nt h em a r k e t a n di ta l s oi m p r o v e so p t i m u me f f i c i e n c yo fs i m p l eg ab yu s i n g c o m p e t i t i o nm e a s u r ea m o n gg e n e r a t i o n sa n dp o p u l a t i o ns i n g | e ts c 哦t t e g y a 矗e rl o t so f e x p e r i m e n t so nc o m p u t e r , i tf i n a l l yg e t st h eg e n e t i co p e r a t o r sf o rs e w e m g ep i p en e t w o r k o p t i m i z a t i o n ：m a x i m t m lg e n e r a t i o ni s2 0 0 o r o s s e v 盯p r o b a b i l i t yp 网8a n dm u m f i o n p m b a b i l i t yj k 卸4 3 t h ea r t i c l eu s e st h ei m p r o v e dg at oo p t i m i z et h ea u x i l i a r ys e w e r a g ep i p en e t w o r k p r o j e c t so fs h a b e is e w a g et r e a t m e n tp l a n to f z h o u k o uc i t y b yc o m p a r i n gw i t ht h eo u t c o m e s o ft r a d i t i o n a la l g o r i t h m , i tg e t st h ef o l l o w i n gr e s u l t s ：g a 啪g e tm o 坞a p p r o p r i a t e a s s o c i a t i o no fp i p ed i a m e t e r , s u f f i c i e n tf u l l n e s sa n di n b u i l tw i t hs a t i s f a c t i o nt oa l lc o n s t r a i n t c o n d i t i o n sa n ds a v ep r o j e c ti n v e s t m e n ta b o u t1 4 ，u s i n gg ai no p t i m i z a t i o n , i t j u s tn e e d s t oi n p u tt h ev a l u eo ff l o wa n dg r o u n de l e v a t i o na tf i r s t , a n dc a ng e to p t i m i z a t i o nr e s u l t sm o r e f a s ta n dc o n v e n i e n t l yi n1 3m i n u t e s i tc a ng e tl o t so f f e a s i b l ep r o g r a m sa n dp r o v i d em o r e c h o o s i n gd l a n c e sf o rs c h e m ec o m p a r i s o na n d d e c i s i o n t h er e s u l t si n d i c a t ei tc a ng e tm o r ea p p r o p r i a t e l ya v a i l a b l ep i p ed i a m e t e ra s s e m b l eb y c h o o s i n gl i t t l ed e s i g nv e l o c i t ya n dl a r g e rd e s i g ns u f f i c i e n t f u l l n e s sa n dd i f f e r e n tv e l o c i t y l i m i t sf o rd i f f e r e n tp i p ed i a m e t e r , a n dc a ng e to p t i m i z a t i o nr e s u l t so fs e w e r a g ep i p en e t w o r k 、 ，i t l l 1 1 i g he f f i c i e n c yb yu s i n gi m p r o v e dg aw h i c h 璐缁n a t u r a ln t m a b e rc o d i n ga n d c o m p e t i t i o nm e a s u r ea m o n gg e n e r a t i o n sa n dp o p u l a t i o ns i n e 乒e ts t r a t e g y t h eh i g he f f i c i e n t g ap r o v i d e sag o o db a s ef o rs e w e r a g ep i p en e t w o r kl a y o u to p t i m i z a t i o na n de s t a b l i s h e sa p a t hf o ru s i n gg a i nt h es e w e r a g ep i p en e t w o r kf i e l d k e y w o r d s ：d r a i n a g ep i p en e t w o r k s e w e r a g ep i p en e t w o r ko p t i m a ld e s i g n g e n e t i c a l g o r i t h m s i i l 郑州大学硕士学位论文 1 绪论 1 1 选题的背景和意义 1 , 1 1 排水工程的重要意义 城市排水工程的基本任务是收集城市产生的生活污水、工业废水和降水，并将其输 送到污水处理厂，妥善处理后排入水体或再利用。排水工程在我国国民经济活动和人民 日常生活中的重要作用，主要体现在以下几个方面m ： 从环境保护和可持续发展方面讲，排水工程有保护和改善环境，消除污水危害的作 用。消除污染，保护环境，是进行经济建设必不可少的条件，是保障人民健康和造福子 孙后代的大事。 从卫生方面讲，排水工程的兴建可有力地保障人民群众的身体健康。兴建完善的排 水工程，对污水进行妥善处理，对于预防和控制各种传染病、癌症或“公害病”有着重 要的作用。 从经济方面讲，水是非常宝贵的自然资源，在国民经济各部门中都是不可缺少的。 我国水资源分布不均，利用难度大，许多城市缺水，与此同时，有限的水资源还不断受 到水质恶化及水生态系统破坏的严重威胁，排水工程正是保护水体，防治公共水体水质 污染，以充分发挥其经济效益的基本手段之一。 同时，排水工程有助于城市污水资源化。收集的污水经过污水处理厂处理后，可重 复利用于城市或工业，这是节约用水和解决水资源短缺的一个重要途径，必将产生巨大 的经济效益。 此外，污水本身也能产生很大的经济效益。例如科学地利用污水灌溉农田，能改良 土壤，提高土地肥力，有助于提高作物产量，节约用水，促进农业生产，污水也是一种 资源。 总之，排水工程作为国民经济的一个重要组成部分，对保护环境、促进工农业生产 和保障人民的健康具有巨大和深远的影响。 1 1 2 捧水管网建设存在的问题 排水管网是城市排水工程的重要组成部分，通过排水管网，排水工程完成收集各种 污水并及时地将其输送至适当地点的任务，排水管网的投资一般要占到整个排水工程总 投资的5 0 8 0 ，而且涉及庞大的能耗和运行管理费用，在人民生活和经济建设方面 1 郑州大学硕士学位论文 有很重要的意义。但是由于种种原因，我国排水管网存在很多问题，如果不妥善解决， 会严重影响国民经济的发展和人民的生活健康。 ( 1 ) 我国不少城市的排水管网盲点较多并且日益老化，亟待完善和更新，并且随着 我国经济的飞速增长，城市化也进入迅速发展的阶段，城市人口迅速增加，城市中的工 矿企业如雨后春笋般的涌现，工业用水量也迅速增加，使得城市的用水量和污水排放量 急速增长，现有的城市排水管网日益不堪重负，全国各地的排水管网建设需求越来越大， 必须尽快投资新建和改造城市排水管网系统。 ( 2 ) 与不断增加的污水排放量相比，我国的城市排水管网的建设却陷入尴尬的境地。 一方面，城市基础设施的建设资金主要来自国家拨款和地方财政，限于政府财力的制约， 不可能满足各方面对投资的需求，城市基础设施的建设面临着投资渠道狭窄、建设资金 严重不足的困境。另一方面，投资资金的取向、分配、规模及管理等在很大程度上还缺 乏系统性、科学性、合理性，有些投资项目的效果难尽人意。 ( 3 ) 传统的排水管网设计过程，主要依靠设计人员的经验和手工查阅图表，重复性 的劳动繁多，工程设计时间长，设计效率不高，并且选择有限种方案进行对比，这样就 有可能造成排水管网投资过大，浪费宝贵的资金和时间。 1 1 3 排水管网优化的意义 随着水资源日益紧缺和水资源开发利用率的提高，新系统的兴建和老系统的修复、 改扩建等所需要的工程投资逐渐增大，并且普遍面临资金紧缺、设计质量要求高和设计 时间短等问题。在这种情况下，排水管网优化的意义重大，具体来讲有以下几点： ( 1 ) 排水管网部分的投资一般占到整个排水工程总投资的5 0 8 0 ，而且涉及庞 大的能耗和运行管理费用。因此，排水管网的规划、设计和运行管理是否科学、经济、 实用，直接影响工程总投资和运行管理费。在工程资金投入有限的情况下，进行排水管 网优化设计，寻求能满足水量和设计要求，且能使整个系统的造价最低或年费用最小， 对节约投资、降低能耗、提高经济效益和社会效益等有着重要的现实意义。 ( 2 ) 排水管网结构优化和参数优化是两个相对独立，又相互关联的设计阶段，分 步分级优化能充分考虑不同设计阶段所要重点解决的问题，降低优化模型的复杂性和求 解难度。实现分布分级优化的关键在于为每个优化阶段建立适当的优化模型，选择和设 计简单、快捷的优化方法，提高运算效率和求解精度，以达到布置和设计整体最优。寻 求简单快捷的污水管网参数优化是进行管网结构优化的基础。 2 郑州大学硕士学位论文 ( 3 ) 排水管网的设计计算( 以下称排水管网计算) 虽然不涉及很复杂的计算理论， 但是，由于污水在非满流的管道中靠重力流动，即使按均匀流基本公式进行一个管段计 算，都必须对设计流速、管径、设计充满度和管道坡度等进行多次选择与计算，再加上 各管段之间的连接及各种约束条件的限制等，使得排水管网计算的工作量大而繁琐。传 统人工计算大都采用反复查阅图和表的方法进行，工作量和误差大，设计人员工作效率 低。但是排水管网计算的另一个特点是：每一个管段的设计计算都采用同一公式和基本 相同的计算方法，利用计算机程序来进行优化求解是非常合适的。1 。研究排水管网设计 优化问题，能够把设计人员从繁重的手工劳动中解脱出来，提高工程设计效率和设计人 员的设计水平。 1 2 排水管网优化的国内外研究现状 排水管网的优化研究主要是通过构造抽象或简化的排水管网优化设计模型，借助于 最优化理论和计算机技术，研究如何在排水管网设计中合理地选择有关技术参数，从众 多可行的设计方案中寻找出既能满足工程设计需要，又能降低工程投资成本的最优或次 优设计方案，作为工程建设施工和运行管理的技术依据。 为了探求排水管网的最优化设计计算方法，国内外许多科研、设计、教学系统进行 了广泛研究，取得了大量研究成果。自上个世纪7 0 年代至今，美国、日本、前苏联和 欧洲各国在排水管网方面不仅在方法学和计算机程序上取得了各种研究成果，并且日益 广泛地将所研制的各种计算机软件应用于排水管网的计算机辅助设计和自动化运行管 理上嘲；我国在上个世纪7 0 年代以同济大学环境工程学院杨钦教授为代表的专家学者， 开辟了排水管网优化设计的新领域，特别是最优理论与技术和计算机在排水管网系统 设计中的应用，不仅把设计人员从查阅图表的繁重劳动中解脱出来，加快了设计进度， 而且使整个排水管网系统得到了优化，提高了设计质量“1 ，所确定的最优方案与传统方 法相比，可以降低至少l o 以上的工程造价伽。 对一个城市来说，其排水管网的优化主要包括三个方面的内容“一：1 污水厂选址 和排水区域划分的优化；2 排水管网结构的优化；3 排水管网参数的优化。在国内， 优化的第二个方面的内容有两种提法，一种叫管网布局优化m ”，另外一种叫管网结构 优化“”，国内外在结构和参数优化这两方面都取得了很大的成果，但因为管网结构和参 数优化是两个既相对独立又相互关联的设计阶段，正确的定线是合理地、经济地设计污 水管网系统的先决条件，已定管线下的参数优化是管线平面布置的基础，目前对已定管 3 郑州大学硕士学位论文 线下的优化设计计算不成熟，造成管网结构优化的进展甚微，所以需要寻求简单、快捷 的管网结构和参数优化方法，提高运算效率和求解精度，以达到结构和参数设计的整体 最优。 1 2 1 律水管网结构优化 j c l i e b m a n a n 是国外最早进行管网结构研究的专家。1 。在他的研究中，忽略管道的 水力因素，假定每一段管道的管径相同，以土方费用最小为目标，选择一个初始布置方 案，然后通过试算，逐步调整管道去寻求管网最优结构形式。p r b h a v e 和j e b o r l o w 在方案优化时，同样撇开水力因素不计，不同的是，他们利用网络图论中的最小生成树 算法，假定系统中的每一管段具有相同的权重，用定权方法来求解管线最佳走向。 以上这两种方法的不足之处是没有考虑管道的水力因素，从现在的研究成果来看， 恰恰是管网的投资与管道参数的选择有很大的关系。因此，不考虑水力因素的优化方法 很难得到真正的最优解。 在随后的研究中，s t e k e l 和h b e l k a y a 对排水网络图的边赋予了三种不同的权重： 各管段地面坡度的倒数；各管段的管长；各管段在满足最小覆土条件下，按最小 坡度设计时的挖方量。分别对这三种权值，运用最短路生成树算法求管线结构布置方案， 再进行管径、埋深和提升泵站的优化设计，投资费用最小的平面布置方案作为最优设计 方案。此研究的主要缺陷是，选用的权值不是影响管道投资的主要参数，因而所求最优 结果不具有可靠性。 对于排水管网系统所有可行的管线敷设路径构成的图，各管段的实际权值只有在方 案确定以后才能计算出来，因此属于图论中的变权值问题。可是目前为止，图论中的变 权问题尚无有效的解决方法。 因为遗传算法的运算机制与别的优化方法不同，它对目标函数和约束条件没有特 殊要求，所以遗传算法为排水管道系统平面优化布置提供了可能条件。 一般情况下，排水管网系统结构是树状的，文献埘应用遗传算法对树状管网进行优 化设计可以看作是这方面研究的一个实例。此研究中，作者以网络图中的点为研究对象， 如果某一点上游有多条边( 设为t n ，且礁丑) ，则用i f 个长度为2 的二进制数表示上游 每条边与此点的连接关系，由网络图生成树状管网时，点只能选择与上游某一边相连接。 利用遗传算法，可以随机生成树状管网的各种可能结构，算法对群体中的每个个体的适 应度计算后，复制当代中的最优个体到下一代，淘汰较差个体。 4 郑州大学硕士学位论文 排水管网系统是一棵内向树，树根是污水处理厂所在的位置。资料“”认为树状管网 具有图论中树的性质，有 个节点的树状管网对应于一棵有，1 个节点、有1 1 - l 条边的树。 用遗传算法进行树状管网优化布置时，选择一种合适的编码方式表示树状管网布置问 题，然后以随机方式从h 条边中选取 1 条边构成一个管网连接子图，利用深度优先搜 索算法判断其连通性，如果个体为可行个体，就对其进行水力参数计算，求得其投资费 用，这样，遗传算法经过有限次的迭代，就可以比较得出管网的最优方案。 实际应用中，因为已定管线情况下的参数优化没有快捷、高效的方法，所以这种方 法很能高效的完成排水管网结构优化，而且大部分工作由计算机完成，结果具有一定的 随机性。 文献帆”利用“大系统分解思想”和“多阶段决策原理”，将管网结构优化过程分 为前后衔接的两个优化阶段：主干管优化和次干管优化。排水区域划分为k x k 个格子， 求得每个格子里面的污水排放总量，然后计算任意两相邻点污水排放量的平均值阡0 ， 求出以此为负荷的管道f j 的费用因子g 疆秒，然后计算管道费用指数c d f ( i j ) = c f ( i j ) 觋， 把它作为管道的权值。主干管优化是以污水厂所在的格子为出发点，以最远污水源所在 的格子为终点，利用d u k s t r a 算法求解管网的最佳走向，在主干线走向经历的格子内 部，再用d u k s t r a 算法求其优化结构，它的费用也记入总费用中，如此反复，直到求 解完所有的格子。次干管优化时，直接用“逐步生长法”将不在主干管上的汇集点向主 干管靠拢，构造最小费用树，从而形成系统的最终优化结构。文献【1 0 】也做了类似的研究， 把排水管网规划为一有向网络图，图中的边以管道费用为权值，利用网络优化理论中的 d u k s t r a 算法进行建模求解。该方法在解决小型管网时，可以得到较好的结果，但是， 如果管网规模较大，因为计算复杂、效率低下而降低了其实际应用价值。 1 2 2 排水管网参数优化 对于在管线平面布置已定情况下进行管段管径、埋深的优化设计问题，国内外做了 大量的研究工作。方法一般分为两种：直接优化法和间接优化法。 1 2 2 1 直接优化法 直接最优化方式是根据性能指标的变化，通过直接对各种方案或可调参数的选择、 计算和比较求得最优解或满意斜3 1 。在排水管网优化设计中，应用直接优化方法者认为 “”：由于管径的可选择尺寸不是连续变化的，不能任意选择管径；最大充满度的限制 5 郑州大学硕士学位论文 又与管径大小有关；最小设计流速、流速变化( 随设计流量增加而增大) 及其与管径之 间关系的约束关系等都很复杂，也不能用数学公式来描述。因此，很难建立一个完整的 求解最优化问题的数学模型来用间接优化法求解。相对而言，用直接优化方法来解决具 有直接、直观和容易验证等优点。 直接优化法主要包括电子表格法和两相优化法： ( 1 ) 电子表格法 电子表格法“”是利用l o t u s - 2 3 中的“电子表格”，统计数据、分析数据的功能进行 管网优化的。它能用来准备和分析数据、估计参数模型、演示桌面计算和整理文档工作。 它提供了一种启发式费用估算方法，允许用户寻找最小费用设计，它并不设计太复杂的 算法，能够得出比动态规划法更好的结果，并且更加符合设计规范的要求，在动态规划 法中的许多简化显得不太必要。 ( 2 ) 两相优化法 两相优化法是当设计流量确定后，在满足约束条件的前提下，选取最经济流速和最 大充满度从而得到最优管径和最小坡度，最大限度的降低管道埋深。其算法和人工计算 基本相同，即按污水流动方向，先计算支管后计算干管和主干管，通过从上游至下游依 次对各设计管段进行计算，继而完成一条管道以及整个管网的计算。 一般在直接优化算法中，主要依靠设计人员对管网计算的宏观控制和局部干预，所 设计的最优方案因人而异，所求结果一般是满意解而不一定是最优解。 1 2 2 2 间接优化法 间接优化法是建立在最优化模型的基础上，通过模型求解得到最优解的方法。应用 间接优化法者认为：随着优化技术的发展，尽管排水管网设计计算中存在着关系错综复 杂的约束条件，但是，只要对其中的某些条件适当取舍，合理地应用数学工具，就可以 把它简化、抽象为容易解决的数学模型，通过计算得出最优解。间接优化方法主要分为 以下几类： ( 1 ) 线性规划法 线性规划法是优化方法中最常用的一种算法，特别是重力排水管网的优化设计。排 水管网设计优化模型的目标函数和约束条件是非线性函数，线性规划法的原理就是用这 些函数的一阶泰勒展开式代替原函数，把非线性问题线性化，利用反复迭代的方法，不 断逼近非线性规划问题的最优解。实际工程中管径的取值都是离散型的，而线性规划法 6 郑州大学硕士学位论文 的却是把管径当作连续变量来处理的，这样就存在计算管径与市售规格管径不能相适合 的矛盾，这是这种优化方法存在的一个主要缺陷，同时模型求解采用的是目标函数的近 似表达式，优化结果的精度也会存在问题。2 。 ( 2 ) 混合整数规划法 混合整数规划法，作为线性规划法的发展形式，克服了线性规划的部分缺点，可以 解出离散的标准管径，但由于整数变量过多，往往难以求解，从而应用受到限制嘲。 ( 3 ) 非线性规划法 为了适应排水管网优化设计中目标函数和约束条件的非线性征，1 9 7 2 年d a j a n i 和 g c m m d l 建立了非线性规划模型1 ：基于求导原则，即目标函数的导数为零的点就是所 求的最优解这种算法假定管径是离散的，这样它就可以按照市场上销售的管道管径规 格进行计算，易于对目标函数和约束条件进行敏感性分析，可以优化选择排水管网的管 径和埋深，以及中途泵站的位置。但该方法极大地限制了目标函数和约束条件的形式， 当无法证明排水管道费用函数是一个单值函数时，得到的计算结果可能是局部最优，而 非全局最优解；而且该方法对管网的各种可行解进行遍历，在解决大型管网问题时，存 在运行时间长和内存占用量大的缺点。 ( 4 ) 罚函数离散优化法 罚函数离散优化法将排水管网的特点与罚函数优化思想联系，可以排除不合理的设 计方案，以管网末端管底标高作为全局控制因素，建立与目标函数的可行解对应的关系， 并通过同时进行整体控制与局部控制的水力计算方法，遍历目标函数的可行解及局部最 优解，从而得到管网的全局最优设计方案。该方法由于对排水管网的各种可行解进行遍 历，在解决大型管网问题时，必然存在运行时间长和内存占用量大的缺点1 。 ( 5 ) 动态规划法 动态规划法是目前在国内外广泛应用的排水管网优化设计计算方法，它的基本思想 是把排水管网的设计看作是一个多阶段的决策过程，通过划分阶段，寻找最优路线来进 行优化设计。动态规划法有两个分支：一支是以节点埋深作为状态变量，另一支是以管 径为状态变量。 以节点埋深作为变量的规划方法。”，在优化计算时主要对管网设计坡度进行全面搜 索。这种方法的优点是直接利用标准管径，优化结果与初始解无关，而且能控制计算精 度，它的缺点就是要求状态点的埋深间隔很小，使存储量和计算时间大为增加。拟差动 态规划法”倒是在动态规划法的基础上引入了缩小范围的迭代过程，可以显著地减少计 7 郑州大学硕士学位论文 算时问和存储量，但在迭代过程中有可能遗漏最优解，而且在复杂地形条件处理跌水、 缓坡情况时受到限制。 以管径为状态变量的规划方法，主要通过对管道流速和充满度的决策，寻求管网的 最优解”“。由于标准管径的数目有限，较以节点埋深为决策变量方法在计算机存储和 计算时问上有显著优势。最初的动态规划对每一管段选取的一组标准管径中并不全是可 行管径，因此发展出可行管径法。可行管径法通过数学分析，对每一管段的管径采用满 足约束条件的最大和最小管径及其之间的标准管径，构成可行管径集合，进而应用动态 规划计算。可行管径法使得优化计算精度得以提高，并显著减少了计算工作量和计算机 存储量。 尽管动态规划法是解决多阶段决策问题最优化的一种有效方法，但其要求变量均应 满足“无后效性”的特点。“无后效性”是指当给定某一阶段的状态时，在以后各阶段 的进行要不受当前各阶段状态的影响。在排水管网设计计算时，前一管段的设计结果将 直接影响到后续管段设计参数的选用，无论是利用节点埋深还是利用管段管径作为状态 变量，都没有充足的证据能够证明阶段状态的“无后效性”。因此利用动态规范法求出 的污水管道优化设计方案并不一定是真正的最优方案。 ( 6 ) 遗传算法 遗传算法是模拟生物学中的自然遗传变异机制而提出的随机优化算法，是进化算法 的一个重要分支。遗传算法的全局寻优能力和隐含并行特征，对目标函数没有可微可导 的要求，使遗传算法特别适合于处理传统算法无法解决的复杂的非线性问题。近年来， 它显示出比传统优化算法更大的优越性，并成为解决许多水力和水资源问题应用最广泛 的技术之一，应用遗传算法进行排水管网优化设计研究，是管网系统优化设计研究的一 个新方向。 文献“”提出一种进行树状管网优化布置的单亲遗传算法，可一次获得一批管网投资 最小的布置形式。文献嘲应用自适应遗传算法优化设计污水管网，直接以变量的二进制 编码为操作对象进行寻优而得到离散的标准管径。文献汹1 采用遗传算法对已定管线的排 水管网进行优化，引入了可行管径集的概念，直接利用标准管径并将各管段的管径映射 为适合于遗传算法操作的编码形式，并且通过算例证明这种方法的计算结果既能满足设 计规范的要求，又可节省工程投资。 利用遗传算法进行排水管网优化设计，需要事先编写程序，比较麻烦，并且大部分 的工作由计算机独立完成，结果具有一定的随机性。但较之其它方法，一般在解决中小 8 郑州大学硕士学位论文 管道系统设计时，遗传算法可以求得最优化设计方案；在解决大型管道系统时，尽管它 的搜索方法具有一定的随机性，但仍然可以求得趋近于最优解的可行方案。 1 3 本课题主要研究内容 周口市沙北污水处理厂的建设是淮河流域水环境治理的重要组成部分，也是促进周 1 3 沙北地区经济、社会效益同步发展的迫切需要3 6 1 。沙颖河以北地区污水管网改扩建工 程作为污水处理厂建设的配套工程，作用重大，它的建设好坏关系到沙北污水处理厂能 否切实的发挥作用、沙北和周口地区的环境污染能否得到有效的改变；该改扩建工程的 投资在整个污水处理厂建设工程中所占比重较大，需要进行方案的比较，如果采用传统 的设计方法，只能对几种方案进行对比，而且方案设计因人而异，很难做到真正的优化 设计。本研究以周口沙北污水管网改扩建工程为研究对象，探索利用遗传算法进行污水 管网优化设计的可行性和优越性，并为污水管网工程的设计提供多种优化设计方案，提 高工程设计水平和设计效率，为科学的方案决策提供依据。 基于城市污水管网系统的设计理论和遗传算法的基本原理与实现技术，本课题主要 进行了以下工作： ( 1 ) 对污水管网水力计算进行深入的研究和分析； ( 2 ) 遗传算法基本原理的应用和参数设置的改进措旌研究； ( 3 ) 以周口市沙北污水管网改扩建工程为实例，在管网布置形式已定的情况下， 以管网造价最低为目标函数，应用遗传算法进行管网参数优化，为遗传算法在设计工程 中的应用探索一条新途径； ( 4 ) 用m a t l a b 6 5 编写优化算法程序。 1 4 本章小结 作为排水工程重要组成部分的排水管网系统存在很多问题：盲点较多并且日益老 化，不能满足飞速增长的城市用水量和污水排放量的要求，新建和改造管网工程量需求 巨大；建设基金不足；传统设计过程费时费力，效率低下。排水管网优化设计不仅可以 缓解飞速增长的污水量和排水系统建设资金不足之间的矛盾，而且可以提高工程设计效 率和设计人员的设计水平，在实际应用中有着广阔的前景。为了探求排水管网系统的最 优化设计计算方法，国内外许多科研、设计、教学系统进行了不少的工作，并且随着系 统分析方法、计算技术和电子计算机的发展，遗传算法显示出比传统优化算法更大的优 9 郑州大学硕士学位论文 越性，它可以同时搜索可行解空间内的许多点，通过选择、杂交和变异等遗传操作，最 终得到最优解。本课题在认真研究管网水力参数之间函数关系和标准遗传算法的基础 上，得到污水管网优化思想，利用改进的遗传算法对管网布置形式已定的周口市沙北地 区污水管网改扩建工程进行优化，为遗传算法在设计工程中的应用探索一条新途径，并 且利用易于修改的m a t l a b 6 5 编写优化算法程序。 l o 郑州大学硕士学位论文 2 遗传算法基本原理 2 1 遗传算法简介 早在2 0 世纪6 0 年代初，一些生物学家就开始利用计算机模拟自然遗传系统，但由 于缺乏一种通用的编码方案，人们只能以变异而非交叉来产生新的基因结构，缺乏带有 指导性的理论和计算工具的开拓。2 0 世纪6 0 年代中期，美国m i c h i g a n 大学的j h o l l a n d 教授在a s f r a s e r 和h j b r e m e r m a n n 等人工作的基础上提出了能进行变异和交叉的二进 制位串编码技术，并强调将交叉作为主要的遗传操作。随后，h o l l a n d 教授将该算法用 于自然和人工系统的自适应行为研究中，并于1 9 7 5 年出版了其开创性著作“a d a p t a t i o n i n n a t u r a la n d a r t i f i c i a ls y s t e m ( 自然系统和人工系统的自适应性行为) ”，该书给出了遗 传算法的基本定理模式定理和大量的数学证明，奠定了遗传算法的理论基础，其中 首次确认了选择、交叉和变异等遗传算子，以及结构重组的遗传操作对获得隐含并行性 的重要作用，是遗传算法的经典之作；后来，h o l l a n d 等人将该算法加以推广，应用到 优化及机器学习等问题中，并正式命名为遗传算法。 在2 0 世纪6 0 、7 0 年代，由于遗传算法本身不成熟以及计算机不够普及等原因，遗 传算法的研究不受重视，但自8 0 年代中期以来，世界上许多国家掀起了遗传算法的研 究热潮，尤其是遗传算法的应用研究格外活跃【3 ”。例如，g o l d b e r g ( 1 9 8 3 ) 应用遗传 算法解决天然气管道系统的稳态和暂态优化以及机器学习问题；g o l d b e r g 和s a m t a n i ( 1 9 8 6 ) 采用遗传算法进行结构优化研究；s i m p s o n 等人应用遗传算法进行管网系统的 规划设计研究等。目前，遗传最优化技术在解决旅行商问题、煤气管道最优控制、通信 网络连接长度优化、铁路运输计划优化、高压输电线设计等工程优化问题中已取得很大 成功。据德国d o r t m u n d 大学1 9 9 3 年末的一份研究报告不完全统计遗传算法已在1 6 个 大领域、2 5 0 多个小领域中得到了广泛地应用。 随着遗传算法研究和应用的不断深入和发展，自1 9 8 5 年以来，以遗传算法为主题 的学术会议和研讨会在世界各地定期召开，极大地促进了国际间的研究交流与合作； i n t e r n e t 技术的发展和普及应用，遗传算法的有关研究单位建立了大量的专题网站，比 较著名的就是( h t t p ：w w w a i e n d n a v y m i l g a l i s t ) ，它包括了世界范围内开展遗传算法和 进化计算研究的大学和机构，历年来可公开发表的论文和报告，有关国际会议消息，典 型应用实例和程序( 源代码) ，等等。可以预料，随着遗传算法理论研究的深入和应用 领域的拓宽，遗传算法必将取得更大的成功。 郑州大学硕士学位论文 2 2 遗传算法的基本思想 遗传算法是一种模拟自然界生物群体进化过程的全局搜索算法，它是从代表问题可 能潜在解集的一个群体开始的，而一个群体则由经过基因编码的一定数目的个体组成。 每个个体实际上是带有染色体特征的实体，染色体作为遗传物质的主要载体及多个基因 的集合，其内部表现是某种基因组合，决定了个体的形状的外部表现。初始群体产生之 后，按照适者生存和优胜劣汰的原理，逐代演化产生出越来越好的近似解。在每一代， 根据问题域中个体的适应度大小挑选个体，并借助于自然遗传学的遗传算子进行组合交 叉和变异，产生出代表新的解集的群体，这个过程将导致群体像自然进化一样的后生代 群体比前代更加适应于环境，末代群体中的最优个体经过解码，可以作为问题近似最优 解。遗传算法必须完成的工作内容和基本步骤如图2 - 1 与图2 - 2 所示 3 9 , 4 2 4 珂： 图2 - 1遗传算法基本流程图 1 2 郑州大学硕士学位论文 群体 位串适应值排序 l io o o l l lo o 0 1 l l0 l0 1o l 0 l l l0 l0 0 0 l lo l l0 l l 0 l l 5 4 5i 3 8 3 3 4 3 72 3 4 6 4 新后代 选择 变异 交叉 图2 - 2 遗传算法算子示意图 交配池 iil0 0 0 lll0 0 l 1 0 ii10 10 0 0 l 1 i 交叉点l l 2 3 遗传算法的特点 作为一种新的随机优化技术，遗传算法能解决许多传统算法所不能解决的问题。与 传统优化方法相比，遗传算法具有以下特点【3 ”9 , 4 2 - 4 7 ： ( 1 ) 求解问题时，遗传算法首先要选择编码方式，它直接处理的对象是参数的编 码集而不是问题参数本身，搜索过程既不受优化函数连续性的约束，也没有优化函数导 数必须存在的要求。通过优良染色体基因的重组，遗传算法可以有效地处理传统上非常 复杂的优化函数求解问题。 ( 2 ) 遗传算法在每一代对群体规模为以的个体进行操作，实际上处理了大约o ( n 3 1 个模式，具有很高的并行性，因而具有显著的搜索效果。 ( 3 ) 遗传算法采用群体方式组织优化搜索，能同时对搜索空间中的多个解进行评 价；并采用概率的变迁规则来指导搜索过程，以随机方式执行选择、交叉和变异等遗传 算子，因此在所求解问题为非连续、多峰以及有噪声的情况下，能够以很大的概率收敛 到最优解或满意解，因而具有较好的全局最优解求解能力。 ( 4 ) 对函数的性态无要求，针对某一问题的遗传算法经简单修改即可适应于其他 问题，或者加入特定问题的领域知识，或者与已有算法相结合，能够较好地解决一类复 杂问题，因而具有较好的普适性和易扩充性。 ( 5 ) 传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。 1 3 口目 郑州大学硕士学位论文 2 4 遗传算法的实现方法 遗传算法的实现包括编码方式、群体规模取值、适应度函数设计、遗传算子( 选择、 交叉和变异) 以及相关控制参数的设定等，这几个方面对遗传算法的性能影响很大，必 须根据所要应用的问题，采用合适的编码方式，设计适当的遗传算子，才能使得遗传算 法得以有效的实现。 2 4 1 编码 按照遗传算法的工作流程，当用遗传算法解决问题时，必须在