Stochastic competitive Hopfield network and its application to maximum clique problem

被引:0
作者
Wang, JH [1 ]
Tang, Z
Cao, QP
机构
[1] Toyama Univ, Fac Engn, Toyama 9308555, Japan
[2] Tateyama Syst Inst, Toyama 9300001, Japan
来源
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES | 2004年 / E87A卷 / 10期
关键词
maximum clique problem; optimal competitive Hopfield model; stochastic dynamistic; NP-complete problem;
D O I
暂无
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
In this paper, introducing a stochastic hill-climbing dynamics into an optimal competitive Hoplield 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 per-forms 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.
引用
收藏
页码:2790 / 2798
页数:9
相关论文
共 25 条
[1]   FINDING A MAXIMUM CLIQUE IN AN ARBITRARY GRAPH [J].
BALAS, E ;
YU, CS .
SIAM JOURNAL ON COMPUTING, 1986, 15 (04) :1054-1068
[2]   EXPERIMENTS IN QUADRATIC 0-1 PROGRAMMING [J].
BARAHONA, F ;
JUNGER, M ;
REINELT, G .
MATHEMATICAL PROGRAMMING, 1989, 44 (02) :127-137
[3]   AN EXACT ALGORITHM FOR THE MAXIMUM CLIQUE PROBLEM [J].
CARRAGHAN, R ;
PARDALOS, PM .
OPERATIONS RESEARCH LETTERS, 1990, 9 (06) :375-382
[4]   A NOTE ON THE APPROXIMATION OF THE MAX CLIQUE PROBLEM [J].
CRESCENZI, P ;
FIORINI, C ;
SILVESTRI, R .
INFORMATION PROCESSING LETTERS, 1991, 40 (01) :1-5
[5]  
Funabiki N, 1996, IEICE T FUND ELECTR, VE79A, P452
[6]   Design and analysis of maximum Hopfield networks [J].
Galán-Marín, G ;
Muñoz-Pérez, J .
IEEE TRANSACTIONS ON NEURAL NETWORKS, 2001, 12 (02) :329-339
[7]   Modelling competitive Hopfield networks for the maximum clique problem [J].
Galán-Marín, G ;
Mérida-Casermeiro, E ;
Muñoz-Pérez, J .
COMPUTERS & OPERATIONS RESEARCH, 2003, 30 (04) :603-624
[8]  
HAMMER PL, 1965, OPER RES, V13, P388
[9]  
HOPFIELD JJ, 1985, BIOL CYBERN, V52, P142
[10]   APPROXIMATING MAXIMUM CLIQUE WITH A HOPFIELD NETWORK [J].
JAGOTA, A .
IEEE TRANSACTIONS ON NEURAL NETWORKS, 1995, 6 (03) :724-735