A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem
Mathematics · 22.07.2023 · 11 (14) · 3221
DOI: 10.3390/math11143221 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematics, online erschienen am 22.07.2023. Verfasst von Jun Xu und 3 weiteren Autor:innen. Die Arbeit wurde bisher 10-mal zitiert (Crossref) und nennt 41 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Fundamental Research Funds for the Central Universities, Double First-class Talent Introduction Project of China, National Natural Science Foundation of China.
Abstract (Originalsprache)
The JAYA algorithm is a population-based meta-heuristic algorithm proposed in recent years which has been proved to be suitable for solving global optimization and engineering optimization problems because of its simplicity, easy implementation, and guiding characteristic of striving for the best and avoiding the worst. In this study, an improved discrete JAYA algorithm based on reinforcement learning and simulated annealing (QSA-DJAYA) is proposed to solve the well-known traveling salesman problem in combinatorial optimization. More specially, firstly, the basic Q-learning algorithm in reinforcement learning is embedded into the proposed algorithm such that it can choose the most promising transformation operator for the current state to update the solution. Secondly, in order to balance the exploration and exploitation capabilities of the QSA-DJAYA algorithm, the Metropolis acceptance criterion of the simulated annealing algorithm is introduced to determine whether to accept candidate solutions. Thirdly, 3-opt is applied to the best solution of the current iteration at a certain frequency to improve the efficiency of the algorithm. Finally, to evaluate the performance of the QSA-DJAYA algorithm, it has been tested on 21 benchmark datasets taken from TSPLIB and compared with other competitive algorithms in two groups of comparative experiments. The experimental and the statistical significance test results show that the QSA-DJAYA algorithm achieves significantly better results in most instances.
Förderung
- Fundamental Research Funds for the Central Universities
- Double First-class Talent Introduction Project of China
- National Natural Science Foundation of China
Zitieren
APA
Xu, J., Hu, W., Gu, W., & Yu, Y. (2023). A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem. Mathematics, 11(14), 3221. https://doi.org/10.3390/math11143221
Vancouver
Xu J, Hu W, Gu W, Yu Y. A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem. Mathematics. 2023;11(14):3221. doi:10.3390/math11143221
BibTeX
@article{Xu2023,
author = {Xu, Jun and Hu, Wei and Gu, Wenjuan and Yu, Yongguang},
title = {A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem},
journal = {Mathematics},
year = {2023},
volume = {11},
number = {14},
pages = {3221},
doi = {10.3390/math11143221}
}
EUVIMED