SIMULATED ANNEALING METHOD IN THE CLASSIC BOLTZMANN MACHINES
DOI:
https://doi.org/10.17770/etr2023vol2.7214Keywords:
Boltzmann machine, simulated annealing, thermal equilibrium, travelling salesman problemAbstract
The classical Boltzmann machine is understood as a neural network proposed by Hinton and his colleagues in 1985. They added noise interferences to the Hopfield model and called this network a Boltzmann machine drawing an analogy between its behaviour and physical systems with the presence of interferences. This study explains the definition of “simulated annealing” and “thermal equilibrium” using the example of a partial network. A technique for calculating the probabilities of transition states at different temperatures using Markov chains is described, an example of the application of the SA - travelling salesman problem is given. Boltzmann machine is used for pattern recognition and in classification problems. As a disadvantage, a slow learning algorithm is mentioned, but it makes it possible to get out of local minima. The main purpose of this article is to show the capabilities of the simulated annealing algorithm in solving practical tasks.
Downloads
References
J.J. Hopfield, “Neural Networks and physical systems with emergent collective computational abilities.” Proc.Natl. Acad.Sci. USA,79, P. 2554-2558, 1982. https://doi.org/10.1073/pnas.79.8.2554
J.J. Hopfield, “Neurons with graded response have collective computational properties like those of two state neurons.” Proc.Natl. Acad.Sci. USA,81, P. 3088-3092, 1984. https://doi.org/10.1073/pnas.81.10.3088
D.H. Ackley, G.E. Hinton and T.J. Sejnowski,T.J. “A learning algorithm for Boltzmann machines,” Cognitive Science,9, P. 147-169, 1985. https://www.cs.toronto.edu/~fritz/absps/cogscibm.pdf
S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, “Optimization by simulated annealing.” Science, 220, P. 671-680, 1983. https://www.science.org/doi/10.1126/science.220.4598.671
P.J. Laarhoven and E.H. Aarts, Simulated Annealing: Theory and Applications. Holland: D. Reidel Publishing Company, 1987. https://doi.org/10.1007/978-94-015-7744-1
R.H. Otten and L.P. Ginneken, The Annealing Algorithm. Kluwer Academic Publishers, 1989.
V. Granville, M. Krivanek and J-P. Rasson, “Simulated annealing: A proof of convergence.” IEEE Transactions on Pattern Analysis and Machine Intelligence, 16(6), 652–656, 1994. https://doi.org/10.1109/34.295910
L. Ingber, “Simulated annealing: Practice versus theory.” Math. Comput. Modelling, 18, 29–57, 1993. https://doi.org/10.1016/0895-7177(93)90204-C
J.P. Coughlin and R.H. Baran, Neural Computation in Hopfield Networks and Boltzmann Machines. University of Delaware Press, 1985.
B. Maxwell, Advanced Simulated Annealing. Clanrye International, 2015.
E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines: A stochastic approach to combinatorial optimization and neural computing. John Wiley and Sons, 1989.
P. Grabusts, Analysis of the simulated annealing method in classic Boltzmann machines. Environment. Tehnologies. Resources. Proceedings of the International Scientific and Practical Conference, Rezekne, Latvia, 1997. https://doi.org/10.17770/etr1997vol1.1857
P. Grabusts, J. Musatovs and V. Golenkov, The Application of Simulated Annealing Method for Optimal Route Detection Between Objects, Procedia Computer Science, ICTE in Transportation and Logistics, ICTE 2018, Volume 149, 2019, Pages 95-101, https://doi.org/10.1016/j.procs.2019.01.112
W.J. Cook, In Pursuit of the Traveling Salesman. Princeton: Princeton University Press, USA, 2011.
D.L. Applegate, R. Bixby, V. Chvátal and W. Cook, The Traveling Salesman Problem: A Computational Study. Princeton University Press, 2006.
