An Improved Immune Algorithm for Solving TSP Problem

Abstract:

Immune algorithm is a set of computational systems inspired by the defense process of the biological immune system, and is widespread used in the combinatorial optimization problems. This paper describes an improved immune algorithm to solve the combinatorial optimization problems. The TSP problem is a typical application of the combinatorial optimization problems. The improved immune algorithm which based on the quantum principles is proposed for finding the optimal solutions to solve the TSP problem. In process of solving TSP problem, the quantum concept is used in initializing a population of quantum bit chromosomes. In the antibody’s updating, the general quantum rotation gate strategy and the dynamic adjusting angle mechanism are applied to accelerate convergence.According to the analysis of the experiment, the algorithm is not only feasible but also effective to solve TSP problem. It effectively relieves some disadvantages of the quantum and immune optimization.

• Periodical: Advanced Materials Research (Volumes 468-471)
• Pages: 678-682
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.468-471.678
• Online since: February 2012
• Authors: Hong Quan Xue, Sheng Min Wei, Lin Yang
• Keywords: Immune Optimization, Improved Immune Algorithm, Quantum Optimization, TSP Problem

References

[1] LN.de Castro, J.Timmis: Artificial Immune System:A New Computational Intelligence Approach(Springer-Verlag, Heidelberg 2002).

[2] E.Hart, J.Timmis:Application areas of AIS: Applied Soft Computing.Vol.8(2008),p.191.

[3] Zhuhong Zhang: Applied Soft Computing.Vol.7(2007),p.840.

[4] Licheng Jiao, Yangyang Li, Maoguo Gong, Xiangrong Zhang: IEEE Transcations on Systems, and Cybernetics-part B.Vol.38(2008),p.1234.

DOI: 10.1109/tsmcb.2008.927271

[5] Jiaquan Gao,Jun Wang: Applied Mathematics and Computation. Vol.217(2011),p.4754.

[6] Hong Guo, Juheng Zhang, Gary J. Koehler: Decision Support Systems. Vol.46(2008), p.318.

[7] Dorigo M, Maniezzo V, and Colorni A: IEEE Transactions on SMC,Vol.26(1996), p.29.

[8] Guan-Chun Luh, Chung-Huei Chueh: Information Sciences, Vol 179(2009), p.1516.

[9] Licheng Jiao, Lei Wang: IEEE Transaction systems, Vol.9(2000), p.552.

[10] http://www.hackchina.com/r/46734/att48.txt__html.