Solving The Set Covering Problem Using The Hopfield Neural Networks

The minimum set covering problem is an important NP-hard problem on hyper graphs. It has many practical applications in important fields such as production, capital investment and project selection. Since the classical optimization techniques are inefficient to solve such problems, the artificial neural network is usually used to solve the problem. The artificial neural network is becoming more and more popular recently, and has already developed into a comprehensive cross-subject branch. It mainly focuses on simulating the structure and intellectual behavior of the brain based on the deep knowledge about the function and structure of human brain. One of the most popular ones is the Hopfield Neural Network, which is good at solving optimization problems. But this classical model has lots of shortcomings, including the local minimum problem. The existed neural network based algorithms sometime lead to inaccurate results and oscillatory behaviors in the convergence process. In this paper, we propose a learning algorithm of the Hopfield neural network which can escape from local minimum. The learning algorithm adjusts the balance between constraint term and cost term of the energy function so that the local minimum that the network once falls into vanishes and the network can continue updating in a gradient descent direction of energy. Approximation performance is experimentally determined on random instances of hyper graphs by comparing it to several known algorithms. The experimental results show that the proposed algorithm works much better than the existing algorithms for the problem.