原创《谱聚类在给水管网分区优化中应用》：本论文为免费优秀的关于聚类论文范文资料，可用于相关论文写作参考。
摘 要：利用图划分技术和图论算法实现给水管网分区.根据给水管网分析,确定分区数量,建立权重邻接矩阵并计算图拉普拉斯矩阵及其特征向量,通过多路图划分对隐藏在特征向量中的聚类信息进行数据挖掘,采用遗传算法和K均值方法实现最佳节点聚类.利用PageRank和最短路径算法确定水表和阀门位置,最终实现给水管网优化分区.实际给水管网模型分区实例表明所提方法在给水管网分区的有效性.
关键词：给水管网；分区；聚类；优化
中图分类号：TU991
文献标志码：A
文章编号：1674-4764（2016）06-0142-06
给水管网分区是在系统性能影响最小的情况下通过安装阀门、水表形成独立供水区域,便于优化调度、漏损控制等各方面的管理,以适应信息化、智能化、精细化的要求.管网分区目的是获得规模均等,压力、水质均衡的分区.由于管网的高度复杂性以及众多技术要求和制约因素,使得分区这一问题面临较大挑战.
目前,管网分区优化方法主要有图论算法和复杂网络聚类算法.图论分区算法主要使用搜索算法获得管网拓扑结构.其中,广度优先搜索算法在DMA规模约束下,搜索和某一节点路径最短的节点集,当满足设定规模时,搜索终止,则可得到满足要求的分区.这类方法可获得各种分区方案供决策者选定,或者通过模型分析获得水力最优方案.相比于广度优先搜索算法的局部搜索,深度优先搜索算法可从整体上获得给水管网树状结构,并通过优化算法获得减压阀最佳位置,进而实现分区,或者确定各水源供水范围.另外,也可以最短路径算法为基础,通过压力均衡性确定分,或者通过管道介数中心性选定阀门、水表位置,以实现分区.
在复杂网络聚类中,同一聚类内节点连接紧密,而不同聚类间节点连接相对稀疏,这和管网分区的内在要求一致.相应聚类算法包括计算机科学中的图划分和社会学中的社团发现.图划分将复杂网络聚类转换为优化问题,如Nardo等人使用多层次递归二分法自动获得规模均等的分区布局.社团发现则将分区问题转换为模块度等启发式规则的设计问题,其中刁克功等在管网分区中首次引入社区发现贪心算法进行给水管网分区.Giustolisi等引入管道权重提出了给水管网设施模块度,可以发现更小规模的结构.另外,也有其他相似度的度量方式用于给水管网分区,如按照节点位置信息采用K-均值聚类,以此为基础形成供水管网规划方案,或者按照节点水压波动相似性分区,确定最优压力监测点.
笔者提出一种基于复杂网络谱聚类和图论算法的给水管网分区方法.目的是在尽量降低分区不利影响的前提下,根据给水管网拓扑结构,利用数据挖掘发现隐含在其中的结构聚类信息,确定节点聚类,继而实现满足要求的分区.
1.给水管网分区方法
所提出的分区流程主要包含3个部分：
1）数据输入：管网分析和模拟,确定分区数量,建立权重矩阵.
2）实现分区：图拉普拉斯矩阵求解,根据第二特征向量,采用多路图划分确定各分区内节点聚类,即确定分区范围.
3）确定阀门、水表位置：PageRank算法确定每个分区中心节点,水源到该节点的最短路径中确定水表位置,其他分区间连接管道则为阀门位置.
1.1给水管网分区数量的确定
给水管网分区数量需要根据分区目的、系统规模、分區大小、成本等综合确定.本方法旨在通过发现给水管网内在聚类结构,实现分区设计,因此,在获得指定数量的分区时,每个分区的规模不是严格相同.
1.2规范化拉普拉斯矩阵
谱平分法利用第二小特征值对应的特征向量实现两个分区的优化划分.如果需要得到多个分区,则需要对子分区重复该方法.为了提高分区效率,采用NJW多路谱算法,即根据多个第二最小特征向量,通过聚类算法直接获得指定数量的分区.矩阵E的最大特征值为1,其他特征值均小于1.对于社团结构比较明显的管网,有些特征值接近于1,其对应的第二特征向量中,同一社团内部节点的值接近.对于社团结构不明显的一般给水管网,少量第二特征向量也可获得良好分区.第二特征向量确定方法如下：
K均值算法取决于初始化聚类中心,是一种局部优化算法.为了实现最优化分区,采用遗传算法优化聚类中心.种群中每个个体对应于各个聚类中心,以SSE最小化为目标函数,通过线性排序确定个体适应度,交叉、变异逐渐产生新的子代.为了提高搜索速度,在每次得到聚类划分后,用校正后的聚类中心代替个体中原来的聚类中心.
1.4确定阀门、水表位置
在确定分区范围后,接下来要确定水表和阀门的位置.在每个分区中均存在中心节点,一般是拓扑连接紧密的节点,即度较高的节点,这意味着该节点是流量的枢纽节点,则水源到该枢纽节点的最短供水路径应该是该分区的主要供水路径,主要供水路径必经过分区间连接管道,则这个管道即为进水点,也就是水表位置,其他连接管道则为阀门位
1.6分区间运行关系
DMA按进水点数量和流量关系可分为单进口、多进口和串联DMA,如图1所示,其中,DMA2和DMA3为单进口类型,DMA4为多进口,上述3个分区共同特征是均只有流量流入而无流出.而DMAl除满*区用水外,还需向DMA2供水,因此,DMAl为串联类型,有流量的流人和流出.目前的分区方法为了方便管理并减少计量误差,一般DMA设计优先选择单进口、无流出类型.但DMA设计影响因素多、情况复杂,有时难以满足上述原则,同时单进口DMA也存在系统弹性能力降低、难以满足消防流量要求和末端水质下降等问题,因此,根据具体情况也可选择多进口DMA,但进水口数量不宜太多,否则进水点处减压阀会引起压力波动可采用主、副进水口设计,即在正常供水时只开启主进水口,而当高峰用水或消防时,可开启副进水口.当远离干管的DMA其供水路径需要经过其他分区时,或者管理、技术等多因素综合比较后串联DMA具有优势时,也可选择串联类型DMA.
2.分区实例
以图2所示环状给水管网为例验证所提分区方法的有效性.该给水管网含有1个水源,36个用水点,58根管道,具有复杂的环状结构.设定分区数量为4个.
4个分区的方案如图2所示.每个分区的规模可见表1,从表中可知每个分区的规模和平均规模有一定偏差.如前所述,如果分区时强调每个分区应含有相同的规模（用水量）,则必将破坏给水管网内部的聚类结构.而依据聚类算法,属性相似的节点组成一个分区,这可从整体上降低分区对给水管网结构的影响.分区后的压力分析见表2.由表2可知,每个分区压力范围相似,平均压力有微小差别.压力均衡性较好,PU值均低于平均压力的10%,说明分区后管网性能没有明显降低,对系统性能的影响较小.
K均值算法是局部优化方法,遗传算法是一种全局优化方法,二者结合将增加收敛速度,由图3可知,经过25次进化后种群即实现收敛.另外,每一代的最佳个体都能搜索到最佳聚类.
在确定分区边界后,需要确定每个分区的进水点和设置阀门的管道.为此根据PageRank算法分析每个节点的中心性,给水管网末端节点中心性较
利用最短路径算法可得每个分区水表位置,其他分区边界管道则为阀门位置.由图2分区结构可知,基于谱聚类的分区方法将干管节点也纳入分区,因此,DMAl和DMA4具有流量流人流出,为串联分区,DMA2和DMA3则为单进口分区.串联分区结构的引人,使得DMAl和DMA4内节点分区前后水流路径不变,分区对这些节点没有影响.
3.结论
提出了基于谱聚类的给水管网分区方法,同时可确定每个分区的进水点和阀门位置,并以一个真实给水管网说明本分区方法的可行性.本方法将给水管网拓扑结构通过谱方法映射到高维向量空问,并依据聚类将拓扑相似节点划分到一个分区,遗传算法和K均值算法相结合提高了算法效率,同时,本方法具有较强的健壮性,可根据要求实现不同规模的分区设计.
本文中不仅确定了分区边界,也给出了进水点位置,下一步工作可在此基础上通过优化进水点减压阀,将各分区内压力控制在合理范围,从而在整体上降低漏损.
聚类论文参考资料：
结论：谱聚类在给水管网分区优化中应用为关于对不知道怎么写聚类论文范文课题研究的大学硕士、相关本科毕业论文聚类算法论文开题报告范文和文献综述及职称论文的作为参考文献资料下载。
