Improvement of Simulated Annealing Algorithm to Solve NP Complete problems
by
Nutan Mishra
Department of Mathematics and Statistics, University of South Alabama, Mobile, Alabama 36688, USA

Simulated Annealing Algorithm is one of the optimization algorithms to find the near optimal solutions to NP complete problems which are combinatorial in nature. It is one of the most popular algorithms to solve the problems pertaining to design and planning. VLSI design and traveling salesman problem are couple of examples where the said algorithm has been implemented successfully Although this is not a viable option for real time software where the response is desired in certain time limit. Simulated Annealing algorithm takes longer computer time to return the solution. Efforts have been done to improve the performance of the algorithm by reducing amount of times taken. Set of solutions are produced by the algorithms during the search of near optimal solution. This set has the markovian property among the elements which has been exploited by the Martin et. al. to improve the performance. The present article reviews the different techniques to improve the algorithm in the recent years.

Date received: October 29, 2002