MARCO: 内存增强的组合优化增强学习框架
内容提要
本文提出了一种深度强化学习框架来解决受限组合优化问题，定义为受约束马尔可夫决策过程（CMDP）。实验结果表明，该方法在约束工厂和资源分配问题上优于传统启发式算法。此外，介绍了自我改进学习（SIL）方法和ARCO框架，显著提升了神经组合优化的可扩展性和效率，尤其在旅行推销员和车辆路径问题上表现突出。
延伸解读
约束组合优化的强化学习建模
文章将受限组合优化问题定义为完全可观的受约束马尔可夫决策过程（CMDP），并通过从不满足的约束中产生惩罚信号来推断启发式策略。这种建模方式使深度强化学习能够直接处理约束，而无需依赖传统启发式算法中的手工规则。实验表明，在约束工厂和资源分配问题上，该方法比经典启发式、元启发式及约束编程求解器更快求得答案，为约束优化提供了新的求解思路。
自我改进学习提升可扩展性
自我改进学习（SIL）方法旨在提高神经组合优化的可扩展性，包括有效的模型训练和解决大规模问题实例的线性复杂度注意机制。在旅行推销员问题（TSP）和容量车辆路径问题（CVRP）上的实验证明了其出色可扩展性。此外，基于序列抽样的SIL通过修改策略以忽略已抽样的序列，强制考虑未见的替代方案，从而增加解决方案多样性，在作业车间调度问题上也优于之前的神经组合优化方法。
ARCO框架的跨平台优化效果
ARCO是一个基于多智能体强化学习的自适应协同编译框架，旨在提高将机器学习模型映射到不同硬件平台的效率。它包含三个专用的演员-评论家智能体，分别专注于硬件和软件优化，形成协同的硬件/软件协同优化策略。该框架超越了现有领先框架，在各种深度神经网络上实现了最高37.95%的吞吐量增加，同时将优化时间降低了最高42.2%，显著提升了部署的精度和速度。
神经组合优化的多样性进展
文章还介绍了MEMENTO和多样性增强的神经启发式方法。MEMENTO是一种基于记忆的强化学习方法，能在推理时动态更新行动分布，提高神经求解器的适应性和性能。多样性增强的神经启发式方法则能从多目标组合优化问题的不同视角产生更多帕累托解，在经典多目标问题上取得更高的多样性帕累托前沿和卓越的整体性能。这些进展共同推动了神经组合优化在多样性和适应性方面的发展。
Q&A
什么是受约束马尔可夫决策过程（CMDP）？
受约束马尔可夫决策过程（CMDP）是一种用于解决受限组合优化问题的框架，定义为完全可观的决策过程。
ARCO框架的主要优势是什么？
ARCO框架通过多智能体强化学习提高了机器学习模型在不同硬件平台上的映射效率，实现了最高37.95%的吞吐量增加，并将优化时间降低了最高42.2%。
自我改进学习（SIL）方法如何提升神经组合优化的效率？
自我改进学习（SIL）方法通过有效的模型训练和线性复杂度注意机制，提升了神经组合优化的可扩展性，尤其在旅行推销员和车辆路径问题上表现突出。
实验结果显示该框架在什么问题上优于传统算法？
实验结果表明，该框架在约束工厂和资源分配问题上优于传统启发式算法。
MEMENTO方法的主要功能是什么？
MEMENTO是一种基于记忆的强化学习方法，能够在推理时间动态更新行动分布，提高神经求解器的适应性和性能。
如何通过序列抽样增加解决方案的多样性？
通过基于序列抽样的自我改进学习方法，修改策略以忽略先前抽样的序列，从而强制考虑未见过的替代方案，增加解决方案的多样性。
