A Chaotic Neural Network for the Maximum Clique Problem

摘要

This paper applies a chaotic neural network (CNN) to solve the maximum clique problem (MCP), a classic NP-hard and computationally intractable graph optimization problem, which has many real-world applications. Prom analyzing the chaotic states of its neuron output and computational energy, we reach the conclusion that, unlike the conventional Hopfield neural networks (HNN) for the MCP such as steepest descent (SD) algorithm and continuous Hopfield dynamics (CHD) algorithm based on the discrete Hopfield neural network and the continuous Hopfield neural network respectively, CNN can avoid getting stuck in local minima and thus yields excellent solutions. Detailed analysis of the optimality, efficiency, robustness and scalability verifies that CNN provides a more effective and efficient approach than conventional Hopfield neural networks to solve the MCP.