
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

An "Optimal" Hopfield Network for Combinatorial Optimization and Its Approximate Realization
Satoshi MATSUDA
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E83A
No.6
pp.12111221 Publication Date: 2000/06/25 Online ISSN:
DOI: Print ISSN: 09168508 Type of Manuscript: PAPER Category: Graphs and Networks Keyword: Hopfield network, optimal Hopfield network, combinatorial optimization, traveling salesman problem,
Full Text: PDF>>
Summary:
Taking traveling salesman problems (TSPs) as examples of combinatorial optimization problems, an "optimal" Hopfield network for ("optimal" neural representation of) TSPs is presented, where a vertex of state hypercube of the network is asymptotically stable if and only if it is an optimal solution. Of all the Hopfield networks for TSPs, this network most sharply distinguishes an optimal solution from other nonoptimal solutions and infeasible solutions. In this sense, we call this network "optimal" for TSPs. Whenever the network converges to a vertex, we can always obtain an optimal solution. However, we can not design such network without knowing an optimal solution to the problem. So, its approximate realization, which can be designed without apriori knowledge of an optimal solution, is proposed. Simulations show that the "optimal" network and its approximate realization obtain optimal or good feasible solutions more frequently than familiar Hopfield networks. We can also design such "optimal" Hopfield networks for many combinatorial optimization problems as well as for TSPs.

