caa a22 4500 465774199 CHVBK 20180323111937.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02023058 doi (NATIONALLICENCE)springer-10.1007/BF02023058 Combinatorial optimization by stochastic automata [Elektronische Daten] [Eugene Shragowitz, Rung-Bin Lin] The significance of combinatorial optimization for many important applications is well understood. The simulated annealing algorithm (which we will denote from here on as SA) has generated great interest and attention in the scientific community. Its authors derived it from analogies to the physical domain [15,10], and a myriad of publications followed (see references to the book on simulated annealing in [11]). The prevailing opinion expressed in these publications was that the SA algorithm represents a new, hitherto unknown class of algorithms and provides a breakthrough in the solution of NP-hard optimization problems. As might be expected, roots of the SA do exist, and one of the purposes of this paper is to trace these roots. We prove that SA, like many other randomized algorithms, belongs to the class of S-type GH-stochastic automata. We provide other representatives of this class together with algorithms from some other classes, and discuss the issue of convergence. Large computational experiemts were performed on a network of Apollo computers. J.C. Baltzer AG, Scientific Publishing Company, 1990 Shragowitz Eugene Department of Computer Science, EE/CSci. Bldg., University of Minnesota, 200 Union Street SE, 55455, Minneapolis, Minnesota, USA aut Lin Rung-Bin Department of Computer Science, EE/CSci. Bldg., University of Minnesota, 200 Union Street SE, 55455, Minneapolis, Minnesota, USA aut Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 22/1(1990-12-01), 293-324 0254-5330 22:1<293 1990 22 10479 https://doi.org/10.1007/BF02023058 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02023058 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Shragowitz Eugene Department of Computer Science, EE/CSci. Bldg., University of Minnesota, 200 Union Street SE, 55455, Minneapolis, Minnesota, USA aut NATIONALLICENCE 700 1- Lin Rung-Bin Department of Computer Science, EE/CSci. Bldg., University of Minnesota, 200 Union Street SE, 55455, Minneapolis, Minnesota, USA aut NATIONALLICENCE 773 0- Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 22/1(1990-12-01), 293-324 0254-5330 22:1<293 1990 22 10479 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer