专利摘要

本发明涉及一种基于分解多目标进化算法的选址优化方法，用于供水管网污染监测点的选址，所述基于分解多目标进化算法的选址优化方法将一个多目标优化问题分解成一定数量的子多目标优化问题，并规定每个所述子多目标优化问题有其固定的种群个体数，用多目标进化算法同时求解所述子多目标问题。以MOEA/D‑CRA为算法框架，在初始化范围内对所述种群和子区域及选择算子进行初始化，再在目标函数内进行子区域个体选择，比较当前代数和指定代数从而产生新的个体，最后使用选择策略将个体组成外部集合，计算子问题贡献度。通过对所有分解子问题动态分配计算资源的优化策略的改进，更有效的选取供水管网的监测地址，且在保证精度的前提下提升了算法的收敛速度。

权利要求

1.一种基于分解多目标进化算法的选址优化方法，用于供水管网污染监测点的选址，其特征在于：所述基于多目标进化算法的优化方法将一个多目标优化问题分解成一定数量的子多目标优化问题，并规定每个所述子多目标优化问题有其固定的种群个体数，用多目标进化算法同时求解所述子多目标问题，所述基于多目标进化算法的优化方法包括以下步骤：

S1：在初始化范围内，对种群、子区域及选择算子进行初始化；

S2：分解所述种群，在目标函数空间内进行子区域个体选择，在所述目标函数空间内选择K个单位向量，根据所述K个单位向量分为K个子区域，所述子区域Ωk(k＝1,2，...，k)定义为：

其中，<u，vj>表示向量u和vj之间的锐角；

S3：指定多目标进化算法更新所述子区域的选择算子的学习代数即累计代数为L，比较当前代数和指定代数L并采用遗传算法或差分进化算法产生新的种群个体；

S4：使用选择策略选出所述个体组成外部集合；

S5：统计所述外部集合中的所述个体分别属于哪一个所述子区域；

S6：计算每个所述子区域的贡献度；

S7：当各个所述子区域计算贡献度的累计代数达到预先设定的代数或达到最大循环迭代次数则结束，否则用所述当前代数除以所述指定代数L，若能整除，则更新每个所述子区域的选择算子并返回步骤S2，反之直接返回步骤S2。

2.如权利要求1所述的一种基于分解多目标进化算法的选址优化方法，其特征在于：所述目标函数包含监测时间Z1、被感染的居民人数Z2、居民已使用的污染水量Z3及监测概率Z4。

3.如权利要求1所述的一种基于分解多目标进化算法的选址优化方法，其特征在于：对于某个所述子区域k，在其第g代的贡献解的总个数可表示为λk,g，则贡献度C定义为：

Ck,g＝(1+Δ)Ck,g-1

其中，分母中的W为正实数，大于所述种群个体数。

4.如权利要求1所述的一种基于分解多目标进化算法的选址优化方法，其特征在于：所述步骤S2具体如下：

若所述当前代数小于所述指定代数L，则对每个所述子区域应用遗传进化算子产生新的个体；反之，则根据所述选择算子选择所述子区域产生新的个体。

5.如权利要求1所述的一种基于分解多目标进化算法的选址优化方法，其特征在于：在所述步骤S4中，所述“选择策略”为NSGA-II算法。

说明书

技术领域

本发明涉及一种基于分解多目标进化算法的选址优化方法，用于供水管网污染监测点的选址，属于群体智能优化领域。

背景技术

城市供水管网监测系统适用于供水企业远程监测供水管网，工作人员可以在水司调度中心远程监测全市供水管网的压力及流量情况。中国城市的供水管网为几亿的居民们提供日常用水，饮用水一旦发生污染，若没有及时发现，就会对居民、对经济、对社会造成巨大的危害。因此，需要建立一个完善的供水管网监测系统，以应对各种可能发生的污染事件，能够在第一时间进行预警，尽可能地减少人员伤亡以及经济损失。在监测系统中，对监测点的选择是一个重要的课题，对于不同的供水网络，具有不同的监测目标，甚至一个网络中的不同区域，也会有不同的需求。

发明内容

本发明的目的在于提供一种基于分解多目标进化算法的选址优化方法，通过对所有分解子问题动态分配计算资源的优化策略的改进，更有效的选取供水管网的监测地址，且在保证精度的前提下提升了算法的收敛速度。

为达到上述目的，本发明提供如下技术方案：一种基于分解多目标进化算法的选址优化方法，用于供水管网污染监测点的选址，所述基于分解多目标进化算法的选址优化方法将一个多目标优化问题分解成一定数量的子多目标优化问题，并规定每个所述子多目标优化问题有其固定的种群个体数，用多目标进化算法同时求解所述子多目标问题，所述基于分解多目标进化算法的选址优化方法包括以下步骤：

