
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Chaotic Maximum Neural Network for Maximum Clique Problem
Jiahai WANG Zheng TANG Ronglong WANG
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E87D
No.7
pp.19531961 Publication Date: 2004/07/01 Online ISSN:
DOI: Print ISSN: 09168532 Type of Manuscript: PAPER Category: Biocybernetics, Neurocomputing Keyword: maximum clique problem, maximum neural network, transient chaos, NPcomplete problem,
Full Text: PDF(399.2KB)>>
Summary:
In this paper, based on maximum neural network, we propose a new parallel algorithm that can escape from local minima and has powerful ability of searching the globally optimal or nearoptimum solution for the maximum clique problem (MCP). In graph theory a clique is a completely connected subgraph and the 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 realworld applications, and is also known to be NPcomplete. Lee and Takefuji have presented a very powerful neural approach called maximum neural network for this NPcomplete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parametertuning. However, the model has a tendency to converge to the local minimum easily because it is based on the steepest descent method. By adding a negative selffeedback to the maximum neural network, we proposed a parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm.

open access publishing via







