Research On TSP Using Parallel Immune Algorithm

TSP(Travelling Salesman Problem,TSP)is a classic combinatorial optimization problem, and is also a NP complete problem. It has become and will continue to become a standard problem to test a new algorithm of combination optimization and has been widely used in practice, for example,in manufacturing ultra-large-scale integrated chip,producing printed circuit board and controlling robots, etc. On the basis of these significance, researchers keep searching a best approximation algorithm which has not only high-quality solution but also a fast convergence and stability method. Theoretically speaking, the enumeration not only can solve TSP, but also can get the best answer. Under the current situation, it is hardly to obtain its best answer in such huge researching space by using common enumeration. Therefore, a number of different algorithms to solve TSP emerged.Traditional methods include branch-and-bound method, Successive Correction, greedy algorithm, MST(minimum-cost spanning tree), local search, multilateral of adjustment, etc. The modern optimization methods include simulated annealing, genetic algorithm, ant algorithm, Particle Swarm optimization, Tabu Search Algorithm, Hopfield neural networks .etc. Among of them,Immune Algorithm(IA)is one of advanced technologies.Immune system has strong robustness, adaptability and inherent parallelism. These features give the premise to IA to be more widely used in the area of parallel processing. At present, the parallel immune algorithm(PIA) has become an important direction of immune algorithm. This thesis explores how to integrate Immune Algorithm into solution of TSP.First, the development and the characteristics of parallel computing, the basic immune algorithm and the parallel immune algorithm are reviewed in this thesis, hardware and software settings required for parallel experiments are given, the PC cluster and the parallel programming environment MPI on it are also mainly described. Second, the TSP is translated to a special Hamiltonian path problem, and the problem is formulated. Then, for dealing with the defect, the feedback system is often under-utilized when immune algorithm runs to a certain degree, especially in solving large scale TSP, a new parallel immune algorithm is proposed. This algorithm is based on a master-slave - coarse-grained model. It ensures population stability, diversity, and increase understanding of the accuracy and convergence speed. Finally, this algorithm is applied to solve the TSP problem. The procedure is programmed by C language, and is compiled and run.Experimental results show that, compared with other algorithms, parallel immune algorithm proposed in this paper improves the solution accuracy and convergence speed. When solving large scale TSP problems, it has strong search capabilities, a good stability and a greater probability of getting optimal solution. The research of the Parallel Immune Algorithm application will help to solve other combinatorial optimization problems.