Single Minimum Method for Combinatorial Optimization Problems and Its Application to the TSP Problem

Dan XU
Itsuo KUMAZAWA

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E76-A    No.5    pp.742-748
Publication Date: 1993/05/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Neural Nets,Chaos and Numerics)
Category: Neural Nets--Theory and Applications--
Keyword: 
single minimum method,  combinatorial optimization,  neurocomputing,  local minima problem,  TSP problem,  

Full Text: PDF>>
Buy this Article


Summary: 
The problem of local minima is inevitable when solving combinatorial optimization problems by conventional methods such as the Hopfield network, relying on the minimization of an objective function E(X). Such a problem arises from the search mechanism in which only the local information about the objective function E(X) is used. In this paper we propose a new approach called the Single Minimum Method (SMM) which uses the global information in searching for the solutions to combinatorial optimization problems. In this approach, we add a function -TS(X) to the original objective function E(X) to construct the function F(X)=E(X)-TS(X) which has only one minimum, one which can be easily found by any general gradiet method including the Hopfield network. Based on an analogy between thermodynamic systems and neural networks, it is shown that the global information about the original objective function E(X) is included in the single minimum of the function F(X) and can be used for finding the global minimum of the objective function E(X). In order to show how to apply the Single Minimum Method to a combinatorial optimization problem we give an algorithm for the TSP problem based on our method. The simulation results show that the algorithm can almost always find the shortest or near shortest paths. Finally, a modified SMM, which has some great advantages for hardware implementation, is also given.