A DELAYED-STATE ALGORITHM USING HOPFIELD NEURAL NETWORK WITH CHN FOR MCP

作者：Zhang Wei^*; Tang Zheng; Wang Ronglong

来源：International Journal of Innovative Computing Information and Control, 2010, 6(4): 1737-1748.

• Maximum cut problem
• Hopfield neural network
• Hysteresis
• Collective properties
• NP-complete problem

The goal of maximum cut problem is to partition the vertex set of an undirected graph into two parts in order to maximize the cardinality of the set of edges cut by the partition. Many optimization problems can be formulated in terms of finding the maximum cut in a network or a graph. In this paper, we propose a new parallel algorithm using Hopfield neural network with continuous hysteresis neurons (CHN) for efficiently solving maximum cut problem. We prove theoretically that the emergent collective properties of the Hopfield neural network with TIBN also are present in the Hopfield network with CHN. A large number of instances have been simulated to verify the proposed algorithm. The simulation results show that our proposed algorithm finds the optimum or near-optimum solution for the maximum cut problem superior to that of the best existing parallel algorithms in both the computation time and the solution quality.

• 出版日期2010-4