一种求解能量受限的最大圆盘覆盖问题的进化算法

An evolutionary algorithm for energy-constrained maximum power cover problem

面对大规模多数据监测任务,有限的能量将成为无线传感器的瓶颈,本文将该问题抽象为能量受限的最大圆盘覆盖问题.即试图寻找一种能量分配方案,使得在总能量受限的情况下,传感器网络覆盖的用户收益之和最大.基于贪婪策略,设计了一个多项式时间(1/2)(1-1/e)-近似算法;进一步通过构造一个合理的代理函数,设计了一个分组进化算法,并证明在期望多项式时间内,该算法具有相同近似比.实验结果表明,分组进化算法输出解的目标函数值与最优值几乎相同.

ed 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.