计算机科学与探索

作者：吴良成, 杨 凯, 钟一文, 林娟

单位：1. 福建农林大学 计算机与信息学院，福州 3500082. 福建农林大学 智慧农林福建省高校重点实验室，福州 350008

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

基金：福建省自然科学基金（2022J01153，2023J01078）；福建农林大学科技创新基金（KFB23192）。

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

来源：2025年第8期

《计算机科学与探索》期刊编辑部

查看计算机科学与探索杂志2025年第8期