Application Of Artificial Immune Algorithm In TSP

With the continuous development of immunological theory, people have had a deep understanding of biological immune system, and proposed artificial immune system. It has been widely used in scientific research and engineering practice in many areas.With a simple structure, Immune Algorithm (IA) has global convergence under certain conditions. By using random searching method, IA guarantees its global convergence, while its ability of finding local optimal is affected, and the convergence speed of IA is also not good. The Ant Colony Algorithm (ACA) uses much more information of the target problem. The convergence speed is much better, and the ability of finding local optimal is better, however, it will fall into the trap of local optimum. It can be said, IA supplies a global point searching technique, and ACA supplies a local surface searching technique. Two methods both have advantages and disadvantages.For the above problems of IA, this thesis improves it and gets the Immune Algorithm based on Ant Colony (IAAC). It used the strong local optimization ability and the fast convergence speed. The thesis combines with the idea of its positive feedback to produce a better solution in the taboo list, and extracting IA's vaccine from these better fragments, injecting vaccine into the updating stage of the group to solve the problem. By this way, it not only keeps the diversity of population, but also avoids the renewed antibodys which have a low affinity being eliminated in each iteration. This method allows point and surface search, making the two methods complement each other.In view of the too large scope in Affinity calculation method of Traveling Saleman Problem (TSP), this thesis designs a method of calculating affinity through the optimal solution and the worst solution of current generation. Its range is zero to one. If the affinity closes to one, antibody will close to the more excellent solution. On the contrary, antibody is worse while affinity is closer to zero.This thesis applied IAAC to TSP, and simulated BIA and IAAC by using the Visual C++ 6.0 platform. It also tested the eight examples of standard TSPLIB including Uleysses16, Uleysses22, Att48, Eil51, Berlin52, St70, Eil76, and Gr96. The test results showed that the method for solving TSP is effective.