一种求解能量受限的最大圆盘覆盖问题的进化算法OA北大核心CSTPCD
An evolutionary algorithm for energy-constrained maximum power cover problem
面对大规模多数据监测任务,有限的能量将成为无线传感器的瓶颈,本文将该问题抽象为能量受限的最大圆盘覆盖问题.即试图寻找一种能量分配方案,使得在总能量受限的情况下,传感器网络覆盖的用户收益之和最大.基于贪婪策略,设计了一个多项式时间(1/2)(1-1/e)-近似算法;进一步通过构造一个合理的代理函数,设计了一个分组进化算法,并证明在期望多项式时间内,该算法具有相同近似比.实验结果表明,分组进化算法输出解的目标函数值与最优值几乎相同.
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…查看全部>>
李伟东;蓝欢;刘晓非
云南大学数学与统计学院,云南 昆明 650504云南大学数学与统计学院,云南 昆明 650504云南大学信息学院,云南 昆明 650504
数学
圆盘覆盖问题能量受限贪婪算法进化算法近似比
disk coverage problemenergy-constrainedgreedy algorithmevolutionary algorithmapproximation factor
《华中科技大学学报（自然科学版）》 2024 (2)
36-41,6
国家自然科学基金资助项目(12071417)云南省基础研究专项(202301AU070197).
评论