Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem

Jiahai WANG  Zheng TANG  Qiping CAO  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E87-A   No.10   pp.2790-2798
Publication Date: 2004/10/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Neural Networks and Bioengineering
maximum clique problem,  optimal competitive Hopfield model,  stochastic dynamistic,  NP-complete problem,  

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

In this paper, introducing a stochastic hill-climbing dynamics into an optimal competitive Hopfield network model (OCHOM), we propose a new algorithm that permits temporary energy increases, which helps the OCHOM escape from local minima. In graph theory, a clique is a completely connected subgraph and the maximum clique problem (MCP) is to find a clique of maximum size of a graph. The MCP is a classic optimization problem in computer science and in graph theory with many real-world applications, and is also known to be NP-complete. Recently, Galan-Marin et al. proposed the OCHOM for the MCP. It can guarantee convergence to a global/local minimum of energy function, and performs better than other competitive neural approaches. However, the OCHOM has no mechanism to escape from local minima. The proposed algorithm introduces stochastic hill-climbing dynamics which helps the OCHOM escape from local minima, and it is applied to the MCP. A number of instances have been simulated to verify the proposed algorithm.