EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

A Discrete JAYA Algorithm Based on Reinforcement Learning and Simulated Annealing for the Traveling Salesman Problem

Jun Xu, Wei Hu, Wenjuan Gu, Yongguang Yu

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.

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →