Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem

Jiahai WANG; Zheng TANG; Qiping CAO

Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem

Jiahai WANG, Zheng TANG, Qiping CAO

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.10 pp.2790-2798

Publication Date: 2004/10/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Neural Networks and Bioengineering

Cite this

Copy

Jiahai WANG, Zheng TANG, Qiping CAO, "Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem" in IEICE TRANSACTIONS on Fundamentals, vol. E87-A, no. 10, pp. 2790-2798, October 2004, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e87-a_10_2790/_p

Copy

@ARTICLE{e87-a_10_2790,
author={Jiahai WANG, Zheng TANG, Qiping CAO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem},
year={2004},
volume={E87-A},
number={10},
pages={2790-2798},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={October},}

Copy

TY - JOUR
TI - Stochastic Competitive Hopfield Network and Its Application to Maximum Clique Problem
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 2790
EP - 2798
AU - Jiahai WANG
AU - Zheng TANG
AU - Qiping CAO
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 10
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - October 2004
AB - 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.
ER -