武汉大学浅析遗传算法在管网中的应用.docx

浅析管网优化设计中的遗传算法 宋银强 韦布波摘 要：本文主要介绍了管网优化设计中的遗传算法，通过分析遗传算法在给水管网设计中的运用，体现了这种算法运用时的经济合理性。关键词：遗传算法；优化设计；管网； 1 引言：随着社会经济快速发展和城镇化进程的加快，城市规模不断扩大，建设经济适用安全可靠的给排水系统，对保障城市正常生产生活越发显得重要。在城市的给排水系统中，管网建设往往占到水工程总投资的6080%，因此，在城市给排水工程规划设计工作中，管网优化设计具有重要的现实意义。 仅仅只靠过去的经典优化理论早已不能满足当今社会的需要，越来越多的新型算法已经涌现出来。遗传算法就是这些算法中最富有成效的一种算法。2 正文：2.1 什么是遗传算法遗传算法是建立在自然选择和群众遗传学机理基础上的随机，迭代，进化，具有广泛适应性的搜索方法。他最先由 John Holland 于1975年提出。从此以后，它逐渐发展成为一种通过模拟自然进化过程解决最优化问题的计算模型。具体来说，它是一种模拟生物学中基因遗传和自然选择而提出的并行随机优化算法。在遗传算法中,先建立工程优化问题的数学模型,将问题的所有决策变量编码,称为一个基因。多个基因形成一个有限长的编码串,称为染色体。其对应的表现型即个体,都对应于优化问题的一个可行解,一组个体组成一代种群。优化问题的目标函数作为种群所处的环境,可以得出每个个体对环境的适应度,由适应度决定该个体生存的概率。搜索时先随机产生一定数量的原始种群,从这些种群开始,模拟进化过程。按每个个体的适应度依概率进行优胜劣汰,从而使适应度高的个体生存下来。再利用交换、变异等遗传手段，使这些种群的优良特性得以遗传并保留到下一代。如此选择-交换-变异-再选择，循环往复,使各代的优良基因成分逐渐积累,种群的平均适应度和最优个体适应度不断上升,直到迭代过程趋于收敛,从而求得一组最优种群。2.2 遗传算法在管网优化设计中的特点 (1)遗传算法从问题解的串集开始搜索，而不是从单个解开始。这是遗传算法与传统优化算法的极大区别。传统优化算法是从单个初始值迭代求最优解的；容易误入局部最优解。遗传算法从串集开始搜索，覆盖面大，利于全局择优。(2)遗传算法同时处理群体中的多个个体，即对搜索空间中的多个解进行评估，减少了陷入局部最优解的风险，同时算法本身易于实现并行化。(3)遗传算法基本上不用搜索空间的知识或其它辅助信息，而仅用适应度函数值来评估个体，在此基础上进行遗传操作。适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。这一特点使得遗传算法的应用范围大大扩展。(4)遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导他的搜索方向。(5)具有自组织、自适应和自学习性。遗传算法利用进化过程获得的信息自行组织搜索时，适应度大的个体具有较高的生存概率，并获得更适应环境的基因结构。2.3 遗传算法的一般应用步骤 1)初始化种群;2)计算种群上每个个体的适应度;3)按由个体适应度值所决定的某个规则选择将进入下一代的个体;4)按概率Pc进行交叉操作;5)按概率 Pm进行变异操作;6)若没有满足某种停止条件，则转入2)，否则进入下一步;7)输出种群中适应度最优的染色体作为问题的满意解或最优解;2.4 遗传算法在应用中可能出现的问题 遗传算法是一种通用而有效的求解最优化问题的方法，然而，单用简单的遗传算法在许多情况下不是十分有效，容易产生早熟现象以及局部寻优能力较差等问题。另外，遗传算法在解决一些实际问题时，由于它一般具有较大的群体规模，需要对较多的个体进行大量的遗传和进化操作，特别是要对大量的个体进行适应度计算或评价，从而使得算法的进化运算过程进展缓慢，难以达到计算速度的要求，因而遗传算法的并行计算问题日益受到重视。人们认识到对遗传算法进行并行处理的可能性，于是提出了多种基于各种并行计算机或局域网的并行遗传算法。2.5 遗传算法的优化现在广泛应用的并行遗传算法主要是在遗传算法的基础上考虑了四个方面的并行性并对其加以改进和优化之后形成的。这四个方面的并行性是指: 1)个体适应度评价的并行性;2)整个群体中各个个体的适应度评价的并行性;3)群体产生过程的并行性;4)基于群体分组的并行性;2.6 遗传算法在给水管网优化设计中的应用 给水管网优化的目标是经济性、可靠性和供水水质安全性的全面优化。但是由于水质安全性不易量化,管网运行正常时和故障时用水量会发生变化,以及管网拓扑结构的复杂性,使得至今还没有成熟的理论来分析管网的安全性,因而也无法将可靠性因素很好地量化以纳入适应度函数中。现在常用的方法是以经济性为目标函数,而将其他因素作为约束条件,据此建立适应度函数,来评价个体的适应度,这样处理的结果使得最终方案在供水安全性上不够完善。事实上,现有很多研究成果表明,对环状管网来说,流量优化分配是个凹规划问题,即它的最优解往往出现在约束区域的边界上。如果没有与供水水质和供水安全性相关的下限约束条件,则优化的结果会使某些管段的流量为零,成为树状网。应当依据工程实际情况对遗传算法获取的优化结果加以修正。例如在实际管网的运行维护中,管线故障概率是与敷设所在地的道路等级及当地用水情况等密切相关的,如能结合GIS的地物属性关系,合理确定相应干管的事故转输流量,让道路等级高的干管承载较高的供水输送任务,对道路等级较低或将来可能改造地区采用安全性较高的设计方案,在经济和安全上寻求一个最佳的平衡点,才能真正达到优化设计的目的。3 结束语：遗传算法具有全局性、并行性、对问题依赖性小等优点，适用于求解离散管径的组合优化问题。其独特的设计思路和卓越的求解性能，使其在给水管网优化设计中具有较强的实用性。不仅如此，对于多目标优化问题，遗传算法能克服传统算法依赖权重向量的局限性，利用自身强大的全局搜索能力，找出所有可能的优化解，供决策者参考。综上所述，遗传算法用于管网优化设计是可行的，但同时也还存在一些问题亟待研究，如如何加快收敛的速度和效果，如何利用管网水力计算本身的特点来确定约束条件和对成果的修正等。4 参考文献：1 严煦世,赵洪宾.给水管网理论和计算M.北京:中国建筑工业出版社,1986:172-178.2 曹彬,马凤先,城市输配水系统优化设计,给水排水,1989,(1):1-11.3 范鸣玉,张莹,最优化技术基础,清华大学出版社,1982:1-4.4 严煦世,范瑾初,给水工程,中国建筑工业出版社(第四版),23-92.5 王文远.用基因算法求管网经济管径J.给水排水,1997,23(12):22-25.6 Goldberg D E,Kuo CH.Genetic algorithms in pipeline optimizationJ.Computing in Civil Engineering,1987,(2):128-141.7 Davidson J,W,Goulter I C.Evolution Program for Design of Rectilinear Branched NetworksJ.Comp in Civ Engrg,1995,9(2):112-121.8 Walters G A,Lohbeck T.Optimal layout of tree networks using genetic algorithmsJ.Engineering,1993,(22):27-48.9 Reed, P., B. Minsker, D. E, Goldberg. Designing a competent simple genetic algorithm for search and optimization. Water Resources Research, 2000,36