云环境下基于Memetic框架的水质传感器大规模优化布置方法研究

In recent years, water pollution incidents happen frequently, which have caused serious disasters and loss to the society. Through arranging sensors of monitoring water quality for water supply networks to realize the real-time monitoring of drinking water in the municipal water supply network, we can effectively prevent and reduce the safety risk. So the problem of sensor allocation optimization of water supply network is not only a NP-Hard coverage optimization problem, but also a large-scale, high dimensional optimization problem. The optimal sensor placement is very difficult to provide for detecting all of the popution event. Our project aims to consider the sensor optimization placement of the large-scale water supply network. By combining the characteristics of set covering and maximum covering model, we will set up the optimization model of the optimal layout to monitor all pollution incidents with the least sensors. We propose the large-scale optimization algorithm under the framework of memetic, using global search and local search algorithms through knowledge rules guide, so that the algorithm has faster convergence speed and precision. We will study the Map-Reduce programming model under the cloud platform, and modify its adaptability, thus improving the speed ratio of the advanced algorithm. Through the research of our project, it is expected to construct the basic theoretical framework of large scale optimization problem of high dimension and distributed processing mode in theory. We will explore the evolutionary mechanism of the memetic algorithm guided by expert knowledge or rules, and provide practical optimization placement of water quality monitors for the municipal engineering management departments and the others.

近些年，突发性水污染事件频频发生，给社会造成了巨大经济损失，通过在城镇给水管网中布置水质传感器对饮用水实时监测，可有效预警和降低安全风险。大规模给水管网传感器布置优化问题不仅是一个NP-Hard覆盖优化问题，也是一个高维大规模优化问题，目前尚未找覆盖管网全部节点的有效布置优化方法。本项目拟针对大规模给水管网传感器布置优化模型进行研究，建立能监测节点全部污染事件的最少传感器数目及最优布局的优化模型；研究Memetic框架下大规模优化算法，利用专家知识规则对算法的个体局部搜索进行引导，从而使算法具有更快的收敛速度和求解精度；研究云平台下的MapReduce编程模型，并对其适应性修改，提高算法加速比。通过本项目研究，可望在理论上建构求解高维大规模优化问题的基础理论框架及云环境下求解模式，探索Memetic算法基于专家知识规则引导的进化机制；在实践上为市政工程及其它部门提供水质监测点优化选址方案。

在城镇给水管网中布置水质传感器可有效预警和降低安全风险，本项目主要关注给水管网中传感器布置的原理、优化模型和算法。在本项目中，主要完成的研究工作有（1）利用控制理论、矩阵理论对配水系统进行分析，建立了配水系统状态方程，从原理层面分析配水系统中传感器布置和污染源定位的相关因素，并利用线性系统可控性理论，给出传感器布置的个数和大致位置。（2）以中等规模管网为研究对象，建立了静态传感器布置优化模型，提出了Memetic框架下多粒子群协同优化算法，在仿真中与遗传算法、粒子群算法比较，其结果显示多粒子群协同算法在搜索精度和速度方面具有一定的优越性。（3）针对大规模给水管网优化的时间复杂度较高的问题，提出了基于Spark的并行遗传算法（SGA，Spark-based Genetic Algorithm），在实验仿真，与基于MapReduce的并行遗传算法（MGA, MapReduce-based Genetic Algorithm）相比较，显示了所提出的算法在速度和扩展性方面具有较大的提升。（4）当获取水质传感器检测到的污染物信息后，首要的任务是反向定位到污染源。 我们从理论上证明了污染源定位问题是一个多峰函数优化问题，然后建立了污染源定位的优化模型，提出了一种基于Spark计算模型的改进遗传小生境优化方法，通过实验仿真证明了所提出得优化模型及方法的有效性。基于以上研究，项目组共发表学术论文28篇，其中期刊论文18篇，会议论文10篇，包括CCF A类论文2篇，C类论文5篇，共获得国家发明专利4项。. 城镇给水管网中水质传感器的布置问题是一个典型的高维组合优化问题，通过该项目的研究，我们探索了求解高维组合优化算法的原理和方法，研究了基于云计算的演化算法实现架构，使其可以求解计算密集、数据密集型优化问题。