Dataset Information

Hybrid pointer networks for traveling salesman problems optimization.

ABSTRACT: In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer's encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GPN). For the sack of fairness, we used the same setting as proposed in GPN paper. The experimental results show that our network significantly outperforms the original graph pointer network for small and large-scale problems. For example, it reduced the cost for travelling salesman problems with 50 cities/nodes (TSP50) from 5.959 to 5.706 without utilizing 2opt. Moreover, we solved benchmark instances of variable sizes using HPN and GPN. The cost of the solutions and the testing times are compared using Linear mixed effect models. We found that our model yields statistically significant better solutions in terms of the total trip cost. We make our data, models, and code publicly available https://github.com/AhmedStohy/Hybrid-Pointer-Networks.

SUBMITTER: Stohy A

PROVIDER: S-EPMC8670669 | biostudies-literature | 2021

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

Hybrid pointer networks for traveling salesman problems optimization.

Stohy Ahmed A Abdelhakam Heba-Tullah HT Ali Sayed S Elhenawy Mohammed M Hassan Abdallah A AA Masoud Mahmoud M Glaser Sebastien S Rakotonirainy Andry A

PloS one 20211214 12

In this work, we proposed a hybrid pointer network (HPN), an end-to-end deep reinforcement learning architecture is provided to tackle the travelling salesman problem (TSP). HPN builds upon graph pointer networks, an extension of pointer networks with an additional graph embedding layer. HPN combines the graph embedding layer with the transformer's encoder to produce multiple embeddings for the feature context. We conducted extensive experimental work to compare HPN and Graph pointer network (GP ...[more]

PMID: 34905571

Similar Datasets

Project description:This research paper develops a novel hybrid approach, called hybrid particle swarm optimization-teaching-learning-based optimization (hPSO-TLBO), by combining two metaheuristic algorithms to solve optimization problems. The main idea in hPSO-TLBO design is to integrate the exploitation ability of PSO with the exploration ability of TLBO. The meaning of "exploitation capabilities of PSO" is the ability of PSO to manage local search with the aim of obtaining possible better solutions near the obtained solutions and promising areas of the problem-solving space. Also, "exploration abilities of TLBO" means the ability of TLBO to manage the global search with the aim of preventing the algorithm from getting stuck in inappropriate local optima. hPSO-TLBO design methodology is such that in the first step, the teacher phase in TLBO is combined with the speed equation in PSO. Then, in the second step, the learning phase of TLBO is improved based on each student learning from a selected better student that has a better value for the objective function against the corresponding student. The algorithm is presented in detail, accompanied by a comprehensive mathematical model. A group of benchmarks is used to evaluate the effectiveness of hPSO-TLBO, covering various types such as unimodal, high-dimensional multimodal, and fixed-dimensional multimodal. In addition, CEC 2017 benchmark problems are also utilized for evaluation purposes. The optimization results clearly demonstrate that hPSO-TLBO performs remarkably well in addressing the benchmark functions. It exhibits a remarkable ability to explore and exploit the search space while maintaining a balanced approach throughout the optimization process. Furthermore, a comparative analysis is conducted to evaluate the performance of hPSO-TLBO against twelve widely recognized metaheuristic algorithms. The evaluation of the experimental findings illustrates that hPSO-TLBO consistently outperforms the competing algorithms across various benchmark functions, showcasing its superior performance. The successful deployment of hPSO-TLBO in addressing four engineering challenges highlights its effectiveness in tackling real-world applications.

Dataset Information

Hybrid pointer networks for traveling salesman problems optimization.

Publications

Hybrid pointer networks for traveling salesman problems optimization.

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure

Tweets