求解TSP问题的三角形编码抗体克隆选择算法

Abstract

Abstract:

According to the analysis of the affections of the coding strategies and the basic operators, including crossover and mutation, we find that the schema theory can not analyse the Genetic Algorithm very well when it is used to solve the Traveling Salesman Problems (TSP). Because the non-binary coding strategy and the crossover overly destroy the TSP path, the good schema of the parents can not be inherited effectively. In order to overcome the above shortcoming of the Genetic Algorithm, a new artificial immune system algorithm for TSP, Hyper-mutation Antibody Clone Selection Algorithm (HACSA), is put forward in this paper. A new triangle-based path representation is adopted, and some heuristic mutation strategies based on the triangle coding method are also designed. The antibody clonal selection theory of immunology is used to enhance the local search performance of the antibody. Both HACSA algorithm and the corresponding genetic algorithms are implemented to the typical traveling salesman problems respectively. Experiments indicate that HACSA, behaving as an evolutionary strategy, is shown to be capable of solving complex machine learning tasks effectively like TSP. The experimental results show that HACSA can achieve or exceed the known optimal solution in over 60％ problems, but that almost all the corresponding immune system algorithms and genetic algorithms fall into the local maximum, and they can not lead to the satisfied solutions.

Key words: traveling salesman problems(TSP), artificial immune system, clonal selection, genetic algorithms

CLC Number:

TP183

References

［1］Michalewicz Z. Genetic Algorithm+Data Structure=Evolution Programs［M］. Berlin Heidelberg: Springer-Verlag, 1996.
［2］Dasgupta D, Forrest S. Artificial Immune Systems in Industrial Applications［C］//IPMM'99. Proceedings of the Second International Conference on Intelligent Processing and Manufacturing of Materials. Honolulu: IEEE press, 1999: 257-267.
［3］Gong Maoguo, Jiao Licheng, Du Haifeng, et al. Multiobjective Immune Algorithm with Nondominated Neighbor-based Selection［J］. Evolutionary Computation, 2008, 16(2): 225-255.
［4］Gong Maoguo, Jiao Licheng, Ma Wenping, et al. Multiobjective Optimization Using an Immunodominance and Clonal Selection Inspired Algorithm［J］. Science in China: Series F Information Sciences, 2008, 51(8): 1064-1082.
［5］尚荣华, 马文萍, 焦李成, 等. 用于求解多目标优化问题的克隆选择算法［J］. 西安电子科技大学学报, 2007, 34 (5): 716-721.
Shang Ronghua, Ma Wenping, Jiao Licheng, et al. Conal Selection Algorithm for Multi-objective Optimization Problems［J］. Journal of Xidian University, 2007, 34(5): 716-721.
［6］马文萍, 尚荣华, 焦李成. 免疫克隆优化聚类技术［J］. 西安电子科技大学学报, 2007, 34(6): 911-921.
Ma Wenping, Shang Ronghua, Jiao Licheng. Immune Clonal Optimization Clustering Technique［J］. Journal of Xidian University, 2007, 34(6): 911-921.
［7］戚玉涛, 刘芳, 焦李成. 求解TSP问题免疫算法的动态疫苗策略［J］. 西安电子科技大学学报, 2008, 35(2): 37-42.
Qi Yutao, Liu Fang, Jiao Licheng. Immune Algorithm for TSP with Dynamic Vaccination［J］. Journal of Xidian University, 2008, 35(2): 37-42.
［8］De Castro L N, Von Zuben F J. Learning and Optimization Using the Clonal Selection Principle［J］. IEEE Trans on Evolutionary Computation, 2002, 6(3): 239-251.
［9］Kim J, Bentley P J. Towards an Artificial Immune System for Network Intrusion Detection: an Investigation of Dynamic Clonal Selection［C］//Proceedings of Congress on Evolutionary Computation. Hawaii: IEEE Press, 2002: 1015-1020.
［10］陈国良, 王煦法, 庄镇泉, 等. 遗传算法及其应用［M］. 北京: 人民邮电出版社, 1996.
［11］Larraaga P, Kuijpers C M H, Murga R H, et, al. Genetic Algorithms for the Traveling Salesman Problem: a Review of Representations and Operators［J］. Artificial Intelligence Review, 1999, 13(2): 129-170.
［12］Homaifar A, Guan S. A New Approach on the Traveling Salesman Problem by Genetic Algorithm［C］//Proceedings of the 5th International Conference on Genetic Algorithms. San Mateo: Morgan Kaufmann, 1993: 460-466.
［13］Darrell W, Starkweather T, Fuquay D A. Scheduling Problems and Traveling Salesman: the Genetic Edge Recombination Operator［C］//Proceedings of the 3th International Conference on Genetic Algorithms. Palo Alto: Morgan Kaufmann, 1989: 133-140.
［14］焦李成, 杜海峰, 刘芳, 等. 免疫优化计算、学习与识别［M］. 北京: 科学出版社, 2006.
［15］Satoshi E, Naruaki T, Koji Y. Immune Algorithm for n-TSP［C］//Proceedings of the IEEE International Conference on Systems. San Diego: Man and Cybernetics, 1998: 3844-3849.

