基于改进谱聚类及遗传算法的供水管网独立计量分区方法

1.本发明属于城市供水管网设计技术领域，涉及一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法。


背景技术：

2.随着城镇化进程的快速发展，由供水管网漏损问题所带来的巨大的经济损失和负面社会效应也与日俱增，供水管网的漏损问题越来越被社会所重视，同时也是智能水务亟待解决的一大难题。经过多年国内外实践证明，供水管网dma(district metering area)技术凭其先进管理方式和立竿见影的控制漏损表现，已经成为供水管网控制漏损技术之一。由于供水管网的拓扑复杂，漏失点不易探查修复，因此实现dma分区的压力优化运行、建立dma分区压力优化控制系统是降低当前供水管道条件下漏损量的最佳办法。
3.dma分区发展至今，按其发展过程可分为经验分区法和智能算法自动分区两大类，具体介绍如下：经验分区法是管理者基于对供水管网的熟悉掌握进行手动分区，根据是否借助水力模型，又可将经验分区法分为直接和间接分区法；经验分区法的对象大多为简单的小型供水管网且分区结果的主观成分较多，但是对于结构复杂的大型环状管网由于依靠经验并无法完全熟知全部管网的运行状况，所以经验分区法已不能满足大型供水分区的需求。近年来，国内外的研究学者尝试将智能算法引入到dma分区中来，智能算法自动分区法使管网分区方案更有科学性和依据性，根据方法和用途的不同，可将算法自动分区分为以下几类：1)供水分界线法，即将各个水源的供水区域可以看做是从该水源流出的所有有向路径的集合，从而实现多水源供水区域的划分；2)社区结构法，即基于社区结构将复杂的供水管网等效为复杂网络进行聚类分析，对管网中连边关系的局部聚集关系来进行dma的聚类分区；3)单目标或多目标优化算法分区，即使用供水管网水力优化和经济因素等单个或多个目标的优化分区方法；4)基于图论的方法，即是将实际供水管网等效为无向加权拓扑图，采用不同的方法对管网无向拓扑图的节点进行划分，得到dma分区，诸多研究人员对此类的方法进行了研究。


技术实现要素：

