Shojaee, K., Shakouri, H., Menhaj, M. (2010). A Mushy State Simulated Annealing. Journal of Industrial and Systems Engineering, 4(3), 193-208.

Kambiz Shojaee; Hamed Shakouri; Mohammad Bagher Menhaj. "A Mushy State Simulated Annealing". Journal of Industrial and Systems Engineering, 4, 3, 2010, 193-208.

Shojaee, K., Shakouri, H., Menhaj, M. (2010). 'A Mushy State Simulated Annealing', Journal of Industrial and Systems Engineering, 4(3), pp. 193-208.

Shojaee, K., Shakouri, H., Menhaj, M. A Mushy State Simulated Annealing. Journal of Industrial and Systems Engineering, 2010; 4(3): 193-208.

^{1}Low-Power High-Performance Nanosystems Laboratory, School of Electrical and Computer Engineering, University of Tehran

^{2}Industrial Engineering Department, University of Tehran, Tehran, Iran

^{3}Electrical Engineering Department, Amirkabir University of Technology

Abstract

It is a long time that the Simulated Annealing (SA) procedure is 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 starts or the time schedule itself. 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 depends on 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.

[1] Aarts E., Korst J. (1989), Simulated Annealing and Boltzmann Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing; Wiley, New York. [2] Aras N., Altınel I.K., Oommen J. (2003), A Kohonen-Like Decomposition Method For The Euclidean Traveling Salesman Problem Knies-Decompose; IEEE Transactions on Neural Network 14(4). [3] Chen H., Flann S.N., Watson W.D. (1998), Parallel Genetic Simulated Annealing: A Massively Parallel SIMD Algorithm; IEEE Transactions on Parallel and Distributed Systems 9(2); 126-136. [4] Cheng C.-H., Lee W.-K., Wong K.-F. (2002), A Genetic Algorithm-Based Clustering Approach for Database Partitioning; IEEE Transactions on Systems, Man, and Cybernetics—PART C: Applications and Reviews 32(3). [5] Cho H.J., Young Oh S., Choi D.-H. (1998), Population-oriented simulated annealing technique based on local Temperature concept; Electronics Letters 34(3); 312-313. [6] Creput J.C., Koukam A. (2008), A memetic neural network for the Euclidean traveling salesman problem; Neurocomputing. [7] Dueck G., Scheuer T. (1990), Threshold accepting: A general purpose optimization algorithm appearing superior to simulated annealing; J. Computer. Phys. 90; 161–175.

[8] Garey M.R., Johnson D.S. (1979), Computers and Intractability: A Guide to the Theory of NPCompleteness; Freeman, New York. [9] He Y. (2002), Chaotic Simulated Annealing With Decaying Chaotic Noise; IEEE Transactions on Neural Networks 13(6); 1526-1531. [10] Hung M.-H., Shu L.-S., Ho S.-J., Hwang S.-F., Ho S.-Y. (2008); A Novel Intelligent Multiobjective Simulated Annealing Algorithm for Designing Robust PID Controllers; Proceeding of IEEE Transactions on Systems, Man, and Cybernetics—PART A: Systems and Humans 38(2); 319-330. [11] Ingber L., Rosen B. (1992), Genetic Algorithms and Very Fast Simulated Reannealing: A Comparison; Mathematical Computer Modeling 16(11); 87-100. [12] Jang J., Sun C., Mizutani E. (1997), Neuro-Fuzzy and Soft Computing; Proc. of the Prentice Hall. [13] Jin H.-D., Leung K.-S., Wong M.-L., Xu Z.-B. (2003), An Efficient Self-Organizing Map Designed by Genetic Algorithms for the Traveling Salesman Problem; IEEE Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics 33(6); 877-888. [14] Kirkpatrick S., Gelatt C.D., Vecchi M.P. (1983), Optimization by simulated annealing; Science 220; 671–680. [15] Kravitz S.A., Rutenbar R.A. (1987), Placement by simulated annealing on a multiprocessor; IEEE Trans. Computer-Aided Design Integr. Circuits Syst. 6(4); 534–549. [16] Leung K.-S., Jin H.-D., Xu Z.-B. (2004), An expanding Self-Organizing neural network for the traveling salesman problem; Neurocomputing 62; 267-292. [17] Lin F.-T., Kao C.-Y., Hsu C.-C. (1993), Applying the Genetic Approach to Simulated Annealing in Solving Some NP-Hard Problems; IEEE Transactions on Systems, Man, and Cybernetics, 23(6). [18] Pao D.C.W., Lam S.P., Fong A.S. (1999), Parallel implementation of simulated annealing using transaction processing; IEE Proc-Comput. Digit. Tech.. 146(2); 107-113. [19] Pepper W.J., Golden L.B., Wasil A.E. (2002), Solving the Traveling Salesman Problem With Annealing-Based Heuristics: A Computational Study; IEEE Transactions on Systems, Man, and Cybernetics—PART A: Systems and Humans 32(1). [20] Saadatmand-Tarzjan M., Khademi M., Akbarzadeh M.R.., Abrishami Moghaddam H. (2007), A Novel Constructive-Optimizer Neural Network for the Traveling Salesman Problem; IEEE Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics 37(4). [21] Shakouri G.H., Shojaee K., Behnam T.M. (2009), The Wise Experiencing Traveling Salesman (WETS): Introduction to a simple evolutionary solution for the problem; Proc. in CEC 2009 IEEE Congress on Evolutionary Computation; 18-21 May, Trondheim, Norway; 771-776. [22] Smith K.I., Everson M.R., Fieldsend E.J, Murphy C., Misra R. (2008), Dominance-Based Multiobjective Simulated Annealing; IEEE Transactions on Evolutionary Computation 12(3); 323- 341. [23] Soh A. (1995), Parallel N-ary Speculative Computation of Simulated Annealing; IEEE Transactions on Parallel and Distributed Systems 6(10); 997-1005. [24] Thompson R.D., Bilbro L.G. (2005), Sample-Sort Simulated Annealing; IEEE Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics 35(3); 625-632. [25] Tsang H.H., Wiese K.C. (2007), The Significance of Thermodynamic Models in the Accuracy Improvement of RNA Secondary Structure Prediction Using Permutation-based Simulated Annealing; Proceeding of IEEE Congress on Evolutionary Computation. [26] Wang L., Li S., Tian F., Fu X. (2004), A Noisy Chaotic Neural Network for Solving Combinatorial Optimization Problems: Stochastic Chaotic Simulated Annealing; Transactions on Systems, Man, and Cybernetics—PART B: Cybernetics 34(5); 2119-2125.

[27] Wong K.L., Constantinides A.G. (1998), Speculative parallel simulated annealing with acceptance prediction; Electronics Letters 34(3); 312-313. [28] Wu S., Chow W.S.T. (2007), Self-Organizing and Self-Evolving Neurons: A New Neural Network for Optimization; IEEE Transactions on Neural Network 18(2); 385-396. [29] Yip C.P., Pao Y.-H. (1995), Combinatorial Optimization with Use of Guided Evolutionary Simulated Annealing; IEEE Transactions on Neural Networks 6(2); 290-295. [30] Reinelt G. (1995), Tsplib95, http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95, 2010