遗传算法在树状管网中的应用.docx

《遗传算法在树状管网中的应用.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法在树状管网中的应用输配水管网是城市供水系统和管道化灌溉系统的重要组成部分，它通过各级输配水管道把水安全可靠地输送到各个用水点，并满足水量、水压和水质要求。如何科学、经济、实用地对管网进行规划、设计和运行管理，直接影响工程总投资、运行管理费及系统可靠性。一遗传法算应用原理树状管网具有图论中生成树的性质，有ND个节点的树状管网，对应于一个过ND个节点有ND-1条边的生成树。对于树状管网优化布置问题，实质上就是以管网初步连接图为基础，以管段长度或管道造价为权值，寻找管网总长度最短或投资最小的最小生成树。一个有ND定点和NP条待选边的

2、管网初步连接图有许多个不同的生成树。不同形式的生成树代表不同的树状管网布置方案。由于管网内流量分配模式的不同，管网投资和水力性能差异较大。有时权值次小的生成树，可能是实际问题的一个较好布置方案，如果任选其中的一个，可能会丢弃或忽略更优的布置方案。因此，在树状管网优化布置中，希望能够同时获得若干个权值最小或次小的生成树。由图论原理可知，过个顶点的树的数目为。若用枚举法从个树中寻找最适合实际问题的最优管网布置形式，计算量非常大，求解效率低。若用图论中的Kruskal算法和Dijkstral算法求解，只能分别获得一个管网总长度和路径最短的布

3、置方案，但其管网投资未必最小。因此，有必要寻找更好的算法来确定最小树和次最小树。考虑如下一个进行树状管网优化布置的搜索过程：对于一个有ND个顶点，NP条待选边的管网初步连接图，从NP条边中随机选取ND-1条边，可构成一个管网连接子图。利用深度优先搜索算法(DFS)对该子图进行一次搜索，如果能搜索到ND个顶点，则所选择的ND-1条边所构成的连接子图是一个连通图。过ND个顶点且有ND-1条边的连通图一定是一棵生成树，即所选择的ND-1条边构成一个树状管网。对于一个给定的树状管网，可根据已知条件，计算出该树状管网的管网总长度或管网投资的大小

4、，以此评价该树状管网布置形式的优劣。如果能采用一定的优化技术，搜索并评价尽可能多的树状管网布置形式，就可以寻找出一组管网总长度最短或管网投资最小的布置方案，从而实现树状管网的优化布置。遗传算法，是一种新兴的全局优化算法。其仅以目标函数值为搜索依据，通过群体优化搜索和随机执行基本遗传运算，实现遗传群体的不断进化，适合解决离散组合优化问题和复杂非线性问题。树状管网布置优化属于典型的组合优化问题，可以应用遗传算法进行树状管网优化布置。已有的研究成果表明，应用单亲遗传算法求解最小生成树问题非常有效，能够在较短时间内，以较高概率获得一批最优或次

5、最优的生成树。根据树状管网的图论特性，可以把由管网初步连接图求最优树状管网的问题抽象为一个求网络图的最小树问题，然后应用单亲遗传算法进行求解，可实现树状管网的遗传优化布置。应用单亲遗传算法进行树状管网优化布置，可按如下步骤进行：(1)根据工程规划区地形条件、水源位置、给水栓布置以及工程设计要求等，制定管网初步连接方案，并概化成网络图，确定网络节点数目ND、待选边数目NP、节点需水量以及节点和边之间选边数目的连接关系等基本数据。(2)采用边编码方式表示可能的树状管网形式，并确定单亲遗传算法的主要控制参数，如群体规模(Popsize)、最

6、大遗传代数(Maxgen)、选择率(Ps)和换位率(Pt).(3)随机产生一组初始群体，作为第一代遗传群体。对遗传群体中的各个个体进行连通性判断，根据优化布置目标（管网总长度最短或管网总投资最小）采取不同的适应度函数形式，计算个体适应度。(4)根据选择率Ps确定每一代的遗传选择机制，按优先选择或平等选择机制，选择进行遗传运算的母体；根据换位率Pt对母体执行换位算子或逆转算子，产生一个具有相同群体规模的子代群体。计算子代群体中各个个体的适应度。(5)所有的亲代个体和子代个体共同参与生存竞争，按适应度的高低进行排序，选择适应度最大且基因链

7、不同的群体规模(Popszie)个最优个体作为新一代遗传群体。(6)）对遗传群体循环执行步骤(4)、(5)，直到满足进化准则条件，即达到最大进化代数(Maxgen)，终止算法。(7)选择最终遗传群体中的全部或部分个体作为树状管网优化布置结果。考虑实际问题中的其他限制因素，对优化布置方案进行评估、选择和修正，确定进行树状管网优化设计的最优布置方案。二应用实例分析设有一个小型供水管网，共有10个需水节点（含设有一小型供水管网，共有水源点）。按照近邻规划原则，确定出管网初步连接方案如下图所示。图中共23有条可能的管道连接路线，各条连线上的数

8、据分别表示管段编号和管段长度（单位以100m计），其中括号的数据为管段长度。假定管网上各个节点所必需的连续供水量为10m3/h，管网允许最低流速为0.5m/s。单位长度的管低流速为道价格数据见表管网图管道价格：管径（mm