Abstract:

To address the limited solving accuracy of the existing heuristic algorithms for Minimum Weakly Connected Dominating Set Problem （MWCDSP）， a Master-Apprentice Evolutionary algorithm based on improved Local Search （MAE-LS） was proposed. First， double simplification rules were used in the initial solution construction stage to identify vertices that must be included in the optimal solution， thereby narrowing the searching space and improving quality of the initial solution. Second， a feasible solution construction mechanism with priority of weak connectivity was introduced in the local search stage. Compared to traditional methods， this mechanism maintained the weak connectivity and dominance of solutions more effectively. At the same time， combined with an efficient vertex selection strategy， the addition to the candidate solutions or removal from the solutions of vertices was guided dynamically， thereby improving diversity and feasibility of the solutions. Third， a dual cycle suppression mechanism combining frequency and tabu strategy was designed to effectively reduce the probability of repeated searches. Finally， a path-breaking strategy and a perturbation strategy were proposed to help the algorithm escape from the local optimum. The proposed algorithm was compared with the CPLEX （C Programming Language for EXpressions） exact solver and 6 state-of-the-art algorithms on 98 instances of the 4 benchmark test sets. Experimental results show that MAE-LS is the algorithm obtaining the largest number of optimal solutions， especially on the NDR （Network Data Repository） instance， where the number of optimal solutions obtained by MAE-LS is 61.5% higher than that of the algorithm with suboptimal performance， FPLS （Local Search algorithm based on the Feedback mechanism and the Perturbation strategy）， significantly， fully proving the significant advantages of this algorithm in terms of solving accuracy and algorithm stability. MAE-LS provides an effective solution to NP （Nondeterministic Polynomial） -hard network optimization problems， and is of great value to practical applications such as wireless sensor network construction.

Key words: combinatorial optimization, Minimum Weakly Connected Dominating Set Problem (MWCDSP), Master-Apprentice Evolutionary algorithm (MAE), local search, path-breaking strategy

摘要：

针对现有的启发式算法对最小弱连通支配集问题（MWCDSP）的求解精度受限问题，提出一种基于改进局部搜索的师徒进化算法（MAE-LS）。首先，在初始解构造阶段利用双重简化规则识别必然存在于最优解中的顶点，以缩小搜索空间并提升初始解的质量；其次，在局部搜索阶段引入弱连通优先的可行解构造机制，该机制相较于传统方法能更有效地维持解的弱连通性与支配性，同时结合高效的顶点选择方式动态指导顶点加入候选解或从解中移除，以增强解的多样性和可行性；再次，设计混合频率与禁忌策略的双重循环抑制机制，以有效降低重复搜索的概率；最后，提出破路策略以及扰动策略帮助算法跳出局部最优。在4组基准测试集的98个实例上，把所提算法与CPLEX （C Programming Language for EXpressions）精确求解器以及6种最先进的算法进行对比。实验结果表明， MAE-LS是获得最优解数量最多的算法，特别是在NDR （Network Data Repository）实例上，它获得最优解的数量较性能次优的算法FPLS （Local Search algorithm based on the Feedback mechanism and the Perturbation strategy）有61.5%的显著提升，充分证明了该算法在求解精度和算法稳定性方面的显著优势。MAE-LS为NP （Nondeterministic Polynomial）难网络优化问题提供了有效的求解途径，对无线传感器网络构建等实际应用具有重要价值。

关键词: 组合优化, 最小弱连通支配集问题, 师徒进化算法, 局部搜索, 破路策略