A Mushy State Simulated Annealing

Document Type : Research Paper

Authors

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.

Keywords

Main Subjects


[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