When solving combinatorial optimization problems with a binary Hopfield-type neural network, the updating process in neural network is an important step in achieving a solution. In this letter, we propose a new updating procedure in binary Hopfield-type neural network for efficiently solving combinatorial optimization problems. In the new updating procedure, once the neuron is in excitatory state, then its input potential is in positive saturation where the input potential can only be reduced but cannot be increased, and once the neuron is in inhibitory state, then its input potential is in negative saturation where the input potential can only be increased but cannot be reduced. The new updating procedure is evaluated and compared with the original procedure and other improved methods through simulations based on N-Queens problem. The results show that the new updating procedure improves the searching capability of neural networks with shorter computation time. Particularly, the simulation results show that the performance of proposed method surpasses the exiting methods for N-queens problem in synchronous parallel computation model.

The goal of the 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. The maximum cut problem has many important applications including the design of VLSI circuits and communication networks. Moreover, many optimization problems can be formulated in terms of finding the maximum cut in a network or a graph. In this paper, we propose an improved Hopfield neural network algorithm for efficiently solving the maximum cut problem. A large number of instances have been simulated. The simulation results show that the proposed algorithm is much better than previous works for solving the maximum cut problem in terms of the computation time and the solution quality.

A near-optimum parallel algorithm for bipartite subgraph problem using gradient ascent learning algorithm of the Hopfield neural networks is presented. This parallel algorithm, uses the Hopfield neural network updating to get a near-maximum bipartite subgraph and then performs gradient ascent learning on the Hopfield network to help the network escape from the state of the near-maximum bipartite subgraph until the state of the maximum bipartite subgraph or better one is obtained. A large number of instances have been simulated to verify the proposed algorithm, with the simulation result showing that our algorithm finds the solution quality is superior to that of best existing parallel algorithm. We also test the proposed algorithm on maximum cut problem. The simulation results also show the effectiveness of this algorithm.

This paper describes a new learning method for Multiple-Value Logic (MVL) networks using the local search method. It is a "non-back-propagation" learning method which constructs a layered MVL network based on canonical realization of MVL functions, defines an error measure between the actual output value and teacher's value and updates a randomly selected parameter of the MVL network if and only if the updating results in a decrease of the error measure. The learning capability of the MVL network is confirmed by simulations on a large number of 2-variable 4-valued problems and 2-variable 16-valued problems. The simulation results show that the method performs satisfactorily and exhibits good properties for those relatively small problems.