Research On Genetic Algorithm For Solving Traveling Salesman Problem

TSP (Traveling Salesman Problem) is a problem of combination optimization with simple definition but difficult to be solved, which attracts many researchers in various fields including mathematics, physics, biology and artificial intelligence (AI). It has become and will continue to become a standard problem to test a new algorithm of combination optimization. Theoretically speaking, the enumeration not only can solve TSP, but also can get the best answer. But to all computers nowadays, it's hardly to obtain its best answer in such huge researching space by using common enumeration. Therefore, all kinds of algorithms to solve TSP emerged because of demand. Among of them, Genetic Algorithm (GA) is one of advanced technologies.Genetic Algorithm (GA) are powerful search techniques. Parallel genetic algorithm (PGA) is one of the main research fields of genetic algorithms. It can efficiently satisfy the multiple needs of large-scale computing on a network of workstation clusters. Java language provides a parallel level with the language support, this characteristic is one of Java's great innovation, and for the design of parallel genetic algorithm provides the best technical support. In the collection of relevant information at home and abroad, read the related literature on the basis of this paper, systematic exposition of the principles of a genetic algorithm. In using the Java language, the author introduces a TSP genetic algorithm which uses a "roulette wheel" selection, Ordered Crossover operation and heuristic mutation. When the author understands the basic concept of parallel genetic algorithms, the author introduces two parallel genetic algorithm to solve the TSP problem.Chapter one describes the research projects in the background, the feasibility and significance of parallel genetic algorithm, as well as the basic theory of the problems faced by. The author also introduces the background of TSP and significance of research, and the content of the thesis.Chapter two describes the genetic algorithms and parallel genetic algorithm modelChapter three describes the basic theory of solving TSP with genetic algorithm, and introduces a genetic algorithm model. With examples, the author analyses the innovation of the algorithm.Chapter four describes two parallel genetic algorithm models to solve TSP, and discusses the process for TSP in detail. The author analyses the innovation of each parallel genetic algorithm, and compares their performance with examples.Chapter five sums up the entire research work and study in the direction of the future.