A Mushy State Simulated Annealing

Document Type : Research Article

Authors

Abstract

It is a long time that the Simulated Annealing (SA) procedure has been introduced as a model-free optimization for solving NP-hard problems. Improvements from the standard SA in the recent decade mostly concentrate on combining its original algorithm with some heuristic methods. These modifications are rarely happened to the initial condition selection methods from which the annealing schedules or the time schedule itself start. There are several parameters in the process of annealing, the adjustment of which affects the overall performance. This paper focuses on the importance of initial temperature and then proposes a lower temperature with low energy to speed up the process, using an auxiliary memory to buffer the best solution. Such an annealing indeed starts from a “mushy state” rather than a quite liquid molten material. The mushy state characteristics indeed depends upon the problems that SA is being applied to solve for. In this paper, the Mushy State Simulated Annealing (MSSA) is fully developed and then applied to the popular Traveling Salesman Problem (TSP). The mushy state may be obtained by some simple methods like crossover elimination. A very fast version of a Wise Traveling Salesman, who starts from a randomly chosen city and seeks for the nearest one as the next, is also applied to initiate SA by a low-energy, low-temperature state. This fast method results in quite accurate solutions compared to the methods recently cited in the literature. 

Keywords

References

[1]     S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing”, Science, vol. 220, pp. 671–680, 1983.
[2]     M. R. Garey and D. S. Johnson, "Computers and Intractability: A Guide to the Theory of NP-Completeness", New York: Freeman, 1979.
[3]     Herbert H. Tsang, and Kay C. Wiese, “The Significance of Thermodynamic Models in the Accuracy Improvement of RNA Secondary Structure Prediction Using Permutation-based Simulated Annealing”, IEEE Congress on Evolutionary Computation, (CEC 2007).
[4]     Ming-Hao Hung, Li-Sun Shu, Shinn-Jang Ho, Shiow-Fen Hwang, and Shinn-Ying Ho, “A Novel Intelligent Multiobjective Simulated Annealing Algorithm for Designing Robust PID Controllers”, IEEE Transactions on Systems, Man, and Cybernetics—PART A: Systems and Humans, Vol. 38, No. 2, pp. 319-330, (Mar. 2008).
[5]     Kevin I. Smith, Richard M. Everson, Jonathan E. Fieldsend , Chris Murphy, and Rashmi Misra, “Dominance-Based Multiobjective Simulated Annealing”, IEEE Transactions on E Evolutionary Computation, Vol. 12, No. 3, pp. 323-341, (June 2008).
[6]     S. A. Kravitz and R. A. Rutenbar, “Placement by simulated annealing on a multiprocessor,” IEEE Trans. Computer-Aided Design Integr. CircuitsSyst., vol. 6, no. 4, pp. 534–549, Jul. 1987.
[7]     E. Aarts and J. Korst, "Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing", New York: Wiley, 1989.
[8]     Joshua W. Pepper, Bruce L. Golden, and Edward A. Wasil, “Solving the Traveling Salesman Problem With Annealing-Based Heuristics: A Computational Study”, IEEE Transactions on Systems, Man, and Cybernetics—PART A: Systems and Humans, Vol. 32, No. 1, (Jan. 2002).
[9]     Hyeon-Joong Cho, Se-Young Oh and Doo-Hyun Choi, “Population-oriented simulated annealing technique based on local Temperature concept”, ELECTRONICS LETTERS Vol. 34 No. 3 pp.312-313 (5th February 1998).
[10]  Percy P. C. Yip, and Yoh-Han Pao, “Combinatorial Optimization with Use of Guided Evolutionary Simulated Annealing”, IEEE Transactions on Neural Networks, Vol. 6. No. 2, pp. 290-295 (March 1995).
[11]  Andrew Soh, “Parallel N-aray Speculative Computation of Simulated Annealing”, IEEE Transactions on Parallel and Distributed Systems, Vol. 6, No. 10, pp. 997-1005 (Oct. 1995).
[12]  D. C. W. Pao, S. P. Lam and A. S. Fong, “Parallel implementation of simulated annealing using transaction processing”, IEE Proc-Computer Digit. Tech., Vol. 146, No. 2, pp. 107-113, (March 1999).
[13]  Feng-Tse Lin, Cheng-Yan Kao, and Ching-Chi Hsu, “Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems”, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 23. No. 6, (Nov./Dec. 1993)
[14]  Dale R. Thompson  and Griff L. Bilbro, “Sample-Sort Simulated Annealing”, IEEE Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics, Vol. 35, No. 3, pp. 625-632 (Jun. 2005).
[15]  Hao Chen, Nicholas S. Flann, and Daniel W. Watson, “Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm”, IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 2, pp.126-136 (February 1998).
[16]  K.L. Wong A.G.Constantinides, “Speculative parallel simulated annealing with acceptance prediction”, Electronic Letters, Vol. 34, No. 3, (February 1998), pp. 312-313.
[17]  L. Ingber and B. Rosen, “Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison”, Mathematical Computer Modeling, vol. 16, no. 11, (1992), pp. 87-100.
[18]  Lipo Wang, Sa Li, Fuyu Tian, and Xiuju Fu, “A Noisy Chaotic Neural Network for Solving Combinatorial Optimization Problems: Stochastic Chaotic Simulated Annealing”, Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics, Vol. 34, No. 5 pp. 2119-2125, (Oct. 2004).
[19]  Yuyao He, “Chaotic Simulated Annealing With Decaying Chaotic Noise”, IEEE Transactions on Neural Networks, Vol. 13, No. 6, (November 2002), pp. 1526-1531.
[20]  Sitao Wu and Tommy W. S. Chow, “Self-Organizing and Self-Evolving Neurons: A New Neural Network for Optimization”, IEEE Transactions on Neural Networks, VOL. 18, NO. 2, (March 2007), pp. 385-396.
[21]  J. Jang, C. Sun, E. Mizutani, “Neuro-Fuzzy and Soft Computing”, Proc. of the Prentice Hall 1997.
[22]  G. Dueck and T. Scheuer, “Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing,” J. Computer. Phys., vol. 90, 1990, pp. 161–175.
[23]  G. Reinelt. Tsplib95, 1995. Available at: http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95.
[24]  M. Saadatmand-Tarzjan, M. Khademi, M. R. Akbarzadeh-T., and H. Abrishami Moghaddam, “A Novel Constructive-Optimizer Neural Network for the Traveling Salesman Problem” IEEE Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics, Vol. 37, No. 4, (Aug. 2007).
[25]  Necati Aras, I. Kuban Altınel, and John Oommen, “A Kohonen-Like Decomposition Method for the Euclidean Traveling Salesman Problem Knies_Decompose”, IEEE Transactions on Neural Networks, Vol. 14, No. 4, (July 2003).
[26]  Chun-Hung Cheng, Wing-Kin Lee, and Kam-Fai Wong, “A Genetic Algorithm-Based Clustering Approach for Database Partitioning”, IEEE Transactions on Systems, Man, and Cybernetics—PART C: Applications and Reviews, Vol. 32, No. 3, (Aug. 2002).
[27]  Kwong-Sak Leung, Hui-Dong Jin, and Zong-Ben Xu, “An expanding Self-Organizing neural network for the traveling salesman problem”, Neurocomputing, Vol. 62, pp. 267-292, (Dec. 2004).
[28]  Hui-Dong Jin, Kwong-Sak Leung, Man-Leung Wong and Zong-Ben Xu, “An Efficient Self-Organizing Map Designed by Genetic Algorithms for the Traveling Salesman Problem”, IEEE Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics, Vol. 33, No. 6, (Dec. 2003), pp. 877-888.
[29]  J. C. Creput, A. Koukam, “A memetic neural network for the Euclidean traveling salesman problem”, Neurocomputing Accepted 22 (January 2008).
[30]  Hamed Shakouri G., Kambiz Shojaee, Mojtaba Behnam T. " The Wise Experiencing Traveling Salesman (WETS): Introduction to a simple evolutionary solution for the problem" IEEE Congress on Evolutionary Computation CEC 2009 18-21 (May 2009) Trondheim, Norway.
[31]  Hamed Shakouri G., kambiz shojaee, " Investigation on the choice of the initial temperature in the Simulated Annealing: A Mushy State SA for TSP " 17th Mediterranean Conference on Control Automation, MED'09 Thessaloniki, Greece on June 24-26, 2009.
AUT Journal of Modeling and Simulation
Volume 43, Issue 2 - Serial Number 2
November 2011
Pages 59-70

Files

Share

How to cite

Statistics