Refined descriptive sampling simulated annealing algorithm for solving the traveling salesman problem

Cherabli Meriem (), Ourbih-Tari Megdouda () and Boubalou Meriem ()
Additional contact information
Cherabli Meriem: Centre Universitaire Morsli Abdellah de Tipaza, 42000, Tipaza; and Laboratoire de Mathématiques Appliqués, FSE, Université de Bejaia, 06000, Bejaia, Algeria
Ourbih-Tari Megdouda: Centre Universitaire Morsli Abdellah de Tipaza, 42000, Tipaza; and Laboratoire de Mathématiques Appliqués, FSE, Université de Bejaia, 06000, Bejaia, Algeria
Boubalou Meriem: Centre Universitaire Morsli Abdellah de Tipaza, 42000, Tipaza; and Laboratoire de Mathématiques Appliqués, FSE, Université de Bejaia, 06000, Bejaia, Algeria

Monte Carlo Methods and Applications, 2022, vol. 28, issue 2, 175-188

Abstract: The simulated annealing (SA) algorithm is a popular intelligent optimization algorithm which has been successfully applied in many fields. In this paper, we propose a software component under the Windows environment called goRDS which implements a refined descriptive sampling (RDS) number generator of high quality in the MATLAB programming language. The aim of this generator is to sample random inputs through the RDS method to be used in the Simple SA algorithm with swap operator. In this way, the new probabilistic meta-heuristic algorithm called RDS-SA algorithm will enhance the simple SA algorithm with swap operator, the SA algorithm and possibly its variants with solutions of better quality and precision. Towards this goal, the goRDS generator was highly tested by adequate statistical tests and compared statistically to the random number generator (RNG) of MATLAB, and it was proved that goRDS has passed all tests better. Simulation experiments were carried out on the benchmark traveling salesman problem (TSP) and the results show that the solutions obtained with the RDS-SA algorithm are of better quality and precision than those of the simple SA algorithm with swap operator, since the software component goRDS represents the probability behavior of the SA input random variables better than the usual RNG.

Keywords: Monte Carlo methods; random number generator; variance reduction; simulated annealing algorithm; traveling salesman problem (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma-2022-2113 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:28:y:2022:i:2:p:175-188:n:9

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma-2022-2113

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().