Application of artifical neural network in optimization

Abstract

The simple, parallel, and stable recurrent networks are becoming an interesting alternative to conventional algorithms for solving optimization problems. In this thesis, the Hopfield Model of Neural Network is adopted to solve two problems namely "Optimal path determination between two nodes in a graph" and "Scheduling of n jobs on one machine". The Hopfield Model is adopted due to its ease of implementation and high potential of hardware realization in terms of analog and digital components. The Kohonen Network is used to solve the "Travelling Salesman Problem". From simulation point of view, the Kohonen Network takes less memory space as compared to that of Hopfield Model when applied to the " Travelling Salesman Problem". The number of neurons in case of Kohonen Model are n (for n cities problem) and the size of weight matrix is (nx2), where as in case of Hopfield Model, the number of neurons are n2 and the size of the weight matrix is n2xn2. The performance of Neural Networks is analysed in terms of running time. The results obtained show that for the problem "Optimal path determination between two nodes in a graph", the performance of Hopfield Model is between Dijkastra's and Floyd's algorithms for small size problem. But as the size of the problem increases, the performance of Hopfield Model improves considerably overf the performance of Dijkastra's and Floyd's algorithms. The results obtained for the problem " Scheduling of n jobs on one machine" indicates that, the performance of Hopfield Model is same as that of nearest neighbour algorithm for small size problem. But as the size of problem increases, the performance of hopfield Model improves considerably over nearest neighbour algorithm. The results obtained for "Travelling Salesman Problem" indicate that the performance of Kohonen Model is better than that of Hopfield Model and of nearest neighbour algorithm.