强化学习的组合探索优化

AAAISep, 2019

Exploratory Combinatorial Optimization with Reinforcement Learning

Thomas D. Barrett, William R. Clements, Jakob N. Foerster, A. I. Lvovsky

TL;DR在解决复杂优化问题方面，探索式组合优化（ECO-DQN）通过连续改进解决方案，从而有效地学习有效的启发式方法来解决图上的组合优化问题，并在最大割问题上展示了最先进的强化学习性能。

Abstract

Many real-world problems can be reduced to combinatorial optimization on a graph, where the subset or ordering of vertices that maximize some objective function must be found. With such tasks often NP-hard and an

combinatorial optimization reinforcement learning exploratory optimization maximum cut problem graph

发现论文，激发创造

组合优化的强化学习：一项调查研究

本文综述了近期在强化学习领域中在解决组合优化问题方面的进展，包含了 RL 框架与传统算法的比较以及各方法解决不同问题的时间线，结果表明基于 RL 的模型成为解决组合问题的方向值得期待。

Mar, 2020

使用强化学习的受限组合优化

本文提出一个深度强化学习的框架来解决受限的组合优化问题，将受约束的组合问题定义为完全可观的受约束马尔可夫决策过程（CMDP），并提出从不满足的约束产生惩罚信号，以推断作为启发式算法的策略。通过对约束工厂和资源分配问题进行的实验表明，本文的提议对于比较经典的启发式算法、元启发式算法和约束编程（CP）求解器来说，能更快地求得答案。

Jun, 2020

可逆行动设计与强化学习在组合优化中的应用

利用图神经网络和深度 Q 学习的强化学习方法，针对组合优化问题提出了一种无需问题特定设计即可实现状态最优化策略搜索的通用模型，并在最大 k-Cut 问题和旅行商问题上实验验证了其优越性。

Feb, 2021

结合强化学习和约束编程用于组合优化

本文介绍了一种基于深度强化学习和约束编程的混合算法，应用于复杂的组合优化问题，并在实验中成功运用于旅行商问题和投资组合优化问题，表现优于单独的深度强化学习和约束编程算法，同时也达到了与工业级求解器相竞争的水平。

Jun, 2020

通过高效探索学习解决组合图分割问题

本文介绍了一种名为 ECORD 的新型强化学习算法，它通过限制图神经网络的使用，提升了在最大割问题上的表现和可扩展性。在 500 个节点的图上，ECORD 相较于最接近的竞争者，优化效果缩小了最多 73%。同时，ECORD 在具有多达 10000 个节点的图的普适性方面保持了强有力的表现。

May, 2022

在图上学习组合优化算法

本文介绍了结合强化学习和图嵌入的方法，使用元算法来解决 NP-hard 组合优化问题和图上的最小点集覆盖、最大割和旅行商问题等优化问题。

Apr, 2017

增强强化学习的量子启发式组合优化算法

本文提出了一种基于量子启发式算法 + 强化学习的方法，在解决 Ising 能量最小化问题方面，该方法通过调整其中一个参数以改进最近看到的解，并使用一种新的 Rescaled Rank Reward (R3) 方法来提高稳定的自我博弈训练效果。训练后可在任何问题实例中采样高质量的解，并优于基线启发式和黑盒超参数优化方法。

Feb, 2020

精确组合优化的深度强化学习：学习分支

本文提出一种基于强化学习的方法用于解决组合优化中的数据标记和推理延迟问题，并使用蒙特卡罗树搜索和价值网络提高策略网络的性能表现。作者在四种不同类别的组合优化问题上进行了评估，结果表明该方法相较于现有机器学习和启发式方法有更优的性能表现。

Jun, 2022

进化强化学习：综述

这篇文章综述了将进化计算方法与强化学习相结合的最新研究进展和方法，涉及强化学习中的关键研究领域及未来方向，为研究者和实践者提供参考和资源。

Mar, 2023

线性时间内学习在实际图中求解组合优化问题

本文介绍一种使用强化学习训练图神经网络求解单人游戏定义的图组合优化问题的新框架，可以处理最小生成树、最短路径、旅行商问题和车辆路径问题等一系列问题，该方法可在线性运行时间内输出近似解，并且能够推广到多种情况，包括 NP 困难的问题和真实世界的图。

Jun, 2020