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

计算机工程与科学

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

李进生，蒙江，童名文

（华中师范大学教育信息技术学院,湖北武汉 430079）

收稿日期:2018-03-26 修回日期:2018-06-20 出版日期:2019-03-25 发布日期:2019-03-25
基金资助:
教育部人文社科基金（15YJA880062）

Water quality sensor placement optimization

based on distributed genetic algorithm

LI Jinsheng,MENG Jiang,TONG Mingwen

（School of Educational Information Technology,Central China Normal University,Wuhan 430079,China）

Received:2018-03-26 Revised:2018-06-20 Online:2019-03-25 Published:2019-03-25

摘要/Abstract

摘要：

水质传感器优化布置是指在城镇配水管网中最优位置布置水质传感器对污染物进行检测，从而达到监测预警的目的，其本质是一类大规模离散组合优化问题。
首先从数学上对该问题进行分析，论证了其具有NPComplete特性；然后针对该问题计算开销大等特点，提出了基于Spark云计算模型的分布式遗传算法；最后以一个典型的复杂配水管网为对象进行实验，仿真结果表明，所提出的算法不仅具有搜索速度快、精度高等优点，而且还具有较好的线性加速比。

关键词: 分布式遗传算法, 水质传感器布置, 云计算, 大规模离散组合优化

Abstract:

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.

Key words: distributed genetic algorithm, water quality sensor placement, cloud computing, large-scale discrete combination optimization

李进生，蒙江，童名文. 基于分布式遗传算法的水质传感器布置优化研究[J]. 计算机工程与科学.

LI Jinsheng,MENG Jiang,TONG Mingwen.

Water quality sensor placement optimization

based on distributed genetic algorithm

[J]. Computer Engineering & Science.

[1]	李卫平1,2，武海燕2，杨杰1. 基于效益博弈的云计算资源动态可协调分配策略研究[J]. J4, 20160101, 38(01): 57-61.
[2]	徐嘉, 张骥先, 王喆民, 刘林杰. 基于NUMA云计算架构的多资源分配可信拍卖机制[J]. 计算机工程与科学, 2024, 46(05): 761-775.
[3]	马柯帆, 李宝峰, 周悦锦, 武园园, 余永兰, 多瑞华. 基于ZYNQ 芯片的基板管理控制器设计与实现[J]. 计算机工程与科学, 2024, 46(02): 217-223.
[4]	杨柏蔼, 赵山, 刘芳. 无服务器计算技术研究综述[J]. 计算机工程与科学, 2022, 44(04): 611-619.
[5]	李波, 侯鹏, 牛力, 武浩, 丁洪伟. 基于软件定义网络的云边协同架构研究综述[J]. 计算机工程与科学, 2021, 43(02): 242-257.
[6]	廖建锦, 孙庆骁, 杨海龙, 栾钟治, 钱德沛. 满足工作流执行时限的可抢占虚拟机实例配置和调度方法研究[J]. 计算机工程与科学, 2020, 42(11): 1956-1964.
[7]	林涛, 冯竞凯, 郝章肖, 黄少群. 基于组合预测模型的云计算资源负载预测研究[J]. 计算机工程与科学, 2020, 42(07): 1168-1173.
[8]	史文杰，詹雨奇，李奎. 一种面向多平台航电资源建模及其调度算法[J]. 计算机工程与科学, 2019, 41(11): 1976-1984.
[9]	刘梓璇，周建涛. 负载均衡的主导资源公平分配算法[J]. 计算机工程与科学, 2019, 41(09): 1574-1580.
[10]	曹云梦1,2,周胜军3,刘晨1,2,韩燕波1,2. 面向服务的云-端动态协作方法[J]. 计算机工程与科学, 2019, 41(04): 598-605.
[11]	罗裕春,武继刚,史雯隽,贺子楠. 移动云计算中的任务调度与计算迁移算法[J]. 计算机工程与科学, 2018, 40(11): 1915-1924.
[12]	齐平1,2,王福成1,王必晴1,梁昌勇2. 云计算环境下基于可靠性感知的任务调度算法[J]. 计算机工程与科学, 2018, 40(11): 1925-1935.
[13]	付伟1，李墨泚2，赵华容2，吴勇2. CRSHE：基于同态加密的新型密文检索方案[J]. 计算机工程与科学, 2018, 40(09): 1540-1545.
[14]	何丽,汤莉. 基于Kalman滤波的云数据中心能耗和性能优化[J]. 计算机工程与科学, 2018, 40(07): 1165-1172.
[15]	童钊1,2，陈洪剑1,2，陈明1,2，梅晶1,2，刘宏1,2. 一种云环境下基于混合型BBO的任务调度算法[J]. 计算机工程与科学, 2018, 40(05): 765-772.