软件学报

作者：李睿智，何锦涛，欧阳丹彤

单位：李睿智，吉林财经大学 管理科学与信息工程学院, 吉林 长春 130117;吉林省商务大数据研究中心, 吉林 长春 13011711,何锦涛，吉林财经大学 管理科学与信息工程学院, 吉林 长春 13011702,欧阳丹彤，吉林大学 计算机科学与技术学院, 吉林 长春 13001203

关键词：最小弱连通支配集问题;组合优化;局部搜索;反馈机制;扰动策略;年龄属性

基金：吉林省科技厅自然科学基金(YDZJ202201ZYTS413); 吉林省教育厅重点基金(JJKH20240201KJ)

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

来源：2025年第8期

《软件学报》期刊编辑部

查看软件学报杂志2025年第8期