强化学习+组合优化创新！快速学会登上CCF-A的热门组合

AI算法科研paper · 公众号 · · 2025-01-02 19:10

正文

强化学习 特别擅长处理高维、非线性及具有复杂约束条件的问题， 和组合优化可以说是“天生一对” 。其自适应性和策略改进能力，可以让它在未知或动态变化的环境中逐步学习到最优策略，在COP求解上远远优于传统方法。

实际上， 这种组合一直是个前沿且相当热门的研究领域， 最近在顶会Neurips上已经看见了不少新的突破性成果，比如一种群体强化学习方法Poppy，在四个NP难题上都实现了SOTA，另外还有一种基于GNN的强化学习方法，在解决组合优化问题上参数量减少了83%，同时保持高性能。

所以 对于组合优化领域的论文er来说，+强化学习真的是一大创新趋势， 尤其是深度强化学习（目前想要在组合优化问题领域发论文真得上DRL），建议感兴趣的同学抓紧。我这边有已经整理好的 12篇 强化学习+组合优化新论文＆代码， 需要参考的可以无偿领~

扫码添加小享，回复“ 强化组合 ”

免费获取全部论 文+开源代码

Graph Q-Learning for Combinatorial Optimization

方法： 论文是关于使用GNNs和强化学习（RL）来解决组合优化问题的，作者提出了一种方法，将组合优化问题表示为图序列，并使用强化学习来寻找有前景的解决方案。实验证明，使用图神经网络通过Q-Learning训练的模型在解决组合优化问题上的性能接近最先进的启发式求解器，同时仅使用了六分之一的参数量和更少的训练时间。

创新点；

首次将GNNs应用于解决灵活作业车间调度问题（FJSP），并将组合优化问题表示为马尔可夫决策过程（MDP）。
在保持与其他算法和基线启发式方法相当性能的同时，仅使用了它们一小部分的参数和训练时间。
通过将问题空间以图形表示，所提出的方法不仅限于固定问题规模，能够跨多种规模问题实现通用的元学习。

Reinforcement Learning-Based Formulations With Hamiltonian-Inspired Loss Functions for Combinatorial Optimization Over Graphs

方法： 作者将QUBO-Hamiltonian集成到基于强化学习的无监督框架中，解决图论组合优化问题，提出了改进PI-GNN的策略以及两种新的RL架构（GRL QUBO和MCTS-GNN），并在Max-Cut问题上实现了高达44%的约束满足率提升，以展示其在广泛适用性、解决方案质量和收敛模式上的贡献。