The Definition of Necessary Hidden Units in Neural Networks for Combinatorial Optimization
Abstract
Among the earliest successful applications of multi-layered neural networks are combinatorial optimization problems, most notably, the travelling salesman problem. Hopfield-type thermodynamic networks comprised of functionally homogenous visible units have been applied to a variety of structurally simple NP-hard optimization problems. A fundamental obstacle to the application of neural networks to difficult problems is that these problems must first be reduced to 0-1 Hamiltonian optimization problems. We show that certain optimization problems cannot be embedded in networks composed entirely of visible units and present a method for defining necessary hidden units together with their best features. We derive a knapsack-packing network of O(n) units with both standard and conjunctive synapses. Encouraging simulation results are cited.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jan 01, 1990
- Accession Number
- ADA227142
Entities
People
- Benjamin J. Hellstrom
- Laveen N. Kanal
Organizations
- University of Maryland