S1：在初始化范围内，对种群、子区域及选择算子进行初始化；

S2：分解所述种群，在目标函数空间内进行子区域个体选择；

S3：指定多目标进化算法更新所述子区域的选择算子的学习代数即累计代数为L，比较当前代数和指定代数L并采用遗传算法或差分进化算法产生新的种群个体。

S4：使用选择策略选出所述个体组成外部集合；

S5：统计所述外部集合中的所述个体分别属于哪一个所述子区域；

S6：计算每个所述子区域的贡献度；

S7：当各个所述子区域计算贡献度的累计代数达到预先设定的代数或达到最大循环迭代次数则结束，否则用所述当前代数除以所述指定代数L，若能整除，则更新每个所述子区域的选择算子并返回步骤S2，反之直接返回步骤S2。

进一步的，所述目标函数包含监测时间Z1、被感染的居民人数Z2、居民已使用的污染水量Z3及监测概率Z4。

进一步的，在所述目标函数空间内选择K个单位向量，根据所述K个单位向量分为K个子区域，所述子区域Ωk(k＝1，2，...，k)定义为：

其中，<u，vj>表示向量u和vj之间的锐角。

进一步的，对于某个所述子区域k，在其第g代的贡献解的总个数可表示为λk，g，则贡献度C定义为：

Ck，g＝(1+Δ)Ck，g-1

其中，所述分母中的W为正实数，大于所述种群个体数。

进一步的，所述步骤S2具体如下：

若所述当前代数小于所述指定代数L，则对每个所述子区域应用遗传进化算法产生新的个体；反之，则根据所述选择算子选择所述子区域产生新的个体。

进一步的，在所述步骤S4中，所述“选择策略”为NSGA-II算法。

本发明的有益效果在于：本发明的一种基于分解多目标进化算法的选址优化方法对多个分解子问题动态分配计算资源的优化策略有所改进，增加分解子问题之间的信息交流，在保证算法精度的前提下提升算法的收敛速度；

以目标函数作为评判全局标准，更为有效的选取供水管网的监测点，满足工程需求。

上述说明仅是本发明技术方案的概述，为了能够更清楚了解本发明的技术手段，并可依照说明书的内容予以实施，以下以本发明的较佳实施例并配合附图详细说明如后。

附图说明

图1为本发明采用的算法框架。

图2为本发明的基于分解多目标进化算法的选址优化方法的流程图。

图3为图2中的目标函数得到的监测点分布图。

具体实施方式

下面结合附图和实施例，对本发明的具体实施方式作进一步详细描述。以下实施例用于说明本发明，但不用来限制本发明的范围。

请参见图1，本发明的一种基于分解多目标进化算法的选址优化方法的一较佳实施例采用算法框架MOEA/D-CRA，先进行多目标优化问题分解，分解的子问题产生新的种群个体，然后再用遗传算法选出优秀解生成外部集合，计算子问题的贡献度，根据各个子问题的贡献度选择进行遗传进化的子问题。

再结合图2，本发明的一种基于分解多目标进化算法的选址优化方法的具体步骤如下：

S1：在初始化范围内，对种群、子区域及选择算子进行初始化。

S2：分解所述种群，在目标函数空间内进行子区域个体选择。该目标函数包含监测时间Z1、被感染的居民人数Z2、居民已使用的污染水量Z3及监测概率Z4。

S21：监测时间(Z1)：

对于一个特定的污染物时间，传感器的监测时间为从污染物注入的时刻开始，到监测点监测到污染物(污染物浓度大于0)的时间间隔。定义ti为第i个监测点的监测时间，则在此污染事件中，所有的监测点的最小的监测时间为td＝mini(ti)。因此检测时间Z1(即目标函数Z1)为：

Z1＝E(td)

其中，E(*)表示左右随机事件的数学期望。

S22：被感染的居民人数(Z2)

对于一个特定的污染物事件，感染的人数与摄入的污染物浓度有关，而摄入的污染物浓度与监测时间有关。这里需做一个假设，即从监测到污染物的时刻开始，不再有污染物被人体摄入。因此，对于特定的污染物事件，每个节点的用户在监测到事件之前摄入的污染物浓度如下：

其中， 为平均摄取速率(Liters/day),Δt为仿真时间间隔(days)，cik，ρik分别是节点i在第t个时间步长的污染物浓度(mg/Liter)和剂量乘子，N是监测到事件之前的时间步长总数。ρik用来模拟一天之内的污染物摄入速率，因此 其中qik是节点i在第k个时间步长的需水量， 是节点i的平均需水量。

