Traveling Salesman Problem Based On Genetic Algorithm Simulation Calculation

Traveling Salesman Problem (TSP) is the well-known combination optimizing problem, it colligates the classical typicality of a type of combination optimizing problem, and exists .in VLSI chip manufacture, printing circuit design, X-ray crystallography, robot control and many other high-tech fields. According to N P-completed theory, TSP belongs to NPH, it can't be solved by routine search methods, and different types of solutions must be employed. Genetic algorithm (GA) is showing its potential in solving large combination optimizing problem more and more.Considering existed problems TSP, dispatch problems of static state for PTV are studied and discussed with genetic algorithms (GA) and Hybrid GA. Making full use of intelligent characteristics of GA, static dispatch of PTV is improved effectively. Based on GA and the study of the immune principle of creature, immune algorithm is missed into GA, and they become an improved GA. This advanced algorithm—Immune GA (IGA) is applied to solve some optimization problems. The computing programs applying GA and IGA are simulated and compared. The results show that IGA is simple, efficient and robust.A hybrid algorithm usingd istributed PGA based on the DDs model and heuristic method (2opt) for rapid solution of Travelling Salesperson Problem (TSP) is presented. A c program based on this algorithm in Parallel Virtual Machine (PVM) environment is developed. In this hybrid method, the mutation is provided by the 2opt method which is one of the most well-known local searches algorithms among TSP solving algorithms. It improves the TSP tour and reverses order of the sub-tour. The DDs model is combination of global parallelism with coarse grained PGA. There is how ever no migration operator as such, because the whole population is treated during the evolution as a single collection of individuals. The main idea of the model is to cut down waiting time for the last individuals, by dynamic splitting the population into demes, which can then be processed without delay. It gives more efficiency in terms of processings peed.The algorithm is fully scalable. The proposed method is used to solve TSP on PC clustering computing system, the experiment results demonstrates that the new method is effective and valid.