论文标题
图形组合优化问题的神经改善启发式
Neural Improvement Heuristics for Graph Combinatorial Optimization Problems
论文作者
论文摘要
图形神经网络体系结构和增加计算能力的最新进展彻底改变了组合优化的领域（CO）。在提出的CO问题模型中，神经改善（NI）模型特别成功。但是，现有的NI方法的适用性有限，因为它们仅考虑节点特征和节点位置编码，因此将其适用于编码重要信息的问题。为了克服这一局限性，我们引入了一个新型的NI模型，该模型能够处理基于图的问题，其中信息在节点，边缘或两者兼而有之。提出的模型是基于爬山的算法的基本组成部分，可指导每次迭代的邻里运营选择。进行的实验表明，提出的模型可以推荐邻里操作，以表现出第99个百分位的性能，以优于偏好排名问题的常规版本。我们还将提案扩展到两个众所周知的问题：旅行推销员问题和图形分配问题，分别建议在第98％和第97个百分位上进行操作。
Recent advances in graph neural network architectures and increased computation power have revolutionized the field of combinatorial optimization (CO). Among the proposed models for CO problems, Neural Improvement (NI) models have been particularly successful. However, existing NI approaches are limited in their applicability to problems where crucial information is encoded in the edges, as they only consider node features and node-wise positional encodings. To overcome this limitation, we introduce a novel NI model capable of handling graph-based problems where information is encoded in the nodes, edges, or both. The presented model serves as a fundamental component for hill-climbing-based algorithms that guide the selection of neighborhood operations for each iteration. Conducted experiments demonstrate that the proposed model can recommend neighborhood operations that outperform conventional versions for the Preference Ranking Problem with a performance in the 99th percentile. We also extend the proposal to two well-known problems: the Traveling Salesman Problem and the Graph Partitioning Problem, recommending operations in the 98th and 97th percentile, respectively.
