Abstract
Simulated Annealing (SA) is usually implemented in a sequential way. We propose a Methodology to Parallel the Simulated Annealing Algorithm (MPSA). This methodology carries out the parallelization of the cycle that controls the temperature in the algorithm. This approach lets a massive parallelization. The initial solution for each internal cycle may be set through a Monte Carlo random sampling to adjust the Boltzmann distribution at the cycle beginning. In MPSA the communication scheme and its implementation must be in an asynchronous way. Through a theoretical analysis we establish that any implementation of MPSA leads to a Simulated Annealing Parallel Algorithm (SAPA) that is in general more efficient than its sequential implementation version.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Kirkpatrik, S., Gelatt Jr., C.D., Vecchi, M.P.: Optimization by simulated annealing. Science 220(4598), 671–720 (1983)
Cerny, V.: Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications 45(1), 41–51 (1985)
Sanvicente, S.H.: Recocido simulado: optimización combinatoria. Estado del arte. Instituto Tecnológico y de Estudios Superiores de Monterrey (campus Morelos), México. p. 72 (1997)
Sanvicente, S.H.: Recocido simulado paralelo. Propuesta de Tesis Doctoral. Instituto Tecnológico y de Estudios Superiores de Monterrey (Campus Morelos), México, p. 38 (1998)
Aarts, E., Korst, J.: Simulated annealing and Boltzmann machines: A stochastic approach to combinatorial optimization and neural computing, p. 272. John Wiley & Sons, Great Britain (1989)
Greening, D.R.: Parallel simulated annealing techniques. Physica D. 2, 293–306 (1990)
Azencott, R.: Simulated Annealing: Parallelization techniques. In: Azencott, R. (ed.), p. 200. John Wiley & Sons, Chichester (1992)
Diekmann, R., Lüling, R., Simon, J.: Problem independent distributed simulated annealing and its applications. Tech. Report No. TR-003-93. Department of Mathematics and computer Science, University of Paderborn, Germany, p. 23 (1993)
Krishna, K., Ganeshan, K., Ram, D.J.: Distributed simulated annealing algorithms for job shop scheduling. IEEE Transactions on Systems, Man, and Cybernetics 25(7), 1102–1109 (1995)
Voogd, J.M., Sloot, P.M.A.: Crystallization on a sphere using the simulated annealing algorithm implemented on H.P.C. systems. Technical Report: PSCSG-93-01, Parallel Scientific Computing and Simulation Group, University of Amsterdam, p. 6 (1993)
Voogd, J.M., Sloot, P.M.A., Dantzing, R.V.: Simulated annealing for N-body systems. Technical Report: PSCSG-94-01, Parallel Scientific Computing and Simulation Group, University of Amsterdam, p. 6 (1994)
Dowsland, K.A.: Simulated annealing. In: Reeves, C.R. (ed.) Modern heuristic techniques for combinatorial problems, pp. 20–69. John Wiley and Sons, Great Britain (1993)
Ingber, L.: Simulated Annealing: Practice versus theory. J. Mathl. Comput. Modelling 18(11), 29–57 (1993)
Roussel-Ragot, P., Dreyfus, G.: Parallel annealing by multiple trials: an Experimental study on a transputer network. In: Azencott, R. (ed.) Simulated annealing: parallelization techniques, pp. 91–108. John Wiley & sons, USA (1992)
Graffigne, C.: Parallel annealing by periodically interacting multiple searches: An experimental study. In: Azencott, R. (ed.) Simulated annealing: Parallelization techniques, pp. 47–79. Wiley & Sons, USA (1992)
Metropolis, N., Rosenbluth, A., Rosenbluth, M., Teller, A., Teller, E.: Equation of state calculations by fast computing machines. Journal of Chemical Physics 21, 1087–1092 (1953)
Kemeny, J.G., Snell, J.L.: Finite Markov chains, p. 210. D. Van Nostrand Company, Inc., USA (1965)
Virot, B.: Parallel annealing by multiple trials: Experimental study of a chip placement problem using a sequent machine. In: Azencott, R. (ed.) Simulated annealing: Parallelization techniques, pp. 109–127. John Wiley & Sons, USA (1992)
Nabhan, T.M., Zomaya, A.Y.: A parallel simulated annealing algorithm with low communication overhead. IEEE Transactios on Parallel and distributed Systems 6(12), 1226–1233 (1995)
Sohn, A.: Parallel N-ary speculative computation of simulated annealing. IEEE Transactions on Parallel and Distributed systems 6(10), 997–1005 (1995)
Voogd, J.M., Sloot, P.M.A., Dantzing, R.V.: Comparison of vector and parallel implementations of the simulated annealing algorithm. Technical Report: PSCSG-95-01, Parallel Scientific Computing and Simulation Group, University of Amsterdam, p. 11 (1995)
Marroqin, J.L., Botello, S., Horebeek, J.: A family of parallel search algorithms. Memorias de la 12va. Reunión Nacional de Inteligencia artificial de la SMIA, 164–171 (1995)
Chen, H., Flann, N.S., Watson, D.W.: Parallel genetic simulated annealing: a massively parallel SIMD algorithm. IEEE Transactions on Parallel and Distributed Systems 9(2), 126–136 (1998)
Mutalik, P.P., Knight, L.R., Blaton, J.L., Wainwright, R.L.: Solving combinatorial optimization problems using parallel simulated annealing and parallel genetic algorithms. ACM 0-89791-502-X/92/0002/1031, pp. 1031 – 1038 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sanvicente Sánchez, H., Frausto Solís, J. (2000). A Methodology to Parallel the Temperature Cycle in Simulated Annealing. In: Cairó, O., Sucar, L.E., Cantu, F.J. (eds) MICAI 2000: Advances in Artificial Intelligence. MICAI 2000. Lecture Notes in Computer Science(), vol 1793. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10720076_6
Download citation
DOI: https://doi.org/10.1007/10720076_6
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67354-5
Online ISBN: 978-3-540-45562-2
eBook Packages: Springer Book Archive