Generalized Simulated Annealing Algorithm for Matlab
Main Article Content
Keywords
Simulated annealing, efficiency, optimization, GSA, Matlab
Abstract
Many problems in biology, physics, mathematics, and engineering, demand the determination of the global optimum of multidimensional functions. Simulated annealing is a meta-heuristic method that solves global optimization problems. There are three types of simulated annealing: i) classical simulated annealing; ii) fast simulated annealing and iii) generalized simulated annealing. Among them, generalized simulated annealing is the most efficient. Matlab is one of the most widely software used in numeric simulation and scientific computation. Matlab optimization toolbox provides a variety of functions able to solve many complex problems. In this article, the generalized simulated annealing method was described, the GSA function that contains this method was applied to some mathematical problems were solved in order to evaluate the efficiency of GSA with respect to some of Matlab optimization functions. As a result, it was found that the GSA function not only manages to be effective in its convergence to the global optimum but also it does so quickly. Likewise, it was observed that, in general terms, GSA was more efficient than the functions with which it was compared. Therefore, it can be concluded that the GSA function is a novel and effective alternative for addressing optimization problems using Matlab.
Downloads
Download data is not yet available.
References
[1] L. Ingber, “Simulated annealing: Practice versus theory,” Mathematical and Computer Modelling, vol. 18, no. 11, pp. 29 – 57, 1993. [Online]. Available: https://doi.org/10.1016/0895-7177(93)90204-C
[2] C. Carletti, P. Meoli, and W. R. Cravero, “A modified simulated annealing algorithm for parameter determination for a hybrid virtual model,” Physics in Medicine and Biology, vol. 51, no. 16, pp. 3941–3952, jul 2006.
[3] R. V. Vidal, Applied simulated annealing. Springer, 1993, vol. 396.
[4] W. Y. Yang, W. Cao, T.-S. Chung, J. Morris et al., Applied numerical methods using MATLAB. Wiley Online Library, 2005.
[5] A. Barbato and A. Capone, “Optimization models and methods for demandside management of residential users: A survey,” Energies, vol. 7, no. 9, pp. 5787–5824, sep 2014. [Online]. Available: https://doi.org/10.3390/en7095787
[6] O. Erdinc, Optimization in renewable energy systems: recent perspectives. Butterworth-Heinemann, 2017.
[7] C. Tsallis and D. A. Stariolo, “Generalized simulated annealing,” Physica A: Statistical Mechanics and its Applications, vol. 233, no. 1-2, pp. 395–406, nov 1996. [Online]. Available: https://doi.org/10.1016/s0378-4371(96)00271-3
[8] Y. Xiang, S. Gubian, B. Suomela, and J. Hoeng, “Generalized simulated annealing for global optimization: The GenSA package,” The R Journal, vol. 5, no. 1, p. 13, 2013. [Online]. Available: https://doi.org/10.32614/rj-2013-002
[9] G. Giorgi and K. Yamashita, Theoretical Modeling of Organohalide Perovskites for Photovoltaic Applications. CRC Press, 2017.
[10] M. D. de Andrade, K. C. Mundim, and L. A. C. Malbouisson, “Convergence of the generalized simulated annealing method with independent parameters for the acceptance probability, visitation distribution, and temperature functions,” International Journal of Quantum Chemistry, vol. 108, no. 13, pp. 2392–2397, 2008. [Online]. Available: https://doi.org/10.1002/qua.21736
[11] J. E. Dennis, D. M. Gay, and R. E. Welsch, “An adaptive nonlinear least square algorithm,” 1977.
[12] D. E. Golberg, “Genetic algorithms in search optimization & machine learning. 1953.
[13] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” in World Scientific Lecture Notes in Physics. WORLD SCIENTIFIC, nov 1986, pp. 339–348. [Online]. Available: https://doi.org/10.1142/9789812799371_0035
[14] F. Glover, M. Laguna, E. Taillard, and D. de Werra, Tabu search. Springer, 1993.
[15] T. Schanze, “An exact d-dimensional tsallis random number generator for generalized simulated annealing,” Computer Physics Communications, vol. 175, no. 11-12, pp. 708–712, dec 2006. [Online]. Available: https://doi.org/10.1016/j.cpc.2006.07.012
[16] J. Deng, C. Chang, and Z. Yang, “An exact random number generator for visiting distribution in gsa,” energy, vol. 2, no. 2, 1987.
[17] M. A. Moret, P. G. Pascutti, P. M. Bisch, and K. C. Mundim, “Stochastic molecular optimization using generalized simulated annealing,” Journal of Computational Chemistry, vol. 19, no. 6, pp. 647–657, apr 1998.
[Online]. Available: https://doi.org/10.1002/(sici)1096-987x(19980430)19:6<647::aid-jcc6>3.0.co;2-r
[18] T. J. P. Penna, “Traveling salesman problem and tsallis statistics,” Physical Review E, vol. 51, no. 1, pp. R1–R3, jan 1995. [Online]. Available: https://doi.org/10.1103/physreve.51.r1
[19] G. Haeser and M. G. Ruggiero, “Aspectos teóricos de simulated annealing e um algoritmo duas fases em otimização global,” Trends in Applied and Computational Mathematics, vol. 9, no. 3, pp. 395–404, 2008.
[20] K.-L. Du and M. Swamy, “Search and optimization by metaheuristics,” Techniques and Algorithms Inspired by Nature; Birkhauser: Basel, Switzerland, 2016.
[21] H. Szu and R. Hartley, “Fast simulated annealing,” Physics Letters A, vol. 122, no. 3-4, pp. 157–162, jun 1987. [Online]. Available: https://doi.org/10.1016/0375-9601(87)90796-1
[22] S. Geman and D. Geman, “Stochastic relaxation, gibbs distributions, and the bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, no. 6, pp. 721–741, nov 1984. [Online]. Available: https://doi.org/10.1109/tpami.1984.4767596
[23] H. Peyvandi, Computational Optimization in Engineering: Paradigms and Applications. BoD–Books on Demand, 2017.
[24] Y. Xiang and X. G. Gong, “Efficiency of generalized simulated annealing,” Physical Review E, vol. 62, no. 3, pp. 4473–4476, sep 2000. [Online]. Available: https://doi.org/10.1103/physreve.62.4473
[25] C. Tsallis, “Possible generalization of boltzmann-gibbs statistics,” Journal of Statistical Physics, vol. 52, no. 1-2, pp. 479–487, jul 1988. [Online]. Available: https://doi.org/10.1007/bf01016429
[26] Y. Xiang, D. Sun, W. Fan, and X. Gong, “Generalized simulated annealing algorithm and its application to the thomson model,” Physics Letters A, vol. 233, no. 3, pp. 216–220, aug 1997. [Online]. Available:
https://doi.org/10.1016/s0375-9601(97)00474-x
[27] Y. Xiang, S. Gubian, and F. Martin, “Generalized simulated annealing,” in Computational Optimization in Engineering-Paradigms and Applications. InTech, 2017.
[28] M. Viswanathan, “Simulation and analysis of white noise in matlab,” Nov. 2019. [Online]. Available: https://www.gaussianwaves.com/2013/11/simulation-and-analysis-of-white-noise-in-matlab/
[29] “Normally distributed random numbers,” 2006. [Online]. Available: https://www.mathworks.com/help/matlab/ref/randn.html
[30] “Gamma random numbers,” 2006. [Online]. Available: https://www.mathworks.com/help/stats/gamrnd.html
[31] “Fmincon function,” 2006. [Online]. Available: https://la.mathworks.com/help/optim/ug/fmincon.html?lang=en
[32] “Lsqnonlin function,” 2006. [Online]. Available: https://la.mathworks.com/help/optim/ug/lsqnonlin.html?lang=en
[33] “Simannelbnd function,” 2007. [Online]. Available: https://la.mathworks.com/help/gads/simulannealbnd.html
[34] “Anonymous functions,” 2006. [Online]. Available: https://la.mathworks.com/help/matlab/matlab_prog/anonymous-functions.html
[35] “Isolated global minimum,” 2006. [Online]. Available: https://www.mathworks.com/help/gads/isolated-global-minimum.html
[36] “Rosenbrock function,” 2006. [Online]. Available: https://la.mathworks.com/help/matlab/ref/fminsearch.html#bvadxhn-6
[37] “Maximing an objective function,” 2006. [Online]. Available: https://www.mathworks.com/help/optim/ug/maximizing-an-objective.html
[2] C. Carletti, P. Meoli, and W. R. Cravero, “A modified simulated annealing algorithm for parameter determination for a hybrid virtual model,” Physics in Medicine and Biology, vol. 51, no. 16, pp. 3941–3952, jul 2006.
[3] R. V. Vidal, Applied simulated annealing. Springer, 1993, vol. 396.
[4] W. Y. Yang, W. Cao, T.-S. Chung, J. Morris et al., Applied numerical methods using MATLAB. Wiley Online Library, 2005.
[5] A. Barbato and A. Capone, “Optimization models and methods for demandside management of residential users: A survey,” Energies, vol. 7, no. 9, pp. 5787–5824, sep 2014. [Online]. Available: https://doi.org/10.3390/en7095787
[6] O. Erdinc, Optimization in renewable energy systems: recent perspectives. Butterworth-Heinemann, 2017.
[7] C. Tsallis and D. A. Stariolo, “Generalized simulated annealing,” Physica A: Statistical Mechanics and its Applications, vol. 233, no. 1-2, pp. 395–406, nov 1996. [Online]. Available: https://doi.org/10.1016/s0378-4371(96)00271-3
[8] Y. Xiang, S. Gubian, B. Suomela, and J. Hoeng, “Generalized simulated annealing for global optimization: The GenSA package,” The R Journal, vol. 5, no. 1, p. 13, 2013. [Online]. Available: https://doi.org/10.32614/rj-2013-002
[9] G. Giorgi and K. Yamashita, Theoretical Modeling of Organohalide Perovskites for Photovoltaic Applications. CRC Press, 2017.
[10] M. D. de Andrade, K. C. Mundim, and L. A. C. Malbouisson, “Convergence of the generalized simulated annealing method with independent parameters for the acceptance probability, visitation distribution, and temperature functions,” International Journal of Quantum Chemistry, vol. 108, no. 13, pp. 2392–2397, 2008. [Online]. Available: https://doi.org/10.1002/qua.21736
[11] J. E. Dennis, D. M. Gay, and R. E. Welsch, “An adaptive nonlinear least square algorithm,” 1977.
[12] D. E. Golberg, “Genetic algorithms in search optimization & machine learning. 1953.
[13] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” in World Scientific Lecture Notes in Physics. WORLD SCIENTIFIC, nov 1986, pp. 339–348. [Online]. Available: https://doi.org/10.1142/9789812799371_0035
[14] F. Glover, M. Laguna, E. Taillard, and D. de Werra, Tabu search. Springer, 1993.
[15] T. Schanze, “An exact d-dimensional tsallis random number generator for generalized simulated annealing,” Computer Physics Communications, vol. 175, no. 11-12, pp. 708–712, dec 2006. [Online]. Available: https://doi.org/10.1016/j.cpc.2006.07.012
[16] J. Deng, C. Chang, and Z. Yang, “An exact random number generator for visiting distribution in gsa,” energy, vol. 2, no. 2, 1987.
[17] M. A. Moret, P. G. Pascutti, P. M. Bisch, and K. C. Mundim, “Stochastic molecular optimization using generalized simulated annealing,” Journal of Computational Chemistry, vol. 19, no. 6, pp. 647–657, apr 1998.
[Online]. Available: https://doi.org/10.1002/(sici)1096-987x(19980430)19:6<647::aid-jcc6>3.0.co;2-r
[18] T. J. P. Penna, “Traveling salesman problem and tsallis statistics,” Physical Review E, vol. 51, no. 1, pp. R1–R3, jan 1995. [Online]. Available: https://doi.org/10.1103/physreve.51.r1
[19] G. Haeser and M. G. Ruggiero, “Aspectos teóricos de simulated annealing e um algoritmo duas fases em otimização global,” Trends in Applied and Computational Mathematics, vol. 9, no. 3, pp. 395–404, 2008.
[20] K.-L. Du and M. Swamy, “Search and optimization by metaheuristics,” Techniques and Algorithms Inspired by Nature; Birkhauser: Basel, Switzerland, 2016.
[21] H. Szu and R. Hartley, “Fast simulated annealing,” Physics Letters A, vol. 122, no. 3-4, pp. 157–162, jun 1987. [Online]. Available: https://doi.org/10.1016/0375-9601(87)90796-1
[22] S. Geman and D. Geman, “Stochastic relaxation, gibbs distributions, and the bayesian restoration of images,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. PAMI-6, no. 6, pp. 721–741, nov 1984. [Online]. Available: https://doi.org/10.1109/tpami.1984.4767596
[23] H. Peyvandi, Computational Optimization in Engineering: Paradigms and Applications. BoD–Books on Demand, 2017.
[24] Y. Xiang and X. G. Gong, “Efficiency of generalized simulated annealing,” Physical Review E, vol. 62, no. 3, pp. 4473–4476, sep 2000. [Online]. Available: https://doi.org/10.1103/physreve.62.4473
[25] C. Tsallis, “Possible generalization of boltzmann-gibbs statistics,” Journal of Statistical Physics, vol. 52, no. 1-2, pp. 479–487, jul 1988. [Online]. Available: https://doi.org/10.1007/bf01016429
[26] Y. Xiang, D. Sun, W. Fan, and X. Gong, “Generalized simulated annealing algorithm and its application to the thomson model,” Physics Letters A, vol. 233, no. 3, pp. 216–220, aug 1997. [Online]. Available:
https://doi.org/10.1016/s0375-9601(97)00474-x
[27] Y. Xiang, S. Gubian, and F. Martin, “Generalized simulated annealing,” in Computational Optimization in Engineering-Paradigms and Applications. InTech, 2017.
[28] M. Viswanathan, “Simulation and analysis of white noise in matlab,” Nov. 2019. [Online]. Available: https://www.gaussianwaves.com/2013/11/simulation-and-analysis-of-white-noise-in-matlab/
[29] “Normally distributed random numbers,” 2006. [Online]. Available: https://www.mathworks.com/help/matlab/ref/randn.html
[30] “Gamma random numbers,” 2006. [Online]. Available: https://www.mathworks.com/help/stats/gamrnd.html
[31] “Fmincon function,” 2006. [Online]. Available: https://la.mathworks.com/help/optim/ug/fmincon.html?lang=en
[32] “Lsqnonlin function,” 2006. [Online]. Available: https://la.mathworks.com/help/optim/ug/lsqnonlin.html?lang=en
[33] “Simannelbnd function,” 2007. [Online]. Available: https://la.mathworks.com/help/gads/simulannealbnd.html
[34] “Anonymous functions,” 2006. [Online]. Available: https://la.mathworks.com/help/matlab/matlab_prog/anonymous-functions.html
[35] “Isolated global minimum,” 2006. [Online]. Available: https://www.mathworks.com/help/gads/isolated-global-minimum.html
[36] “Rosenbrock function,” 2006. [Online]. Available: https://la.mathworks.com/help/matlab/ref/fminsearch.html#bvadxhn-6
[37] “Maximing an objective function,” 2006. [Online]. Available: https://www.mathworks.com/help/optim/ug/maximizing-an-objective.html
Article Sidebar
Published
Nov 29, 2019
Article Details
How to Cite
Wilches Visbal, J. H., & Martins Da Costa, A. (2019). Generalized Simulated Annealing Algorithm for Matlab. Ingeniería Y Ciencia, 15(30), 117–140. https://doi.org/10.17230/ingciencia.15.30.6
Issue
Section
Articles
Supporting Agencies
Universidad del Magdalena, Fundação Amparo à Pesquisa do Estado de São Paulo, Coordenação de Aperfeiçoamento de Pessoas do Nível Superior
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).