可用以下模型来表示人在摄入Mi的污染物之后被感染的概率：

Ri＝Φ[βlog10((Mi/W)/D50)]

其中Ri在[0,1]区间，β为一个无单位的乘子，W是人的体重(kg)，D50是可使50％的人染病的剂量(mg/kg)，Φ指标准正态累积分布。

因此，对于一个特定的污染物事件，被感染的人数：

其中Pi是节点i的人口，m是节点总数。因此，对于所有的随机事件，感染的人数为：

Z2＝E(Pa)

S23：居民已使用的污染水量(Z3)

Z3表示在监测到事件之前被用户使用的污水的体积：

Z3＝E(Vd)

Vd表示当污染物浓度大于一个给定的阈值C时用户的需水量体积。这里也需要做一个假设，即在监测到事件之后立即停水。

S24：监测概率(Z4)

给定监测点选址(监测点的数量和位置)，监测概率定义为：

其中，di＝1表示第i个随机事件能够被监测到，反之亦然。N是所有随机事件的总数。

S3：指定多目标进化算法更新所述子区域的选择算子的学习代数即累计代数为L，比较当前代数和指定代数L并采用遗传算法产生新的种群个体。即若所述当前代数小于所述指定代数L，则对每个子区域应用遗传进化算子产生新的个体；反之，则根据所述选择算子选择所述子区域产生新的个体。

在本实施例中，产生新的种群个体采用遗传算法，但在其他的实施例中，也可以采用差分进化算法等算法来产生新的种群个体。

S4：在上述目标函数空间内选择K个单位向量，根据所述K个单位向量分为K个子区域，所述子区域Ωk(k＝1，2，...，k)定义为：

其中，<u，vj>表示向量u和vj之间的锐角。

使用选择策略NSGA-II算法选出所述个体组成外部集合。

S5：统计所述外部集合中的所述个体分别属于哪一个所述子区域。

S6：计算每个所述子区域的贡献度。对于某个所述子区域k，在其第g代的贡献解的总个数可表示为λk，g，则贡献度C定义为：

Ck，g＝(1+Δ)Ck，g-1

其中，分子表示子问题产生贡献解的潜力，分母表示子问题在当代产生贡献解的能力。分母W为一个正实数，大于种群个数体。

S7：如果达到预先设定的代数或达到最大循环迭代次数则结束，否则用所述当前代数除以所述指定代数L，若能整除，则更新每个所述子区域的选择算子并返回步骤S2，反之直接返回步骤S2。

在本实施例中，采用BWSN竞赛126个节点的复杂网络为研究对象，并采用群体只能优化算法对这四个监测目标进行优化分解，需要对决策变量进行编码。即X＝{x1，...，xN}，其中xi，i∈{1，...，N}的取值为0或1，N为管网的节点总数。当xi＝1时表示第i个节点为监测点，∑X＝5。

分别使用MOEA/D-CRA、MOEA/D-M2M以及NSGA-II三种多目标进化算法对模型的4个目标进行两两优化求解，选取了9个代表性的解，其结果在表格1中给出。由表中数据可知，本发明方法具有较好的效果。

表格1

从中选取编号为2的解对监测点进行布置，布置点由表格2给出。

算法监测点位置(管网节点编号)NSGA-II117,71,98,68,82MOEA/D-M2M19,32,82,86,99MOEA/D-CRA9,117,114,101,75

表格2

上述的监测点的布置位置如图3所示。由图可知，三种算法对于监测点的选址有一定的相似性，大部分都处在同一个区域，且有个别监测点位置重合，说明本发明方法有效。

综上所述：本发明的一种基于分解多目标进化算法的选址优化方法对多个分解子问题动态分配计算资源的优化策略有所改进，增加分解子问题之间的信息交流，在保证算法精度的前提下提升算法的收敛速度；

以目标函数作为评判全局标准，更为有效的选取供水管网的监测点，满足工程需求。

以上所述实施例的各技术特征可以进行任意的组合，为使描述简洁，未对上述实施例中的各个技术特征所有可能的组合都进行描述，然而，只要这些技术特征的组合不存在矛盾，都应当认为是本说明书记载的范围。

以上所述实施例仅表达了本发明的几种实施方式，其描述较为具体和详细，但并不能因此而理解为对发明专利范围的限制。应当指出的是，对于本领域的普通技术人员来说，在不脱离本发明构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附权利要求为准。

一种基于分解多目标进化算法的选址优化方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。