改进图注意力机制，让模型同时关注节点和边，更好解决复杂路径规划问题。
EGAM: Extended Graph Attention Model for Solving Routing Problems
- 引入多头点积注意力，同步更新节点与边的嵌入表示
- 在多种路由问题上达到或超越现有最优水平，尤其在高约束场景表现突出
- 适合需要处理复杂图结构的路径优化任务，如物流调度、网络路由
神经组合优化求解器通过图神经网络（GNN）为求解路由问题提供了新方法。基于强化学习训练的当前最优图注意力模型（GAM）可在无需专家知识或标注数据的情况下获得近似最优解。本文提出扩展图注意力模型（EGAM），对现有图注意力机制进行推广。该模型采用多头点积注意力，同时更新节点与边的嵌入表示，克服了传统GAM仅考虑节点特征的局限性。我们采用自回归编码器-解码器架构，并使用结合特殊基线的策略梯度算法进行训练。实验表明，EGAM在各类路由问题上表现达最优或更优，尤其在高度约束的问题中展现出卓越性能，体现出对复杂图结构的高效处理能力。
原文摘要 · Abstract (English)
Neural combinatorial optimization (NCO) solvers, implemented with graph neural networks (GNNs), have introduced new approaches for solving routing problems. Trained with reinforcement learning (RL), the state-of-the-art graph attention model (GAM) achieves near-optimal solutions without requiring expert knowledge or labeled data. In this work, we generalize the existing graph attention mechanism and propose the extended graph attention model (EGAM). Our model utilizes multi-head dot-product attention to update both node and edge embeddings, addressing the limitations of the conventional GAM, which considers only node features. We employ an autoregressive encoder-decoder architecture and train it with policy gradient algorithms that incorporate a specially designed baseline. Experiments show that EGAM matches or outperforms existing methods across various routing problems. Notably, the proposed model demonstrates exceptional performance on highly constrained problems, highlighting its efficiency in handling complex graph structures.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。