Combinatorial optimization by stochastic automata

The significance of combinatorial optimization for many applications is well understood. The simulated annealing alogrithm (which the authors will denote from here on as SA) has generated great interest and attention in the scienfic community. Its authors derived it from analogies to the physical domain, and a myriad of publications followed. 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. The authors prove that SA, like many other randomized algorithms, belongs to the class of S-type GH-stochastic automata. They provide other representatives of this class together with algorithms from some other classes, and discuss the issue of convergence. Large computational experiments were performed on a network of Apollo computers.