旅行商问题(Traveling Salesman Problem ,TSP)是一个典型的NP(Non-deterministic Polynomial)问题,有效地解决TSP问题在可计算理论上有着重要的理论价值。目前,在已有的各种求解TSP问题的算法中,基于人类免疫学的人工免疫新计算模型——免疫算法( Immune Algorithm, IA),凭借其具有较强的收敛性和较好的求解结果等优点成为目前学术界研究的热点。免疫算法是将人工免疫的概念及理论和遗传算法相结合,它不仅保留了遗传算法本身的优良特性,还通过增加免疫算子来抑制其迭代过程中出现的退化现象,并提高了算法的收敛速度。免疫算法是基于免疫系统的学习算法,在解决给定的最优化任务(称之为抗原)时,算法开始时收集一些估计参数(称之为抗体),每个抗体性能由其适应度和浓度来评估。在每一代,适应度好、浓度低的抗体允许交叉和变异,产生新的抗体形成下一代。这种受生物免疫系统启发的算法可以较快地导出复杂问题的有效解。免疫算法中的一个重要步骤就是交叉。在TSP求解中传统的交叉方法是部分匹配交叉,这种交叉方法要求较大的群体规模,算法效率较低,且容易陷入局部最优解。本文对已有的免疫算法进行了分析,并依据生物免疫系统的免疫机制提出了两点改进:(1)在算法中采用更加类似生物免疫系统的记忆细胞的处理方法,由简单地把单个最优个体作为记忆细胞改为生成记忆细胞群体,以增强解群在进化中的多样性;(2)引入“疫苗”的概念,先从父代中的信息抽取出得到疫苗,然后基于疫苗进行交叉,使交叉的效果得到了明显改善,也即在交叉过程中引入了自己学习的能力。首先,文中分析了影响免疫算法性能的几个重要参数,并通过仿真实验选择合适的参数值。其次,为了验证上述两点改进思想的有效性,用基于疫苗交叉的免疫算法对TSP问题进行求解,将改进的免疫算法与基本免疫算法和遗传算法进行了比较分析。以实验结果证明改进方法的有效性。最后,用改进的免疫算法在国际通用的TSP测试库中找到了一条比库中的最佳路径更优的路径和一条较优路径。