（模式识别与智能系统专业论文）基于粒子群遗传混合优化算法的给水管网优化设计的研究.pdf

硕士学位论文 摘要 给水管网系统是城市供水系统的重要组成部分，其投资一般要占整个供水系 统总投资的5 0 8 0 。给水管网系统是一个由多种设施构成的供水输配系统，它直 接影响城市供水系统的运行费用和供水可靠性。随着城市规模的扩大，给水管网 也不断向着大型化、复杂化的方向发展。因此，进行给水管网优化设计具有重要 作用和意义。 目前，采用遗传算法求解给水管网优化问题正逐渐被国内外研究者所重视。 本文在当l j 给水管网优化设计研究成果和遗传算法的基本原理与实现方法的基础 上，一方面针对遗传算法变异算子难以确定和后期收敛速度缓慢容易陷入局部最 优解等问题，将遗传算法和粒子群算法结合使用。用粒子群优化算法构建遗传算 法中的变异算子即粒子群变异算子，形成粒子群遗传混合优化算法；另一方面在 给水管网经济性目标函数的基础上加入以节点富裕水头加权平均值和管网恢复力 定义的管网可靠性目标函数，组成给水管网的多目标数学模型。 在应用粒子群遗传混合优化算法求解给水管网多目标数学模型时，使用整数 编码技术对管径变量进行编码，可以避免其他方法带来的管径二次圆整问题；同 时采用罚函数法对目标函数进行改进，对违反经济流速约束的管段和违反节点水 压约束的节点采用惩罚技术加以处理以剔除不可行解。 最后，以一个具有典型代表性的给水管网优化设计工程案例对该优化模型和 粒子群遗传混合优化算法的理论、方法进行验证，并将计算结果与基本遗传算法 优化结果进行经济、水力性能和可靠性比较，充分说明了粒子群遗传混合优化算 法在给水管网设计中具有重要的理论和实用价值。 关键词：给水管网优化设计；遗传算法；粒子群算法；粒子群遗传混合优化算法； 罚函数 a b s t r a c t w a t e rd i s t r i b u t i o ns y s t e mi sa ni m p o r t a n tp a r to ft h eu r b a n w a t e rs u p p l ys y s t e m ， g e n e r a l l y , i t si n v e s t m e n ta c c o u n t sf o rt h e5 0 一8 0 o ft h et o t a li n v e s t m e n t t ow a t e r d i s t r i b u t i o ns y s t e m w a t e rs u p p l yn e t w o r ks y s t e mi sc o m p o s e d o fav a r i e t yo i f a c i l i t i e sf o rw a t e rd i s t r i b u t i o ns y s t e m ，w h i c hd i r e c t l y a f f e c t st h er u n n i n gc o s t s0 l ； u r b a nw a t e rs u p p l ys y s t e m sa n dw a t e rs u p p l yr e l i a b i l i t y w i t ht h ee x p a n s i o no fu r b a n s c a l e w a t e rs u p p l yn e t w o r kh a sb e e nd e v e l o p e dt o w a r dl a r g e 。s c a l e a n dc o m p i e x d i r e c t i o n t h e r e f o r e ，o p t i m a ld e s i g no fw a t e rd i s t r i b u t i o ns y s t e mp l a y sa l li m p o r t a n t a n dm e a n i n g f u lr o l e a tp r e s e n t ，t h eu s eo fg e n e t i ca l g o r i t h m sf o rp i p en e t w o r ko p t i m i z a t i o np r o b l e m i sg r a d u a l l yb e i n gv a l u e db yd o m e s t i ca n df o r e i g nr e s e a r c h e r s b a s e do nt h ec u r r e n t r e s e a r c hr e s u l t so fo p t i m a ld e s i g no fw a t e rd i s t r i b u t i o ns y s t e m ，t h eb a s i cp r i n c i p l ea n d i m p l e m e n tm e t h o do fg e n e t i ca l g o r i t h m ，t h i sp a p e r , o nt h eo n eh a n d ，t h i n k i n g t h a t m u t a t i o no p e r a t o ro fg e n e t i ca l g o r i t h m si sd i f f i c u l tt od e t e r m i n ea n dp o s t _ c o n v c r g e n c e s l o wi ss oe a s yt of a l li n t ol o c a lo p t i m i z a t i o np r o b l e m ，g e n e t i ca l g o r i t h m ( g a ) a n d p a r t i c l es w a r mo p t i m i z a t i o n ( p s o ) a r e u s e dc o n j o i n t l y u s i n gp a r t i c l es w a r m o p t i m i z a t i o na l g o r i t h mt oc o n s t r u c tt h em u t a t i o no p e r a t o ro fg e n e t i ca l g o r i t h m p s o m u t a t i o no p e r a t o r , i nt h i sw a yh y b r i dp a r t i c l es w a r m g e n e t i ca l g o r i t h m ( p s o g a ) c a n b ef o r m e d o nt h eo t h e rh a n d ，o nt h eb a s i so fe c o n o m i c a lo b j e c tf u n c t i o no fw a t e r d i s t r i b u t i o ns y s t e m ，w e i g h t e dm e a no fn o d a l e x t r a p r e s s u r e a n dr e l i a b l eo b je c t f u n c t i o no fp i p e n e t w o r kr e s i l i e n c ea r ea d d e d t oc o n s t i t u t em u l t 卜ob je c t l v e m a t h e m a t i c a lm o d e lo fw a t e rd i s t r i b u t i o ns y s t e m i nt h e a p p l i c a t i o n o f h y b r i dp a r t i c l es w a r m g e n e t i c a l g o r i t h m t os o i v e m u l t i o b j e c t i v em a t h e m a t i c a lm o d e lo fw a t e rd i s t r i b u t i o ns y s t e m ，d i a m e t e rv a r i a b i e s a r ee h o o d e db yi n t e g e rc o d i n gt e c h n o l o g y t oa v o i do t h e rm e t h o dr a i s e ss e c o n d r o u n d n e s sd i a m e t e r m e a n w h i l e ，p e n a l t y f u n c t i o n ，a n dp e n a l t yt e c h n o l o g yi s u s e d f u n c t i o ni su s e dt oi m p r o v et h eo b j e c t t op r o c e s sb a r r e l st h a tv i o l a t ee c o n o m y v e l o c i t vc o n s t r a i n t sa n dn o d e st h a tv i o l a t en o d e sp r e s s u r ec o n s t r a i n t s ，a n do n l yi n t h i s w a yt h ei n f e a s i b l es o l u t i o nc a n b ee l i m i n a t e d f i n a l l v t h et h e o r i e sa n dm e t h o d so fh y b r i dp a r t i c l es w a r m - g e n e t i ca l g o r i t h ma n d o p t i m i z a t i o nm o d e la r et e s t e db ys t u d y i n gat y p i c a lr e p r e s e n t a t i v eo fo p t i m a ld e s i g n o fw a t e rd i s t r i b u t i o ns y s t e mc a s e ，a n dc a l c u l a t e d r e s u l t sa n dt h er e s u l t so fb a s i c g e n e t i ca l g o r i t h ma r ec o m p a r e df r o mt h ea s p e c to fe c o n o m y , h y d r a u l i cp e r f o r m a n c e 硕：卜学位论文 a n dr e l i a b i l i t yt of u l l ye x p l a i nt h ei m p o r t a n tt h e o r e t i c a la n dp r a c t i c a lv a l u eo fh y b r i d p a r t i c l es w a r m g e n e t i ca l g o r i t h mi nt h ed e s i g no fw a t e rd i s t r i b u t i o ns y s t e m k e yw o r d s ：o p t i m a ld e s i g no fw a t e rd i s t r i b u t i o ns y s t e m ；g e n e t i ca l g o r i t h m ； p a r t i c l es w a r ma l g o r i t h m ；h y b r i dp a r t i c l es w a r m - g e n e t i ca l g o r i t h m ；p e n a l t yf u n c t i o n i i i 兰州理工大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名：日期：年月日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学 校有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅。本人授权兰州理工大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保 存和汇编本学位论文。同时授权中国科学技术信息研究所将本学位论文收 录到中国学位论文全文数据库，并通过网络向社会公众提供信息服务。 作者签名： 喜师签名： 习五次 日期：年月日 日期：沙啤 i s a t ： ( 2 2 3 ) g f ( x ) o ，i = 1 ，2 ，m j l j0 ) = 0 ，j = 1 ，2 ，z 式中， 0 ) ，2 ( x ) ，易q ) 为目标函数，昏g ) h j ( x ) 为约束函数。 在使用线性加权和法进行多目标函数的优化求解时，对那些相对主要的指标 给予较大的权重，对同等重要的目标函数赋予相同的权值。基于这个现实，我们 构造如下评价函数： d d d r 眦 = q d d i 淀詹 q d d；、一 p。p盯v箭 基于粒子群遗传混合优化算法的给水管网优化设计的研究 w 。w 1 ，w 2 ，w p w 1 ，w 2 ，w p 乏0 且w 。= 1 将评价函数与多目标函数做点积并求和， 题转化为单目标函数优化问题： ( 2 2 4 ) 将式( 2 2 3 ) 这个多目标函数优化问 m l n f ( d ) = f j + f 2 ，荟q 肛r 一日一 荟q t q p h p 一q f 日 m i n ，_ 1 一旦l l - 2 l _ 一 2 ( h r 一日一 ( 2 2 6 ) 给水管网优化设计中，管网的经济性和可靠性应当同样重要，所以线性加权 和法的权重系数设为0 5 。将式( 2 2 3 ) 多目标函数转化为单目标函数，转化后的 给水管网优化设计目标函数为： n f i n f ( d ) = 0 5 x 假+ f 2 ) + 0 5 x 瓴圻1 ) = o 5 ( ( g + 与1 0 0 套川附和卟 2 7 ， 0 5 x砉q 一。荟竺一善啦血 lnl 善q善q 一, j 该数学模型综合了管网优化设计的经济性和可靠行。进行管网优化设计，就 是在满足相关约束条件下，求出使式( 2 2 7 ) 最小值的管网管径组合方案。 1 6 硕十学位论文 2 4 本章小结 本章先从给水管网年建造费用与年运行管理费用之间关系的角度介绍了给水 管网经济性目标函数以及约束条件。然后用管网节点富余水头加权平均值与管网 恢复力这两个概念作为管网可靠性目标函数的表示方法，并在给水管网经济性目 标函数的基础上，建立了包含经济性和可靠性管网优化设计的多目标函数数学模 型。即在满足水压、水量、水力性能、管段流速、管径等约束条件前提下，求得 使管网年费用最小、管网可靠性最好的管径布置方案。 1 7 基于粒子群遗传混合优化算法的给水管网优化设计的研究 第3 章给水管网水力计算研究 给水管网优化设计的实质是一种离散管径组合优化问题，是在满足一定约束 条件下寻求使目标函数值最小的某种管径组合。为更好地解决给水管网优化设计 计算问题，本文将采用粒子群遗传混合算法用于管网优化设计【了7 1 。由于粒子群遗 传混合算法具有很好地解决离散组合优化问题的特点，故它可以应用到管网优化 设计这种离散变量的组合优化计算中。 在运用粒子群遗传混合算法进行管网优化设计计算时，群体中每个个体在每 一代进化过程中都必须进行管网水力分析计算( 这里特指稳定流状态下的管网平 差计算) ，以评价每一种可能存在管径组合方案水力性能的好坏程度以及目标函数 值大小。由于该水力分析过程对于检测遗传群体中每个个体的性能好坏来说是不 可避免和缺少的，因此给水管网水力计算是给水管网优化设计中必不可少的环节。 3 1 给水管网图形及水力计算的数学模式 3 1 1 管网图形的概念 管网图形性质可用图论的基本原理进行分析和理解【3 8 1 。管网是个组成部分关 系密切的线性的图，该图由“顶点 和“弧 组成，“顶点”相当于管网节点( 管 网图的节点包括：配水源节点、不同管径或不同材质的水管相连接的点，也就是 水流条件变化的点) ，“弧 相当于连接每个节点的管段。由于水流具有一定的方 向性，故可抽象地认为管网图是由管段和节点连接起来而形成的有向图。它可以 用数学模式来描述，其目的是表达管网结构的信息。在复杂管网求解的过程中， 信息是以管网图的元素或这些元素的系统来描述。通常表达管网图形性质的有力 数学工具是矩阵。 一般来说，管网图按其节点连接方式可分为树状管网、环状管网和混合管网。 从图3 1 可见，树状管网为“树枝图形，任意两节点之间只有一条管线连接； 环状管网是由一个或一个以上的环组成的图形，任意两节点之间至少有两条管线 连接； 1 8 硕七学位论文 工 - 3 45t 7 89矿书 1 11 2 1 31 4 1 0 ( 树状网)( 环状网) 图3 1 树状网和环状网 从多面体的欧拉定理，可以导出平面管网图形的节点数，、管段数j p 和基环 数之间的关系： p = j + l 1( 3 1 ) 树状网中，基环数l = o ，因此p - _ j 1 ，即管段数等于节点数减一。 环状网由s 个水压一定的配水源时，则基环数中应包括配水源连成的s 1 个 虚环和l 个实环。这时，节点数、管段数、环数和水压一定的节点数( 等于配水 源数) 之间的关系为： p = j + l s ( 3 2 ) 混合管网是由树状管网、环状管网组成，是一种结构比较复杂的管网图形。 混合管网是压力管网系统中的一种典型结构代表，是工程实践中最常用的一种形 式，它具有供水可靠性高、管网内各节点压力分布均匀、水量调度灵活、管道利 用率高，同时又具有相对经济的特点。 3 1 2 给水管网水力计算的数学模式 在进行给水管网优化设计时，管网水力计算数学模式的应用是相当广泛的， 也是非常重要的，这些数学模式是以下列基本概念为基础【3 8 】： ( 1 ) 给水管网主要是由配水源( 泵站和水塔) 、用户和管线这三部分组成的互 有联系的系统。 ( 2 ) 系统中每一组成部分或子系统的特性，可用流量、水头损失、某些参数 以及规定的水流流向加以表示。例如管线的水头损失等于其起端和终端节点压力 差。 ( 3 ) 用户可以看作是当量管段，其特性可用流量和压力加以表示，后者表示 流出节点的水压。为保证正常供水，各节点水压应大于等于所要求的最小自由水 压。 ( 4 ) 管线由管段组成，管线的直径越大，水头损失越小；管线的流量越大， 水头损失越大。可以规定管线流量方向与水头损失方向一致，流量方向代表管线 1 9 基于粒子群遗传混合优化算法的给水管网优化设计的研究 暑晕皇詈! 詈i ii 。imi i m m mi i 中水头损失的方向。 ( 5 ) 各种类型子系统的数量和相互关系称为管网结构，表示子系统之间关系 的图形称为管网图。 ( 6 ) 从水源进入输配水管网的流量，等于管网的总用水量。 ( 7 ) 管网中水流符合克契霍夫第一定理和克契霍夫第二定理。第一定理是管 网内任意一节点的进、出流量代数和为零；第二定理是一环内各管段水头损失代 数和为零。 3 2 给水管网水力计算基础方程 给水管网水力计算的任务是在流量已分配和管径已定的基础上，求出各管段 的实际流量，以及各节点的水压高程。为完成水力计算，须有以下原始资料：管 线定线图、水源位置、管段长度、节点地面高程、节点流量、要求的最小自由水 压等基本资料和数据。 设p 为管网中的管段总数，s 为水源数，为节点数( 包括水源节点在内) ， l 为环数，则未知量为p 个管段流量q f ，和水头损失h f ，s 个水源供水量和，个节 点水压凰，共计p u 心个未知量。求解上述未知量的基础方程有节点连续方程、 能量方程、压降方程以及水头损失方程。 ( 1 ) 节点平衡方程，即连续性方程，是指对任一节点，流向该节点的流量必 须等于该节点流出的节点流量，可写成： 罗+ q f 一0 ( 3 3 ) 式中： q i 一一节点f 的流量，l s ： g 玎一一与节点f 相连接的各管段流量，l s ，f ，j 分别为其起，止节点 编号。 ( 2 ) 环能量平衡方程，能量方程是指管网的回路方程，是管网中闭合环的能 量平衡方程，可写成： 罗一衄t ao ( 3 4 ) 局 式中： f 厂一属于环k 的管段f ，歹的水头损失，m ； 胁_ 一一环七的闭合差或增压、减压装置产生的水压差，m 。 对于式( 3 4 ) 管段水头损失的正负号规定如下：环的方向一般为顺时针方向， 当管段流向为顺时针时，管段水头损失为正，反之管段水头损失为负。当环k 内 有增压或减压设备时，风是环k 内增压( 如泵站) 或减压装置( 如减压阀) 产 生的水压差。在多源管网中，凤为两个配水源的水压差。单水源时，风= o 。 如果风不等于零，则在环的方向上，水压增高时取正值，水压降低时取负值。 硕士学位论文 曼皂曼皇皇! 曼曼曼蔓皇曼曼量皇曼蔓皇璺皇曼量- 一 i i ii i i ii,ii t i 万 f i n i i l ” i 率 坚 图3 2 环方程示惫 如图3 2 所示的环( i ) ，能量方程可写成：1 1 5 柏7 一1 1 6 一j i l 2 嘞3 一 4 = 0 。在图中， 用虚线连接节点1 与节点5 ，构成虚环( i i ) ，因节点1 的水压比节点5 高，水流 方向从节点1 到5 ，故虚管段为顺时针方向，取正号，此时，凰= 5 ，则能量方 程为：h 4 - h 3 - h 1 + 5 = o 。 ( 3 ) 压降方程，管段的水头损失可由该管段两端点的压力得出，两者之间的 关系式，称为压降方程( 即水头损失方程) 。根据能量守恒方程，该管段节点水头 之差，应等于该管段压降，可表示为： = n 一 ( 3 5 ) 式中：玩，马一一管段两端节点i ，的水压高程，m ； i l f f 一一管段水头损失，m 。 ( 4 ) 水头损失公式，管网计算时，一般不计局部阻力损失，必要时可适当增 大摩阻系数或当量长度而局部损失估计在内。如果只计沿程水头损失、流量q 和 水头损失h 的关系，一般用指数型公式表示： h 盯= s i s q 善 ( 3 6 ) 式中： f 厂一管段水头损失，m ； s f 广一管段摩阻； g i 岫管段流量，m 2 s ： 万一一指数； 如果考虑水流方向，并假定各管段的h 和口的符号相同，可写成： 一s 蚶鳓 ( 3 7 ) 摩阻曲和指数n 值与管材、管道的使用时间长短有关，可通过适用于这种管 材的水头损失公式来确定。并且以值与所采用的水头损失公式有关，对于海曾一 威廉公式，n = 1 8 5 2 ；海曾一威廉公式如下： 2 1 基于粒子群遗传混合优化算法的给水管网优化设计的研究 ”攀专站8 5 2 8 ， s = 1 0 6 7 c - 1 8 5 2 d 7 岛 ( 3 9 ) 式中，系数c 见表3 1 表3 1 海曾威廉粗糙系数c 值 3 3 给水管网图形信息的矩阵表示 根据本章第一节介绍的知识可知，任何管网给水都是由一些节点和管段连接 起来的几何图形，因为水流有一定方向，所以给水管网是有向图，它可以用数学 模式来描述，其目的是表达管网图形结构信息。为方便应用计算机求解各种管网 问题，必须采用一种有效的数学方法将给水管网图形信息输入计算机。表达管网 图形性质的有力数学工具是矩阵。在给水管网图中，管段、节点和基环等管网图 形信息和关系可以用矩阵表示，同时管网图形信息也可以以矩阵形式存储在计算 机中进行给水管网水力计算。 根据本章第二节可知，能完整表达给水管网图形中管段、节点和基环逻辑关 系的是节点平衡方程和环能量平衡方程。设给水管网有，个管段和j 个节点，按 照图论理论，节点平衡方程和环能量方程的矩阵形式如下： ( 1 ) 节点平衡方程 ：彳q + q 一0 ( 3 1 0 ) j _ 式中：q = q l ，q 2 q r 为节点流量集合，规定流向节点流量为负，流出节点 的流量为正；口= 日l ，9 2 劬 为管段流量集合；彳= 口玎 为基本关联矩阵，表示第f 节点与j 管段的衔接矩阵，如下： 口玎，1 ， 当，管段从f 节点流出 口 = 0 ，当，管段不与f 节点连接 一- 1 ，当管段流向j 节点 ( 2 ) 环能量平衡方程 硕士学位论文 b h 一龃k = 0 ( 3 1 1 ) 式中：h - h l ，h z ，啊】为管段水头损失集合，b - b k j 为管网基本回路矩阵如下： = 一1 ，当f 管段在七环上，水流为逆时针方向； = 0 ，匈管段不在七环上； = l翔管段在七环上，水流为顺时针方向； 3 4 给水管网水力计算 3 4 1 给水管网水力计算方法的分类 管网水力计算过程中，根据待求未知量的类型不同，可分为流量法和水压法。 如果以管段流量作为未知量的求解方法称为流量法；以节点水压作为未知量的计 算方法称为水压法【3 引。本文采用水压法进行管网水力计算，所以对流量法不再累 述。 3 4 2 水压法概述 水压法是用水头损失表示管段流量的管网计算方法。如公式( 3 5 ) 所示，连 接节点f ，_ 的管段水头损失h 等于管段两端节点水压高程凰，马之差。所以管段 水头损失可以用管段两端的节点水压表示，此时未知量从水头损失转化为节点水 压。任意拟定个节点水压都能满足环能量平衡方程( 3 4 ) ，因此通过节点平衡方 程和管段压降方程，计算各节点的水压并逐步调整，最后得到每一节点的真实水 压；节点水压求出后，即可通过任意管段两端的节点水压求出该管段水头损失， 进而从管段流量和水头损失的关系求出全部管段的流量。据上所述，用水压法计 算管网时的方程为：( 1 ) 用节点水压何表示管段流量q 的流量式；( 2 ) 连接在节 点f 上各管段的流量应满足节点平衡方程：( 3 ) 无需考虑环方程，因为在拟定节点 水压时，已满足环能量平衡方程。 应用指数型水头损失公式时，连接节点f ，的管段流量的和水头损失j i l 盯之 间的关系为： ”器等砧8 5 2 8 ， 将上式转化为： q o ；竺掣2 6 3 h 0 s 4 喝付0 s 4 ( 3 1 2 ) 可 其中： 基于粒子群遗传混合优化算法的给水管网优化设计的研究 心= 0 2 7 8 6 c d 善正3 z 尸 ( 3 1 3 ) 将压降方程( 3 5 ) 代入式( 3 1 2 ) ，得： 吩一b 一q ) 呱s i g n ( i - i f q ) ( 3 1 4 ) 式中s l n a ( h f 一马) 为符号函数： 1 1 ，q 日， s i g n ( h , 一q ) 一 一1 ，皿 y v ，1 ；l y m i ni fv ，1 y m i n 4 7 x ，1 ；x 刍+ v 刍“ 硕十学位论文 其中粒子的标号i = i ，2 ，；d = l ，2 ，d ：k 为迭代代数；是惯性因子；c 1 ，c 2 为学习因子( 或称加速因子) ，是两个正常数，一般取值为2 ；y l , y 2 是均匀分布于 o 1 之间的两个随机数；v m 。x ，v m i n 是速度上下限值。 式( 4 7 ) 的第一个式子主要通过三部分来计算粒子f 新的速度：粒子f 前一 时刻的速度，是粒子的虬陨性 ( i n e r t i a ) 行为，反映了粒子的记忆能力；粒子f 当前位置与自己最好位置之间的距离，是粒子的“认知 ( c o g n i t i o n ) 行为，表示 粒子吸取自身经验知识的过程，反映了粒子的思考能力；粒子f 当前位置与群体 最好位置之间的距离，是粒子的“社会 ( s o c i a l ) 行为，表示了粒子学习群体中 其他粒子经验的过程，反映了粒子之间的信息共享和相互合作。粒子f 通过式( 4 7 ) 的第四个式子计算新位置的坐标。通过式( 4 7 ) 即可决定粒子下一步的运动位置。 在图4 3 中，以两维空间为例描述了粒子根据式( 4 7 ) 从某一位置移动到某一新 位置的原理。 图4 3 粒子移动原理图 图中，x x i k “表示粒子移动前后的位置， ， y ；“1 表示粒子移动前后的速 度，p i 为个体极值，p g 为全局极值。 4 2 3 粒子群算法流程 粒子群算法的计算过程如图4 4 基于粒子群遗传混合优化算法的给水管网优化设计的研究 随机初始化每个粒子 评估每个粒子并得到全局最优 一j 一 一一 更新每个粒子的速度和位置 0 评估每个粒子的函数适应值 l 更新每个粒子历史最优位置l 更新群体的全局最优位置 图4 4 粒子群算法流程图 粒子群算法主要计算步骤如下： s t e p l ：初始化，设定加速常数c 1 、c 2 ，最大进化代数盯，将当前进化代 数置为t = l ，在定义空间尺中随机产生m 个粒子s = ( x 1 ，x 2 ，规，轴) ，组成初 始种群；随机产生各粒子初始速度和位置。 s t e p 2 ：评价种群，计算每个粒子在每一维空间的适应值。 s t e p 3 ：比较粒子的适应值和自身最优值p b e s t 。如果当前值比p b e s t 更优，则 置p b e s t 为当前值。并设p b e s t 位置为d 维空间中的当前位置。 s t e p 4 ：比较粒子的适应值与种群最优值g b e s t 。如果当前值g b e s t 更优，则重 置g b e s t 的索引号。 s t e p 5 ：按式( 4 7 ) 更新粒子速度和位置，产生新种群。 s t e p 6 ：检查结束条件，若满足，则结束寻优；否则，t = t + l ，转至s t e p 2 。结 束条件为寻优达到最大进化代数甜或足够好的适应值。 硕十学位论文 4 2 4 粒子群算法的参数分析 粒子群算法中并没有许多参数需要调节，主要是种群规模m ，粒子长度d ， 惯性因子c o ，加速因子c 1 、c 2 ，速度限定y m 。x ，v m i n l 4 3 1 。 ( 1 ) 种群规模m ( 粒子个数) 。当m 取值较小时，p s o 的运算速度较快，但 由于种群的多样性差，容易引起过早收敛；而当m 取值较大时，又会使得p s o 的寻优效率降低。对于大部分问题，一般取2 0 - - 4 0 个粒子已经足够取得好的结果， 对于比较难的问题或者特定类别的问题，粒子的个数可以取得1 0 0 或2 0 0 。 ( 2 ) 粒子长度d ( 空间维度) ，就是问题解得空间维度。 ( 3 ) 惯性因子c o ，它对算法的收敛性起到很大的作用，它使粒子保持运动惯 性，使其有扩展搜索空间的趋势，有能力探索新的区域。通过调整的大小来控 制以前速度对当前速度影响，折中全局搜索与局部搜索，协调搜索精度与搜索速 度。0 7 值小些，有利于在当前解的空间里挖掘更好的解，有利于局部搜索和得到 更为精确的解，但搜索速度慢且有时会陷入局部极值；c o 值大些，有利于粒子搜 索更大的空间，发现新的解域，有利于全局搜索和得到较快的收敛速度，但不易 得到精确解。 ( 4 ) 加速因子c l 、c 2 ，它们对算法的收敛速度影响较大，它们反映了粒子 的自身经验与社会经验在其运动中所起的作用，代表了将每个粒子推向其个体历 史最好位置和全局历史最好位置的统计加速项的权值。合适的加速系数有利于算 法较快收敛和脱离局部极值。低的c l 、c 2 值，许粒子在被拉回之前可以在目标 区域外徘徊；而高的c 1 、c 2 值，则可能导致粒子突然地冲向或越过目标区域。 4 2 5 粒子群算法的特点 粒子群算法具有以下主要优点：易于描述；便于实现；需要调整的参数很少； 使用规模相对较小的群体；收敛需要评估函数的次数少；收敛速度快。 粒子群算法很容易实现，由于其内存和c p u 速度需求都很低，计算代价低。 而且，它不需要目标函数的梯度信息，只依靠函数值。粒子群算法己被证明是解 决许多全局优化问题的有效方法。 4 3 粒子群遗传混合优化算法 粒子群算法和遗传算法同属于进化算法，而在进化算法的研究当中，单一进 化算法的探测和开发能力仅靠算法自身的操作往往无法得到有效的利用与平衡， 从而影响了进化算法的求解精度和效率。故不少学者提出了混合两种算法或多种 算法在一个算法当中，以尽量发挥各个算法的优点。为了提高遗传算法的局部搜 索能力和克服早熟现象，本文提出一种基于遗传算法的粒子群遗传混合优化算法 ( h y b r i dp a r t i c l es w a r m g e n e t i ca l g o r i t h m - p s o g a ) 。其主要原理是将粒子群优化算 4 1 基于粒子群遗传混合优化算法的给水管网优化设计的研冗 法引入到遗传算法中，用粒子群优化算法构建遗传算法中的变异算子，使得染色 体在变异的过程中打破随机变异的特性而根据以往信息的引导进行有向变异。这 样保证了下一代染色体的优良性，使得整个种群能够快速良性发展，这样既可以 确保在全局范围内寻找最优点，而不至于落入局部最优点，又可以避免传统遗传 算法带来的“早熟收敛 。 粒子群算法( p s o ) 与遗传算法( g a ) 结合是由各自的优缺点决定的。 ( 1 ) 均可采用二进制编码、序号编码及整数编码，在编码上可以实现统一。 ( 2 ) 遗传算法中全局收敛理论是以进化代数无限大为前提的，变异算子有助 于增加种群的多样性，但如果变异概率过小，不易产生新的个体结构；变异概率 过大，又会导致搜索的盲目性、随机性，严重影响搜索过程。 p s o 收敛速度快，需要确定的经验性参数少，而且对种群规模大小不十分敏 感，即种群数目下降时性能下降不是很大，但是容易“早熟收敛。粒子群优化算 法中一旦某一粒子发现一个当前最优位置，其他粒子将迅速向其靠拢，聚集在该 点。此时，整个群体丧失了多样性，粒子之间无法相互作用、相互影响。而算法 是依靠群体之间的合作来指导寻优的，粒子本身没有变异机制，整个群体就停滞 在该点。如果该点是局部最优，粒子群就无法再搜索其他区域，算法陷入局部最 优，出现所谓的早熟收敛。 ( 3 ) g a 所有个体通过竞争来被选择成为最优解，所以整个种群是均匀的在 向最优区域移动。 p s o 算法则是通过个体之间的协作来寻找最优解的，而不是竞争。只有群体 的最优位置单向的传递信息给其它粒子，并且个体之间不直接共享信息。 ( 4 ) g a 的个体不具有记忆功能，每个个体只反映其目前状态，进化幅度和 方向不能适时调整。 p s o 算法的个体( 粒子) 则具有记忆功能，可根据历史信息和当前状态来控制 进化幅度和方向，在多数情况下，粒子都能更快地收敛于最优解。 ( 5 ) g a 的遗传操作是无方向制导的，是随机进行的，会导致遗传操作得到 的个体由于适应度低而被淘汰。 p s o 的优化过程是有方向的，它根据个体距离迄今最优解及群体最优解的远 近来自动调整优化的幅度和方向，总是在迄今最优解附近进行，避免了优化的盲 目性。 根据以上几点分析，将p s o 与g a 结合建构成粒子群遗传混合优化算法 ( h y b r i dp a r t i c l es w a r m g e n e t i ca l g o r i t h m p s o g a ) ，可以将两个单一算法相互融 合、互补，发挥各自的优点而弥补对方的缺点，得到更好的寻优效果及速度。 4 2 硕七学位论文 4 4 粒子群遗传混合优化算法在给水管网优化设计中的具体应用 粒子群遗传混合优化算法是一种扩展性能极强的优化方法，它利用所要解决 问题的有关信息，通过各种选择模式、对遗传算子和粒子群参数进行确定、修正 和改进，实现对特定问题的优化求解。在运用粒子群遗传混合优化算法进行给水 管网优化设计计算时，所选择的编码方式、种群大小、适应度函数构造方法、各 遗传控制参数和粒子群参数的选定、约束条件多处理以及所选用的水力计算方法 等都极大地影响着优化算法的性能和优化结果的精度。 应用改进混合遗传算法进行管网优化设计计算，其主要步骤为： ( 1 ) 定义混合管网管径优化问题的目标函数和约束条件，确定待求解问题的 解变量以及变量的定义域。 ( 2 ) 选择适当的编码方式，将问题解空间内的解变量映射为遗传算法的染色 体串。 ( 3 ) 确定遗传算法和粒子群算法各基本参数值，产生初始群体。 ( 4 ) 根据所能选用标准管径集，将初始群体中染色体串解码为管网各管段所 对应的管径值。 ( 5 ) 读取能反映管网节点、管段信息的等原始数据，对遗传群体中各染色体 个体的水力特性进行分析，计算节点水压、管段水头损失和对应的目标函数值， 并将目标函数值映射为染色体个体所对应的适应度函数值。 ( 6 ) 对遗传群体执行选择、交叉遗传操作和粒子群变异操作，产生新一代遗 传群体。 ( 7 ) 重复步骤( 4 ) 、( 5 ) 和( 6 ) 。 ( 8 ) 满足算法终止条件时，将函数适应值最小的染色体串解码为管段管径， 获得最优管径布置方案。 4 4 1 适应度函数设计 粒子群遗传混合优化算法用于给水管网优化设计时，需要将优化设计目标函 数映射为能反映群体中染色体个体性能好坏的适应度函数。根据第二章管网优化 设计目标函数，通过惩罚策略，将管段经济性流速限制和节点水压限制这两约束 条件转化为无约束问题，将优化设计目标函数映射为遗传算法适应值函数【4 4 4 5 1 。 根据第2 3 节内容，管网优化设计多目标函数模型转化为单目标函数模型 倒) ，见( 2 2 7 ) 式。对于该数学模型的遗传算法求解，在将目标函数映射为遗传算 法适应值函数过程中，对于管段经济性流速和节点水压这两个约束条件，须将约 束条件无约束化，为此，这里使用加法形式的惩罚策略，将该问题目标函数映射 为遗传算法所使用的适应度函数： 4 3 基于粒子群遗传混合优化算法的给水管网优化设计的研冗 m i n f ) 一o 5 ( e 峨) + o 5 x 以何1 ) + a m a x ( 矿一只，0 ，h i 一矿) r ( 4 8 ) + 口 m a x 产一“ 0 “，一比严) 2 式中： m a x ( h 尸i 6 一皿，0 ，e 只吣) 】2 ， m a x 严一比，o ，h j 一比尹娃) 】2 分别为节 点水压约束函数和经济流速约束函数；o ，a 为惩罚因子。在已知管网布置形式、 用户用水量、用水压力的条件下，节点水压和泵站的扬程均由管径组合确定，因 此这样构造适应度函数是科学合理的。 在遗传算法中，各个个体被遗传到下一代的概率是由其适应度来确定的。实 践表明，如何确定适应度函数对遗传算法的性能有很大的影响。有时在遗传算法 运行的不同阶段，还需对个体的适应度进行适当的扩大或缩小。这种对个体适应 度所作的扩大或缩小就称作适应度尺度变换( f i t n e s ss c a l i n gt r a n s f o r m ) t 4 6 1 。 在本文中，对原适应度采用线性变换法。将原适应度函数变换为能够反映群 体中个体性能好坏的适应度函数。线性变换如下： 八咖1 1 1 i n ，i 口l 州) - 彘厂 ( 4 9 ) ( 4 1 0 ) 在使用粒子群遗传混合优化算法进行管网优化设计计算时，直接以( 4 1 0 ) 式作 为检测每代染色体性能好坏标准，反映对应解的优劣程度，通过交叉遗传操作和 粒子群变异操作，使染色体向着性能较优的区域发展，最终求得使目标函数值和 适应度函数值为最小染色体对对应对管径布置为最优方案。 4 4 2 编码方式和初始种群的产生 针对二进制编码在管网优化设计中存在的缺陷和不足，本文使用一种基于整 数编码技术的遗传算法来实现给水管网优化设计计算。 整数编码是指将一系列整数与标准管径的种类进行一一对应，将管径的种类 集合映射为一系列对应的整数集合，在进行遗传操作时直接对这些离散整数进行 操作，最后将表示管径组合方案的整数串解码成对应的管径。例如，假设管网中 有8 根管段，其可选用的标准管径种类为5 种，即：d = 1 0 01 5 02 0 0 3 0 04 0 0 ) ， 对于一组整数编码为 5132 4142 ) 的管径组合方案，其表示的管径组合为( 4 0 0 1 0 02 0 01 5 03 0 01 0 03 0 01 5 0 ) 4 7 】。 同二进制编码方式相比，该编码方式明显减少了群体中染色体的串长，缩短 了表示管径组合方案所必须的编码长度，使编码、解码、交叉等遗传操作和粒子 硕十学位论文 群变异操作所需处理的工作量大大减小；另外，这种编码方式不存在冗余码问题， 符合一般使用者的设计习惯，程序实现起来也非常简单方便。 粒子群遗传混合优化算法的第一步是创建由任意染色体组成的初始种群，遗 传操作、粒子群变异操作、适应值函数计算及最适应个体的获得都在此基础上进 行。在本问题中，由于采用的是整数编码技术，且染色体基因位的基本字符与具 有离散特性的标准管径相对应，并且满足标准管径与基因值之间的一一对应关系。 4 4 3 遗传算子设计 选择算子 用轮盘赌方法，又称为适应度比例法，这是目前遗传算法中最基本也是最常 用的选择方法。其基本原理见4 1 3 节。这种方法利用比例于每个个体适应度值 的概率来决定其