4.本发明用于解决如何采用改进谱聚类及遗传算法对供水管网dma分区进行优化的问题。
5.本发明是通过以下技术方案解决上述技术问题的：
6.如图1所示，基于改进谱聚类及遗传算法的供水管网独立计量分区方法，包括以下步骤：
7.1、在epanet软件中建立供水管网微观水力模型，通过调用epanet工具箱获取供水管网拓扑结构、节点需水量、高程属性、节点坐标位置，并构建能够反映供水管网拓扑结构的邻接矩阵
8.(1)将供水管网的拓扑关系和管件运行参数导入到epanet软件中，建立供水管网
微观水力模型，其中供水管网节点集合为v＝{v1,v2,v3......vn}，管段集合为l＝{l1,l2,l3,...,lm}。
9.(2)调用epanet工具箱，执行水力分析，得到供水管网节点坐标位置节点需水量[q1,q2,...,qn]、高程属性[r
1(3)
,r
2(3)
,...,r
n(3)
]、压力属性[h1,h2,...,hn]。
[0010]
(3)构建能够反映供水管网拓扑结构的邻接矩阵需要根据节点vi和vj间有无直接相连的管道进行量化成节点的自然邻关系，公式如下：
[0011][0012]
由节点之间自然邻关系得到供水管网等效的无向连接图的邻接矩阵a，形式如下：
[0013][0014]
其中，a
ij
表示节点vi和vj的自然邻关系，s
ij
表示两节点连接关系，如果a
ij
为1，那么表示节点vi和vj直接相连，即互为自然邻节点；如果a
ij
为0，那么表示节点vi和vj不直接相连，即不是自然邻节点关系。
[0015]
2、利用供水管网节点坐标位置及高程属性构造节点相似度矩阵，同时利用邻接矩阵及节点需水量大小构造需水量相似度矩阵
[0016]
2.1、所述的利用供水管网节点坐标位置及高程属性构造节点相似度矩阵的方法具体如下：
[0017]
(1)将步骤1得到的供水管网节点坐标位置以及高程属性[r
1(3)
,r
2(3)
,...,r
n(3)
]组合成节点属性特征矩阵
[0018]
其中，hi为供水管网第i个节点组成的属性特征向量；r
i(1)
为hi中第1列值，代表第i个节点位置坐标中的横坐标；r
i(2)
为hi中第2列值，代表第i个节点位置坐标中的纵坐标；ri(3)
为hi中第3列值，代表第i个节点的高程。
[0019]
(2)对选择的节点属性特征矩阵h进行标准化，经过处理的数据的均值为0，标准差为1，转化公式如下：
[0020][0021][0022]
其中，r
i(t)
为节点属性矩阵h中第i行向量hi中第t个值，μ
t
为节点属性矩阵h中第t列所有值的均值，σ
t
为节点属性矩阵h中第t列所有值的标准差；
[0023]
经标准化后得到的节点属性矩阵h'为：
[0024][0025]
其中，h'i为节点属性矩阵h中第i行向量hi经标准化后的结果。
[0026]
(3)标准化后的节点属性矩阵h'中第i行向量h'i与第j行向量h'j之间的欧氏距离计算方法如下：
[0027][0028]
其中，h'i,h'j分别表示矩阵h'中第i行与第j行向量；
[0029]
依次计算矩阵h'中各行向量之间欧式距离值并组成向量d如下：
[0030]
其中，
[0031]
(4)利用向量d中各元素建立基于高斯核函数的节点相似度矩阵w1，高斯核变换公式及矩阵w1形式如下：
[0032][0033]
其中，a
ij
为节点相似度矩阵w1中第i行第j列的元素值，std(d)为向量d中所有元素的标准差，std(d)的计算公式如下：
[0034][0035]
2.2、所述的利用邻接矩阵及节点需水量大小构造需水量相似度矩阵的方法具体如下：
[0036]
(1)对供水管网微观水力模型的邻接矩阵a各列求和得到各节点的度z
ii
，z
ii
也可以理解为供水管网中与节点vi存在直接连接的管段总数量，进而形成供水管网度矩阵degv如下：
[0037][0038]
其中，
[0039]
(2)根据管网各节点需水量[q1,q2,...,qn]以及供水管网度矩阵degv，计算出供水管网相邻节点vi和vj之间水分配需求的相似度b
ij
，进而组成需水量相似度矩阵w2如下：
[0040][0041]
其中，b
ij
为节点相似度矩阵w2中第i行第j列的元素值；qi,qj分别为供水管网节点vi和vj需水量大小。
[0042]
3、由节点相似度矩阵和需水量相似度矩阵相加得出边权重矩阵，将所述边权重矩阵输入到改进的加权谱聚类算法中生成dma配置，确定dma分区边界管段集合
[0043]
如图2所示，聚类阶段的主要步骤如下：
[0044]
(1)为了可以更加真实地反映供水管网中节点的相似性，将节点相似度矩阵w1与需水量相似度矩阵w2相加得到边权重矩阵w，边权重矩阵w的形式如下：
[0045]
[0046]
式中，其中w
ij
＝a
ij
+b
ij
，w
ij
为节点相似度矩阵w中第i行第j列的元素值；a
ij
为节点相似度矩阵w1中第i行第j列的元素值，b
ij
为需水量相似度矩阵w2中第i行第j列的元素值。
[0047]
(2)定义对角矩阵y主对角线上的元素为对边权重矩阵w第j列求和的值，对角矩阵y形式如下：
[0048][0049]
其中，
[0050]
(3)利用边权重矩阵w和对角矩阵y，求得标准化拉普拉斯矩阵l
sym
如下：
[0051][0052]
由于标准化拉普拉斯矩阵l
sym
为半正定矩阵，当对标准化拉普拉斯矩阵l
sym
进行特征值分解时，可得到该矩阵有n个非负实特征值0＝λ1≤λ2≤
…
≤λn。
[0053]
(4)基于n-cut切图方式，采用多路分割可以得到准确、稳定的聚类效果，计算标准化拉普拉斯矩阵l
sym
对应的前k个最小特征值{λ1,λ2,
…
,λk}对应的特征向量{u1,u2,...,uk},进而组成矩阵u，形式如下：
[0054][0055]
其中，u
x
为标准化拉普拉斯矩阵l
sym
前k个最小特征值中第x个值对应的特征向量，i,j＝1,2,...n；x＝1,2,...,k。
[0056]
(5)对矩阵u进行规范化，规范化公式以及规范化后的矩阵u'形式如下：
[0057]
[0058]
其中，u'
ix
代表矩阵u'中第i行第x列元素值u
ix
经过规范化后的结果。
[0059]
(6)矩阵u'可以看作是n个行向量组成的集合(o1,o2,oi,...,on)
t
(i＝1,2,...,n),采用k-medoids算法将各行向量oi(i＝1,2,3,...,n)归类到k个簇(c1,c2,cf..,ck)中，cf代表所有属于第f类的行向量集合。
[0060]
(7)若集合(o1,o2,oi,...,on)
t
(i＝1,2,...,n)中第i行元素被归为第f簇，那么相对应原始数据的管网节点vi也被归为第f个区域；结果输出dma配置，并确定k个独立区域之间相连接管段组成的边界管段集合b＝(g1,g2,...g
nec
),其中，nec表示dma间边界管段总数，g表示边界管段索引。
[0061]
4、通过遗传算法优化边界管段集合中流量计及阀门布置，最终完成供水管网dma分区
[0062]
如图3所示，划分阶段的主要步骤如下：
[0063]
(1)为了将复杂的供水管网分割成若干个独立区域，以分别隔离区域和测量流量，需要在边界管段集合b＝(g1,g2,...g
nec
)上布置阀门或流量计；首先根据边界管段集合b中元素总数量nec确定编码的长度，具体到每一根管段上，若给某边界管段布置流量计则对应于染色体编码为二进制数1；反之，若给该边界管段布置阀门则对应于染色体编码为二进制数0，故遗传算法中一组二元染色体序列i的定义如下：
[0064]
i＝(g1,g2,...g
nec
)，其中，
[0065]
同时，为了缩小遗传算法解空间以及最小化dma实施预算，首先定义插入供水管网中流量计的总数量nfm＝k，其中，k为设定的dma分区数量，也就是说这里限制遗传算法的一组二元染色体序列i中仅存在k个1，其余位置为0。
[0066]
(2)目标函数为最大化供水管网节点耗散功率p，故遗传算法的适应度函数f被定义为目标函数的倒数：
[0067][0068]
其中，γ是水的比重，r
i(3)
,hi,qi分别表示供水管网的边界管段集合上布置阀门与流量计后第i个节点的高程、压力以及需水量数据。
[0069]
(3)初始化遗传算法种群规模c、交叉概率p
cro
、变异概率p
het
，并设定算法终止条件：最大遗传代数j、收敛阈值t
thr
；同时，遗传算法输出的最优解还需要满足节点压力约束条件如下：
[0070]hmin
≤hi≤h
max
[0071]
其中，h
min
为节点最小服务水压，h
max
为节点最高允许水压，hi为当前解对应的阀门与流量计布置方案下供水管网水力运行得到的各节点压力数据。
[0072]
(4)流量计及阀门布置问题优化布置流程如下：
[0073]
a、初始化种群，随机生成c个二元染色体序列i，即生成c个个体作为初始父代种群；
[0074]
b、调用epanet工具箱生成某个体编码序列对应布置方案下的dma分区结果并进行水力分析，获取当前dma分区下节点的高程[r
1(3)
,r
2(3)
,...,r
n(3)
]、需水量[q1,q2,...,qn]和压力[h1,h2,...,hn]数据，通过适应度函数f计算得到该个体的适应度值。依次计算父代种群c个个体适应度值，并判断是否满足算法终止条件(达到最大迭代次数j或满足收敛阈值t
thr
)，若不满足，则跳转至c；若满足，则跳转至d；
[0075]
c、根据父代种群c个个体适应度函数值的大小，选择出个体进行交叉、变异操作生成子代，并将生成的子代种群作为父代种群，返回至b，进行下一代进化；
[0076]
d、若算法运行输出的当前解不满足节点压力约束条件，则令布置的流量计数量增加一个，即nfm＝nfm+1，在改变遗传算法染色体编码形式之后返回至s2重新计算新增流量计数量下的最优解；若本次算法运行得到的结果符合节点压力约束条件或达到最大迭代次数nec—nfm(即全部边界管段上都布置流量计)时停止计算，输出最优个体并得到对应边界管段集合中流量计和阀门的最佳布置方式，最终完成dma规划。
[0077]
本发明的优点在于：
[0078]
(1)本发明通过在epanet软件中建立供水管网微观水力模型，通过调用epanet工具箱获取供水管网拓扑结构、节点需水量、高程、坐标参数；构建管网节点的坐标与高程参数组成节点属性特征矩阵并进行标准化，计算标准化后节点属性特征矩阵行之间欧氏距离并经高斯核变换得到供水管网的节点相似度矩阵；同时，结合管网拓扑结构和管网节点需水量参数构建供水管网的需水量相似度矩阵；由节点相似度矩阵和需水量相似度矩阵相加得出边权重矩阵，将该矩阵输入到改进的加权谱聚类算法中生成dma配置，确定dma分区边界管段集合；利用遗传算法确定边界管段集合中水表及阀门最优布置方案，最终完成dma分区；本发明结合供水管网拓扑结构信息和运行状况信息，来提升相似度图的质量，采用改进谱聚类对任意形状的样本空间进行最优划分，得到水力性能影响最小的分区布局；采用遗传算法解决流量计及阀门的布置问题，并通过设定最小化流量计数量可以得到经济性最优情况下的布置方案。经过验证，dma分区后的供水管网在边界管段的数量以及需水量均匀性等指标上有大幅提升。
[0079]
(2)文献《基于谱聚类与评估机制的供水管网dma分区方案》(梁俊卿,孔潇潇.水电能源科学，2022,40(1):4.)公开了一种基于谱聚类与评估机制的供水管网dma分区方案，但是该文献仅利用节点连接距离形成基于图论的相似度图，并基于相似度图连接边的权值经高斯核变换构建相似度矩阵，但它忽略了节点的标高、需水量、坐标等属性，这些属性的缺失导致基于图论形成的相似度图无法完全描述供水管网节点之间的相似关系。因此，基于相似度图信息的缺失形成的节点间相似度矩阵经加权谱聚类算法得出的集群结果水力性能差(例如需水量均匀性过高)、成本高(例如边界管段数量多)。本发明结合节点物理属性和水力特性来表征供水管网，利用供水管网节点需水量、高程、坐标属性及最近邻关系相互融合来提升相似度图的质量，从而构建准确的相似度矩阵，以平衡dma分区内的节点数量和供水量的需求差异。其次，该文献未考虑边界管段上阀门与流量计的优化布置方案，dma实施方案需要在供水管网部分dma边界管段上加装流量计以测量流入和流出，并在剩余dma边界管段上全部安装阀门以隔离dma，未加装相关设备，将导致无法形成完整的dma分区结果。
本发明通过在供水管网的dma间边界管段上安装阀门与流量计的布置，不仅可以实现区域之间相互隔离也可以保护网络免受恶意污染事件，还可以利用长期连续监测数据，确定供水管网每个dma区域的最小夜间流量监测限值，以协助判断新增漏损点。
[0080]
(3)申请公布号为2021年8月17日、申请公布号为cn113312735a的中国发明专利申请文献公开了一种城市供水管网dma分区方法，但是该专利文献仅利用供水管网管段管径、流量和长度属性的乘积来定义相似度，未考虑供水管网节点的相关属性，这些属性的缺失会导致形成基于图论的相似度图不能够完全表征供水管网节点之间的相似关系，从而构建出的相似度矩阵不能很好地反映聚类样本(供水管网节点)之间的相似性，进而影响了后续谱聚类算法结果的可靠性。本发明结合节点物理属性和水力特性来表征供水管网，建立由供水管网节点需水量、高程、坐标属性及最近邻关系相互融合来提升相似度图的质量，从而形成准确的相似度矩阵，更贴近供水管网节点的物理特性以及水需求的多样性，为后续分区奠定基础。其次，该专利文献利用多目标粒子群算法优化dma边界管段的设备布置方案。多目标粒子群算法擅长处理连续变化的变量，但是对于非连续变量的优化问题处理不佳，容易陷入局部最优解。遗传算法不仅可以解决非线性、不连续的问题，同时算法有着较快的收敛速度、较高的寻优精度和较强的全局寻优能力。dma边界管段上阀门与流量计布置问题是一组非连续变量的最优解搜索问题，故本发明利用遗传算法确定边界管段集合中水表及阀门最优布置方案，算法运行速度快，能搜索出高水力性能的最优解。
[0081]
(4)除此之外，上述两个文献中均使用了基于k-means的谱聚类算法，该算法存在聚类容易落入局部最优解的问题。k-means对离群点敏感度不足，这使得异常数据对其算法过程会有较大影响。k-medoids是对k-means的优化和改进算法，k-medoids算法选择实际的数据样本取代k-means算法使用样本均值作为聚类中心点，剩下的数据则根据欧式距离被划分到与其最近的集群中，从而减少某些孤立数据对聚类过程的影响。本发明使用基于k-medoids的谱聚类算法进行dma初步分区，从dma初步分区结果上看，基于k-medoids的谱聚类算法可以在平衡dma分区内节点数量的同时得到dma间边界管段数量最少的集群方案，进而得到最佳dma初步分区结果。
附图说明
[0082]
图1为本发明的基于改进谱聚类及遗传算法的供水管网独立计量分区方法的流程图；
[0083]
图2为本发明的基于改进谱聚类及遗传算法的供水管网独立计量分区方法的聚类阶段的流程图；
[0084]
图3为本发明的基于改进谱聚类及遗传算法的供水管网独立计量分区方法的划分阶段的流程图；
[0085]
图4为本发明的基于改进谱聚类及遗传算法的供水管网独立计量分区方法的实施例的管网模型；
[0086]
图5为本发明的基于改进谱聚类及遗传算法的供水管网独立计量分区方法的实施例的管网模型经谱聚类后的图；
[0087]
图6为本发明的基于改进谱聚类及遗传算法的供水管网独立计量分区方法的实施例的管网模型最终dma分区图。
具体实施方式
[0088]
为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0089]
下面结合说明书附图以及具体的实施例对本发明的技术方案作进一步描述：
[0090]
实施例一
[0091]
如图4所示，选取某市供水管网作为实验研究对象。该管网由268个需水节点，4个供水水库和317条连接管段组成，其中，总需水量为406.94l/s，需水节点标高的最小值为30.39m，最大值为41.83m，管网最小服务水压为14m。该供水管网网络结构复杂，能够很好地模拟实际供水管网。该供水管网分区数量根据分区目的、系统规模、分区大小、成本等综合考虑确定分区数量k为4。
[0092]
本实施例公开的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，具体包括以下步骤：
[0093]
步骤1，将实际供水管网的拓扑关系和管件运行参数导入到epanet软件中，建立实际供水管网微观水力模型，其中供水管网需水节点个数为n＝268，管段数为m＝317；调用epanet工具箱，执行水力分析，获取管网拓扑结构信息和运行状况信息，包括供水管网的邻接矩阵以及各节点位置坐标、高程、需水量、压力数据，具体如下：
[0094]
供水管网等效无向连接图的邻接矩阵形式为：
[0095][0096]
调用epanet工具箱得到供水管网各节点位置坐标、高程、需水量、压力数据，数据以表格展示如下：
[0097][0098]
步骤2，结合供水管网拓扑结构和管网节点参数数据经计算得到节点相似度矩阵以及需水量相似度矩阵，具体步骤如下：
[0099]
2.1、将节点位置坐标与高程数据组合成节点属性特征矩阵h，矩阵形式如下：
[0100][0101]
对选择的节点属性特征矩阵h进行标准化，得到的节点属性矩阵h'为：
[0102][0103]
依次计算标准化后的节点属性矩阵h'中第i行向量h'i与第j行向量h'j之间的欧氏距离，组成向量如下：
[0104]
d＝[0.1645 0.5644 1.2443... 0.5848]1×
35778
[0105]
由向量d中元素经过高斯核变换建立起节点相似度矩阵w1,矩阵形式如下：
[0106][0107]
2.2、根据供水管网微观水力模型的邻接矩阵a可计算出各节点的度d
ii
，d
ii
也可以理解为供水管网中与节点vi存在直接连接的管段总数量，根据管网各节点需水量qi以及供水管网各节点的度d
ii
，计算出供水管网节点vi和vj之间水分配需求的相似度b
ij
，进而组成需水量相似度矩阵w2，矩阵形式如下：
[0108][0109]
步骤3，将节点相似度矩阵w1与需求相似度矩阵w2相加得到边权重矩阵，将该矩阵输入到改进后的加权谱聚类算法中将供水管网划分成指定数量为k簇，相对应的供水管网节点集v中各节点也被划分到k个区域中，并得到各dma间边界管段集合b，具体如下：
[0110]
3.1、为了可以更加真实地反映供水管网中节点的相似性，将节点相似度矩阵与需水量相似度矩阵相加作为边权重矩阵w，计算公式为：
[0111][0112]
3.2、定义对角矩阵d,对角矩阵d主对角线上的元素为边权重矩阵w第i列所有值的总和，形成的对角矩阵如下：
[0113][0114]
3.3、利用边权重矩阵w和对角矩阵d，根据以下公式，求得标准化拉普拉斯矩阵：
[0115][0116]
由于标准化拉普拉斯矩阵l
sym
为半正定矩阵，当对标准化拉普拉斯矩阵l
sym
进行特征值分解时，可得到该矩阵有n个非负实特征值；
[0117]
3.4、基于n-cut切图方式，采用多路分割可以得到准确、稳定的聚类效果，计算标准化拉普拉斯矩阵l
sym
对应的前4个最小特征值{0,0.0039，0.0062，0.0089}对应的特征向量进而组成矩阵u＝(u1,u2,u3,u4)。
[0118]
3.5、对矩阵u进行规范化，得到矩阵u'，规范化后的矩阵u'为：
[0119][0120]
3.6、矩阵u'可以看作是n个行向量组成的集合(o1,o2,oi,...,on)
t
(i＝1,2,...,n),采用k-medoids算法将各行向量ni(i＝1,2,3,...,n)归类到4个簇(c1,c2,c3,c4)中；
[0121]
3.7、若集合(o1,o2,oi,...,on)
t
(i＝1,2,...,n)中第i行被归为第f类，那么相对应原始数据的管网节点vi也被归为第f类。算法结果输出dma配置，并确定分区中边界管段集合如下：
[0122]
b＝(153,273,206,254,272,58,156,166,191,85,160,1,178,247,23,116,178,147)1×
17
[0123]
其中，集合b中各元素为边界管段索引，此时dma间边界管段总数为17，dma配置可视化结果如图5所示。
[0124]
步骤4，采用二进制编码方式对供水管网的边界管段进行编码，以最大化供水管网
节点耗散功率p为目标函数，在满足供水管网水力约束的条件下，使用遗传算法搜索边界管段集合上阀门与流量计的最优布置方案，最终完成dma的分区规划，具体步骤如下：
[0125]
4.1、为了将复杂的供水管网分割成若干个独立区域，以分别隔离区域和测量流量，需要在边界管段集合b＝(153,273,...147)1×
17
上布置阀门与流量计，分别对应二进制编码0与1，并根据边界管段集合的数量nec＝17确定编码的长度为17，故定义的一组二元染色体序列为i＝(g1,g2,...g
17
)，同时预先设定在边界管段集合中布置流量计的数量为dma数量nfm＝4。
[0126]
4.2、所述目标函数为最大化供水管网节点耗散功率z，故遗传算法的适应度函数被定义为目标函数的倒数：
[0127][0128]
其中，γ是水的比重，r
i(3)
,hi,qi分别表示供水管网的边界管段集合上布置阀门与流量计后第i个节点的高程、压力以及需水量。
[0129]
4.3、初始化遗传算法种群规模c＝50、交叉概率p
cro
＝0.8、变异概率p
het
＝0.08，并设定算法终止条件：最大遗传代数j＝100、收敛阈值t
thr
＝1
×
10-6
。同时，遗传算法输出的最优解还需要满足节点压力约束条件hi≥h
min
＝14m：
[0130]
4.4、基于遗传算法解决流量计及阀门布置问题的运行步骤如下：
[0131]
a.初始化种群，随机生成c＝50个个体编码序列作为初始父代种群；
[0132]
b.调用epanet工具箱生成某个体编码序列对应布置方案下的dma分区结果并进行水力分析，获取当前dma分区下节点的高程[r
1(3)
,r
2(3)
,...,r
n(3)
]、需水量[q1,q2,...,qn]和压力[h1,h2,...,hn]数据，通过适应度函数f计算得到该个体的适应度值。依次计算父代种群c＝50个个体适应度值，并判断是否满足算法终止条件，若不满足，则跳转至c；若满足，则跳转至d；
[0133]
c.根据父代种群c＝50个个体适应度函数值的大小，选择出个体进行交叉、变异操作生成子代，并将生成的子代种群作为父代种群，返回至b，进行下一代进化；
[0134]
d.若本次算法运行得到的解不满足节点压力约束条件，则令nfm＝nfm+1，返回至s2重新计算当前流量计数量下的最优解；若本次算法运行得到的结果符合约束条件，则停止计算，输出最优个体并得到对应边界管段集合中流量计和阀门的最佳布置方式，最终完成dma规划。
[0135]
如图6所示，算法在首次运行结束后发现未能找到满足当前流量计下的解，此时令流量计数量加1，开始第一次迭代，即初始父代种群中个体染色体编码定义成nfm＝5个流量计和nec—nfm＝12个阀门的组合，重新运行遗传算法，搜索新增流量计数量下的最优解；由于算法在第二次运行结束后仍不满足压力约束条件，故开始第二次迭代，最终我们发现当遗传算法染色体编码中设置流量计数量为6个，阀门数量为11时满足水力约束条件，输出对应最优染色体序列，最终完成dma分区规划。图6显示了迭代使用遗传算法决策出的最佳dma布局，同时展示了在边界管段集合中阀门与流量计的布置位置且导致的供水管网拓扑结构改变在图中清晰可见。
[0136]
本发明相较于传统的聚类算法，谱聚类的一大优势在于其能对任意形状的样本空
间进行最优划分。由于图是谱聚类算法的输入，因此图的质量在很大程度上对聚类结果有直接影响，如何构造一个高质量相似度图是谱聚类能否得到好的聚类结果的关键，故本发明结合供水管网拓扑结构信息和运行状况信息来提升相似度图的质量，可以得到水力性能影响最小的分区布局。本发明的遗传算法是一种适应性的人工智能技术，主要基于目标函数和计算约束进行优化，非常适合离散和非线性优化问题。由于在选择用于插入流量计或阀门的管道对供水管网进行物理分区存在很多种可能的供水管网dma布局组合，在计算上不可能调查所有的解决方案空间，这是一个np难题，需要启发式算法来找到最优解，故本发明利用遗传算法解决流量计及阀门的布置问题，并通过设定最小化流量计数量可以得到经济性最优情况下的布置方案。
[0137]
以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。

