杨浩志,周 艳,王晨婉,孙 韬
(1.天津理工大学环境科学与安全工程学院,天津 300350;2.天津市生态环境科学研究院,天津 300191)
供水管网系统是维系人们生产生活的重要基础设施。随着城市的发展,管道老化、管线连接冗余等问题严重影响供水安全,同时伴随供水需求和供水面积的增加,管网漏损和水质恶化越来越引起人们的重视。为科学合理的管理供水管网,人们提出了区域计量分区(District Metered Areas,DMA分区)的概念[1]。
在对DMA分区的已有研究中,可分为两种:人工经验法分区和算法分区。人工经验法分区是根据自然地理条件或人为屏障作为区域边界,通过在供水管网配水干管上设置阀门或流量计,将管网划为多个区域。如朱子朋、孙伟等[2]以投资少、方便实施为分区目标,通过设置河流、铁路干线和供水管网的加压站等为分区边界,将广州市的供水管网划分为18个独立供水区域。目前我国对城市供水管网的分区研究大多采用人工经验法[3],虽然该方法操作简单,但往往需要实施者具备大量工作经验,随机性较强,因此收到一定的条件限制。而算法分区多数是将供水管网的节点和管道转化为图,基于图论和复杂网络等理论将管网划分为多个区域。如Gomes等[4]提出了一种基于决策支持系统的分区方法。该方法应用图论中最小路径的原理,搜索供水管网最大用水时刻的水源供水范围,初步划分管网的DMA。然后,以经济最大化为目标,应用模拟退化算法确定DMA进水口的位置,完成DMA分区。算法分区避免了由于人的主观经验造成分区的随机性,使分区更加科学合理。
因此,本文在k近邻算法的基础上引入共享最近邻的概念,构建供水管网节点的相似度矩阵,同时对聚类中心的选择进行优化。基于自适应谱聚类算法,以经济性和管网稳定性为主要目标,选取合适分区数目,完成对管网的DMA分区。该方法引入共享最近邻构建节点的相似度矩阵,实现了自动设定相似度矩阵的参数,解决了人为设定的弊端,提高了聚类精确度,使分区更加合理。
自适应谱聚类算法是一种基于图论将图划分求解的聚类算法。一般对所求问题采取连续松弛的方式,将图划分问题转化为划分图的拉普拉斯矩阵。图的拉普拉斯矩阵一般是由图的相似矩阵和度矩阵转化而来。
相似矩阵反映供水管网元素所构成的图中元素之间的相似度,其组成的数据集以矩阵形式表达,用Wij表示,见式(1)。
式中:d2(xi-xj)为元素之间的欧氏距离; σ为人为选取的尺度参数。
由管网拓扑结构可得节点相似矩阵,见式(2)。
式中:E为管网的边的集合;ij为管网节点。
由管网拓扑关系可知,若两点由管段连接,则这两点互为邻居关系。节点自然邻居越多,说明节点与周围节点联系越紧密。当对管网进行DMA分区时,联系紧密的节点易被分到一个分区中。由式1,传统节点近邻算法在计算相似矩阵时,对σ参数的选取一般为人工经验选取,且对于不同数据对应参数不同[5]。本文引入共享最近邻算法改进相似矩阵,见式(3)。
式中:max( N)为节点集合中的最大邻居数;N(i)为节点i的邻居数。
度矩阵是一个对角矩阵,其对角元素分别是相似矩阵Wij中对应的行向量或者列向量,以Dii来表示,见式(4)。
由图的相似矩阵和度矩阵建立图的拉普拉斯矩阵,目前图的拉普拉斯矩阵分为两种:非规范化和规范化。非规范化的拉普拉斯矩阵Lij表达式见式(5)。式中:Lij为非规范化拉普拉斯矩阵;Dii为度矩阵;Wij为相似矩阵。
规范化的拉普拉斯矩阵有两种形式,见式(6)、式(7)。
由于不同形式的拉普拉斯矩阵对应的图划分准则不同,非规范化拉普拉斯矩阵对应图划分准则为最小分割准则,见式(8)。规范化拉普拉斯矩阵对应图划分准则为规范分割准则(式(9))和比例分割准则(式(10))。
式中:|A| 为子图A的顶点数目;|B|为子图B的顶点数目。
由于最小分割准则只考虑划分子图之间的连接权重,未能考虑子图内部密度分布,在划分过程中易出现分割歪斜现象,同时比例分割准则在运行速度和效率上不如另外两种划分准则,因此本文选取规范分割准则对图进行划分,对应的拉普拉斯矩阵,见式(6)。
本文的自适应谱聚类算法以NJW算法为基础,其本质是通过计算拉普拉斯矩阵的前k个最大特征值和相对应的特征向量,并与节点构成相对应的关系,然后在空间中进行聚类。算法步骤如下:
(1)计算相似矩阵Aij∈ln×n,其中Aij为相似矩阵的邻接矩
(3)计算拉普拉斯矩阵的前K个最大特征值,记为1…k,并计算特征值对应的特征向量a1…ak,构建特征向量矩阵[a]n×k=[a1,a2,a3,…ak] ∈I,k即为聚类数目。
(4)将矩阵[a]n×k中的行向量与原数据集中的节点相对应,应用K-means聚类算法对节点进行聚类,引入center参数矫正聚类中心,得到K个聚类结果,完成管网分区。
本文采用管网校核竞赛的Ctown案例来验证所提出DMA分区方法。管网共包含388 个节点,1 个水库,7 个水池,429 根管段,总管长56.177 km。各个节点位置参数可基于EPANET建立的水力模型得到。由于DMA分区之间是以在边界连接管段上安装阀门或流量计来划分,且流量计和阀门设备费用较高,因此在对DMA分区时应尽可能使边界连接管段数量较少。同时为保证分区合理,本文以模块度M(式11)、节点均衡性B(式12)和边界连接管段数量评价分区是否可行。
式中:Aij为网络邻接矩阵,若节点i与j相连,则Aij=1,若不相连, Aij=0;i和j为节点;e为网络边数;ki为节点i的度;kj为节点j的度;Ci为节点i所在分区;Cj为节点j所在分区。若节点i和节点j分区一致,则 =1,否则 =0。
根据式(11)可知,分区越合理对应模块度的数值越高,其取值范围为[0,1]。
式中:Cd为分区数;nd为第d个分区的节点数,n为各分区的平均节点数。
节点均衡性反应了分区规模是否趋近一致,其数值越小证明分区越合理。
通过已有文献可知[6],相关学者将Ctown划分为5 个DMA分区。本文为比较不同分区数目的管网聚类效果,分别选取分区个数为4、5、6。该管网树状结构和管网控制元件较多,且水池分布均匀,因此管网区域特征较为明显,管网拓扑结构见图1。
图1 Ctown拓扑结构图
分别输入分区个数4、5、6,基于自适应谱聚类算法利用MATLAB对案例管网进行DMA分区,分区结果见图2。
图2 DMA分区结果
根据图2划分结果,分别计算管网的模块度、节点均衡性和边界连接管段数量,计算结果见表1。
表1 DMA分区的评价结果
根据表1的计算结果,三次分区的模块度数值接近,但将管网划分为4个DMA分区的节点均衡性数值较高,分区效果不理想,因此不宜作为DMA分区方案。以5个DMA分区数和6个DMA分区数对管网进行划分,模块度和边界连接管段数量接近,但节点均衡性差别明显,且节点均衡性数值越小分区越合理。因此,本文选取分区方案为6个DMA分区。
本文提出了基于自适应谱聚类算法的DMA分区方法,并矫正聚类中心。该算法有效减少了分区边界连接管的数量,从而使安装阀门和流量计的费用降低。通过模块度和节点均衡性指标评价分区结果,使分区更加合理,完成了分区合理经济的目标。并基于Ctown案例管网验证了该分区方法的可行性。该算法经济有效,能够合理地对管网进行DMA分区,提高对管网的科学管理能力。