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

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.