Shin ISHII, Masaaki SATO
Bifurcations in
traveling salesman problem
Abstract:In the analog Hopfield network and the mean field theory (MFT) of the Boltzmann machine, bifurcations of solutions occur during the course of the annealing procedure. In this report, we investigate the MFT bifurcation processes when MFT is applied to traveling salesman problems (TSPs). A TSP has two types of symmetries, i.e., cyclic and reverse. These symmetries affect the bifurcation structure. This report also describes some features of the MFT annealing procedure. The algorithm does not necessarily give unique solutions, and it does not guarantee the optimal solution. Consequently, MFT annealing has a non-deterministic property and results in "not-so-bad" solutions, in general. To overcome the limitations, we also propose a couple of modified algorithms.