GOAL: A Generalist Combinatorial Optimization Agent Learner

机器学习的启发式方法最近在解决各种难以组合优化问题（COP）上表现出了令人印象深刻的性能。然而，它们通常依赖于单独的神经模型，专门针对每个单一问题进行训练。任何问题的变化都需要调整其模型并从头重新训练。在本文中，我们提出了GOAL（通用组合优化代理学习），这是一个通用模型，能够有效地解决多个COP，并可以微调以解决新的COP。GOAL由一个单一的骨干加上轻量级的问题特定适配器组成，主要用于输入和输出处理。骨干基于一种新型的混合注意力块，可以处理基于图形的问题，这些问题具有节点、边和实例级特征的任意组合。此外，涉及异构节点或边的问题，例如多部分图形，通过一种新型的多类型变换器架构进行处理，其中注意块被复制以仅关注相关类型的组合，同时依赖于相同的共享参数。我们在一组路由、调度和经典图形问题上训练GOAL，并表明它只稍微逊色于专业基线，同时是第一个解决各种COP的多任务模型。最后，我们展示了GOAL的强大的迁移学习能力，通过少量数据的微调或学习适配器来解决新问题。

论文旨在提出一个通用的模型GOAL，可以有效地解决多个组合优化问题，而无需为每个问题训练特定的模型。

GOAL由一个主干和轻量级的问题特定适配器组成，主干基于一种新的混合注意力块，可以处理在图上定义的具有任意节点、边和实例级特征组合的问题。此外，GOAL还提出了一种新的多类型变压器架构，可以处理涉及异构节点或边的问题。

论文通过一系列实验表明，GOAL可以在多个组合优化问题上取得与专用模型相当的性能，且具有较强的迁移学习能力。论文使用了一些公开数据集进行实验，并开源了代码。

最近的相关研究包括使用深度学习解决组合优化问题的多种方法，如基于图神经网络的方法、基于强化学习的方法等。例如，DeepWalk、GCN、GAT等图神经网络模型被广泛应用于组合优化问题的求解中。另外，还有一些基于深度学习的多任务学习模型，如MTL、DTP等，也被用于解决组合优化问题。