SIMULATED ANNEALING ALGORITHM FOR TRAVELLING SALESMAN PROBLEM

Abstract

Sensitivity and Robustness is the key factor while designing the controller for nonlinear systems. One of the performance objectives for controller design is to keep the error between the controlled output and the set-point as small as possible. The control of many non-linear, inherently unstable systems using conventional methods is both difficult to design and marginally satisfactory in implementation. The introduction of optimization techniques in control engineering that makes use of evolutionary computation and an implicit imprecision is successful in counteracting these limitations. The field of computational intelligence has incorporated to such systems with an objective to achieve higher optimality and satisfactory performance. The main objective of this work is to design "Simulated Annealing Algorithm" for the well known "Travelling Salesman Problem". In "Travelling Salesman Problem" the primary goal is to reduce the cost (i.e. the distance travelled by the person to cover all the cities once and once and return to their starting city). Basically, the aim is to achieve "Global Minima" in the total search space given. In this algorithm, firstly a random route is selected and its cost is calculated then onwards, according to "Metropolis Criteria" acceptance and rejection of route are done to improve the cost. For this purpose; the supporting theory of "Simulated Annealing Algorithm" and "Travelling Salesman Problem" were discussed. After that, the mathematical analysis for the convergence of the "Simulated Annealing Algorithm" was discussed. Then onward, the algorithm is implemented for a small size "Travelling Salesman Problem" (i.e. 10 cities "Travelling Salesman Problem"). Then, the size of the problem is increased in the small steps. After that a comparative study of the "Simulated Annealing Algorithm" And "Tabu Search Algorithm" has been done