基于分布式遗传算法的水质传感器布置优化研究
|
摘要
水质传感器优化布置是指在城镇配水管网中最优位置布置水质传感器对污染物进行检测,从而达到监测预警的目的,其本质是一类大规模离散组合优化问题。首先从数学上对该问题进行分析,论证了其具有NP-Complete特性;然后针对该问题计算开销大等特点,提出了基于Spark云计算模型的分布式遗传算法;最后以一个典型的复杂配水管网为对象进行实验,仿真结果表明,所提出的算法不仅具有搜索速度快、精度高等优点,而且还具有较好的线性加速比。
Water quality sensor placement optimization refers to deploying sensor networks at optimal locations in the water distribution system so as to detect the contaminant, thus monitoring and making early warning once pollution occurs. This problem is a large-scale discrete combination optimization problem in essence. We firstly analyze the problem from the perspective of mathematic theory, and prove that the problem is NP-complete. Secondly, aiming at the huge computation overhead, we propose a distributed genetic algorithm based on the Spark cloud computing model to solve the problem. Finally, experiments on a typical complex water distribution network show that the proposed algorithm has fast search speed with high accuracy, as well as a high linear speedup.
Water quality sensor placement optimization refers to deploying sensor networks at optimal locations in the water distribution system so as to detect the contaminant, thus monitoring and making early warning once pollution occurs. This problem is a large-scale discrete combination optimization problem in essence. We firstly analyze the problem from the perspective of mathematic theory, and prove that the problem is NP-complete. Secondly, aiming at the huge computation overhead, we propose a distributed genetic algorithm based on the Spark cloud computing model to solve the problem. Finally, experiments on a typical complex water distribution network show that the proposed algorithm has fast search speed with high accuracy, as well as a high linear speedup.
引文
[1] Ostfeld A, Uber J G, Salomons E, et al. The battle of the water sensor networks(BWSN):A design challenge for engineers and algorithms[J].Journal of Water Resources Planning and Management,2008,134(6):556-568.
[2] Hart W E,Murray R.Review of sensor placement strategies for contamination warning system in drinking water distribution systems[J].Journal of Water Resources Planning and Management,2010,136(6):611-619.
[3] Hu C Y, Li M, Zeng D Z, et al.A survey on sensor placement for contamination detection in water distribution systems[J].Wireless Networks,2018,24(2):647-661.
[4] Chang N B,Pongsanone N P,Ernest A.A rule-based decision support system for sensor deployment in small drinking water networks[J].Journal of Cleaner Production,2013,60(1):152-162.
[5] Chang N B,Pongsanone N P,Ernest A.Comparisons between a rule-based expert system and optimization models for sensor deployment in a small drinking water network[J].Expert System with Application,2011,38(8):10685-10695.
[6] Dorini G, Jonkergouw P, Kapelan Z, et al.SLOTS:Effective algorithm for sensor placement in water distribution systems[J].Journal of Water Resources Planning and Management,2010,136(6):620-628.
[7] Palleti V R, Narasimhan S, Rengaswamy R. Optimal sensor placement for contamination detection and identification in water distribution networks[J].Computer Aided Process Engineering,2014,33:1447-1452.
[8] Liu Shu-ming,Wang Huan-huan,Xu Peng,et al.Multiobjective genetic algorithms for optimal monitoring station placement in large water distribution systems[J].Journal of Tsinghua University(Science and Technology),2013,53(1):78-83.(in Chinese)
[9] Zhang Shi-qiao,Huang Ya-dong,Zhang Yun-xin.Optimal sensor placement in water distribution systems to detect accidental contaminants[J].Journal of Harbin Institute of Technology,2009,41(12):151-156.(in Chinese)
[10] Garey M R,Johnson D S.Computers and intractability:A guide to the theory of NP-completeness[M].New York:W.H.Freeman and Company,1979.
[8] 刘书明,王欢欢,徐鹏,等.多目标大规模供水管网监测点的优化选址[J].清华大学学报(自然科学版),2013,53(1):78-83.
[9] 张土乔,黄亚东,张运鑫.突发性污染情况下给水管网传感器优化选址[J].哈尔滨工业大学学报,2009,41(12):151-156.
[2] Hart W E,Murray R.Review of sensor placement strategies for contamination warning system in drinking water distribution systems[J].Journal of Water Resources Planning and Management,2010,136(6):611-619.
[3] Hu C Y, Li M, Zeng D Z, et al.A survey on sensor placement for contamination detection in water distribution systems[J].Wireless Networks,2018,24(2):647-661.
[4] Chang N B,Pongsanone N P,Ernest A.A rule-based decision support system for sensor deployment in small drinking water networks[J].Journal of Cleaner Production,2013,60(1):152-162.
[5] Chang N B,Pongsanone N P,Ernest A.Comparisons between a rule-based expert system and optimization models for sensor deployment in a small drinking water network[J].Expert System with Application,2011,38(8):10685-10695.
[6] Dorini G, Jonkergouw P, Kapelan Z, et al.SLOTS:Effective algorithm for sensor placement in water distribution systems[J].Journal of Water Resources Planning and Management,2010,136(6):620-628.
[7] Palleti V R, Narasimhan S, Rengaswamy R. Optimal sensor placement for contamination detection and identification in water distribution networks[J].Computer Aided Process Engineering,2014,33:1447-1452.
[8] Liu Shu-ming,Wang Huan-huan,Xu Peng,et al.Multiobjective genetic algorithms for optimal monitoring station placement in large water distribution systems[J].Journal of Tsinghua University(Science and Technology),2013,53(1):78-83.(in Chinese)
[9] Zhang Shi-qiao,Huang Ya-dong,Zhang Yun-xin.Optimal sensor placement in water distribution systems to detect accidental contaminants[J].Journal of Harbin Institute of Technology,2009,41(12):151-156.(in Chinese)
[10] Garey M R,Johnson D S.Computers and intractability:A guide to the theory of NP-completeness[M].New York:W.H.Freeman and Company,1979.
[8] 刘书明,王欢欢,徐鹏,等.多目标大规模供水管网监测点的优化选址[J].清华大学学报(自然科学版),2013,53(1):78-83.
[9] 张土乔,黄亚东,张运鑫.突发性污染情况下给水管网传感器优化选址[J].哈尔滨工业大学学报,2009,41(12):151-156.