计算机科学与探索2025，Vol.19Issue(8)：2110-2122,13.DOI:10.3778/j.issn.1673-9418.2407053
求解最小度约束最小生成树的强化粒子群优化算法
Reinforcement Learning Particle Swarm Optimization Algorithm for Solving Min-degree Constrained Minimum Spanning Tree
摘要
Abstract
To address the min-degree constrained minimum spanning tree problem,a particle swarm optimization(PSO)algorithm combined with reinforcement learning is proposed.During the initialization of the search space,a structure growth method based on short-edge clustering is designed by utilizing the characteristics of the spanning tree structure,which provides a high-quality initial solution space for subsequent searches.Within the PSO framework,learning operators with different evolutionary speeds are designed by leveraging the characteristics of population co-evolution and historical information retention,enabling a multi-level fine-grained search in the solution space.Autonomous flight operators of different granularities are also designed to apply various levels of perturbation,thereby enhancing search diversity.Moreover,a reward-punishment pool is developed around the state feedback mechanism of reinforcement learning,which adjusts individual update strategies according to the feedback of the current search state,achieving a balanced and efficient search.For complex neighborhoods,two types of local search operators targeting different node relationships are designed:one focuses on leaf node evolution with exchange and insertion search operations,forming the finest-grained local search;the other targets non-leaf nodes with replacement and deletion operations,providing a broader search scope while ensuring the quality of local structures.Using 105 widely tested instances for validation and comparison,the results show that the algorithm is able to reach the known optimal solution in 98 instances and surpasses the existing known optimal solution in 48 instances.Comparative results with other algorithms demonstrate the advanced performance and strong competitiveness of the algorithm.关键词
最小度约束最小生成树/强化学习/粒子群优化/局部搜索Key words
min-degree constrained minimum spanning tree/reinforcement learning/particle swarm optimization/local search分类
信息技术与安全科学引用本文复制引用
吴良成,杨凯,钟一文,林娟..求解最小度约束最小生成树的强化粒子群优化算法[J].计算机科学与探索,2025,19(8):2110-2122,13.基金项目
福建省自然科学基金(2022J01153,2023J01078) （2022J01153,2023J01078）
福建农林大学科技创新基金(KFB23192).This work was supported by the Natural Science Foundation of Fujian Province(2022J01153,2023J01078),and the Scientific and Tech-nological Innovation Fund of Fujian Agriculture and Forestry University(KFB23192). （KFB23192）
