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

Effectively Restricted Neighborhood Structure Based Tabu Searchfor the Budgeted Maximum Coverage Problem

作　　者：刘雅文 潘大志[1,2] 池莹[1] LIU Yawen;PAN Dazhi;CHI Ying(School of Mathematics and Information,China West Normal University,Nanchong 637009,China;Sichuan Colleges and Universities Key Laboratory of Optimization Theory and Applications,China West Normal University,Nanchong 637009,China)

机构地区：[1]西华师范大学数学与信息学院,四川南充637009 [2]西华师范大学最优化理论与应用四川省高校重点实验室,四川南充637009

出　　处：《运筹与管理》2024年第7期72-78,共7页Operations Research and Management Science

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

摘　　要：针对预算最大覆盖问题,设计出一种基于有效限制邻域结构的禁忌搜索算法(Effectively Restricted Neighborhood Structure Based Tabu Search,ERNSBTS)对其求解。该算法主要由动态初始化、基于策略限制邻域结构和动态随机扰动重新初始化三部分组成。首先,提出构建剩余利润和剩余价值密度来生成好的初始解。然后,引入计数器G来记录当前解下元素覆盖次数,设计相对置空率和相对增益率两种策略来得到最有期望子集来限制邻域结构。最后,设计扰动程序,将贪婪与启发式思想相结合,考虑全局和局部的凸组合,以增加初始解的多样性。在数值实验中,分析了ERNSBTS算法参数设置,同时将其与近似算法、PLTS和VDLS算法的结果进行比较分析,证实了ERNSBTS算法在求解质量、计算效率和鲁棒性方面的高竞争力。The Budgeted Maximum Coverage Problem(BMCP)(aka the knapsack maximum coverage problem)is a natural and more practical extension of the standard 0-1 knapsack problem and the set cover problem,and is also highly related to the set-union knapsack problem.Give n elements with non-negative profits,a set of m items,each item is a subset of the set of elements and each of them has a non-negative cost,and given a budget,BMCP aims to select some subsets such that the total cost of selected subsets does not exceed the budget,and the total profits of covered elements is maximized.It has a broad range of applications in real life,such as project allocation,financial decisions,worker employment,software installation packages,service operation providers,etc.BMCP,as an NP-complete problem highly related to SUKP,is difficult to solve,and relatively few studies have been conducted on the heuristic or meta-heuristic aspects of the standard BMCP.Therefore,it is of great importance to study this problem.In this paper,we propose a more efficient heuristic algorithm for solving the BMCP and improve the relative stability of the solutions in the existing literature,providing more options for solving such problems.We propose an effective restricted neighborhood structure based tabu search algorithm(ERNSBTS)for the BMCP.The algorithm mainly consists of three parts:dynamic initialization,limiting the neighborhood structure based on relative empty rate and relative gain rate,and re-initializing dynamic random disturbance.First,since the tabu search has a strong dependence on the initial solution,it is proposed to construct the residual profit and residual value density to generate the initial solution.Then,a counter G is introduced to record the times of element coverage under the current solution,and two strategies are designed to expect the most promising subset to restrict the neighborhood structure.After that,greed is combined with heuristic ideas to design a perturbation procedure to take into account convex combinations of global and

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]