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

作     者：李伟东 蓝欢 刘晓非 LI Weidong;LAN Huan;LIU Xiaofei

作者机构：云南大学数学与统计学院云南昆明650504 云南大学信息学院云南昆明650504 

基　　金：国家自然科学基金资助项目(12071417) 云南省基础研究专项(202301AU070197) 

出 版 物：《华中科技大学学报（自然科学版）》 (Journal of Huazhong University of Science and Technology(Natural Science Edition))

年 卷 期：2024年第52卷第2期

页      码：36-41页

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

主 题 词：圆盘覆盖问题 能量受限 贪婪算法 进化算法 近似比 

学科分类：12[管理学] 1201[管理学-管理科学与工程类] 07[理学] 070105[070105] 0701[理学-数学类] 

核心收录：

D　O　I：10.13245/j.hust.240207

馆 藏 号：203125519...