Li Ruizhi, He Jintao, Liu Shangqiong, Hu Shuli, Yin Minghao
School of Management Science and Information Engineering, Jilin University of Finance and Economics, Changchun 130117, China.
Business Big Data Research Center of Jilin Province, Changchun 130117, China.
Biomimetics (Basel). 2024 Jul 15;9(7):429. doi: 10.3390/biomimetics9070429.
The minimum connected dominating set problem is a combinatorial optimization problem with a wide range of applications in many fields. We propose an efficient local search algorithm to solve this problem. In this work, first, we adopt a new initial solution construction method based on three simplification rules. This method can reduce the size of the original graph and thus obtain a high-quality initial solution. Second, we propose an approach based on a two-level configuration checking strategy and a tabu strategy to reduce the cycling problem. Third, we introduce a perturbation strategy and a vertex weighting strategy to help the algorithm be able to jump out of the local optimum effectively. Fourth, we combine the scoring functions and with the aforementioned strategies to propose effective methods for selecting vertices. These methods assist the algorithm in selecting vertices that are suitable for addition to or removal from the current candidate solution. Finally, we verify the performance advantages of the local search algorithm by comparing it with existing optimal heuristic algorithms on two sets of instances. The experimental results show that the algorithm exhibits better performance on two sets of classical instances.
最小连通支配集问题是一个组合优化问题，在许多领域都有广泛的应用。我们提出了一种高效的局部搜索算法来解决这个问题。在这项工作中，首先，我们采用一种基于三条简化规则的新的初始解构造方法。这种方法可以减小原始图的规模，从而获得高质量的初始解。其次，我们提出一种基于两级配置检查策略和禁忌策略的方法来减少循环问题。第三，我们引入一种扰动策略和顶点加权策略，以帮助算法能够有效地跳出局部最优。第四，我们将评分函数与上述策略相结合，提出有效的顶点选择方法。这些方法有助于算法选择适合添加到当前候选解或从当前候选解中移除的顶点。最后，我们通过在两组实例上与现有的最优启发式算法进行比较，验证了局部搜索算法的性能优势。实验结果表明，该算法在两组经典实例上表现出更好的性能。
