Recurrent Neural Networks And It's Application In Some Combinatorial Optimization Problems

Since 1980s, artificial neural networks have been attracting the study of many researchers in science and engineering fields, and many interesting results haven been obtained in the two decades. More and more researchers start to study the neural networks which aim at solving the problems of economical, engineering, military, medical, and other fields of science, such as signal processing, intelligent controls, vision of machines, optimizations, object detecting, mining of knowledge, remote sensing and so on. Some unique characters and capability in computing of the neural networks have been recognized by scientists and engineers.It is well known that neural networks have been considered as an important tool to solve combinative optimization problems. This dissertation studies the characteristics of recurrent neural networks and applies them solve some of the combinative optimization problems. The main topics we will discuss are listed as following:(1). Studying the setting of parameters in Hopfield networks when applied to solve TSPs. By analyzing the behavior of Hopfield networks as a method of solving the traveling salesman problem (TSP) with an enhanced formulation of energy function, we show that this model is more effective than that of the Hopfield-Tank's (H-T). The analysis is based on the geometry of the subspace set up by the degenerate eigenvalues of the connection matrix. A set of criterion for parameter settings is derived. The new parameters performed well in the simulations.(2). Studying the multi-stability of the neural networks with linear threshold (LT) transfer function. Different conditions are derived explicitly to guarantee the mono-stability and multi-stability of the network, respectively. Dynamical properties of the equilibria of two-dimensional networks are analyzed theoretically. We show that the given conditions can drive the network (two-dimensional) of converging to different global stable points, or different multi-stable points. An important implication of the proposed model: Winner-Take-all network, is studied in detail.(3). Studying the application of CCM to the optimization problems. Us- ing some mathematical tools, we prove that CCM is hardly to escape from local minimum states in general. An alternate CCM is presented based on a modified energy function and it enhances the capability of the original CCM. A new algorithm is proposed by combining the alternative CCM with the original one, which enables the network to have lower energy level when trapped in local minima, and makes the network to reach the optimal or near-optimal state quickly. Another optimization problem: Multi-Traveling Salesman Problem(MTSP), an extension of the well known TSP is proposed and studied in detail. CCM is employed to solve the MTSP. Stability conditions of CCM for MTSP are exploited by mathematical analysis.(4). Studying the application of PCNNs to the optimization problems. Studies of the performance of the auto-wave in PCNNs aim at applying them to optimization problems, such as the shortest path problem. A multi-output model of pulse coupled neural networks (M-PCNNs) is studied. A new algorithm for finding the shortest path problem using MPCNNs is presented. Simulations are carried out to illustrate the performance of the proposed method. A static algorithm is presented to compute the SPT more efficiently for large scale computing problems. A dynamic algorithm to compute SPT is proposed also, from which the efficiency of the algorithm is improved greatly.