求解TSP问题的抗体克隆优化算法  

A Novel Antibody Clone Optimization Algorithm for TSP

作　　者：张瑜[1] 李涛[2] 吴丽华[1] 夏峰[1] 

机构地区：[1]海南师范大学信息学院,海南海口571158 [2]四川大学计算机学院,四川成都610065

出　　处：《四川大学学报（工程科学版）》2010年第3期127-131,共5页Journal of Sichuan University (Engineering Science Edition)

基　　金：国家自然科学基金资助项目(60573130;60873246);国家863计划资助项目(2006AA01Z435);教育部博士点基金资助项目(20070610032);海南师范大学引进博士科研启动项目(00203020214)

摘　　要：为解决传统求解TSP问题(Traveling Salesman Problem)的方法所固有的组合爆炸问题,提出了一种新的基于MHC(Major Histocompatibility Complex,主要组织相容性复合体)的抗体克隆优化算法(Antibody Clone Optimization Algorithm inspired by MHC,COAMHC)。该算法应用MHC分子单倍型特性将优秀抗体基因保存为MHC串,并通过疫苗接种遗传至子代以增强其局部搜索能力;应用MHC分子多态性并通过基因突变以及随机引入新抗体基因来提高抗体群多样性,以增强其全局搜索能力。通过TSP问题的仿真实验表明,该算法在收敛速度、和求解精度方面比经典克隆选择算法CLONALG性能更好。To address the traditional Traveling Salesman Problems （TSP） with the combinatorial explosion property,a novel MHC-inspired antibody clone optimization algorithm （COAMHC） was proposed by drawing inspiration from the features of Major Histocompatibility Complex （MHC） in the biological immune system.COAMHC preserves elitist antibody genes through the MHC string to improve its local search capability and improves the diversity of antibody population by gene mutation and some new random immigrant antibodies to enhance its global search capability.The experiments of comparing COAMHC with the canonical clone selection algorithm （CLONALG） were carried out for the TSP and results indicated that the performance of COAMHC is better than that of CLONALG.The COAMHC algorithm provides new opportunities for solving previously intractable optimization problems such as TSP.

关 键 词：人工免疫系统 TSP MHC 抗体克隆算法 优化 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]