华中科技大学学报（自然科学版）2024，Vol.52Issue(2)：36-41,6.DOI:10.13245/j.hust.240207
一种求解能量受限的最大圆盘覆盖问题的进化算法
An evolutionary algorithm for energy-constrained maximum power cover problem
摘要
Abstract
Facing large-scale multi-data monitoring tasks,limited energy will become the bottleneck.This problem is abstracted into the energy-budgeted maximum disk coverage problem,where the objective is to determines an energy assignment maximizing the total benefit of the covered users when the total energy is limited.A(1/2)(1-1/e)-approximation algorithm was designed based on the greedy strategy.An evolutionary algorithm was further designed based on constructing a reasonable surrogate function.It is proved that the evolutionary algorithm achieves the same approximation guarantee in polynomial expected running time.The experimental results show the excellent performance of the evolutionary algorithm,which the objective value of the output solution is almost the same as the optimal value.关键词
圆盘覆盖问题/能量受限/贪婪算法/进化算法/近似比Key words
disk coverage problem/energy-constrained/greedy algorithm/evolutionary algorithm/approximation factor分类
数理科学引用本文复制引用
李伟东,蓝欢,刘晓非..一种求解能量受限的最大圆盘覆盖问题的进化算法[J].华中科技大学学报（自然科学版）,2024,52(2):36-41,6.基金项目
国家自然科学基金资助项目(12071417) （12071417）
云南省基础研究专项(202301AU070197). （202301AU070197）
