An Improved Genetic Algorithm For TSP

This dissertation is composed of three parts. In the first part we introduce the background of our research, describe the optimization problem and give a survey about math and evolutionary computation on how to solve the optimization problem.In the second part, we do research on genetic algorithm. A brief analysis is made on conventional genetic algorithm, and some improved computations are also talked about. Based on the algorithms, we proposed a new genetic algorithm based on comparability. In the third part, we discuss the application of the new genetic algorithm to solve the representative Traveling Salesman Problem (TSP) and job-shop scheduling. Compared with the conventional method, the experimental results of the new algorithm show the advantageous performance. The main research work and innovative points as follows:1. We define the distance, comparability and neighborhoods. Distance can reflect the difference between individuals;comparability is designed to describe how close two individuals are;and neighborhoods are used to realize the division of population.2. The grading strategy is imported in the producing process of new solution: dividing the population by adaptive value. We choose different evolutionary operations in different grades. Firstly, it is capable for individual to acquire new solution based on comparability;secondly, it can avoid the "blind" in producing new solution;thirdly, it makes child get the better dominant characters from the parent. Moreover, it ensures a variety of population that keeps worse individuals with certain probability and replaces repeating individuals by random individuals. Finally, it can achieve a balance between better effect and efficiency. And we design the accelerating operator to search the optimum much faster.3. We propose an genetic algorithm based on similarity which is applied into TSP. Combined with the characteristic of TSP, it defines the distance, comparability and neighborhoods of TSP, and designs an accelerating operator up to TSP in the algorithm. The numerical experiment indicates a faster convergence and a preferable solution.4. The TSP in the dissertation is concluded. We state the history and the present situation, math models, time complexity and the evaluation criterion. Then we do a certain summary and analysis on how to solve TSP. At last, we present the development on genetic algorithm to solve TSP.