Application of the deterministic annealing EM algorithm extended by means of non-extensive statistical mechanics to the traveling salesman problem

摘要

EM-algorithm is one of the major tools to obtain maximum likelihood estimates from incomplete data sets. However the EM-algorithm has the problem that the solution converges to a local optimal on account of the dependence of the initial state of parameters in the posterior distribution. In order to avoid this difficulty, we modified the posterior distribution by means of non-extensive Tsallis entropy. In our posterior distribution, a parameter q, which represents non-extensivity of the entropy, is controlled as q → 1 to reduce the strong dependence of the initial conditions. In this paper, we apply our algorithm to the traveling salesman problem (TSP). As well-known, the TSP can be solved by self-organizing map (SOM) of elastic neural networks. The key point of our method for the TSP is reformulating the SOM in terms of our modified EM-algorithm. Quality of the solution, suitable annealing schedule for the parameter q, speed of the convergence, etc. are discussed.