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

Jun, 2020

Constrained Combinatorial Optimization with Reinforcement Learning

Ruben Solozabal, Josu Ceberio, Martin Takáč

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

Abstract

This paper presents a framework to tackle constrained combinatorial optimization problems using deep reinforcement learning (RL). To this end, we extend the neural combinatorial optimization (NCO) theory in order

constrained combinatorial optimization deep reinforcement learning neural combinatorial optimization constrained markov decision processes heuristic algorithm

发现论文，激发创造

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

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

Jun, 2020

强化学习的组合探索优化

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

Sep, 2019

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

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

Mar, 2020

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

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

Jun, 2022

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

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

Feb, 2021

基于哈密顿量的量子强化学习用于神经计算组合优化

基于 Hamiltonian 的量子强化学习（QRL）是将量子计算与神经组合优化相结合的一种方法，通过对组合优化问题的 Hamiltonian 公式建模，拥有较好的训练性能，适用于广泛的问题类别，并与 QAOA 进行了比较。

May, 2024

神经组合优化：领域的新玩家

本文对神经网络在传统组合优化框架中的性能、可迁移性、计算成本和对更大样本的普适性进行了详细研究，并在 NP-hard 问题线性排序问题上开发了神经组合优化模型。

May, 2022

强化学习的神经组合优化

本文提出了一种利用神经网络和强化学习解决组合优化问题的框架，特别关注旅行推销员问题和背包问题，证明了该方法在不需要太多工程和启发式设计的情况下在二维欧几里得图上取得接近最优结果，并且可以得到具有多达 200 个项目实例的最优解。

Nov, 2016

具有约束恢复的逆强化学习

本文提出了基于最大熵原理的逆强化学习算法，用于推断约束非凸最优化问题的奖励函数和约束条件，并采用指数梯度下降算法解决约束问题。通过在网格世界环境中的实验验证了该算法的效力。

May, 2023

模型不匹配下的受限增强学习

在训练环境下，现有的关于约束强化学习（RL）的研究可能可以获得良好的策略。然而，在真实环境中部署时，由于训练与真实环境之间可能存在模型不匹配，它可能很容易违反最初满足的约束。为了解决上述挑战，我们将问题形式化为模型不确定性下的约束强化学习，即旨在学习一个能够优化奖励并同时满足模型不匹配下的约束的良好策略。我们提出了一种名为鲁棒约束策略优化（RCPO）的算法，这是一种适用于大型 / 连续状态空间且在训练期间每次迭代都具有最坏情况奖励改进和约束违规的理论保证的算法。我们在一组具有约束条件的强化学习任务上展示了我们算法的有效性。

May, 2024