سال انتشار:
2020
عنوان انگلیسی مقاله:
A reinforcement learning approach for optimizing multiple traveling salesman problems over graphs
ترجمه فارسی عنوان مقاله:
یک رویکرد یادگیری تقویت برای بهینه سازی مسائل فروشنده دوره گرد چند گانه از طریق گراف
منبع:
Sciencedirect - Elsevier - Knowledge-Based Systems, 204 (2020) 106244. doi:10.1016/j.knosys.2020.106244
نویسنده:
Yujiao Hua,b,∗, Yuan Yao a, Wee Sun Lee
چکیده انگلیسی:
This paper proposes a learning-based approach to optimize the multiple traveling salesman problem
(MTSP), which is one classic representative of cooperative combinatorial optimization problems.
The MTSP is interesting to study, because the problem arises from numerous practical applications
and efficient approaches to optimize the MTSP can potentially be adapted for other cooperative
optimization problems. However, the MTSP is rarely researched in the deep learning domain because
of certain difficulties, including the huge search space, the lack of training data that is labeled with
optimal solutions and the lack of architectures that extract interactive behaviors among agents. This
paper constructs an architecture consisting of a shared graph neural network and distributed policy
networks to learn a common policy representation to produce near-optimal solutions for the MTSP. We
use a reinforcement learning approach to train the model, overcoming the requirement data labeled
with ground truth. We use a two-stage approach, where reinforcement learning is used to learn an
allocation of agents to vertices, and a regular optimization method is used to solve the single-agent
traveling salesman problems associated with each agent. We introduce a S-samples batch training
method to reduce the variance of the gradient, improving the performance significantly. Experiments
demonstrate our approach successfully learns a strong policy representation that outperforms integer
linear programming and heuristic algorithms, especially on large scale problems.
Keywords: Multi-agent reinforcement learning | Combinatorial optimization problems | Multiple traveling salesman problems | Graph neural networks | Policy networks
قیمت: رایگان
توضیحات اضافی:
تعداد نظرات : 0