A Hill-Shift Learning Algorithm of Hopfield Network for Bipartite Subgraph Problem

Rong-Long WANG  Kozo OKAZAKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E89-A   No.1   pp.354-358
Publication Date: 2006/01/01
Online ISSN: 1745-1337
DOI: 10.1093/ietfec/e89-a.1.354
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Neural Networks and Bioengineering
bipartite subgraph problem,  Hopfield neural network,  hill-shift learning,  NP-complete problem,  

Full Text: PDF>>
Buy this Article

In this paper, we present a hill-shift learning method of the Hopfield neural network for bipartite subgraph problem. The method uses the Hopfield neural network to get a near-maximum bipartite subgraph, and shifts the local minimum of energy function by adjusts the balance between two terms in the energy function to help the network escape from the state of the near-maximum bipartite subgraph to the state of the maximum bipartite subgraph or better one. A large number of instances are simulated to verify the proposed method with the simulation results showing that the solution quality is superior to that of best existing parallel algorithm.