Solving Combinatorial Optimization Problems By Neural Computing

The brain is a mysterious and complex system, which guides all the intelligent behaviors of organism, including the biological thinking, cognition, learning and memory and all other intelligence. Many outstanding scientists and researchers wish to construct a model or method by simulating the biological brain structure and operation mechanism. There is no doubt that these studies will give the scientific community and social community a huge and far-reaching impact. Since the re-emergence of artificial neural networks in eighties of last century, scientists have made a lot of exciting research results in this area. The applications of neural networks have been involved in the economic, military, engineering, medicine and science in all fields. It brings out many important results in the fields such as pattern recognition, image processing, automatic control and nonlinear optimization. Many famous companies such as Microsoft, Intel, IBM, etc.Companies have a lot of products of artificial neural networks. All of those indicate that neural computation approach holds an important scientific position.Neural computation approach is an important tool for solving combinatorial optimization problems. The dynamics analysis of artificial neural network is the basis of application. Generally, the stability of recurrent neural networks includes monostability and multistability. Usually, the optimal solution to the combinatorial optimization problems is not a single point. Therefore, we will discuss the multistability of the recurrent neural networks in the dissertation, and study their properties and performance to solve combinatorial optimization problems. The main contributions of the dissertation are as follows:(1) In the second chapter the Lotka-Volterra neural networks is discussed. A new approach to solve traveling salesman problem (TSP) by using a class of Lotka-Volterra recurrent neural networks is presented. Some stability criteria that ensure the convergence of valid solutions are obtained. It is proved that an equilibrium state is stable if and only if it corresponds to a valid solution of the TSP. Thus a valid solution can always be obtained whenever the network convergence to a stable state. A set of analytical conditions for optimal settings of LVNN is derived. Simulation results illustrate the theoretical analysis.(2) Since the original columnar competitive model (CCM) model is difficult to escape from local minimum; we give a new formulation to express the constraints. Based on the new energy function, chapter 3 proposes an improved columnar competitive model (ICCM) to solve the traveling salesman problem. The ICCM with winner-take-all principle can derive solutions for the TSP. It shows that the competitive computational network guarantees the convergence to feasible states, and it it proved that the ICCM can escape from the local minimum. Experimental results show that the ICCM improve the quality of the solutions, and ensure that the network does not fall into local minima.(3) Chapter 4 presents a class of liner threshold recurrent neural networks for solving the nonlinear complementarity problem. The neural network model is derived from an unconstrained reformulation of the nonlinear complementarity problems. It is proved that the trajectories are still in the positive orthant with the initial state in the same orthant. The existence of the equilibrium points of the linear threshold neural networks is addressed in this chapter. In addition, the convergence of the trajectory of the LT neural network is studied. Simulations show that the proposed network is effective in solving these nonlinear complementarity problems.(4) Based on the characteristics of matrix inequalities, a class of liner threshold recurrent neural networks is proposed to solve the matrix inequalities. The neural network is shown to be completely convergent to the solutions of linear inequality and equality system. It also shows that the proposed neural networks can solve a linear program and its dual simultaneously. Moreover, it is interesting that the stable equilibriums equal to solutions of the linear inequalities and equality systems. Some examples solved by the proposed recurrent neural network are illustrated.