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 a-priori 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." />


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.E83-A   No.6   pp.1211-1221
Publication Date: 2000/06/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
Keyword: 
Hopfield network,  optimal Hopfield network,  combinatorial optimization,  traveling salesman problem,  

Full Text: PDF>>
Buy this Article




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 a-priori 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.