（市政工程专业论文）供水管网早期预警监测系统水质监测点的优化布置研究.pdf

山东建筑大学硕士学位论文 摘要 供水管网空间分布广，影响范围大，极易受到不法分子的袭击，而一旦发生 此类恶性投污事件，将对人民的身体健康造成极大的伤害，因此很有必要在供 水管网建立一套预警监测系统，以便尽快地监测到水质状况的异常并向用户发 出报警信号，以保障人民群众的用水安全。 水质监测点作为供水管网早期预警监测系统的一部分，其位置和数量直接影 响水质预警体系的效率和投资。如何根据不同的管网特性，确定监测点数量与 监测效率之间的关系，以及如何在监测点数量确定的情况下，确定监测点在管 网中的位置以达到最大的监测效率，具有很高的研究价值。 国内外诸多学者对其进行了广泛而深入的研究，提出了线性规划、整数规划、 混合整数规划等优化模型，但在实际应用中均有其局限性。 本文利用电脑模拟恶性投污事件或者管网内部水质突然恶化时对整个供水 管网系统所造成的影响。通过模拟出的所有管网节点的水质变化情况，便可得 知每一节点( 若在该节点上安置水质监测点) 能监测到该投污事件的时刻以及 此时整个管网系统所遭受的危害( 此时被污染的节点数、被污染的管段长度、 用户所使用的被污染水的体积、处于污染水危害之下的人口数) 。通过考察危害 程度便可得出每一节点做为水质监测点的有效性。在监测点数量确定的情况下， 本文根据每一节点做为水质监测点的有效性，再利用优化算法来优选管网中的 节点，组成早期预警水质监测系统，以期发生恶性投污事件时，尽快监测到该 事件的发生并尽快发出报警信号，或者在发生恶性投污事件时，将其对人民群 众的危害降至最小。 本文模拟的是供水管网的动态的水力水质状况，而非静态状况，更加贴合于 管网的实际运行情况；同时本文考察了监测设备延迟、监测设备入口浓度等等 因素对优选水质监测点的影响。 遗传算法是近几年迅速发展起来的一项优化技术，它是模拟生物学中的自然 遗传变异机制而提出的随机优化算法，它是进化算法的一个重要分支，通过编 码、选择、杂交和变异等遗传操作，最终求得最优解，不仅适用于纯数学的优 化问题，而且也适用于一般的工程设计和优化问题。因此本文使用软件e p a n e t 模拟管网的动态水力水质情况后，再用遗传算法优选水质监测点，这一过程均 山东建筑大学硕士学位论文 在d e l p h i 中实现。 本文基于山东某市的供水现状，以及供水系统的相关运行数据，建立了该市 供水系统管网模型，对模拟程序进行测试。结果表明，在投资一定的情况下， 使用本文提出的方法可以建立最高效的管网水质预警监测系统；同时，减少监 测设备的延迟时间可以提高水质预警系统的效率，降低人民群众所面临的风险。 本文的理论和研究成果，可以为供水行业提供水质管理的辅助决策方案。 关键词：供水管网，预警，水质，监测点，优化布置，模拟，遗传算法 i i 山东建筑大学硕士学位论文 o p t i m a ll a y o u to fe a r l yw a r n i n gd e t e c t i o ns t a t i o n st os e c u r e w a t e rd i s t r i b u t i o ns y s t e m z h a n gy i n g ( m u n i c i p a le n g i n e e r i n g ) d i r e c t e db yy ix u e n o n g a b s t r a c t a sw a t e rd i s t r i b u t i o ns y s t e ms p r e a d sw i d e l y , i ti sb ep r o n et ob ep o l l u t e db y d e l i b e r a t ee x t e r n a lc o n t a m i n a t i o no ra c c i d e n t a lc o n t a m i n a t i o nt h a tt a k ep l a c ew i t h i n w a t e rd i s t r i b u t i o ns y s t e mb e c a u s eo fp i p ec o r r u p t i o n , e t c t h e s ee v e n t sw i l ld ob i g h a r mt ot h ep u b l i ch e a l t h , o n c ei to c c u r s a sar e s u l t ，i ti se s s e n t i a lt ob u i l da ne a r l y w a r n i n gd e t e c t i o ns y s t e m ( e w d s ) ，w h i c hi sc o m p r i s e do fc e r t a i nd e t e c t i o ns t a t i o n s ， t od e t e c tt h ec o n t a m i n a t i o no n c ei to c c u r sa n dt om a k eaw a r n i n gf o rp e o p l en o tt o u s et h ec o n t a m i n a t e dw a t e ra n ym o r e w h e nb u i l d i n gt h ee w d s ，t h e r ea r et w op r o b l e m s ：h o wm a n ym o n i t o r sa r e n e e d e da n dw h e r et ol o c a t et h e m n l el o c a t i o n so fm o n i t o r sd e t e r m i n et h e e f f e c t i v e n e s so fe w d s ，a sw e l la st h en u m b e ro fm o n i t o t sd e t e r m i n e st h ei n v e s t m e n t o fe w d s h o wt oe d u c et h er e l a t i o n s h i pb e t w e e nt h en u m b e ro fm o n i t o r sa n dt h e e f f e c t i v e n e s so fe w d s a n dw h e r et ol o c a t ec e r t a i nn u m b e ro fm o n i t o r ss oa st oh a v e t h em o s te f f e c t i v ee w d s ，a r ev a l u a b l et os t u d y o v e r s e a sa n dd o m e s t i ce x p e r t sa n dr e s e a r c h e r sh a v ed o n eal o to fw o r ka b o u t t h i sp r o b l e m m a n yo p t i m i z a t i o nt e c h n i q u e sh a v eb e e np r o m o t e dt os o l v ei t ，s u c ha s l i n e a rp r o g r a m m i n g ，i n t e g e rp r o g r a m m i n g ，m i x e di n t e g e rp r o g r a m m i n g ，e t c t h e s e t e c h n i q u e sh a v em a n yl i m i t a t i o n sw h e ns o l v i n gt h i sp r o b l e m t l l i ss t u d yu s e sc o m p u t e rt os i m u l a t et h ew a t e rq u a l i t yi nw a t e rd i s t r i b u t i o n s y s t e mw h e nd e l i b e r a t eo ra c c i d e n tc o n t a m i n a t i o no c c u r s f r o mt h ew a t e rq u a l i t y h i s t o r yo fe v e r yn o d e ，w ec a l lk n o ww h e nc o n t a m i n a n tw i l lp o l l u t et h i sn o d e ，o rt o s a yw h e nt h i sn o d ec a nd e t e c tt h ec o n t a m i n a n t ( i fa m o n i t o ri sp l a c e da tt h i sn o d e ) a l s o ，w ec a l lk n o ww h a th a r mt h ee v e n th a sd o n et ot h ed i s t r i b u t i o ns y s t e m ( t h e n u m b e ro fp o l l u t e dn o d e s ，t h el e n g t ho fp o l l u t e dp i p e s ，t h ev o l u m eo fc o n s u m e d i i i 山东建筑大学硕士学位论文 w a t e r , t h ep o p u l m i o ne x p o s e dt oc o n t a m i n a t i o n , e t c ) f r o mt h e s ed a t a , w ec a l ls e e t h ee f f e c t i v e n e s so fe v e r yn o d ew h e nm o n i t o ri sp l a c e do ni t b a s e do nt h e e f f e c t i v e n e s sd a t a , a l lo p t i m i z a t i o nt e c h n i q u ei su s e dt oi d e n t i f yt h eo p t i m a ll o c a t i o n s o ft h em o n i t o r s t h ee x t e n d e dp e r i o ds i m u l a t i o n ( e p s ) i su s e di nt h i ss t u d yt os i m u l a t et h e c o n t a m i n a t i o ne v e n t s ，r a t h e rt h a nt h es t e a d ys t a t es i m u l a t i o n t h i ss t u d ya l s ot a k e a c c o u n to ft h ei m p a c t so fm a n yf a c t o r s ，s u c ha st h ed e t e c t i o nd e l a yo fm o n i t o r i n g e q u i p m e n t ，t h en u m b e ro fs i m u l t a n e o u sp o l l u t i o ni n j e c t i o nn o d e s ，e t c d u r i n gt h el a s td e c a d e ，g e n e t i ca l g o r i t h m ( g a s ) b e c a m eo n eo ft h em o r er o b u s t o p t i m i z a t i o nt e c h n i q u e su s e di nw a t e rd i s t r i b u t i o ns y s t e mm a n a g e m e n t g a sa r e h e u r i s t i cc o m b i n a t o r i a ls e a r c ht e c h n i q u e st h a ti m i t a t et h em e c h a n i c so fn a t u r a l s e l e c t i o na n dn a t u r a lg e n e t i c so fd a r w i n sp r i n c i p l eo fe v o l u t i o n t h eb a s i ci d e ai st o s i m u l a t et h en a t u r a le v o l u t i o nm e c h a n i s m so fc h r o m o s o m e s ，i n v o l v i n gs e l e c t i o n ， c r o s s o v e r , a n dm u t a t i o n t h i ss t u d yu s e sg a st os e l e c to p t i m a ll o c a t i o n so ft h e d e w i o ns t a t i o n a l lt h e s eo p e r a t i o n sa r ed o n ew i t h i nd e l p h i b a s e do nt h ea c t u a lo p e r a t i o nd a t ao fs o m ec i t yi ns h a n d o n gp r o v i n c e ，i t sw a t e r d i s t r i b u t i o ns y s t e mm o d e li sb u i l ti nt h i ss t u d y t h em e t h o d o l o g yp r o m o t e di n t h i s s t u d yi sd e m o n s t r a t e dw i t l lt h i sm o d e l t h eo u t c o m ei n d i c a t e st h a tt h i sm e t h o d o l o g y c a nw o r ko u ta ne f f e c t i v ee w d sa n dt h a tr e d u c i n gt h ed e t e c t i o nd e l a yo fm o n i t o r i n g e q u i p m e n tc a ni m p r o v et h ee f f e c t i v e n e s so fe w d s t h eo u t c o m eo ft h i ss t u d yc a n b et a k e na sa s s i s t a n c es c h e m ef o rw a t e ru t i l i t i e s k e yw o r d s ：w a t e r d i s t r i b u t i o n s y s t e m ，e a r l yw a r n i n g ，w a t e rq u a l i t y , d e t e c t i o ns t a t i o n , o p t i m a ll a y o u t ，s i m u l m i o n ，g e n e t i ca l g o r i t h m i v 原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究 取得的成果。除丈中已经注明引用的内容外，论文中不合其他人已经发表或撰 写过的研究成果，也不包含为获得山东建筑大学或其他教育机构的学位证书而 使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确 方式标明。本人承担本声明的法律责任。 学位论文作者签名： 趣粗 e l 期超星：笸：多 学位论文使用授权声明 本学位论文作者完全了解山东建筑大学有关保留、使用学位论文的规定， 即：山东建筑大学有权保留并向国家有关部门或机构送交学位论文的复印件和 磁盘，允许论文被查阅和借阅。本人授权山东建筑大学可以将学位论文的全部 或部分内容编入有关数据库进行检索，可以采用影印、缩印或其它手段保存、 汇编学位论文。 保密论文在解密后遵守此声明。 学位论文作者签名：星叁勉日期塑垒：笸：! 皇 导师签名：李陬日期翌掣 山东建筑大学硕士学位论文 第1 章绪论 1 1 早期预警监测系统的意义 以往在水源、水厂处常常已设置水质监测器以便于水处理系统的运行管理， 而一旦自来水进入管网系统，则被认为水质变化不大，所以很少再在管网系统 设置监测器。然而美国9 1 1 事件以来，人们也更加关注供水系统的安全性，因 为供水管网系统空间分布广，服务对象多，恐怖分子可以通过水源、泵站、清 水池、水龙头等等地方投加污染物而极其轻易地危害到人民群众的身体健康和 正常的生产生活，因而对管网中的水质进行监控是非常有必要的。 除了恐怖分子恶性投污的小概率大危害的事件以外，管网系统中的自来水水 质还面临其它多种危险。例如，旧配水系统中存在的年久管道由于氧化腐蚀会 导致管网中出现一些不受欢迎的化学物质。地层下陷、管道接口松弛以及意外 爆管等也都有可能使被污染的水或土壤进入到配水系统。此外，也有可能出现 未经处理的水进入到配水系统中的情况。 以下是美国1 9 7 6 1 9 9 4 年期间对供水事故的统计结果，因与我国目前供水 状况相当，具有一定的参考借鉴价值。在近2 0 年的时间里，美国一共发生了4 1 4 起城市供水事故。其中净水厂处理运行缺陷3 8 8 起，占9 3 7 2 ，致病人数4 2 万余人；未经处理地下水事故9 起，占2 1 5 ，治病人数7 千余人；管网运行 缺陷7 起，占1 5 8 ，治病人数近8 万人；而其它各种原因只占3 左右【l 】。 从上面的统计看出，虽然管网运行缺陷仅发生7 起，但是治病人数却达到 8 万人，占致病人数比例1 9 ，远远高于事故比例的1 5 8 ，又由于管网造成的 水质安全问题处于分散状态，不象水厂运行事故那样易于发现和控制，往往对 人会造成更大的潜在、慢性的损害，更容易引起社会恐慌，对城市供水安全造 成更深远的负面影响【1 1 。所以，现在的市民已经不仅仅只关心水厂出水水质的 状况了，更关注于自来水从龙头里出来的水质是否达标，是否安全。 要达到保障水质的目标，就要建立一套由一系列设立于管网中的水质监测 点组成的早期预警监测系统，通过在线监测设备实时监测管网中的水质参数， 对其水质状况实行分析、评价，预报不正常状况的时空范围和危害程度，按需 要适时地给出警戒信息及相应的对策。 早期预警监测系统的总体目标是检测低概率高危害的水污染事件，并且允 山东建筑大学硕士学位论文 许足够的反应时间来做出恰当的反应，以减轻或避免其负面影响。对于意外发 生或蓄意实施的外部污染事件，水质监测点能够在允许的时间范围内，检测出 污染事件，发出报警信掣2 1 。 1 2 水质监测点优化布置的意义 有效的水质监测是对饮用水水质的有效保障。管网中一个点或者几个点的 压力降低，最多不过是减少了对用户的供水量；而一旦管网发生恶性投污事件 或者管网水质自身恶化可能对公众健康造成严重危害。 实际上，为了最大化地保障公众的健康安全，管网中的每个点都应该放置 监测器，这当然也就导致了监测系统的投资费用最大化。另一方面，如果假设 水质在管网中不会改变，那么只需在水源处放置监测器。由于水在管网中流动 时，诸多原因( 如蓄意投污事件、管道腐蚀或者三卤化物的形成等等) 皆可导 致水质发生变化，因而仅在水源处放置监测器便不能满足全面监控的要求。这 就涉及到要在管网中布置多少监测点以及在哪里布置监测点这两个问题。 就目前来说，有关监测点选址方法，基本上停留在人工的经验层次上，并 没有上升到理论的高度上来。布置了较多的监测点，花费了较大的投资成本， 而监测系统的效率却不一定高。要想避免这一问题，就要考虑监测点的优化布 置。也就是说确定监测点的位置，使得由有限数量的监测点所组成的监测系统 的效率达到最高。 早期预警监测系统的设计是由投资费用和保护水平来决定的，增加监测站 点的数目可提高保护水平，但也同时造成投资费用的增高，因而监测站点的优 化布置是实现二者平衡的关键，因此它具有很高的实用价值。 1 3 研究现状 在我国制定的城市供水管理一些相关的政策和标准中，有关监测点的选址 问题也只是定性的说明，要求布置在具有“代表性 的节点或管段中，并没有 说明究竟什么样的点才具有“代表性”。 为了实现这一目标，国内外的专家学者作了大量工作，提出了以下两个概 念：( 1 ) 流量覆盖( d e m a n dc o v e r a g em e t h o d ) ；( 2 ) 服务水平( 1 e v e lo f s e r v i c e ) 1 3 1 流量覆盖 l e ee ta 1 ( 1 9 9 1 ) 7 j 基于管网稳态流理论提出这样一种方法。首先假设：离水 源点距离越远，经过的时间越长，水质指标值就会越小。也就是说，如果某一 节点的水质是好的，那么该点的上游水质也是好的。在这里，水从某一点流向 该点，那么那一点就是该的上游。也就是说下游节点的水质可以指示其上游节 2 山东建筑大学硕士学位论文 点的水质。 然后通过水力分析获取每一点的路径( 路径是指从水源到该点所经过的所 有管段和节点) 。 再根据路径得到由元素w ( i j ) ( 其中w ( i j ) 指从上游节点j 流入下游节点i 的 水量占所有流向i 的水量之和的比例) 组成的矩阵w 。 最后根据一定的标准( 标准是指w ( i j ) 大于等于某一数值时，就认为j 的水 质可通过i 来指示，即j 被i 覆盖) ，将该矩阵转变成整数规划问题，就可以确 定监测点的位置以获取整个管网的最多的水质信息。 这种方法比较适用于管网水质自身发生变化的情况，对于对于外部投加污 染物造成的水质迅速恶化不太适用。比如对于一条长管段( 其上有许多节点且 有水流流出) ，上述方法会把该管段的末端节点设为监测点以达到最大覆盖度。 如果不考虑监测用时( 从污染发生到监测点最早监测到该污染的时间) 等限制 条件，这是可行的。然而在这种外部投污的紧急事件中，监测用时是非常重要 的。在布置预警系统的水质监测点时，必须要考虑监测用时这一重要因素。 k u m a re ta 1 ( 1 9 9 7 ) 8 1 沿用了l e ee ta 1 ( 1 9 9 1 ) f 刀的方法，建立矩阵w ，并通过 贪婪启发式算法重新排列矩阵w 使其更易于使用。 a i z a h r a n im a a n dm o i e dk ( 2 0 0 1 ) l 9 】沿用了l e ee ta 1 ( 1 9 9 1 ) 的方法，建立矩 阵w ，并使用遗传算法来获取监测点的优化布置。 虽然上述方法在不断改进，但由于都延用了l e ee ta 1 ( 1 9 9 1 ) 的假设条件“上 游节点水质可通过下游节点水质来指示 和目标函数“获取管网水质的最大信 息量 ，故而限制了这些方法在水质预警监测点优化布置中的应用。 1 3 2 服务水平 k e s s l e ra o s t f e l da a n ds i n a ig ( 1 9 9 8 ) ! 加j 应用服务水平( 1 e v e lo f s e r v i c e ) 的概念，提出了一种优化布置监测点的方法。其中当监测点监测到该污染事件 时，如果用户使用的污染水的体积不大于某一预先设定的数值q ，说明该监测点 对于此次污染事件是有效的。其中q 就是服务水平。q 越小，污染水对用户的健 康影响越小，表示该监测系统的效率越高。该文中优化选取预警监测点的步骤 如下： ( 1 ) 使用静态水力模拟获取所有可能的水流方向 ( 2 ) 假设以某一点作为投污点，用最短路径法获得该污染事件会影响到的 节点( 在q 体积的污染水被用户使用掉之前) ，即q 服务水平下，哪些点可以监 测到此次污染事件。 ( 3 ) 由于投污点可以是任何节点，所有依次以每个节点做为投污点，以获 山东建筑大学硕士学位论文 取每个节点的影响范围。即形成由元素m q ( i j ) 组成的污染矩阵m q 。 ，、f 1j 作为投污点，g 一服务水平下，胄邑够监测到此次投污事件，、 朋- 【，) 21o f 作为投污点，三一服务水平下，不能监测到此次投污事件 1 j ) i 行代表节点i 作为投污点时，能够监测到此次污染事件的节点( q 服务水 平下) ；j 列代表节点j 作为可能的监测点时，可以监测到的污染事件。 ( 4 ) 利用c h r i s t o f i d e s 算法选择最少的监测点使其能够在q 服务水平下监 测到整个管网可能会发生的污染。 o s t f e l da n dk e s s l e r ( 2 0 0 3 ) 1 1 1j 沿用了服务水平的概念，利用遗传算法来选择 最少的监测点使其能够在q 服务水平下监测到整个管网可能会发生的污染。 该方法的主要缺陷是：( 1 ) 没有考虑水质的变化和水的稀释作用，某些污染物 可通过稀释过程迅速扩散；( 2 ) 没有明确强调非稳态的水力条件；( 3 ) 只考虑单点 注入污染物的情况。 1 4 本文的研究目标、主要内容和方法概述 本课题的主要目标是寻求早期预警监测系统中水质监测点的优化布置，以 期达到这样的目标，即：用同样数量的监测点而建立的预警系统的效率最高， 或者说达到同样的预警系统效率而使用的监测点数量最少，实现预警系统效率 与系统投资之间的协调关系，为预警系统的设计提供科学依据。本课题包括以 下几方面的内容： ( 1 ) 选取合适的效率评价指标 在不同的评价指标下，所获取的监测点布置结果亦不相同。本文将在第二 章详细探讨不同指标之间的关系，选出合适的评价指标，以进行后面的研究。 ( 2 ) 建立监测点布置模型 建立怎样的模型体系来计算预警系统的效率，是本课题的主要研究内容。 本文将在第二章对已有的模型理论进行详细讨论，并建立切实可行的监测点布 置模型。 ( 3 ) 优化算法的应用 本文在考察大量资料文献的基础上，选择了具有高效、并行、全局搜索等 优点的遗传算法，用于监测点的优化选择，实践证明该方法稳定、有效。这部 分内容将在第三章进行详细地阐述。 同时为了验证本文所述方法的可行性和有效性，本文在第四章中以一个小 型管网和一个中型实际管网为背景，进行实例考察和结果分析。 4 山东建筑大学硕士学位论文 第2 章监测点优化布置模型 2 1 引言 在我国制定的城市供水管理一些相关的政策和标准中，有关监测点的选址 问题也只是定性的说明，要求布置在具有“代表性”的节点或管段中，并没有 说明究竟什么样的点才具有“代表性 。所以，就目前来说，有关监测点选址方 法，基本上停留在人工的经验层次上，并没有上升到理论的高度上来。布置了 较多的监测点，花费了较大的投资成本，而监测系统的效率却不一定高。要想 避免这一问题，就要考虑监测点的优化布置。本章就重点讲述监测点优化布置 模型建立的理论和方法。 2 2 建立监测点布置模型 本文采用动态模拟污染物在管网中的传播情况，即查看管网中各节点( 候 选监测点) 对该污染污染事件的反应情况，应用服务水平( 1 e v e lo fs e r v i c e ) 的 概念，评定每一节点作为候选监测点的有效性，即在所设定的服务水平内，该 候选监测点能否监测到污染事件的发生，并根据其有效性，选择一组监测点， 使其能最大化监测到管网中发生的污染事件。 所谓服务水平，就是指发生投污事件时，在用户遭受到一定程度的危害之 前，如果监测点能监测到此次投污事件，就可以说该监测点能提供这个程度的 服务。或者说，在该服务水平下，该监测点是有效的；否则就是无效的。 服务水平通常可以具体化为如下四个指标： 监测用时( w t d ：t i m et od e t e c t i o n ) ：从污染事件发生到污染事件被监测 到的时间。也叫做、小时服务水平”， 意思是说管网中任一点发生投 污事件时，监测系统中必须有至少一个监测点监测到该污染并发出报 警信号，这样该监测系统才被认为是有效的。 用户消耗的污染水的体积( v c ：v o l u m ec o n s u m e d ) ：在监测系统发出报 警之前，用户所消费的污染水的体积。 暴露在污染中的人口( p e ：p o p u l a t i o ne x p o s e d ) ：在监测系统发出报警 之前，使用受污水的人口数。 污染广度( e c ：e x t e n to fc o n t a m i n a t i o n ) ：在监测系统发出报警之前，被 污染的管段的长度。 山东建筑大学硕士学位论文 这些表示服务水平的指标都是相关的，但根据不同的指标得出的结果可能 是不一样的。第一个指标致力于寻求能尽快监测到污染事件的监测系统；而其 余的几个指标都是力求找到能最大化地降低污染事件危害的监测系统。不同的 指标侧重点不同。监测系统的初级目标应该是一旦污染发生，能尽快监测到污 染事件；然而最终目标又是尽量减少污染事件对用户的危害。本章以监测用时 为例介绍如何建立监测点优化布置模型。 2 2 1 动态模拟管网水力和水质情况 污染事件的本质特性非常复杂，管网系统的运行情况又具有多样性，所以 要模拟管网系统遭受污染后的情况变化，就要首先做一些简化和假设，以利于 研究的进行。 污染事件可在任何时间任何节点上发生，也就是说每个节点被投加污 染物的概率是相同的。 当某节点的污染物浓度c 超过监测器的监测浓度c 木( 与监测仪器的精 度有关) 时，就认为放置在该节点的监测器可以监测到该污染物。 可以用两种方式模拟供水管网的运行状况：静态模拟( s t e a d ys t a t es i m u l a t i o n ) 和动态模拟( e x t e n d e dp e r i o ds i m u l a t i o n ) 。静态模拟常被用在水力分析中，来考 察管网的极端情况或代表情况( 如最大日或者最大时) ，它不适用于实时变化的 实际管网，因而本文采用动态模拟来进行管网的水质分析。 在进行管网模拟之前，要确定一下参数：污染事件发生的时间、地点、污 染物的量以及投加污染物的方式( 连续投加还是一次完成) 。这些叫做污染情境 ( c o n t a m i n a t i o ns c e n a r i o ) 。设立好污染情境之后，就可以用模拟软件进行管网的 动态模拟了。 2 2 2 建立污染数据库( c o n t a m i n a t i o nd a t a b a s e ) 把每个节点依次作为投污点进行水质模拟。模拟数据( 每一个节点的浓度 信息) 产生之后就形成了污染数据库。同时，管网中任何节点的污染物浓度变 化都可以通过图表展示出来。 2 2 3 建立评价矩阵( e v a l u a t i o nm a t r i x ) 污染数据库中记录了所有节点在任何时刻的浓度信息，这些浓度组成污染 矩阵( p o l l u t i o nm a t r i x ) ，其元素g 砧就表示当在节点i 发生投污的f 时间之后， 节点嬲的污染物浓度。 6 山东建筑大学硕士学位论文 基于上述的污染矩阵，一个就可以按照以下方式建立：其元素为f ， r j ，巴，f r c 厂l dq ， ， - w t d 山，【1t m ，w t d ( 2 2 ) 即当，小于等于w t d 时，也就是说节点m 能在节点f 发生投污的w t d 小时 内监测到该污染时间，那么就认为该监测点m 是有效的，将厶，设为1 ，否则设 为0 。下矩阵”是一个甩以的0 1 矩阵。其中，露是指管网中的所有节点。该 矩阵的第所行就表示放置在节点垅处的监测点能在w t d 小时内监测到哪些节点 作为投污点所发生的污染事件；第f 列表示当节点f 发生污染事件时，该污染在 w t d 小时内所传播到的节点，也就是说能在w t d 小时内监测到该污染的所有节 点。 寻求行的组合以达到“f 矩阵”的最大“列覆盖 ( m a x i m u mc o l u m n c o v e r a g e ) 。即将几个行按照同列相加的原则建成一个一维数组a ，当这个数组 的某个元素仍( f 从1 到露) 大于等于l 时，代表这几个监测点组成的监测系统 能够监测到在节点f 处发生的污染事件。这个数组大于等于l 的元素越多，就 代表该监测系统的效率越高。这一步就是要考察哪些监测点组合起来形成效率 最高的监测系统。这一步可以通过应用优化算法来实现。 2 2 4 优化算法优选监测点 遗传算法( g a ：g e n e t i ca l g o r i t h m ) 是近几年迅速发展起来的一项优化技术， 它是模拟生物学中的自然遗传变异机制而提出的随机优化算法，它是进化算法 的一个重要分支，通过编码、选择、杂交和变异等遗传操作，最终求得最优解， 不仅适用于纯数学的优化问题，而且也适用于一般的工程设计和优化问题。近 几年在给水系统管理方面，遗传算法已成为一种非常有效的优化技术之一。在 确定污染矩阵和评价矩阵之后，本文就是使用遗传算法寻求能达到最大“列覆 7 山东建筑大学硕士学位论文 盖的监测点。 1 9 7 5 年h o l l a n d 教授出版了g a 方面的经典著作g a d a p m t i o ni nn a t u r a la n d a r t i f i c i f ls y s t e m s ) ) ，该书标志着遗传算法作为- - n 智能计算科学的正式诞生。 进入2 0 世纪8 0 年代，g a 己发展成一类自组织、自适应的综合优化技术，并开 始广泛应用于计算机科学、管理科学、工程技术等领域。遗传算法作为一种新 的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理以及应用范围 广等显著特点，奠定了它作为2 1 世纪关键智能计算之一的地位。 2 2 4 1 优化算法的基本要素 遗传算法就是在生物进化论的基础上，通过选择、交叉、变异等算子以及 根据实际问题构造出适应函数来解决优化问题的一种启发式算法。 遗传算法是一种群体型操作，该操作以群体中的所有个体为对象。遗传算 法的基本流程如图2 1 所示。 近几年在给水系统管理方面，遗传算法已成为一种非常有效的优化技术之 一。在确定污染矩阵和评价矩阵之后，本文就是使用遗传算法寻求能达到最大 “列覆盖”的监测点。 图2 1 遗传算法的基本流程 遗传算法中包含了如下六个基本要素：( 1 ) 参数编码；( 2 ) 初始群体的设定；( 3 ) 适应度函数的设计；( 4 ) 遗传操作设计；( 5 ) 控制参数的设定( 主要是指群体大小和 使用遗传操作的交叉概率、变异概率等) ；( 6 ) 算法终止法则的确定。这六个要素 8 山东建筑大学硕士学位论文 构成了遗传算法的核心内容。 1 ) 编码 由于遗传算法不能直接处理解空间的解数据，因此我们必须通过编码将他 们表示成遗传空间的由基因按一定结构组成的染色体或个体。这一转换就叫作 编码，也可以称作( 问题的) 表示( r e p r e s e n t a t i o n ) 。 一般来讲，由于遗传算法的鲁棒性，它对编码的要求并不苛刻。然而，编 码的策略或方法对于遗传操作，尤其是对于交叉操作的功能有很大影响。在很 多情况下，编码形式也就决定了交叉操作，编码问题往往称作编码一交叉问题。 因此，作为遗传算法流程中第一步的编码技术是遗传算法中需要认真考虑的课 题，它将直接影响到优化结果和算法的计算效率。 标准遗传算法( s g a ) 采用的是二进制编码方案，因为它符合d e j o n g 的编码 原理【3 1 。但二进制编码易引起精度和效率的冲突。为得到高精度最优解，个体 的二进制编码串就要保持相当的长度，从而造成计算量的迅速增加。要保证计 算效率，又不得不缩短编码长度，从而造成解的精度受限。因此，对于较复杂 的解空间，一般采用十进制编码方案4 1 或实数编码方案5 1 ，这种编码方案比较直 观，不需解码过程。 2 ) 初始群体的生成 由于遗传算法的群体性操作的需要，所以我们必须为遗传算法操作准备一 个由若干初始解组成的初始群体。 群体规模的确定受遗传操作中选择的影响很大。群体规模越大，遗传操作 所处理的模式就越多，生成有意义的最优解的机会就越高。换句话说，群体规 模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小。所以，从 考虑群体多样性出发，群体规模应较大。但是，群体规模太大会带来若干弊病： 一是从计算效率考虑，群体规模越大，其适应度评估次数增加，所以计算量也 增加，从而影响计算效率；二是群体中个体生存下来的概率( 即选择概率) 大多采 用和适应度成比例( 即蒙特卡罗模型) 的方法，当群体中个体非常多时，少量适应 度很高的个体就会被选择而生存下来，但大多数个体却被淘汰，这会影响配对 库的形成，从而影响交叉操作。另一方面，群体规模太小，会使遗传算法的搜 索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起早熟收敛现 象( p r e m a t u r ec o n v e r g e n c e ) 。显然，要避免早熟收敛现象，必须保持群体的多样 q 山东建筑大学硕士学位论文 性，即群体规模不能太小。在实际应用中群体个数的取值范围一般为几十几 百个。 3 1 适应度函数 遗传算法在进化搜索中基本上不用外部信息，仅用目标函数或适应度函数 为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。 对目标函数的唯一要求是，针对输入可计算出能加以比较的非负结果。在具体 应用中，适应度函数的设计要结合求解问题本身的要求而定。需要强调的是， 适应度函数评估是选择操作的依据。适应度函数设计直接影响到遗传算法的性 能。 4 ) 选择操作( 复制操作) 选择或复制操作的目的是为了从当前群体中选出优良的个体，使它们有机 会作为父代为下一代繁衍子孙。选择操作算子作用是判断个体优良与否，标准 就是个体各自的适应度值大小。个体适应度值越高，其被选中的机会就越多。 目前遗传算法中最基本也是最常用的是适应度比例法6 1 。它y , n t l 赌轮法或蒙特 卡罗模型，这个模型是利用比例于各个个体适应度的概率决定其子孙的遗留可 能性，即各个个体的选择概率和其适应度值成正比。设群体大小为n ，其中个 体i 的适应度值为石，则个体i 被选择的概率只为： v 只= z z ( 2 3 ) i = 1 此外，还有( 1 ) 期望值法：在此法中，首先计算各个个体遗留后代的期望值， 然后在被选择的个体期望值中减去0 5 。因此，即使最坏的情况，也可能比期望 值有0 5 的偏差遗留后代；( 2 ) 排位次法：此法是根据适应度把各个个体排序，然 后利用对于各位次序预先已被确定的概率，决定遗留后代。 上述三种选择法都是基于概率的选择，概率选择法的优点在于，对适应度 值低的个体也给予选择的机会，能维持群体的多样性。另一方面，即使适应度 值高的个体也有被淘汰的可能，这是概率选择的缺点。为弥补概率选择法的不 足，常常采用精华保存法【3 1 。这种方法，在现世代适应度大的个体不是受交叉 和变异的影响，而是无条件遗传给下一代，此法常被用于最优化问题。不过， 这种方法也有一定的不足，因为作为精华的个体的遗传因子在集团中急速扩大 的可能性高，有陷入局部最优解的危险。 1 0 山东建筑大学硕士学位论文 5 ) 交叉操作( 重组操作) 在自然界生物进化过程中起核心作用的是生物遗传基因的重组( 加上变 异) 。同样，遗传算法中起核心作用的是遗传操作的交叉算子。通过交叉操作， 遗传算法的搜索能力得以飞跃提高。以事先给定的交叉概率p ，在选择出的n 个 个体中任意选择两个个体进行交叉操作，产生两个新的个体，重复此过程直到 所有要求交叉( 重组) 的个体交叉完毕。交叉是两个染色体之间随机交换信息的一 种机制。交叉算子需保证前一代中优秀个体的性状能在后一代的新个体中尽可 能得到遗传和继承。 6 ) 变异操作 变异操作的基本内容是对群体中个体串的某些基因座上的基因值按一定变 异概率作变动。就基于 o ，1 ) 的二进制编码串而言，变异操作就是把某些基因座 上的值取反，即0 变l 或l 变0 ，而变异位置是随机选择的。 在遗传算法的结构中引入突然变异的目的在于：第一，使遗传算法具有局部 随机搜索功能；第二，维持群体的多样性，避免出现早熟收敛问题。变异和交叉 既有一定联系，又有不同之处。交叉与大范围的搜索手段相对应，而突然变异 可以说是局部探索手段。变异和交叉之间，有互补的一面，又有竞争的一面。 二者互补指当群体的全体陷于超平面，而只用交叉又不能摆脱超平面时，突然 变异有可能使之摆脱超平面。二者的竞争是指交叉所形成的积木程序块存在着 被突然变异破坏的危险。 从上述算法的描述中，可以知道，选择操作体现了优胜劣汰的竞争和进化思 想，遗传算法依靠选择保持优秀种群，而交叉和变异其目的都是为了产生优秀 个体。实际上，突然变异是为了更好地交叉，在这个意义上说，交叉和变异实 质上都是交叉，因此，交叉是遗传算法的核心，有了不断的交叉才能不断产生 新的各体，才能不断推陈出新。 7 1 遗传算法的终止法则 遗传算法的终止法则应根据不同的问题采用不同的法则。文【3 8 】把这些法则 归纳为四种。第一类方法就是给定一个最大的遗传代数g e n m a x ，算法迭代代 数在达到g e n m a x 时停止。第二类方法是给定问题一个下界l b ，当进化中达 到要求的偏差度时，算法终止。第三类方法则有一定的自适应性：设生物群体 中个体总数