A novel digital neural network for the travelling salesman problem

Author

Varma, Ankush ; Jayadeva

Author_Institution

Dept. of Electr. & Comput. Eng., Maryland Univ., College Park, MD, USA

Volume

3

fYear

2002

fDate

18-22 Nov. 2002

Firstpage

1320

Abstract

In this paper, we present a novel neural network solution to the Travelling Salesperson´s Problem. In comparison to the Hopfield Neural Network for the task, the proposed network requires N neurons and O(N²) weights to solve a N-city instance. The proposed network is entirely digital, and has been mapped onto a Field Programmable Gate Array. Initial results are encouraging and the FPGA takes under 20 microseconds to solve the task for chosen examples. The re-programmable nature of the FPGA makes the proposed approach a very low cost, reusable hardware approach.

Keywords

Hopfield neural nets; computational complexity; field programmable gate arrays; travelling salesman problems; FPGA; Hopfield neural network; TSP; compact analog neural network; digital neural network; field programmable gate array; travelling salesman problem; Cities and towns; Costs; Field programmable analog arrays; Field programmable gate arrays; Hardware; Hopfield neural networks; Neural networks; Neurons; Phased arrays; Traveling salesman problems;

fLanguage

English

Publisher

ieee

Conference_Titel

Neural Information Processing, 2002. ICONIP '02. Proceedings of the 9th International Conference on

Print_ISBN

981-04-7524-1

Type

conf

DOI

10.1109/ICONIP.2002.1202835

Filename

1202835