Combinatorial Optimization, Markov Chains, and Stochastic Automata
Eugene B. Shragowitz, Rung‐Bin Lin · 2021
It has been known for some time [ KIR83 , MIT86 ] that Markov chain techniques can be applied to solving combinatorial optimization problems. Under certain conditions a nonstationary Markov chain of states in the solution space of the combinatorial problem asymptotically converges in probability to a global minimum. A similar set of ideas was introduced earlier in the domain of automata theory for adaptive optimization of the unknown function of parameters. Random search algorithms were interpreted there as stochastic automata and were investigated by means of discrete Markov chains. In this paper we prove the equivalence between some popular randomized algorithms for combinatorial optimization (simulated annealing, SA), certain types of stochastic automata (S-type GH-stochastic automata with variable structure), and non-stationary Markov chains. By using Markov chain techniques, it was demonstrated that many stochastic automata have properties similar to those of simulated annealing and are not inferior to SA in computations. 544 Large computational experiments were conducted on a network of Apollo computers.