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.
Acknowledgements
We thank the Directorate General of Scientific Research and Technological Development, Ministry of Higher Education and Scientific Research, Algeria, as a sponsoring institution.
References
[1] A. Aloui and M. Ourbih-Tari, The use of refined descriptive sampling and applications in parallel Monte Carlo simulation, Comput. Inform. 30 (2011), no. 4, 681–700. Search in Google Scholar
[2] A. Aloui, A. Zioui, M. Ourbih-Tari and A. Alioui, A general purpose module using refined descriptive sampling for installation in simulation systems, Comput. Statist. 30 (2015), no. 2, 477–490. 10.1007/s00180-014-0545-7Search in Google Scholar
[3] L. Baghdali-Ourbih, M. Ourbih-Tari and A. Dahmani, Implementing refined descriptive sampling into three-phase discrete-event simulation models, Comm. Statist. Simulation Comput. 46 (2017), no. 5, 4035–4049. 10.1080/03610918.2015.1085557Search in Google Scholar
[4] L. Baiche and M. Ourbih-Tari, Large-sample variance of simulation using refined descriptive sampling: Case of independent variables, Comm. Statist. Theory Methods 46 (2017), no. 1, 510–519. 10.1080/03610926.2014.997362Search in Google Scholar
[5] H. Bayram and R. Şahin, A new simulated annealing approach for travelling salesman problem, Math. Comput. Appl. 18 (2013), no. 3, 313–322. 10.3390/mca18030313Search in Google Scholar
[6] M. Boubalou, M. Ourbih-Tari, A. Aloui and A. Zioui, Comparing M/G/1 queue estimators in Monte Carlo simulation through the tested generator “getRDS” and the proposed “getLHS” using variance reduction, Monte Carlo Methods Appl. 25 (2019), no. 2, 177–186. 10.1515/mcma-2019-2033Search in Google Scholar
[7] B. Cakir, F. Altiparmak and B. Dengiz, Multi-objective optimization of stochastic assembly line balancing: A hybrid simulated annealing algorithm, Comput. Indust. Eng. 60 (2011), 376–384. 10.1016/j.cie.2010.08.013Search in Google Scholar
[8] V. Černý, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm, J. Optim. Theory Appl. 45 (1985), no. 1, 41–51. 10.1007/BF00940812Search in Google Scholar
[9] I. T. Dimov, Monte Carlo Methods for Applied Scientists, World Scientific, Hackensack, 2008. 10.1142/2813Search in Google Scholar
[10] G. Dueck and T. Scheuer, Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing, J. Comput. Phys. 90 (1990), no. 1, 161–175. 10.1016/0021-9991(90)90201-BSearch in Google Scholar
[11] R. W. Eglese, Simulated annealing: a tool for operational research, European J. Oper. Res. 46 (1990), no. 3, 271–281. 10.1016/0377-2217(90)90001-RSearch in Google Scholar
[12] A. E. S. Ezugwu, A. O. Adewumi and M. E. Frincu, Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem, Expert Syst. Appl 77 (2017), 189–210. 10.1016/j.eswa.2017.01.053Search in Google Scholar
[13] X. Geng, Z. Chen, W. Yang, D. Shi and K. Zhao, Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search, Appl. Soft Comput. 11 (2011), 3680–3689. 10.1016/j.asoc.2011.01.039Search in Google Scholar
[14] J. Helton and F. Davis, Latin hypercube sampling and the propagation of uncertainty in analyses of complex systems, Reliab. Eng. Syst. Safety 81 (2003), 23–69. 10.2172/806696Search in Google Scholar
[15]
K. Idjis, M. Ourbih-Tari and L. Baghdali-Ourbih,
Variance reduction in
[16] L. Ingber, Very fast simulated re-annealing, Math. Comput. Modelling 12 (1989), no. 8, 967–973. 10.1016/0895-7177(89)90202-1Search in Google Scholar
[17] S. Kirkpatrick, C. D. Gelatt, Jr. and M. P. Vecchi, Optimization by simulated annealing, Science 220 (1983), no. 4598, 671–680. 10.1126/science.220.4598.671Search in Google Scholar PubMed
[18] S. W. Lin, V. F. Yu and S. Y. Chou, Solving the truck and trailer routing problem based on a simulated annealing heuristic, Comput. Oper. Res. 36 (2009), 1683–1692. 10.1016/j.cor.2008.04.005Search in Google Scholar
[19] Y. Lin, Z. Bian and X. Liu, Developing a dynamic neighbourhood structure for a adaptive hybrid simulated annealing-tabu search algorithm to solve the symmetrical traveling salesman problem, Appl. Soft Comput. 49 (2016), 937–952. 10.1016/j.asoc.2016.08.036Search in Google Scholar
[20] P. Lucic and D. Teodorovic, Simulated annealing for the multi-objective aircrew roistering problem, Transp. Res. 33 (1999), 19–45. Search in Google Scholar
[21] M. Ourbih-Tari and A. Aloui, Sampling methods and parallelism into Monte Carlo simulation, J. Statist. Adv. Theory Appl. 2 (2009), 169–192. Search in Google Scholar
[22] M. Ourbih-Tari and S. Guebli, A comparison of methods for selecting values of simulation input variables, ESAIM Probab. Stat. 19 (2015), 135–147. 10.1051/ps/2014020Search in Google Scholar
[23] M. Ourbih-Tari, A. Zioui and A. Aloui, Variance reduction in the simulation of a stationary M/G/1 queuing system using refined descriptive sampling, Comm. Statist. Simulation Comput. 46 (2017), no. 5, 3504–3515. 10.1080/03610918.2015.1096374Search in Google Scholar
[24] K. K. Sabelfeld, Random walk on spheres algorithm for solving transient drift-diffusion-reaction problems, Monte Carlo Methods Appl. 23 (2017), no. 3, 189–212. 10.1515/mcma-2017-0113Search in Google Scholar
[25] K. K. Sabelfeld and G. Eremeev, A hybrid kinetic-thermodynamic Monte Carlo model for simulation of homogeneous burst nucleation, Monte Carlo Methods Appl. 24 (2018), no. 3, 193–202. 10.1515/mcma-2018-0017Search in Google Scholar
[26] K. K. Sabelfeld and N. A. Simonov, Stochastic Methods for Boundary Value Problems. Numerics for High-Dimensional PDEs and Applications, De Gruyter, Berlin, 2016. 10.1515/9783110479454Search in Google Scholar
[27] R. Sahin, A Simulated annealing algorithm for solving the bi-objective facility layout problem, Expert Syst. Appl. 38 (2011), no. 4, 4460–4465. 10.1016/j.eswa.2010.09.117Search in Google Scholar
[28] H. Szu and R. Hartley, Fast simulated annealing, Phys. Lett. A 122 (1987), 157–162. 10.1063/1.36250Search in Google Scholar
[29]
K. Tamiti, M. Ourbih-Tari, A. Aloui and K. Idjis,
The use of variance reduction, relative error and bias in testing the performance of
[30] M. Tari and A. Dahmani, Refined descriptive sampling: A better approach to Monte Carlo simulation, Simul. Model. Practice Theory 14 (2006), 143–160. 10.1016/j.simpat.2005.04.001Search in Google Scholar
[31] Z. Wang, X. Geng and Z. Shao, An effective simulated annealing algorithm for solving the traveling salesman problem, Comput. Theoret. Nanoscience 6 (2009), 1680–1686. 10.1166/jctn.2009.1230Search in Google Scholar
[32] S. Zhan, J. Lin, Z. Zhang and Y. Zhong, List-based simulated annealing algorithm for traveling salesman problem, Comput. Intell. Neurosci. 2016 (2016), 8–18. 10.1155/2016/1712630Search in Google Scholar PubMed PubMed Central
[33] R. Zhang and C. Wu, A hybrid immune simulated annealing algorithm for job shop scheduling problem, Appl. Soft Comput. 10 (2010), 79–89. 10.1016/j.asoc.2009.06.008Search in Google Scholar
[34] D. Zhao, W. Xiong and Z. Shu, Simulated annealing with a hybrid local search for solving the traveling salesman problem, J. Comput. Theor. Nanosci. 12 (2015), 1165–1169. 10.1166/jctn.2015.3868Search in Google Scholar
[35] A.-H. Zhou, L.-P. Zhu, B. Hu, S. Deng, Y. Song, H. Qiu and S. Pan, Traveling salesman problem algorithm based on simulated annealing and gene-expression programming, Information 10 (2019), 10.3390/info10010007. 10.3390/info10010007Search in Google Scholar
© 2022 Walter de Gruyter GmbH, Berlin/Boston