Traveling-salesman problem

Artificial Neural Networks have been widely used for obtaining solutions for combinational optimization problems. Traveling Salesman problem is a well known nonlinear combinational optimization problem. In Traveling Salesman problem, a fixed number of cities is given. An optimal tour of all these cities is required such that each city is visited only once and the total tour distance to be covered has to be minimized. Hopfield Networks have been applied for generating an optimal solution. However there are certain factors which result in instability and local optimization of Hopfield Networks. In such cases the solutions obtained may not be optimal and feasible. In this thesis, the application of the K-Means algorithm is combined with the Hopfield Networks to generate more stable and optimum solutions to traveling salesperson problem.

This report details an approach to solving the Traveling Salesman Problem (TSP) using learning automata and a unique geometric approach. Two-dimensional Euclidean TSPs are considered and the type of learning automata used are commonly called neural networks. A standard neural net algorithm called back propagation proved to be fairly good at learning the sample figures, but a newer substitute for back propagation, called counter propagation, performed extremely well. An important goal of this research was to derive increased theoretical understanding of the TSP. This goal has been satisfied, especially with regard to instabilities in path length and the order of points traversed along the minimal path route. In addition, some applications to larger point problems are considered, and it is shown that configurations with isolated clusters of relatively closely spaced points relative to the convex hull apexes and the fixed points map quite well into the geometric figures presented here.