Page 232 - 《软件学报》2025年第8期

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
2025,36(8):3655−3676 [doi: 10.13328/j.cnki.jos.007234] [CSTR: 32375.14.jos.007234] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563

*
局部搜索算法求解最小弱连通支配集问题

李睿智 1,3 , 何锦涛 1 , 欧阳丹彤 2

1
(吉林财经大学 管理科学与信息工程学院, 吉林 长春 130117)
2
(吉林大学 计算机科学与技术学院, 吉林 长春 130012)
3
(吉林省商务大数据研究中心, 吉林 长春 130117)
通信作者: 欧阳丹彤, E-mail: ouyd@jlu.edu.cn

摘 要: 最小弱连通支配集问题是一个经典的 NP 难问题, 在许多领域都有广泛的应用. 提出一种高效的局部搜索
算法求解该问题. 在该算法中, 首先采用一个基于锁定顶点和频率反馈信息的初始解构造方法. 该方法可以确保将
一定处于最优解中的顶点和大概率存在于最优解中的顶点添加到初始解中, 从而可以得到高质量的初始解. 其次,
提出基于双层格局检测策略, 年龄属性和禁忌策略的方法来避免循环问题. 第三, 提出扰动策略, 使得算法能够有
效跳出局部最优. 第四, 将两个评分函数 Dscore 和 Nscore 与避免循环问题的策略相结合, 提出有效的顶点选择方
法, 帮助算法选择适合添加到候选解中或从当前候选解中删除的顶点. 最后, 与现有的最优启发式算法和 CPELX
求解器, 在 4 组基准测试实例上对提出的局部搜索算法进行了对比. 实验结果表明, 该算法在 4 组经典基准测试实
例上表现出更好的性能.
关键词: 最小弱连通支配集问题; 组合优化; 局部搜索; 反馈机制; 扰动策略; 年龄属性
中图法分类号: TP301

中文引用格式: 李睿智, 何锦涛, 欧阳丹彤. 局部搜索算法求解最小弱连通支配集问题. 软件学报, 2025, 36(8): 3655–3676. http://
www.jos.org.cn/1000-9825/7234.htm
英文引用格式: Li RZ, He JT, Ouyang DT. Local Search Algorithm for Minimum Weakly Connected Dominating Set Problem. Ruan
Jian Xue Bao/Journal of Software, 2025, 36(8): 3655–3676 (in Chinese). http://www.jos.org.cn/1000-9825/7234.htm

Local Search Algorithm for Minimum Weakly Connected Dominating Set Problem
1
1,3
LI Rui-Zhi , HE Jin-Tao , OUYANG Dan-Tong 2
1
(School of Management Science and Information Engineering, Jilin University of Finance and Economics, Changchun 130117, China)
2
(College of Computer Science and Technology, Jilin University, Changchun 130012, China)
3
(Jilin Province Business Big Data Research Center, Changchun 130117, 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.

* 基金项目: 吉林省科技厅自然科学基金 (YDZJ202201ZYTS413); 吉林省教育厅重点基金 (JJKH20240201KJ)
收稿时间: 2024-03-21; 修改时间: 2024-05-02; 采用时间: 2024-06-05; jos 在线出版时间: 2024-09-30
CNKI 网络首发时间: 2024-10-08