基于分布式遗传算法的水质传感器布置优化研究

Water quality sensor placement optimization based on distributed genetic algorithm

水质传感器优化布置是指在城镇配水管网中最优位置布置水质传感器对污染物进行检测,从而达到监测预警的目的,其本质是一类大规模离散组合优化问题。首先从数学上对该问题进行分析,论证了其具有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.