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

摘要： 为解决最小度约束最小生成树问题，提出一种结合强化学习求解的粒子群优化（PSO）算法。在搜索区域初始化过程中，利用生成树结构特征信息，设计基于短边聚类的结构生长方法，为后续搜索提供优质初始解空间；在PSO算法框架内，利用群体协同进化和保留历史信息的特点，设计不同进化速度的学习算子，在求解空间中展开多级精细搜索；设计不同粒度的自主飞行算子，负责不同程度的扰动，提供搜索多样性。同时围绕强化学习的状态反馈机制设计针对不同进化状态的奖惩池，根据当前搜索状态反馈及时调整个体更新策略，实现均衡高效搜索。进一步针对复杂邻域设计针对不同节点关系的两类局部搜索算子，针对叶节点进化设计交换、插入搜索操作，构成最小粒度的局部搜索；针对非叶节点设计替换、删除操作，在保证优质局部结构的同时提供更大范围内的搜索。使用105个被广泛用于测试的实例进行验证及对比，结果表明算法在98个实例上能够达到已知最优解，在其中48个实例中超越现有已知最优解，与其他算法的比较展示了算法的先进性和强有力的竞争力。

关键词: 最小度约束最小生成树, 强化学习, 粒子群优化, 局部搜索