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

概要

論文の詳細を見る
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 gradient 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.
社団法人電子情報通信学会の論文
1993-05-25