| 摘要: |
| 最小弱连通支配集问题是一个经典的NP难问题, 在许多领域都有广泛的应用. 提出一种高效的局部搜索算法求解该问题. 在该算法中, 首先采用一个基于锁定顶点和频率反馈信息的初始解构造方法. 该方法可以确保将一定处于最优解中的顶点和大概率存在于最优解中的顶点添加到初始解中, 从而可以得到高质量的初始解. 其次, 提出基于双层格局检测策略, 年龄属性和禁忌策略的方法来避免循环问题. 第三, 提出扰动策略, 使得算法能够有效跳出局部最优. 第四, 将两个评分函数Dscore和Nscore与避免循环问题的策略相结合, 提出有效的顶点选择方法, 帮助算法选择适合添加到候选解中或从当前候选解中删除的顶点. 最后, 与现有的最优启发式算法和CPELX求解器, 在4组基准测试实例上对提出的局部搜索算法进行了对比. 实验结果表明, 该算法在4组经典基准测试实例上表现出更好的性能. |
| 关键词: 最小弱连通支配集问题 组合优化 局部搜索 反馈机制 扰动策略 年龄属性 |
| DOI：10.13328/j.cnki.jos.007234 |
| 分类号: |
| 基金项目:吉林省科技厅自然科学基金(YDZJ202201ZYTS413); 吉林省教育厅重点基金(JJKH20240201KJ) |
|
| Local Search Algorithm for Minimum Weakly Connected Dominating Set Problem |
|
LI Rui-Zhi1,2, HE Jin-Tao1, OUYANG Dan-Tong3
|
|
1.School of Management Science and Information Engineering, Jilin University of Finance and Economics, Changchun 130117, China;2.Jilin Province Business Big Data Research Center, Changchun 130117, China;3.College of Computer Science and Technology, Jilin University, Changchun 130012, China
|
| Abstract: |
| The minimum weakly connected dominating set problem is a classic NP-hard problem that has wide applications in various fields. This study proposes an efficient local search algorithm to solve this problem. The algorithm employs a method to construct an initial solution based on locked vertices and frequency feedback. This method ensures the inclusion of vertices that are certain or highly likely to be in the optimal solution, resulting in a high-quality initial solution. Furthermore, the study introduces a method to avoid cycling based on two-hop configuration checking, age properties, and tabu strategies. A perturbation strategy is also proposed to enable the algorithm to effectively escape from the local optimum. Additionally, effective vertex selection methods are presented to assist the algorithm in choosing vertices suitable for addition to or removal from the candidate solution by combining two scoring functions, Dscore and Nscore, with strategies for avoiding cycling. Finally, the proposed local search algorithm is evaluated on four benchmark test instances and compared with four state-of-the-art algorithms and the CPELX solver. Experimental results demonstrate that the proposed algorithm achieves better performance. |
| Key words: minimum weakly connected dominating set problem combinatorial optimization local search feedback mechanism perturbation strategy age property |
