组合优化问题在物流、电路设计、药物研发等领域具有广泛应用，但传统方法在处理大规模问题时往往效率低下，难以找到高质量解。尽管图神经网络（GNN）为组合优化提供了新思路，但其训练过程易陷入局部最优，导致性能受限。
为解决这一难题，近日国科大杭州高等研究院生命与健康科学学院陈洛南/陶鹏团队在人工智能国际知名期刊IEEE Transactions on Neural Networks and Learning Systems上发表了题为“Brain-Inspired Chaotic Graph Backpropagation for Combinatorial Optimization”的研究论文。该研究受大脑混沌动力学启发，提出了混沌图反向传播（CGBP）算法，通过引入局部损失函数模拟神经元的混沌特性，显著提升了GNN在组合优化中的全局搜索能力。
研究团队基于混沌动力学理论，创新性地将大脑的伪随机性和全局遍历性融入GNN训练过程。CGBP框架通过添加混沌损失项，使梯度更新过程呈现混沌动态，从而避免陷入局部最小值。该方法首次将组合优化问题转化为GNN的训练任务，利用延迟嵌入和混沌模拟退火策略，实现了高效的大规模问题求解。如图1所示，CGBP将问题映射到GNN训练中，通过概率输出投影得到最终解。
图1 CGBP框架图
CGBP的突出优势在于其通用插件式设计，可无缝集成到现有优化算法中。实验表明，在最大独立集（MIS）、最大割（MC）和图着色（GC）等经典问题上，CGBP在Gset、DIMACS和Citation等大规模基准数据集上均达到或超越了当前最优方法的性能。例如，在正则图上的测试中，CGBP将近似比提升至98%，远超传统梯度方法。该研究的另一重要贡献是揭示了混沌动力学在机器学习中的普适性。CGBP作为一种基础学习框架，不仅适用于组合优化，还可扩展至其他复杂系统预测任务，展现出强泛化能力。
杭高院为该工作的第一完成单位。杭高院生命学院陶鹏助理研究员为论文的第一作者，陈洛南研究员为论文的通讯作者，东京大学的Kazuyuki Aihara教授也提供了重要支持。该工作得到了国家自然科学基金、浙江省科技厅和杭高院的大力支持。