[1]	YUAN Haobo;WU Zhengguo;HOU Jianqiang;DANG Xiaojie. Accurate optimization algorithm for the antenna phase center [J]. Journal of Xidian University, 2017, 44(5): 64-68.
[2]	WEI Mingjun;WANG Yueyue;JIN Jianguo. Intrusion detection design of the impoved immune algorithm [J]. Journal of Xidian University, 2016, 43(2): 126-131.
[3]	CHEN Lihua;WANG Shicheng;LIU Zhiguo;SUN Yuan. Low cost geomagnetic matching navigation method [J]. J4, 2013, 40(1): 118-122+188.
[4]	ZHANG Yan;FENG Dazheng;QU Xiaoning. A Hybrid Phase Unwrapping Algorithm Combining Branch-Cut and Surface-Fitting for InSAR [J]. J4, 2012, 39(5): 47-53.
[5]	TONG Ming;QIN Kezhen;JI Hongbing. Video semantics robust watermarking method for the AVS compressed domain [J]. J4, 2011, 38(1): 28-33+46.
[6]	XU Zhanqi;JIN Xing;YANG Fan;HAN Sen. Hybrid genetic and tabu search algorithm for static virtual topology designs in three layers of optical networks [J]. J4, 2011, 38(1): 22-27.
[7]	LIU Xing-bao;CAI Zi-xing;WANG Yong;PENG Wei-xiong. Hybrid immune evolutionary algorithm for global optimization problems [J]. J4, 2010, 37(5): 971-980.
[8]	MA Jing-jing;YANG Dong-dong;JIAO Li-cheng. Immune nondominated adaptive particle swarm multi-objective optimization [J]. J4, 2010, 37(5): 846-851.
[9]	SUN Yi-fei;JIAO Li-cheng. Immune optimization algorithm based on the social network searching model [J]. J4, 2010, 37(4): 642-647.
[10]	HUANG Bo-hu;DUAN Zhen-hua. Application of the quantum genetic algorithm in web services selection [J]. J4, 2010, 37(1): 56-61+67.
[11]	SHANG Rong-hua;JIAO Li-cheng;WU Jian-she;MA Wen-ping;LI Yang-yang. Immune clonal multi-objective algorithm for unsupervised feature selection [J]. J4, 2010, 37(1): 18-22.
[12]	WANG Jiang-an;ZHUANG Yi-qi;LI Di;JIN Zhao. Study of optimum fitting using the genetic algorithm for multipath mitigation in GPS receivers [J]. J4, 2009, 36(6): 1044-1048.
[13]	LU Man-jun;ZHAN Yi;SI Xi-cai;YANG Xiao-niu. Extraction of the transient characteristics of the communication radiating source and individual indentification [J]. J4, 2009, 36(4): 736-740.
[14]	TIAN Xiao-lin;JIAO Li-cheng;GOU Shui-ping. SAR image segmentation using optimized FCM with weighted spatial function [J]. J4, 2008, 35(5): 846-852.
[15]	QI Yu-tao;LIU Fang;JIAO Li-cheng. Immune algorithm for TSP with dynamic vaccination [J]. J4, 2008, 35(1): 37-42.

Hyper-mutation antibody clone algorithms for TSP

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

Recommended 0