The search functionality is under construction.

The search functionality is under construction.

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

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

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 -