基于有效限制邻域结构的禁忌搜索求解预算最大覆盖问题

作     者：刘雅文 潘大志 池莹 LIU Yawen;PAN Dazhi;CHI Ying

作者机构：西华师范大学数学与信息学院四川南充637009 西华师范大学最优化理论与应用四川省高校重点实验室四川南充637009 

基　　金：国家自然科学基金资助项目(11871059) 四川省教育厅自然科学基金项目(18ZA0469) 西华师范大学英才科研基金项目(17YC385) 西华师范大学大学生创新创业训练项目(cxcy2022023) 

出 版 物：《运筹与管理》 (Operations Research and Management Science)

年 卷 期：2024年第33卷第7期

页      码：72-78页

摘      要：针对预算最大覆盖问题,设计出一种基于有效限制邻域结构的禁忌搜索算法(Effectively Restricted Neighborhood Structure Based Tabu Search,ERNSBTS)对其求解。该算法主要由动态初始化、基于策略限制邻域结构和动态随机扰动重新初始化三部分组成。首先,提出构建剩余利润和剩余价值密度来生成好的初始解。然后,引入计数器G来记录当前解下元素覆盖次数,设计相对置空率和相对增益率两种策略来得到最有期望子集来限制邻域结构。最后,设计扰动程序,将贪婪与启发式思想相结合,考虑全局和局部的凸组合,以增加初始解的多样性。在数值实验中,分析了ERNSBTS算法参数设置,同时将其与近似算法、PLTS和VDLS算法的结果进行比较分析,证实了ERNSBTS算法在求解质量、计算效率和鲁棒性方面的高竞争力。

主 题 词：大覆盖问题 相对置空率 相对增益率 有效限制邻域结构 禁忌搜索 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.12005/orms.2024.0218

馆 藏 号：203138952...