Solving Combinatorial Optimization Problems Using the Oscillatory Neural Network

Yoshiaki WATANABE  Keiichi YOSHINO  Tetsuro KAKESHITA  

IEICE TRANSACTIONS on Information and Systems   Vol.E80-D   No.1   pp.72-77
Publication Date: 1997/01/25
Online ISSN: 
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Bio-Cybernetics and Neurocomputing
neural network,  optimization problem,  NP-complete,  

Full Text: PDF(431.7KB)
>>Buy this Article

The Hopfield neural network for optimization problems often falls into local minima. To escape from the local minima, the neuron unit in the neural network is modified to become an oscillatory unit by adding a simple self-feedback circuit. By combining the oscillatory unit with an energy-value extraction circuit, an oscillatory neural network is constructed. The network can repeatedly extract solutions, and can simultaneously evaluate them. In this paper, the network is applied to four NP-complete problems to demonstrate its generality and efficiency. The network can solve each problem and can obtain better solutions than the original Hopfield neural network and simple algorithms.