信息素学习增强的神经蚁群优化算法

《Neurocomputing》:Pheromone learning-enhanced neural ant colony optimization

【字体: 大 中 小 】 时间:2026年03月19日 来源:Neurocomputing 6.5

编辑推荐:

  蚁群优化(ACO)通过信息素机制平衡探索与利用,但传统手动设计规则缺乏问题实例特征自适应能力。本文提出PL-NACO框架,通过GNN提取问题结构特征与动态精英解特征,结合自适应注意力加权与MLP预测信息素增量,并引入基于最优解的概率约束优化REINFORCE损失。实验表明,PL-NACO在TSP、CVRP等8类组合优化问题上显著优于传统ACO及神经ACO方法。

  
王浩|秦金
贵州大学计算机科学与技术学院,贵阳,550025,中国

摘要

一个设计良好的信息素机制使蚁群优化(ACO)能够快速收敛到组合优化问题(COPs)的高质量解决方案。传统上,手动设计的信息素更新规则通过信息素的释放和蒸发来平衡探索和利用。然而,由于缺乏对问题实例特征的挖掘,这些规则的适应性较差。因此,我们提出了信息素学习增强型蚁群优化(PL-NACO)。PL-NACO是一个自动学习信息素的框架,旨在提升现有ACO的信息素学习能力。PL-NACO通过对精英解决方案和问题实例分别提取的动态特征和结构特征进行加权融合,然后使用融合特征动态预测信息素增量。在训练模型学习信息素时,基于最佳解决方案的概率约束被添加到REINFORCE损失函数中,这可以有效引导模型关注最佳解决方案。实验结果表明,PL-NACO可以作为通用的信息素更新框架,有效增强传统的ACO和神经ACO算法。

引言

蚁群优化(ACO)是一种经典的元启发式方法,已被广泛应用于解决组合优化问题(COPs)[1]。ACO利用一群蚂蚁基于启发式信息和信息素以迭代方式构建解决方案。当蚂蚁在解空间中搜索解决方案时,它们主要通过信息素的释放和蒸发来实现全局指导。信息素更新规则决定了ACO的搜索效率和解决方案质量。传统上,手动设计的更新规则存在以下缺点:首先,搜索速度慢。在解决COPs时,需要大量迭代才能生成有效的信息素。其次,这些规则依赖于先验知识,因此需要大量的试错来调整参数,这既耗时又费力[2]。第三,它们缺乏对问题实例特征的利用,不具备动态适应性。
近年来,基于学习的神经组合优化(NCO)方法取得了显著进展[3],它们可以在序列决策过程中逐步构建COPs的解决方案[4]。一般来说,现有的NCO方法可以分为端到端方法和混合方法。端到端方法通过自回归构建解决方案或生成热图,然后进行基于采样的解码过程。端到端方法的研究包括设计更优秀的神经架构[5]、改进训练范式[6]、开发更先进的解码过程[7]以及扩展应用场景[8]。尽管端到端方法效率较高,但在构建解决方案过程中难以有效探索解空间。在混合方法中,传统的(元)启发式方法通过使用神经学习器从收集的数据中自动发现启发式规则来得到增强。
混合方法将神经学习器整合到启发式方法中,以辅助决策或生成热图,从而支持启发式方法。例如,Xin等人[9]提出了一种基于分数的学习和节点惩罚方法来指导LKH-3[10]的搜索过程。Kool等人[11]训练神经模型来预测路径优化问题中潜在的高质量边,为动态规划提供了神经增强。Fu等人[12]训练小型图神经网络(GNN)为大规模TSP实例生成热图,并将这些热图应用于蒙特卡洛树搜索以提高解决方案质量。
上述大多数混合方法仅限于少数路径规划问题,通用性有限。相比之下,Ye等人[13]创新地将GNN学习器与ACO集成,提出了一种更通用的算法DeepACO,该算法对包括路径规划、分配、调度和子集问题在内的八种COPs提供了有效的神经增强。DeepACO可以自动生成启发式信息,从而消除了对手动设计启发式信息的依赖,并显著提高了ACO的解决方案性能。GFACS算法[14]进一步整合了GFlowNets[15],考虑了组合解决方案的对称性[16],并提升了组合解决方案空间的探索能力。然而,这两种算法仍然采用传统的手动设计的信息素更新规则。
与DeepACO和GFACS不同,本文提出了一种新型的神经增强型ACO算法,即信息素学习增强型蚁群优化(PL-NACO)。PL-NACO使用信息素学习器自动更新信息素。信息素学习器通过自适应注意力加权,将GNN提取的问题实例结构特征与每次迭代中的精英解决方案的动态特征进行融合,然后利用多层感知器(MLP)生成自适应的信息素增量。这种方法增强了信息素对问题特征和搜索过程的动态适应性。
总结来说,我们的贡献有三个方面:
  1. •
    我们提出了PL-NACO,一种新型的神经增强型ACO算法。它可以根据神经学习自动更新信息素,并加速收敛到高质量解决方案。
  2. •
    我们提出了一种自适应的注意力加权特征融合机制,用于融合精英解决方案的动态特征和问题实例的特征,以提高信息素对问题实例特征的动态适应性。同时,我们引入了针对最佳解决方案的概率约束来修改REINFORCE损失函数,从而提高模型对最佳解决方案的拟合效果。
  3. •
    广泛的实验验证表明,PL-NACO可以作为通用的信息素更新框架,有效提升传统ACO和神经ACO算法在八种COPs上的性能。

部分摘录

蚁群优化

ACO是一种元启发式算法[17],其灵感来源于蚂蚁寻找巢穴和食物源之间最短路径的觅食行为[18]。常用的ACO变体包括蚁系统(AS)[19]、精英蚁系统(EAS)[20]和最大最小蚁系统(MMAS)[21]。
当ACO解决COPs时,每只蚂蚁选择下一个要访问的节点。在AS中,当蚂蚁位于节点时,选择下一个节点的概率如下:其中
相关新闻
生物通微信公众号
微信
新浪微博
  • 搜索
  • 国际
  • 国内
  • 人物
  • 产业
  • 热点
  • 科普

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号