Multi-objective Pointer Network for Combinatorial Optimization
Multi-objective combinatorial optimization problems (MOCOPs), one type of complex optimization problems, widely exist in various real applications. Although meta-heuristics have been successfully applied to address MOCOPs, the calculation time is often much longer. Recently, a number of deep reinforcement learning (DRL) methods have been proposed to generate approximate optimal solutions to the combinatorial optimization problems. However, the existing studies on DRL have seldom focused on MOCOPs. This study proposes a single-model deep reinforcement learning framework, called multi-objective Pointer Network (MOPN), where the input structure of PN is effectively improved so that the single PN is capable of solving MOCOPs. In addition, two training strategies, based on representative model and transfer learning, respectively, are proposed to further enhance the performance of MOPN in different application scenarios. Moreover, compared to classical meta-heuristics, MOPN only consumes much less time on forward propagation to obtain the Pareto front. Meanwhile, MOPN is insensitive to problem scale, meaning that a trained MOPN is able to address MOCOPs with different scales. To verify the performance of MOPN, extensive experiments are conducted on three multi-objective traveling salesman problems, in comparison with one state-of-the-art model DRL-MOA and three classical multi-objective meta-heuristics. Experimental results demonstrate that the proposed model outperforms all the comparative methods with only 20\% to 40\% training time of DRL-MOA.
Code (1)
Tasks
Combinatorial OptimizationDeep Reinforcement Learningreinforcement-learningReinforcement Learning (RL)Transfer LearningMethods 이 논문이 사용한 방법론
Similar Papers 제목 키워드 기반
Learnable Evolutionary Multi-Objective Combinatorial Optimization via Sequence-to-Sequence Model
Recent advances in learnable evolutionary algorithms have demonstrated the importance of leveraging population distribution information and historical evolutionary trajectories. While significant progress has been made i…
Combinatorial OptimizationDiversityEvolutionary AlgorithmsHybrid Pointer Networks for Traveling Salesman Problems Optimization
In this work, a novel idea is presented for combinatorial optimization problems, a hybrid network, which results in a superior outcome. We applied this method to graph pointer networks [1], expanding its capabilities to …
Combinatorial OptimizationGraph EmbeddingTraveling Salesman ProblemLearning to Branch in Combinatorial Optimization with Graph Pointer Networks
Branch-and-bound is a typical way to solve combinatorial optimization problems. This paper proposes a graph pointer network model for learning the variable selection policy in the branch-and-bound. We extract the graph f…
Combinatorial OptimizationGraph Neural NetworkVariable SelectionPointer Networks with Q-Learning for Combinatorial Optimization
We introduce the Pointer Q-Network (PQN), a hybrid neural architecture that integrates model-free Q-value policy approximation with Pointer Networks (Ptr-Nets) to enhance the optimality of attention-based sequence genera…
Combinatorial OptimizationGraph EmbeddingQ-LearningReinforcement Learning (RL)Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning
In this work, we introduce Graph Pointer Networks (GPNs) trained using reinforcement learning (RL) for tackling the traveling salesman problem (TSP). GPNs build upon Pointer Networks by introducing a graph embedding laye…
Combinatorial OptimizationGraph EmbeddingHierarchical Reinforcement Learningreinforcement-learning+3