Improved Genetic Simulated Annealing Algorithm And Its Application In Traveling Problem

The idea of simulated annealing algorithm was firstly given out by Metropolis in the year 1953, and it was successfully imported into the combinational optimization area in 1983 by Kirkpatrick. The algorithm originates from the simulation of the solid substance' s cooling process. While the heated solid was slowly cooling, the temperature would get the lowest point, this phenomenon aroused people' s interest. Through the particular observation and research, people found that the particles inside the solid gradually became an orderly manner while the temperature is down, and in every temperature the particles obtained an equilibrium. The process repeated and eventually the solid attained a basic statement in the room temperature and the inner energy reached lowest. The Simulated Annealing Algorithm made a simulation for the target function as the inner energy, in each temperature the algorithm carried out a long iterative in a Markov chain length to make the target function get a balance state, and ultimately achieve the most optimization state by sustained cooling process.Abstract Genetic algorithm is one kind of organic and adaptive random searching algorithm that simulates the evolution process and mechanism in nature to solve the optimization problems. It express the process of solving a problem as the process of survival of the fittest of the chromosome using for reference the idea of "survive the superior and eliminate the inferior survival of the fittest" in Darwin's nature selection and the genetic mutation theory of Mendel. It makes the population search the best acclimation individual by the incessant evolution to the chromosomes, in- cluding the selection operator the crossover operator the mutation operator and so on, and then gain the optimal solution or satisfactory solution. Genetic algorithm is a highly all-purpose optimal algorithm. Its coding technique and genetic operator is more simple. It has few requests to the condition of constrain in an optimization problem. It is very good at parallel and global searching. It can solve a great many actual questions and it has applied well in many fields such an machine learning pattern recognition image disposal optimization controller combinatorial optimization manage decision-making and so on. Despite genetic algorithm has been applied well in many fields, after all it is an new subject, its theory and method still have crudeness and itself has several shortages to be ameliorated and consummated ulteriorly. Although we have much theory study in genetic algorithm and we also can provide some theory to prove it could search the global optimal solution, genetic algorithm still has faultiness in theory. There are many problems still have not settled well, for instance the convergence rate estimator of multifarious improved algorithms have not been done well.Both GA and SA is the bionics algorithm of optimizing. They can be applicable to various problem of excellent. But at the same time they have some weakness too. When the GA solves the large-scale problem of excellent, its partial manhunt ability is worse. The calculation speed of the SA is too slow, in this paper,we combine the GA and SA together taking to repair each other short and put forward a new kind of the calculate way(Hybrid Genetic /Simulated -Annealing Algorithm—HGSA). This algorithm has several characteristics: (1)Alleviating the choice pressure of the GA. Strengthening the overall situation astringency of the algorithm. Improving the speed of finding the superior solution. (2) Making the algorithm launch many places. Raising the ability that the SA processes the part problem. (3) Speeding to search the progress. Raising the searching accuracy. Having the higher efficiency and extensive applicability.The Traveling Salesman Problem (TSP) is a very famous issue in mathematical field, it' s equal to find the right Hamilton circuit with lowest price in a symmetrical complete graph with n vertexes. This is a NP complete problem, while the question' s scale is too large, the possible solutions emerged explosive growth, and it' s very troublesome to find the precise solution.We presented the principle of the HGSA method which are frequently used to solve the TSP in this paper.and use vc++ to solve it, In conclusion, about The Traveling Salesman Problem, the HGSA algorithm is a very excellent algorithm.