CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for
Solving Traveling Salesman Problem
- URL: http://arxiv.org/abs/2312.15412v1
- Date: Sun, 24 Dec 2023 05:25:43 GMT
- Title: CARSS: Cooperative Attention-guided Reinforcement Subpath Synthesis for
Solving Traveling Salesman Problem
- Authors: Yuchen Shi, Congying Han, Tiande Guo
- Abstract summary: This paper introduces CARSS, a novel approach to address the Traveling Salesman Problem (TSP)
CARSS decomposes the TSP solving process into two distinct yet synergistic steps: "subpath generation" and "subpath merging"
Empirical experiments reveal CARSS's superiority compared to single-agent alternatives.
- Score: 4.190087134771218
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper introduces CARSS (Cooperative Attention-guided Reinforcement
Subpath Synthesis), a novel approach to address the Traveling Salesman Problem
(TSP) by leveraging cooperative Multi-Agent Reinforcement Learning (MARL).
CARSS decomposes the TSP solving process into two distinct yet synergistic
steps: "subpath generation" and "subpath merging." In the former, a cooperative
MARL framework is employed to iteratively generate subpaths using multiple
agents. In the latter, these subpaths are progressively merged to form a
complete cycle. The algorithm's primary objective is to enhance efficiency in
terms of training memory consumption, testing time, and scalability, through
the adoption of a multi-agent divide and conquer paradigm. Notably, attention
mechanisms play a pivotal role in feature embedding and parameterization
strategies within CARSS. The training of the model is facilitated by the
independent REINFORCE algorithm. Empirical experiments reveal CARSS's
superiority compared to single-agent alternatives: it demonstrates reduced GPU
memory utilization, accommodates training graphs nearly 2.5 times larger, and
exhibits the potential for scaling to even more extensive problem sizes.
Furthermore, CARSS substantially reduces testing time and optimization gaps by
approximately 50% for TSP instances of up to 1000 vertices, when compared to
standard decoding methods.
Related papers
- SHERL: Synthesizing High Accuracy and Efficient Memory for Resource-Limited Transfer Learning [63.93193829913252]
We propose an innovative METL strategy called SHERL for resource-limited scenarios.
In the early route, intermediate outputs are consolidated via an anti-redundancy operation.
In the late route, utilizing minimal late pre-trained layers could alleviate the peak demand on memory overhead.
arXiv Detail & Related papers (2024-07-10T10:22:35Z) - Multimodal Learned Sparse Retrieval with Probabilistic Expansion Control [66.78146440275093]
Learned retrieval (LSR) is a family of neural methods that encode queries and documents into sparse lexical vectors.
We explore the application of LSR to the multi-modal domain, with a focus on text-image retrieval.
Current approaches like LexLIP and STAIR require complex multi-step training on massive datasets.
Our proposed approach efficiently transforms dense vectors from a frozen dense model into sparse lexical vectors.
arXiv Detail & Related papers (2024-02-27T14:21:56Z) - Enhancing Column Generation by Reinforcement Learning-Based
Hyper-Heuristic for Vehicle Routing and Scheduling Problems [9.203492057735074]
Column generation (CG) is a vital method to solve large-scale problems by dynamically generating variables.
We propose a reinforcement learning-based hyper-heuristic framework, dubbed RLHH, to enhance the performance of CG.
arXiv Detail & Related papers (2023-10-15T00:05:50Z) - Inter-Cell Network Slicing With Transfer Learning Empowered Multi-Agent
Deep Reinforcement Learning [6.523367518762879]
Network slicing enables operators to efficiently support diverse applications on a common physical infrastructure.
The ever-increasing densification of network deployment leads to complex and non-trivial inter-cell interference.
We develop a DIRP algorithm with multiple deep reinforcement learning (DRL) agents to cooperatively optimize resource partition in individual cells.
arXiv Detail & Related papers (2023-06-20T14:14:59Z) - Pointerformer: Deep Reinforced Multi-Pointer Transformer for the
Traveling Salesman Problem [67.32731657297377]
Traveling Salesman Problem (TSP) is a classic routing optimization problem originally arising in the domain of transportation and logistics.
Recently, Deep Reinforcement Learning has been increasingly employed to solve TSP due to its high inference efficiency.
We propose a novel end-to-end DRL approach, referred to as Pointerformer, based on multi-pointer Transformer.
arXiv Detail & Related papers (2023-04-19T03:48:32Z) - MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion
Control in Real Networks [63.24965775030673]
We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms.
Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return.
We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
arXiv Detail & Related papers (2023-02-02T18:27:20Z) - Travel the Same Path: A Novel TSP Solving Strategy [0.0]
We consider the imitation learning framework, which helps a deterministic algorithm making good choices whenever it needs to.
We demonstrate a strong generalization ability of a graph neural network trained under the imitation learning framework.
arXiv Detail & Related papers (2022-10-12T03:56:37Z) - Low-rank Optimal Transport: Approximation, Statistics and Debiasing [51.50788603386766]
Low-rank optimal transport (LOT) approach advocated in citescetbon 2021lowrank
LOT is seen as a legitimate contender to entropic regularization when compared on properties of interest.
We target each of these areas in this paper in order to cement the impact of low-rank approaches in computational OT.
arXiv Detail & Related papers (2022-05-24T20:51:37Z) - Decoupled and Memory-Reinforced Networks: Towards Effective Feature
Learning for One-Step Person Search [65.51181219410763]
One-step methods have been developed to handle pedestrian detection and identification sub-tasks using a single network.
There are two major challenges in the current one-step approaches.
We propose a decoupled and memory-reinforced network (DMRNet) to overcome these problems.
arXiv Detail & Related papers (2021-02-22T06:19:45Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.