An  Optimal  Hopfield Network for Combinatorial Optimization and Its Approximate Realization

Satoshi MATSUDA

An "Optimal" Hopfield Network for Combinatorial Optimization and Its Approximate Realization

Satoshi MATSUDA

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E83-A No.6 pp.1211-1221

Publication Date: 2000/06/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Graphs and Networks

Cite this

Copy

Satoshi MATSUDA, "An "Optimal" Hopfield Network for Combinatorial Optimization and Its Approximate Realization" in IEICE TRANSACTIONS on Fundamentals, vol. E83-A, no. 6, pp. 1211-1221, June 2000, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e83-a_6_1211/_p

Copy

@ARTICLE{e83-a_6_1211,
author={Satoshi MATSUDA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={An "Optimal" Hopfield Network for Combinatorial Optimization and Its Approximate Realization},
year={2000},
volume={E83-A},
number={6},
pages={1211-1221},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={June},}

Copy

TY - JOUR
TI - An "Optimal" Hopfield Network for Combinatorial Optimization and Its Approximate Realization
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1211
EP - 1221
AU - Satoshi MATSUDA
PY - 2000
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E83-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2000
AB - 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.
ER -