技术特征：
1.一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，包括以下步骤：s1、在epanet软件中建立供水管网微观水力模型，通过调用epanet工具箱获取供水管网拓扑结构、节点需水量、高程、坐标参数，并构建能够反映供水管网拓扑结构的邻接矩阵；s2、利用供水管网节点坐标位置及高程属性构造节点相似度矩阵；同时利用邻接矩阵及节点需水量大小构造需水量相似度矩阵；s3、由节点相似度矩阵和需水量相似度矩阵相加得出边权重矩阵，将所述边权重矩阵输入到改进的加权谱聚类算法中生成dma配置，确定dma分区边界管段集合；s4、通过遗传算法优化边界管段集合中流量计及阀门布置，最终完成供水管网dma分区。2.根据权利要求1所述的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，步骤s1中所述的在epanet软件中建立供水管网微观水力模型，通过调用epanet工具箱获取供水管网拓扑结构、节点需水量、高程属性、节点坐标位置，的方法如下：(1)将供水管网的拓扑关系和管件运行参数导入到epanet软件中，建立供水管网微观水力模型，其中供水管网节点集合为v＝{v1,v2,v3......v
n
}，管段集合为l＝{l1,l2,l3,...,l
m
}；(2)调用epanet工具箱，执行水力分析，得到供水管网节点坐标位置节点需水量[q1,q2,...,q
n
]、高程属性[r
1(3)
,r
2(3)
,...,r
n(3)
]、压力属性[h1,h2,...,h
n
]。3.根据权利要求2所述的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，步骤s1中所述的构建能够反映供水管网拓扑结构的邻接矩阵的方法如下：构建能够反映供水管网拓扑结构的邻接矩阵需要根据节点v
i
和v
j
间有无直接相连的管道进行量化成节点的自然邻关系，公式如下：由节点之间自然邻关系得到供水管网等效的无向连接图的邻接矩阵a，形式如下：其中，a
ij
表示节点v
i
和v
j
的自然邻关系，s
ij
表示两节点连接关系，如果a
ij
为1，那么表示节点v
i
和v
j
直接相连，即互为自然邻节点；如果a
ij
为0，那么表示节点v
i
和v
j
不直接相连，即不是自然邻节点关系。
4.根据权利要求3所述的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，步骤s2中所述的利用供水管网节点坐标位置及高程属性构造节点相似度矩阵的方法如下：(1)将步骤1得到的供水管网节点坐标位置以及高程属性[r
1(3)
,r
2(3)
,...,r
n(3)
]组合成节点属性特征矩阵其中，h
i
为供水管网第i个节点组成的属性特征向量；r
i(1)
为h
i
中第1列值，代表第i个节点位置坐标中的横坐标；r
i(2)
为h
i
中第2列值，代表第i个节点位置坐标中的纵坐标；r
i(3)
为h
i
中第3列值，代表第i个节点的高程；(2)对选择的节点属性特征矩阵h进行标准化，经过处理的数据的均值为0，标准差为1，转化公式如下：r
i
'
(t)
＝(r
i(t)-μ
t
)/σ
t
(i＝1,2,3......n,t＝1,2,3)其中，r
i(t)
为节点属性矩阵h中第i行向量h
i
中第t个值，μ
t
为节点属性矩阵h中第t列所有值的均值，σ
t
为节点属性矩阵h中第t列所有值的标准差；经标准化后得到的节点属性矩阵h'为：其中，h'
i
为节点属性矩阵h中第i行向量h
i
经标准化后的结果；(3)标准化后的节点属性矩阵h'中第i行向量h'
i
与第j行向量h'
j
之间的欧氏距离计算方法如下：其中，h'
i
,h'
j
分别表示矩阵h'中第i行与第j行向量；依次计算矩阵h'中各行向量之间欧式距离值并组成向量d如下：
其中，(4)利用向量d中各元素建立基于高斯核函数的节点相似度矩阵w1，高斯核变换公式及矩阵w1形式如下：其中，a
ij
为节点相似度矩阵w1中第i行第j列的元素值，std(d)为向量d中所有元素的标准差，std(d)的计算公式如下：5.根据权利要求4所述的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，步骤s2中所述的利用邻接矩阵及节点需水量大小构造需水量相似度矩阵的方法如下：(1)对供水管网微观水力模型的邻接矩阵a各列求和得到各节点的度z
ii
，z
ii
也可以理解为供水管网中与节点v
i
存在直接连接的管段总数量，进而形成供水管网度矩阵degv如下：其中，i,j＝1,2,...n；(2)根据管网各节点需水量[q1,q2,...,q
n
]以及供水管网度矩阵degv，计算出供水管网相邻节点v
i
和v
j
之间水分配需求的相似度b
ij
，进而组成需水量相似度矩阵w2如下：
其中，b
ij
为节点相似度矩阵w2中第i行第j列的元素值；q
i
,q
j
分别为供水管网节点v
i
和v
j
需水量大小。6.根据权利要求5所述的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，步骤s3中所述的由节点相似度矩阵和需水量相似度矩阵相加得出边权重矩阵，将所述边权重矩阵输入到改进的加权谱聚类算法中生成dma配置，确定dma分区边界管段集合的方法如下：(1)为了可以更加真实地反映供水管网中节点的相似性，将节点相似度矩阵w1与需水量相似度矩阵w2相加得到边权重矩阵w，边权重矩阵w的形式如下：式中，其中w
ij
＝a
ij
+b
ij
，w
ij
为节点相似度矩阵w中第i行第j列的元素值；a
ij
为节点相似度矩阵w1中第i行第j列的元素值，b
ij
为需水量相似度矩阵w2中第i行第j列的元素值；(2)定义对角矩阵y主对角线上的元素为对边权重矩阵w第j列求和的值，对角矩阵y形式如下：其中，(3)利用边权重矩阵w和对角矩阵y，求得标准化拉普拉斯矩阵l
sym
如下：由于标准化拉普拉斯矩阵l
sym
为半正定矩阵，当对标准化拉普拉斯矩阵l
sym
进行特征值分解时，可得到该矩阵有n个非负实特征值0＝λ1≤λ2≤
…
≤λ
n
；(4)基于n-cut切图方式，采用多路分割可以得到准确、稳定的聚类效果，计算标准化拉
普拉斯矩阵l
sym
对应的前k个最小特征值{λ1,λ2,
…
,λ
k
}对应的特征向量{u1,u2,...,u
k
},进而组成矩阵u，形式如下：其中，u
x
为标准化拉普拉斯矩阵l
sym
前k个最小特征值中第x个值对应的特征向量，i,j＝1,2,...n；x＝1,2,...,k；(5)对矩阵u进行规范化，规范化公式以及规范化后的矩阵u'形式如下：其中，u'
ix
代表矩阵u'中第i行第x列元素值u
ix
经过规范化后的结果；(6)矩阵u'可以看作是n个行向量组成的集合(o1,o2,o
i
,...,o
n
)
t
(i＝1,2,...,n),采用k-medoids算法将各行向量o
i
(i＝1,2,3,...,n)归类到k个簇(c1,c2,c
f
..,c
k
)中，c
f
代表所有属于第f类的行向量集合；(7)若集合(o1,o2,o
i
,...,o
n
)
t
(i＝1,2,...,n)中第i行元素被归为第f簇，那么相对应原始数据的管网节点v
i
也被归为第f个区域；结果输出dma配置，并确定k个独立区域之间相连接管段组成的边界管段集合b＝(g1,g2,...g
nec
),其中，nec表示dma间边界管段总数，g表示边界管段索引。7.根据权利要求6所述的一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，其特征在于，步骤s4中所述的通过遗传算法优化边界管段集合中流量计及阀门布置，最终完成供水管网dma分区的方法如下：(1)为了将复杂的供水管网分割成若干个独立区域，以分别隔离区域和测量流量，需要在边界管段集合b＝(g1,g2,...g
nec
)上布置阀门或流量计；首先根据边界管段集合b中元素总数量nec确定编码的长度，具体到每一根管段上，若给某边界管段布置流量计则对应于染色体编码为二进制数1；反之，若给该边界管段布置阀门则对应于染色体编码为二进制数0，故遗传算法中一组二元染色体序列i的定义如下：i＝(g1,g2,...g
nec
)，其中，同时，为了缩小遗传算法解空间以及最小化dma实施预算，首先定义插入供水管网中流
量计的总数量nfm＝k，其中，k为设定的dma分区数量，也就是说这里限制遗传算法的一组二元染色体序列i中仅存在k个1，其余位置为0；(2)目标函数为最大化供水管网节点耗散功率p，故遗传算法的适应度函数f被定义为目标函数的倒数：其中，γ是水的比重，r
i(3)
,h
i
,q
i
分别表示供水管网的边界管段集合上布置阀门与流量计后第i个节点的高程、压力以及需水量数据；(3)初始化遗传算法种群规模c、交叉概率p
cro
、变异概率p
het
，并设定算法终止条件：最大遗传代数j、收敛阈值t
thr
；同时，遗传算法输出的最优解还需要满足节点压力约束条件如下：h
min
≤h
i
≤h
max
其中，h
min
为节点最小服务水压，h
max
为节点最高允许水压，h
i
为当前解对应的阀门与流量计布置方案下供水管网水力运行得到的各节点压力数据；(4)流量计及阀门布置问题优化布置流程如下：a、初始化种群，随机生成c个二元染色体序列i，即生成c个个体作为初始父代种群；b、调用epanet工具箱生成某个体编码序列对应布置方案下的dma分区结果并进行水力分析，获取当前dma分区下节点的高程[r
1(3)
,r
2(3)
,...,r
n(3)
]、需水量[q1,q2,...,q
n
]和压力[h1,h2,...,h
n
]数据，通过适应度函数f计算得到该个体的适应度值；依次计算父代种群c个个体适应度值，并判断是否满足算法终止条件，若不满足，则跳转至c；若满足，则跳转至d；c、根据父代种群c个个体适应度函数值的大小，选择出个体进行交叉、变异操作生成子代，并将生成的子代种群作为父代种群，返回至b，进行下一代进化；d、若算法运行输出的当前解不满足节点压力约束条件，则令布置的流量计数量增加一个，即nfm＝nfm+1，在改变遗传算法染色体编码形式之后返回至s2重新计算新增流量计数量下的最优解；若本次算法运行得到的结果符合节点压力约束条件或达到最大迭代次数nec—nfm时停止计算，输出最优个体并得到对应边界管段集合中流量计和阀门的最佳布置方式，最终完成dma规划。

技术总结
一种基于改进谱聚类及遗传算法的供水管网独立计量分区方法，属于城市供水管网设计技术领域，解决如何采用改进谱聚类及遗传算法对供水管网DMA分区进行优化的问题；本发明结合供水管网拓扑结构信息和运行状况信息，采用来提升相似度图的质量，采用改进谱聚类对任意形状的样本空间进行最优划分，得到水力性能影响最小的分区布局；采用遗传算法解决流量计及阀门的布置问题，并通过设定最小化流量计数量可以得到经济性最优情况下的布置方案；经过验证，DMA分区后的供水管网在边界管段的数量以及需水量均匀性等指标上有大幅提升。及需水量均匀性等指标上有大幅提升。及需水量均匀性等指标上有大幅提升。


技术研发人员：谢陈磊 赵红宇 方潜生 蒋婷婷 汪明月 杨亚龙 李善寿 朱徐来 张睿 陈涛 苏亮亮 张公泉 陈杰 田政 冯择优 杨雪雷
受保护的技术使用者：安徽建筑大学
技术研发日：2023.05.04
技术公布日：2023/8/4