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

J4 ›› 2009, Vol. 36 ›› Issue (3): 527-534.

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

杜巍¹,杜海峰²,栗茂林³

(1. 西安交通大学管理学院，陕西西安 710049;
2. 西安交通大学公共管理与复杂性科学研究中心，陕西西安 710049;
3. 西安交通大学现代设计及转子轴承系统教育部重点实验室，陕西西安 710049)

收稿日期:2008-10-27 修回日期:2008-11-14 出版日期:2009-06-20 发布日期:2009-07-04
通讯作者: 杜巍
基金资助:
国家自然科学基金资助(50505034;70671083);教育部“新世纪优秀人才支持计划”资助(NCET-07-0668);西安交通大学“985工程”二期重点项目资助(07200701)

Hyper-mutation antibody clone algorithms for TSP

DU Wei¹;DU Hai-feng²;LI Mao-lin³

(1. School of Management, Xi'an Jiaotong Univ., Xi'an 710049， China;
2. Research Center of Public Administration and Complex Sci., Xi'an Jiaotong Univ., Xi'an 710049， China;
3. Key Lab. of Edu. Ministry for Modern Design and Rotor-Bearing Sys., Xi'an Jiaotong Univ., Xi'an 710049， China)

Received:2008-10-27 Revised:2008-11-14 Online:2009-06-20 Published:2009-07-04
Contact: DU Wei

摘要/Abstract

摘要：

在探讨遗传算法求解TSP问题中编码方式和交叉、变异算子作用特点的基础上，发现模板理论已经不能很好地适应TSP问题，主要是因为非二值符号编码和交叉算子对边的过度破坏导致子代难以继承父代的优良模式．为了克服上述问题，提出一种三角形表示的路径编码方案，并给出相应的启发式路径搜索策略;引入生物免疫系统的克隆选择机理加强局部搜索，进而构造一种适合TSP问题求解的人工免疫系统算法——超变异抗体克隆选择算法(HACSA)．典型TSP问题的求解表明，和Endoh等人的免疫算法和遗传算法相比，HACSA的计算复杂度相当，60％以上的求解结果达到或者超过问题已知的最优值，而相应的免疫算法和遗传算法几乎均陷入局部极值，无法获得满意的求解结果．

关键词: TSP问题, 人工免疫系统, 克隆选择, 遗传算法

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

中图分类号:

TP183

杜巍杜海峰栗茂林. 求解TSP问题的三角形编码抗体克隆选择算法[J]. J4, 2009, 36(3): 527-534.

参考文献

［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]	孙骞,张家瑞,高岭,王宇翔,杨建锋. 一种改进的边缘层节点健康态势预估方法[J]. 西安电子科技大学学报, 2020, 47(3): 32-39.
[2]	谢凡,冯莉芳. 可见光辅助中继通信系统与功率分配方案[J]. 西安电子科技大学学报, 2020, 47(1): 95-103.
[3]	杨亚君,陈章. 分块制造下硬件木马攻击方法及安全性分析[J]. 西安电子科技大学学报, 2019, 46(4): 167-175.
[4]	呙鹏程;王星;程嗣怡;汪峰. 改进Chirplet时频原子的非线性调频信号分解[J]. 西安电子科技大学学报, 2018, 45(1): 123-128.
[5]	袁浩波;吴征国;侯建强;党晓杰. 天线相位中心的精确优化算法[J]. 西安电子科技大学学报, 2017, 44(5): 64-68.
[6]	任衍青;逯志宇;巴斌;王大鸣. 锐化遗传直接定位快速估计算法[J]. 西安电子科技大学学报, 2017, 44(4): 144-150.
[7]	魏明军;王月月;金建国. 一种改进免疫算法的入侵检测设计[J]. 西安电子科技大学学报, 2016, 43(2): 126-131.
[8]	王晓丽;王宇平;孟坤. 考虑处理机释放时间的可分任务调度优化模型[J]. J4, 2016, 43(1): 47-53.
[9]	龚昌妹;邵晓鹏;吴腾飞;代伟佳;刘杰涛;张建奇. 随机散射光波的全局优化调幅聚焦[J]. J4, 2016, 43(1): 99-104.
[10]	吴凯;苏涛 . 全通型分数延时滤波器的设计[J]. J4, 2015, 42(4): 8-13.
[11]	葛琳;季新生;江涛 . 利用E-IGA-RBF的网络信息内容安全事件态势预测[J]. J4, 2015, 42(4): 107-113.
[12]	冯学勇;杨林;龚书喜;王建晓. 可用于基站天线测量的平面波产生器的设计[J]. J4, 2015, 42(3): 33-37.
[13]	王尔申;张淑芳;蔡明;庞涛. 遗传粒子滤波的GPS接收机自主完好性监测[J]. J4, 2015, 42(1): 136-141.
[14]	刘帆;张凯;焦李成;杨淑媛. 结合最优亮度分量的遥感图像融合方法[J]. J4, 2014, 41(6): 45-50.
[15]	陈励华;王仕成;刘志国;孙渊. 一种低成本地磁匹配导航方法[J]. J4, 2013, 40(1): 118-122+188.