（计算机软件与理论专业论文）基于微粒群算法的污水管道优化系统研究.pdf

基壬微揎叠簋选笪透盔筐道选丝丕统婴窥主塞擅墨 中文摘要 本文以苏州市污水管道系统规划项目为背景。管道系统规划通常涉及管道布局优 化和管道水力参数优化两部分。通常情况下，污水管道系统投资较大，偿还期限长， 这就需要提供一种比较先进、可靠的设计方法( 算法) 或设计平台，对污水管道进行优 化设计，寻求满足各种技术条件，且能使整个系统总费用最低的设计方案。这不仅具 有重要的理论和应用价值，而且具有明显的经济和社会效益。 本文提出基于改进微粒群的方法，用于解决污水管道优化问题，目标是使整个污 水管道系统的费用降低。本文的主要研究成果如下： ( 1 ) 将离散微粒群算法应用到污水管网布局优化中。首先建立了污水管网布局优 化的数学模型，将离散微粒群算法应用到该模型中。实验结果与遗传算法相比，离散 微粒群算法具有更好的性能。 ( 2 ) 针对微粒群算法收敛速度慢及多样性丢失等问题，在基于带有微分扰动因子 的微粒群优化算法基础上，提出了一种改进多种群的微粒群算法。 ( 3 ) 将改进多种群的微粒群算法应用到污水管道水力参数优化设计中。以苏州市 管道规划为应用背景，建立相应的简化数学模型。该算法应用于污水管道水力参数优 化，实验结果表明，该算法是可行和高效的。 ( 4 ) 开发了污水管道优化系统。依托苏州园区联图软件公司，基于改进微粒群的 算法，开发了污水管道优化系统，实现了与公司原有管道系统的无缝对接。目前该系 统已经应用于污水管道优化中，使整个管道系统的费用较以前有明显降低。 ( 5 ) 开发了污水管线管理系统。为了实现项目方式管理成果数据，根据不同管线 特点，实现点线数据的快速编辑等，采用m i c r o s t a t i o nd e v e l o p m e n tl a n g u a g e ( m d l ) 语言在m i c r o s t a t i o n 环境下开发了污水管线管理系统。目前，该系统已应用到管道局的 管线产品管理中。 本课题求解方法具有理论意义和应用参考价值，为继续深入研究污水管道优化设 计方法提供了参考。 关键词：微粒群算法，布局优化，水力参数优化，管道优化系统 作者：李明华 指导教师：刘全( 教授) r e s e a r c ho no p t i m a l s y s t e mo f t h es e w a g ep i p e l i n e ba se do np a r t i c l es w a r m a l g o r i t h m a b s t r a c t i nt h ep a p e r , t h ee n g i n e e r i n gb a c k g r o u n di ss e w a g ep i p e l i n es y s t e mp r o j e c ti ns u z h o u c i t y p i p e l i n es y s t e mp l a n n i n gu s u a l l yi n v o l v e sp i p e l i n el a y o u to p t i m i z a t i o na n dp i p e l i n e h y d r a u l i cp a r a m e t e ro p t i m i z a t i o n i ng e n e r a l ，t h e r ei sal a r g ei n v e s t m e n ta n dal o n g r e p a y m e n tp e r i o df o rs e w a g ep i p e l i n es y s t e m t h i sw i l ln e e dt oo f f e ram o r ea d v a n c e da n d r e l i a b l ed e s i g nm e t h o d ( a l g o r i t h m ) o rd e s i g np l a t f o r mt oo p t i m i z et h ed e s i g no ft h es e w e r s ， m a k ea no p t i m i z e dd e s i g na c c o r d i n g t ot h es e w a g ep i p en e t w o r k ，a n ds e e kt h ee c o n o m i c a n dr e a s o n a b l ed e s i g ns c h e m e ，w h i c hw i l lh a v ee x t r e m e l yv i t a ls i g n i f i c a n c e a ni m p r o v e dp 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 l g o r i t h mi sp r o p o s e da n da p p l i e dt o s e w a g ep i p e l i n eo p t i m i z a t i o ns ot h a tt h ec o s to ft h ew h o l es y s t e mf o rs e w a g ep i p e l i n ei s r e d u c e d t h em a i nr e s e a r c hr e s u l t sa r ea sf o l l o w s ： ( 1 ) d i s c r e t ep a r t i c l es w a r ma l g o r i t h mw i l lb ea p p l i e dt oo p t i m i z et h el a y o u to ft h e s e w e r s f i r s t ，l a y o u to p t i m i z a t i o nm a t h e m a t i c a lm o d e lf o ras e w a g ep i p en e t w o r ki s e s t a b l i s h e d ，a n dt h e nd i s c r e t ep a r t i c l es w a r ma l g o r i t h mi sa p p l i e dt ot h em o d e l c o m p a r e d w i t hg e n e t i ca l g o r i t h m ( g a ) ，t h ee x p e r i m e n t a lr e s u l t ss h o wt h a td i s c r e t ep a r t i c l es w a r m a l g o r i t h mh a sb e t t e rp e r f o r m a n c e ( 2 ) b a s e do nt h ed i f f e r e n t i a ld i s t u r b a n c ef a c t o rp a r t i c l es w a r mo p t i m i z a t i o n ，a l l i m p r o v e dm u l t i s w a r mp a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ( m s p s o ) i sp r e s e n t e dt o s o l v et h ep r o b l e mo ft h es l o wc o n v e r g e n c ea n d d i v e r s i t yi s s u e sf o rl o s s ( 3 ) ap a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h mb a s e do ni m p r o v e dm u l t i - s w a r mi s a p p l i e dt oh y d r a u l i cp a r a m e t e r so p t i m i z e dd e s i g no ft h es e w e r s u n d e rt h eb a c k g r o u n do f s e w a g es y s t e m f o rt h e p i p e l i n ep r o j e c t i ns u z h o u c i t y , c o r r e s p o n d i n gs i m p l i f i e d m a t h e m a t i c a lm o d e li se s t a b l i s h e d t h ea l g o r i t h mi sa p p l i e dt ot h es e w e r s h y d r a u l i c p a r a m e t e r so p t i m i z a t i o n ，a n dt h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ea l g o r i t h mi sf e a s i b l e l i a n de f f i c i e n t ( 4 ) t h es e w a g ep i p e l i n eo p t i m a ls y s t e mi sd e v e l o p e d b a s e d o na ni m p r o v e d m u l t i s w a n lp s o ( i v i s p s o ) m e t h o d ，t h es e w a g eo p t i m a ls y s t e mi sd e v e l o p e dr e l y i n go n s h z h o uu n i m a ps o f t w a r ec o l t d ，w h i c hi ss e a m l e s sw i t ht h ec o m p a n y se x i s t i n gp i p e l i n e s y s t e m t h es y s t e mh a sb e e na p p l i e dt oo p t i m i z a t i o no ft h es e w e r ss ot h a tt h ew h o l e p i p e l i n es y s t e mc o s ti ss i g n i f i c a n t l yl o w e rt h a ni n t h ep a s t ( 5 ) s e w a g ep i p e l i n em e a s u r e ds y s t e mi sd e v e l o p e d i no r d e rt oa c h i e v er e s u l td a t a m a n a g e m e n ti nt h ew a y o fp r o j e c t ，a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fd i f f e r e n tp i p e l i n e s ， a c h i e v er a p i dd a t ae d i t i n gf o rp o i n ta n dl i n ee t c ，s e w a g ep i p e l i n em e a s u r e ds y s t e mi s d e v e l o p e du s i n gm i c r o s t a t i o nd e v e l o p m e n tl a n g u a g e ( m d l ) i nt h e m i c r o s t a t i o n e n v i r o n m e n t t h es y s t e mh a sb e e na p p l i e dt op i p e l i n ep r o d u c to fp i p e l i n eb u r e a ua t p r e s e n t t h i sr e s e a r c ha n dp r o p o s e dm e t h o dn o to n l yb e n e f i tt h ed e v e l o p m e n to ft e c h n i q u e si n r e l a t e df i e l d st h e o r e t i c a l l y , b u ta l s oi tc a nb ea p p l i e dt op r a c t i c a la p p l i c a t i o n m o r e o v e r , i t m a k e sr e f e r e n c ef o rf u r t h e rr e s e a r c hi nt h es e w a g ep i p e l i n eo p t i m i z a t i o nf i e l d k e yw o r d s ：p a r t i c l es w a r mo p t i m i z a t i o na l g o r i t h m ，l a y o u to p t i m i z a t i o n ，h y d r a u l i c p a r a m e t e r so p t i m i z a t i o n ，p i p e l i n eo p t i m a ls y s t e m i i i w r i t t e nb y s u p e r v i s e db y ： m i n g h u al i q u a n l i u 苏州大学学位论文独创性声明及使用授权声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或集体已经发 表或撰写过的研究成果，也不含为获得苏州大学或其它教育机构的学位证书而使用 过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。 本人承担本声明的法律责任。 研究生签 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文合作部、中 国社科院文献信息情报中心有权保留本人所送交学位论文的复印件和电子文档，可 以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内 容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权苏州大学学位办办理。 研究生签 导师签 基于微粒群算法的污水管道优化系统研究 第一章绪论 1 之1 课题背景和研究意义 1 1 1 课题背景 第一章绪论 污水管道优化设计通常涉及两个问题，一是管道系统布局优化；二是在管道布局 确定的情况下管道水力参数的优化。在进行管道规划设计时，这两个问题是相互关联 的。因此，必须综合考虑上述两个问题的关联性，才能获得优化效果【1 j 。 传统的污水管道优化设计中，设计人员在掌握了较为完整的设计基础资料后，一 般先按照管道定线和系统布置的原则，确定出一种较为合理的管道系统布局图。然后 计算出各设计管段的设计流量，以水力计算图或水力计算表及有关的设计规定作为控 制条件，从上游到下游依次进行各设计管段的水力计算，求出各管段的管径、坡度以 及在检查井处的管底标高和埋设深度。计算中，一般只是凭经验对管段的管径和坡度 等进行适当的调整，以求达到经济合理的目的，但其合理程度受到设计人员个人能力 的限制；而且大多数计算采用反复查阅图表的方法进行，工作效率低，时间长，不利 于设计方案的优化。采用以上方法不仅计算量大、不够准确，而且会导致造价偏高， 难以满足城市建设和环境保护的需要【2 】。为了探求污水管道系统的最优设计方法，国 内外专家、学者进行了不少的工作，发表了大量的文章，并进行了大量的研究和实践。 自七十年代以来，随着计算机技术的发展，污水管道的优化研究与计算机技术结合的 越来越紧密，取得了大量的成果，开发了很多的计算程序或软件应用于污水管网的计 算机辅助设计和自动化管理上，产生了巨大的经济效益。但这些优化程序并不适用于 每一个场合，在许多设计院仍然使用常规方法进行设计【3 】，因此有必要采用新的方法 研究适用性更强的管道优化设计算法及应用软件。 本课题以苏州市污水管道系统规划项目为应用背景，对污水管道优化设计问题进 行了探索。优化是人们在科学研究、工程技术和经济管理等诸多领域中经常碰到的问 题，其目的是找到使目标函数达到最大或最小的条件。一般流行的优化方法如牛顿法、 共轭梯度法、模式搜索法、单纯形法等。在问题的解域选取一个初始点，通过迭代找 第一章绪论基子微粒群算法的污水管道优化系统研究 到一个极值点。微粒群优化算法( 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 ) 是一种新兴的基f 群体进化的优化方法，具有计算简单、鲁棒性好且所需领域知识少等特点，已成功应 用于多个领域。依托苏州园区联图软件公司，本文提出基于改进微粒群的方法，开发 了污水管道优化系统，实现了与公司原有管道系统的无缝对接。为了实现项目方式管 理成果数据，根据不同管线特点，实现点线数据的快速编辑等，在污水管道优化系统 的基础上，采用m d l 语言在m i c r o s t a t i o n 环境下开发了污水管线管理系统。 1 1 2 研究意义 污水管道系统是市政建设最重要的组成部分之一，也是城市可持续发展的基础设 施。通常情况下，污水系统投资较大，偿还期限长【3 1 ，这就需要提供一种比较先进、 可靠的设计方法( 算法) 或设计平台，对污水管道进行优化设计，寻求满足各种技术条 件，且能使整个系统总费用最低的设计方案，不仅具有重要的理论和应用价值，而且 具有明显的经济和社会效益。 近年来，计算机技术的不断发展使得大规模的数据处理成为可能，应用计算机进 行污水管道设计计算，不仅把设计人员从查阅图表、手工计算的繁重劳动中解脱出来， 加快了设计进度，而且整个污水管道系统得封了优化，提高了设计质量。所确定的最 优方案与传统方法相比，可降低近1 0 的工程造价【4 】，污水管网的合理布局和优化设 计意义深远。 从目前的研究成果来看，较为实用的管道优化设计方法有：遗传算法、动态规划 法、直接优化法等。上述几种方法在解决污水管道优化问题时在不同的方面有各自的 优点，但也有各自的不足【5 】。微粒群算法是一种基于群智能的演化计算技术，由于其 容易理解、易于实现，在许多优化问题中得到成功应用，并且己被证明该算法在优化 问题中收敛速度和结果优于传统的遗传算法1 6 1 。但在解决污水管道设计问题时还存在 一些弱点，如早熟及多样性丢失等问题。因此，需求一种克服微粒群缺陷的有效算法， 对微粒群算法能否更有效地应用于管道优化设计问题求解具有直接的现实意义。本文 针对基本微粒群算法存在早熟及多样性丢失的问题，提出一种改进多种群的微粒群算 法，并将该算法应用于污水管道优化设计中，既具有一定的理论价值，又有广泛的应 用参考价值。 2 基于微粒群算法的污水管道优化系统研究第一章绪论 1 2 国内研究现状及存在的问题 近年来，国内学者从各个不同的层面、采用不同的方法和技术对这个领域的相关 课题进行了研究，发表了大量的文章。李树平以随机生成的管网平面布局图作为初始 群体，并由已定管线下的优化算法求解其工程造价，从而求得系统布局的优化方案1 1 7 1 。 郭维刚引入了模糊动态规戈i j 方法，依据隶属度函数引导管径、埋深控制策略，以污水 管线的管段设计为模糊动态规划的优化阶段。通过每个阶段关于管径和埋深的优化决 策，形成污水管道系统总体的优化策略【8 】。陆少鸣通过数学分析，对每一管段的管径 采用满足约束条件的最大和最小管径及其之间的标准管径，提出可行管径法1 9 】。可行 管径法使得管径优化计算精度得以提高，并显著减少了计算工作量和计算机存储量。 对于地面坡度较缓甚至逆坡铺管的情况，张绍园认为需要采用最小充满度和不於 流速作为控制条件才能得到最优结果【1 0 】。郭迎庆在应用直接优化法时，对管内底标高 做了约束，通过增加人机对话功能，加强设计人员对管网计算的宏观控制与局部干预， 使污水管道的设计得以进一步优化【l 。张联民通过调整尾速、权衡埋深和管径对造价 的综合效应，提出流速控制法【1 2 1 。周琦认为影响埋深的主要因素是管道的管径和管道 坡度，并从坡度出发对两相优化法做了改进【1 3 】。何亚男【1 4 1 、黄怀友【1 5 】引入管段平均 坡度的概念，并以平均坡度的某一变化范围作为控制条件求出所有管段敷设方式的组 合，同时还根据工程情况拟定出不同的控制埋深，计算出相应的管网管径、坡度、埋 深及总造价的优化组合，选出最优者为最满意设计方案。 张云采用规格管径作为状态变量，利用遗传算法同时搜索可行解空间内的许多 点，从而得到优化方案，但在计算中没有考虑充满度的约束【1 6 1 。李树平根据设计流量 和设计充满度确定污水管道可行管径集，并将各管段的可行管径直接映射为适合于遗 传算法操作的编码形式，提高算法的高效性【l7 1 。周荣敏以管径和设计充满度为决策变 量，采用二维混合编码方案进行方案表达，直接应用污水管网水力计算基本公式进行 管网计算，能有效地提高遗传算法的进化过程【1 8 】。陈胜兵以管径和坡度为状态变量， 充分利用约束条件建立可行空间，求得满足工程实际的较优解，但其适用性受管网规 模的限制【1 9 1 。伊学农结合节点递归算法将遗传算法用于中型城市的污水管道系统的优 化，获得较为满意的结果【2 0 1 。王磊以规格管径作为离散型变量组合，利用蚁群算法进 行寻优，可以大大减少计算机的运算时间，提高工作效率【2 1 1 。智能算法一般在解决中 第一章绪论 基于微粒群算法的污水管道优化系统研究 小型管道系统优化设计计算问题时，可以求得最优设计方案，当解决大型管道系统问 题时，由于缺少判别条件，只能说是求得趋近于最优解的设计方案【2 2 - 2 3 。 1 3 国外研究现状及存在的问题 污水管道优化在国外发展较早，提出了许多成熟的方法。最早着手管网最小费用 布局和设计问题研究的是j c l i e b m a n ，他假定每一管段管径相同，以挖方费用为优 选依据，选择初始布局方案，用试算法逐步进行调整，在研究中撇开了水力因素，且 优化效率也不高【2 4 1 。1 9 9 5 年，g a w a l t e r s 2 5 】牙c p a l m e r 2 叼利用遗传算法对树状管网 进行系统布局，得到一组优化布局方案。m a y s 弓 入排水道的概念，从动态规划非序 列化到序列化，不仅节省时间，程序的编制也比较简单1 2 7 1 。m a y s 和y e n 在此基础上 引入了缩小范围的迭代过程，将动态规划法发展为逆差动态规划法【2 8 】。逆差动态规划 法在污水管道优化设计过程中可以显著减少计算时间和存储量【2 9 】，但计算出来的方案 有可能偏离理论最优解。j o s e 采用规格管径作为状态变量，利用遗传算法同时搜索可 行解空间内的许多点，得到优化方案【3 0 】，但在计算中没有考虑充满度的约束。 e 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 又分别用 各管段地面坡度的倒数、各管段的管长、各管段按最小坡度设计的挖方量等3 种权值 求管网系统布局方案，以便改善优化结果。但对于污水管网所有可行的管网布局图， 各管段的实际权值只有在布局方案确定以后才能计算出来，应属于图论中的变权问 题，目前还没有有效解决的办法。a r g a m a n 和m a y s 在管道布局方案中引入排水道的 概念，将排水区域内与最终出水口相距同样可行管段数的节点用一根排水线连接起 来。所有可行管道敷设路径组成的图可分割成多个阶段，用多阶段的决策过程表示管 道系统布局方案的优选课题，并用动态规划法求解【3 l 】。此模型己经考虑到水力因素， 但排水道的引入使寻优过程的搜索范围受到限制，容易漏掉最优的设计方案。在污水 管道系统优化设计技术的发展和应用过程中，上述优化方法同时存在【3 】，并且都在不 断地改进和完善，其共同点都是以设计规范及管径、流速、坡度、充满度间的水力关 系为约束条件，以达到费用最小的目标。 无论国内还是国外，在污水管道系统设计的理论计算和工程应用上均已取得很大 4 基于微粒群算法的污水管道优化系统研究第一章绪论 的成果，也仍然存在着许多期待解决的问题。随着计算技术和系统方法的发展，更好 地研究开发污水管道系统优化设计是必然的发展趋势。 1 4 本文的主要工作 本文针对目前污水管道优化设计领域所存在的问题，进行了系统的研究，主要目 标是寻求一种高质量的优化算法，实现污水管道系统的优化设计。本文的主要研究成 果归纳如下： ( 1 ) 将离散微粒群算法应用到污水管网布局优化中。首先建立了污水管网布局优 化数学模型，即给定初始点和终点，计算管道的总长度最短。在建立该模型时，借助 了网络中的有向图来简化该模型，将离散微粒群算法应用到该模型中。实验结果与遗 传算法相比，离散微粒群算法具有更好的性能。 ( 2 ) 针对微粒群算法收敛速度慢及多样性丢失等问题，在基于带有微分扰动因子 的微粒群优化算法基础上，提出了一种改进多种群的微粒群算法。该算法通过引入多 种群并行进化机制，使多个种群同时在相同的解空间上搜索。使用m a t l a b 对该算 法进行了实验，并在五个标准测试函数上与标准微粒群算法、带有微分扰动的微粒群 算法、带有小生境特性的微粒群算法进行了比较。实验结果表明，该算法在优化高维 度多峰函数时，在收敛速度方面明显优于其它算法。 ( 3 ) 将改进多种群的微粒群算法应用到污水管道水力参数优化设计中。以苏州市 管道规划系统项目为应用背景，污水管道系统的设计理论与设计规范为依据，建立了 污水管道优化设计模型。并应用改进多种群的微粒群算法寻求管网投资最小的设计方 案。该方法以管径和设计充满度为决策变量，采用二进制编码方案进行表达，可直接 应用污水水力计算基本公式进行污水管道计算，能有效地提高微粒群算法的进化过 程。实验结果表明，将改进多种群的微粒群算法应用于污水管道水力参数优化中是可 行的和高效的，与标准微粒群算法、遗传算法和蚁群算法相比具有较好的优化结果。 ( 4 ) 开发了污水管道优化及管理软件。将改进微粒群算法应用到污水管网布局优 化和管道水力参数优化中，在v i s u a lc + + 环境下开发了污水管道优化系统。污水管道 设计优化阶段完成之后，为了实现项目方式管理成果数据，根据不同管线特点，实现 点线数据的快速编辑，实现管线成果生成过程的智能化，内容的标准化，导出成果交 第一章绪论基于微粒群算法的污水管道优化系统研究 换文件，实现与现状管道系统的无缝对接等，依托苏州园区联图软件公司，采用m d l 语言在m i c r o s t a t i o n 环境下开发了污水管线管理系统。 1 5 本文组织 本文共七章，具体内容按如下方式组织： 第一章绪论。主要介绍污水管道优化概述及国内外发展现状。 第二章对微粒群优化算法的基础理论知识进行回顾。概括讲述了微粒群算法优 化的主要领域：全局优化、约束优化和组合优化。介绍了微粒群算法的工作原理，为 下面的污水管道优化奠定理论基础。本章还介绍了微粒群算法与遗传算法的比较和微 粒群算法在科学工程中的应用。 第三章将离散微粒群算法应用到污水管网布局优化中。首先建立污水管网布局 优化网络模型。由于基本微粒群算法对解决连续型问题能达到较好效果，但是污水管 网布局优化为离散型的组合优化问题，为了将其能够应用到管网布局优化中，采用离 散微粒群算法解决管网的布局优化问题。与遗传算法相比，该算法具有更好的性能。 第四章在基于带有微分扰动因子的微粒群优化算法基础上，针对微粒群算法收 敛速度慢及多样性丢失等问题，提出了一种改进多种群的微粒群算法。并从收敛精度、 参数设置等方面对该算法进行了实验分析。结果表明，该算法在优化高维度多峰函数 时，在收敛速度方面明显优于其它算法。 第五章将改进算法应用到污水管道水力参数优化中。首先介绍了污水管道水力 参数优化设计中所涉及的变量，给出了目标函数和约束条件，在此基础上建立了污水 管道水力参数优化的数学模型，将改进多种群的微粒群算法应用到该模型中并进行了 实验分析。 第六章开发了污水管道优化及管理系统。针对目前污水管道优化系统存在的问 题，提出了污水管道优化的目标、系统结构、系统设计和开发流程，在v i s u a lc + + 平 台上给出了污水管道优化系统的演示效果。采用m d l 语言，在m i c r o s t a t i o n 平台上 给出了管线管理系统的演示效果。目前该系统已经应用于污水管道优化中，使整个管 道系统的费用较以前有明显降低，在工程优化设计中有一定的实用价值。 第七章对全文进行了总结，并提出下一步工作可能的研究方向。 6 基于微粒群算法的污水管道优化系统研究第二章微粒群算法 2 1 优化问题 第二章微粒群算法 优化问题是指在满足一定约束条件下，寻找一组参数值，使得系统的某些性能指 标达到最大或者最小。它广泛存在于农业、国防、工程、交通、金融、能源、通信、 材料等诸多领域。最优化技术在上述领域的应用已经产生了巨大的经济效益和社会效 益。国内外的实践证明，在同样条件下，经过优化技术的处理，对系统效率的提高， 能耗的降低，资源的合理利用及经济效益的提高均有显著的效果，而且随着处理对象 规模的增大，这种效果也更加显著。但随着处理对象规模的增大，优化问题也越来越 复杂，而经典的优化技术对问题的约束比较大，如梯度下降法要求优化函数是可导等。 因此，对于新型优化算法的研究具有重要的意义。近年来，由于微粒群算法作为新型 化优化方法具有良好的潜质，该算法受到普遍的关注。微粒群算法具有操作简单、鲁 棒性好和全局等特点，它已经在非常广泛的领域中取得了成功应用。本节给出微粒群 算法优化的主要领域【3 2 j ：全局优化、约束优化和组合优化。 2 1 1 全局优化 全局优化( g l o b a lo p t i m i z a t i o n s ) 采用在感兴趣的区域内可以区分全局最优解和众 多局部最优解的方法，全局优化问题通常具有无约束化的形式，即问题除了一个最小 化或最大化函数之外没有其它限制【3 3 1 。一般来说，无约束优化问题可以在数学上描述 为【3 4 】： r a i nf ( 功 ( 2 1 ) s f x 臼 ( 2 2 ) 其中厂是实值函数，可行集合臼是r 玎( 解空间) 的子集。可行集纺哝刀代表了完全 无约束的情况。在许多应用问题中，仅仅需要考虑q 是f 特定的子集的情况。如果 存在e o ，对于所有满足臼且与x + 的距离小于的x ，都有m ) 狐+ ) ，则点x 称作厂 在q 上的局部最优解。如果对于所有x e t 2 都有瓜) 狮+ ) ，则点x + 称作厂在t 2 上的全 7 第二章微粒群算法 基于微粒群算法的污水管道优化系统研究 局最优解。尽管大多数实际优化问题需要满足边界约束条件，但这对于无约束优化问 题方法的研究为进一步研究打下了基础【3 2 1 。 2 1 2 约束优化 约束优化( 或非线性规划) 处理【3 2 1 是有等式和( 或) 不等式约束的优化目标函数的问 题。由于许多实际问题无法建模为线性规划问题，因此非线性规划成为在几乎所有工 程、运筹学和数学领域中非常重要的工具。非线性规划的般形式如下： m a x f ( x ) ( 2 3 ) 量tg f ( 劝s 0 ，- - 1 ，2 , 3 ，m t ( 2 4 ) 厅f 2 0 ，卢m l + l ，m ，r 所l + m 2 )( 2 5 ) x e x ( 2 6 ) 其e p f , g l ，9 2 ，g m ，办耐i ，办枷，+ 珂是在上定义的实值函数，z 是 科的子集，x 是n 维实向量，其元素为x l ，娩，砀。上述问题的解必须为既能满 足约束同时又最小化函数厂的变量x i ，x 2 ，砀。函数厂通常称作目标函数( o b j e c t i v e f u n c t i o n ) 或判据函数( c r i t e r i o nf u n c t i o n ) 。约束舒郢称作不等式约束( i n e q u a l i t y c o n s t r a i n t ) ，约束h t ( x ) = o 称作等式约束( e q u a l i t yc o n s t r a i n t ) 。集合彳通常可能包括变量 的下界和上界，称作域约束( d o m a i nc o n s t r a i n t ) 。满足所有约束的向量x e x 称作问题 的可行解( f e a s i b l es o l u t i o n ) 。这种解的集合构成可行区域( f e a s i b l er e g i o n ) 。非线性规划 问题就是要找到一个可行点x ，并对每一个可行点x ，都有翮驰+ ) ，这种点称作最 优解( o p t i m a ls o l u t i o n ) 。与线性规划不同，非线性规划的传统解法非常复杂，而且效 率不高。 2 1 3 组合优化 组合优化( c o m b i n a t o r i a lo p t i m i z a t i o n ) l 拘特点是可行解的数量有限。虽然从理论上 讲这种有限问题可以通过简单枚举找到最优解，然而在实际情况下通常无法实现。特 别当实际问题的规模比较大，可行解的数量非常多时更是如此。解决这种困难问题的 主要方法是启发式搜索。在过去的几年中，遗传算法和微粒群算法受到组合优化界人 士越来越多的关注，并且在研究和许多工业工程领域的实际应用中表现出很强的生命 基于微粒群算法的污水管道优化系统研究第二章微粒群算法 力。 组合优化包含具有不同特征和属性的一大类问题。虽然这些问题彼此不同，然而 问题的本质可以归纳为下列类型之一： 一确定与问题相关的某些项的排列 一确定某些项的组合 - 确定某些项的排列和组合 一任何带有约束的上述类型 集覆盖问题【3 2 ( s e t c o v e r i n gp r o b l e m ) 是组合优化中的典型问题。问题可以描述为： 对于一个掰行n 列的0 1 矩阵，用最小的费用选择一些矩阵的列使其能够覆盖所有的 行。设向量x 的元素矿1 表示列j f 被选中( 费用是矿o ) ，矿0 则表示其未被选中 ( _ 1 ，, - - - , n ) 。集覆盖问题可以表示为： m i n z ( x ) - - z c j x j j = 1 - 鼠_ l ，- - 1 ，2 ，珑 j = l 0 ，1 ) ，户1 ，2 ，刀 ( 2 7 ) ( 2 8 ) ( 2 9 ) 式( 2 8 ) 保证每行至少被一列覆盖，式( 2 9 ) 是完整性约束。如果所有费用系数。 一 都相同，则问题称作单一费用集覆盖问题( u n i c o s ts e t c o v e r i n gp r o b l e m ) 。如果式( 2 8 ) 为等式约束，上述问题则称为集划分问题( s e tp a r t i t i o n i n gp r o b l e m ) 。 优化问题几乎在各个领域中都存在，特别是在工程界成为关注的焦点。工程界提 出的很多问题非常复杂，同时难以用传统优化方法求解。微粒群算法作为复杂问题优 化问题的潜质已经受到了普遍的关注，已经成功应用于工业工程领域。 2 2 微粒群算法基本原理 微粒群算法是基于对鸟群、鱼群的模拟，具有“人工生命”的背景。其最初的设 想是模拟鸟群觅食的过程，但后来发现微粒群也是一种很好的优化工具，于是得到了 快速的发展。通常单个自然生物并不是智能的，但是整个生物群体却表现出处理复杂 问题的能力。群体智能就是这些团体行为在人工智能问题中的应用。微粒群优化最初 是处理连续优化问题的，目前其应用已扩展到组合优化问题。由于其具有简单、有效 的特点，所以得到了众多研究人员的关注和研究。 9 第二章微粒群算法基于微粒群算法的污水管道优化系统研究 微粒群优化算法是由k e n n e d y 和e b e r h a r t 于1 9 9 5 年提出的一种基于群体寻优的启 发式搜索算法【3 5 1 。与基于达尔文“适者生存，优胜劣汰”进化思想的遗传算法不同， 微粒群算法的核心思想是群体中个体之间信息的社会共享和协同进化。微粒群中每一 个体代表待求解问题的一个潜在解，并具有位置和速度两个状态量。在算法开始时， 先随机初始化一群微粒，然后通过群体的协作和迭代运算找到最优解。在每一次迭代 过程中，各微粒根据简单的位置和速度更新规则改变自身的状态量，通过跟踪微粒自 身的历史最优值和邻域内所有个体找到的最优值不断“完善”自己。 下面给出微粒群优化算法的数学描述【3 6 ，。 假设搜索空间为d 维，微粒群中第衍微粒的两个状态量位置和速度分别用 x t = ( x i l 歹忍，曲和v f - m l ，睨，- , v 动表示，该微粒迄今为止搜索到的最好位置( 即历史最 优值) 记为p 尸p f l 护1 2 ，妒动，其所在邻域内的所有微粒迄今为止搜索到的最好位置记为 p g = ( p g l , p 9 2 ，。谚劫。那么该微粒的速度和位置更新等式( 第雠) 分别为： = + q r a n d ( ) ( 砌。x j , i ) + c 2 r a n d ( ) ( 翰勃) 砀= 砀+ f 屹= 矿呦 1 = 一矿 一 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) 其中，加速常数c l 和q 是两个非负值，r a n d ( ) 和r a n d ( ) 是在范围 o ，1 内取值的随 机数。“是常数，限制了速度的最大值，由用户设定。当甜较大时，微粒的飞行 速度大，有利于全局搜索，但有可能飞过最优解；甜较小时，微粒可在特定区域内 精细搜索，但容易陷入局部最优。因此可以说碥艇决定了搜索的精度。 公式( 2 1 0 ) 中的第1 部分称为动量部分，表示微粒对当前自身运动状态的信任，为 微粒提供了一个必要动量，使其依据自身速度进行惯性运动。第2 部分称为认知部分， 代表了微粒自身的思考行为，鼓励微粒飞向自身曾经发现的最佳位置。第3 部分称为 社会部分，表示微粒间的信息共享与相互合作，它引导微粒飞向微粒群中的最佳位置 【3 7 】。这3 个部分之间的相互平衡和制约决定了算法的主要性能。 基本微粒群算法的流程如下： s t e p l ：依照初始化过程，对微粒群的随机位置和速度进行初始设定。 s t e p 2 ：计算每个微粒的适应值。 s t e p 3 ：对于每个微粒，将其适应值与所经过的最好位置p ，的适应值进行比较， i o 基于微粒群算法的污水管道优化系统研究第二章微粒群算法 若较好，则将其作为当前的最好位置。 s t e p 4 ：对每个微粒，将其适应值与全局所经历的最好位置只的适应值进行比较， 若较好，则将其作为当前的全局最好位置。 s t e p 5 ：根据方程( 2 1 0 ) 、方程( 2 1 1 ) 对微粒的速度和位置进行进化。 s t e p 6 ：如未达到结束条件通常为足够好的适应值或达到一个预设最大代数 ( g 掰d ，则返回步骤s t e p 2 ，否则退出。 基本微粒群算法的流程图如图2 1 所示： ( 开始 ) 微粒群体初始化 0 评价每个微粒的适应废 j 更新每个微粒的速度i v i a = t dv i d + e , r a n d , o ( p - d x i a ) + c 2 r a n d 2 0 ( p s d - x i d ) 广 0 更新每个微粒的位置 x i d 2 x i d + v i d 评价每个微较的适应度 。 零 r 将徽较当前微粒设置为p b “ 参 1 孕 t将微粒当前微粒设置为曲 乞之孓 是 c 垫 图2 1 基本微粒群算法流程图 2 3 微粒群算法参数分析 在微粒群算法中，下面几个参数对算法的寻优性能的影响非常显著：惯性权重、 最大速度甜和加速常数c 1 ，c 2 ，群体规模朋和粒子的维度d 等【3 8 】。 ( 1 ) 惯性权重c o ：权重函数对于微粒群算法的收敛性起到很大的作用。0 2 值越大， 全局寻优能力越强，局部寻优能力越弱；反之，则局部寻优能力增强，而全局寻优能 第二章微粒群算法 基于微粒群算法的污水管道优化系统研究 力减弱，通过调整c o 的大小来控制以前速度对当前速度的影响，使其成为兼顾全局搜 索与局部搜索的一个折中。惯性权重0 9 大时，速度v 就大，有利于微粒群搜索更大的 空问，并可能发现新的解域；而惯性权重c o j , 、，速度v 就小，有利于在当前的解空间 附近挖掘更好的解。通常将迭代开始时的惯性权重0 9 设置较大，并在迭代过程中逐渐 减小。这样可使微粒群算法更好地控制探索( e x p l o r a t i o n ) 与开发( e x p l o i t a t i o n ) 之间的关 系，在开始优化时搜索较大的解空间，得到合适的种子，然后在后期逐渐搜索到较好 的区域进行更精细的搜索，以加快收敛速度。 ( 2 ) 参数v m a x ：微粒群算法是通过每一次迭代时每一个微粒在每一维上移动的距 离来进行的。速度的改变是随机的，而一个不希望的结果是，不受控制的微粒搜索轨 道被扩展到问题空间越来越广阔的范围，并最终达到无穷。如果微粒要有效的进行搜 索，必