An Optimal Cooling Schedule Using a Simulated Annealing Based Approach
- 1 Department of Computer Science, Catholic University College of Ghana, Sunyani, Ghana
- 2 Department of Mathematics, College of Science, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana
- 3 Department of Mathematics, College of Science, Kwame Nkrumah University of Science and Technology, Kumasi, Ghana
Abstract
Simulated annealing (SA) has been a very useful stochastic method for solving problems of multidimensional global optimization that ensures convergence to a global optimum. This paper proposes a variable cooling factor (VCF) model for simulated annealing schedule as a new cooling scheme to determine an optimal annealing algorithm called the Powell-simulated annealing (PSA) algorithm. The PSA algorithm is aimed at speeding up the annealing process and also finding the global minima of test functions of several variables without calculating their derivatives. It has been applied and compared with the SA algorithm and Nelder and Mead Simplex (NMS) methods on Rosenbrock valleys in 2 dimensions and multiminima functions in 3, 4 and 8 dimensions. The PSA algorithm proves to be more reliable and always able to find the optimum or a point very close to it with minimal number of iterations and computational time. The VCF compares favourably with the Lundy and Mees, linear, exponential and geometric cooling schemes based on their relative cooling rates. The PSA algorithm has also been programmed to run on android smartphone systems (ASS) that facilitates the computation of combinatorial optimization problems.
- Lombardi, A.M. (2015) Estimation of the Parameters of ETAS Models by Simulated Annealing. Scientific Reports, 5, Article ID: 8417. https://doi.org/10.1038/srep08417
- Kirkpatrick, S., Gelatt, J.C.D. and Vecchi, M.P. (1983) Optimization by Simulated Annealing. Science, 220, 671-680. http://dx.doi.org/10.1126/science.2204598.671
- Ledesma, S., Avina, G. and Sanchez, R. (2008) Practical Considerations for Simulated Annealing Implementation. In: Ming, C., Ed., Simulated Annealing, InTech, 401-420. http://cdn.intechopen.com/pdfs/4631.pdf
- Nikolaev, A.G., Jacobson, S.H. and Johnson, A.W. (2003) Simulated Annealing. In: Gendreau, M. and Potvin, J.-Y., Eds., Handbook of Metaheuristics, 2nd Edition, Springer, New York, 1-39.
- Henderson, D., Jacobson, S. and Johnson, A. (2003) The Theory and Practice of Simulated Annealing. International Series in Operations Research & Management Science, 57, 287-319. https://doi.org/10.1007/0-306-48056-5_10
- van Laarhoven, P.J.M. and Aarts, E.H.L. (1987) Simulated Annealing: Theory and Applications. Reidel, Dordrecht. https://doi.org/10.1007/978-94-015-7744-1
- Aarts, E.H.L. and Korst, J.H.M. (1989) Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. John Wiley & Sons, Chichester.
- Bryan, K., Cunningham, P. and Bolshakova, N. (2006) Application of Simulated Annealing to the Bi-Clustering of Gene Expression Data. IEEE Transactions on Information Technology Biomedicine, 10, 519-525. https://doi.org/10.1109/TITB.2006.872073
- Tiwari, M. and Cosman, P.C. (2008) Selection of Long-Term Reference Frames in Dual-Frame Video Coding Using Simulated Annealing. IEEE Signal Processing Letters, 15, 249-252. https://doi.org/10.1109/LSP.2007.914928
- Thompson, D.R. and Bilbro, G.L. (2005) Sample-Sort Simulated Annealing. IEEE Transactions on Systems, Man, and Cybernetics—Part B: Cybernetics, 35, 632. https://doi.org/10.1109/TSMCB.2005.843972
- Koziel, S. and Yang, X.-S. (2011) Computational Optimization: An Overview. In: Koziel, S. and Yang, X.-S., Eds., Computational Optimization Methods and Algorithms, Springer-Verlag, Berlin.
- Nelder, J.A. and Mead, R. (1965) A Simplex Method for Function Minimization. Computer Journal, 7, 308-313. https://doi.org/10.1093/comjnl/7.4.308
- Powell, M.J.D. and Fletcher, R. (1964) A Rapidly Convergent Descent Method for Minimization. Computer Journal, 6, 163-168.