An Improved Genetic Algorithm's Application Research On TSP Problem

Genetic algorithm is a kind of random searching method using lives' natural selection and genetic mechanism. Its application predominance lies in complicated and non-linear problems, which are difficult for traditional searching methods. This paper analyzes the factors affecting the performance of Genetic Algorithm, a novel improved genetic algorithm (IGA) is described. The crosser probability and mutation probability can alter itself. If fitness of chromosome is above the average value of the population, it should assign the less Pc and Pm, chromosome can enter the next generation. If fitness of the chromosome is below the average value of the population, it should assign the more Pc and Pm, chromosome should be removed. The calculation result of an example shows that IGA is able to get the real-time information of population diversity during the process of evolution. IGA can keep the population's diversity as long as it keeps the population's convergency. The traveling salesman problem is a typical NP problem. This paper implements a program to resolve the TSP problem according to the improved Genetic Algorithm, and calculate a TSP problem of 48 cites. Comparing the calculation result of GA program and Simulated Annealing Algorithm. This paper describes the parameters selection and the coding method, fitness function design, population's initialization and genetic operators' design in the program of resolving the TSP using the improved genetic algorithm. The result proves that the improved GA program excels the SA program. The improved GA program can get the satisfied result in a short time.