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

Abstract: To address the limited solving accuracy of existing heuristic algorithms for the 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 to narrow the search space and improve the quality of the initial solution. Then, a feasible solution construction mechanism with priority of weak connectivity was introduced in the local search stage. Compared to traditional methods, this mechanism more effectively maintains the weak connectivity and dominance of solutions. It was combined with an efficient vertex selection strategy to dynamically guide the addition or removal of vertices, improving the diversity and feasibility of solutions. A dual cycle suppression mechanism combining frequency and tabu strategies 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 local optima. In terms of experimental evaluation, on 98 instances of the 4 sets of benchmark tests, it was compared with the CPLEX (C Programming Language for EXpressions) precision solver and 6 state-of-the-art algorithms. Statistical results show that MAE-LS is the algorithm with the largest number of optimal solutions, especially on the NDR (Network Data Repository) instance, the number of optimal solutions obtained is 61.5% higher than that of suboptimal performance FPLS (Local Search algorithm based on the Feedback mechanism and the Perturbation strategy), which fully proves the significant advantages of this algorithm in 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