旅行商问题(Travelling Salesman Problem,TSP)是一个经典的组合优化问题,也是一个NP完全问题,它已经成为并将继续成为测试组合优化新算法的标准问题。TSP在实际中的应用很广泛,例如超大规模集成芯片制造、印刷电路板制造、机器人控制等诸多领域。鉴于TSP的重要实际意义,研究者一直在努力寻找一种既能找到质优解,又能保证高效收敛性稳定性的算法。从理论上讲,穷举法不但可以保证TSP问题有解,而且还可以最终得出该问题的最优解。但是在现有条件下,使用常规的穷举法在如此庞大的搜索空间中寻求最优解是不实际的,所以,产生了许多优化算法。求解TSP的传统求解算法主要有:分支定界法,改良回路法(逐次修正法)、贪婪算法(最邻近法)、最小生成树法、局部搜索法、多边交换调整法等;现代优化算法主要有:模拟退火算法、遗传算法、蚁群算法、粒子群优化算法、禁忌搜索算法、Hopfield神经网络算法等。免疫系统具有很强的鲁棒性、适应性和固有的并行性,这些特点给予了免疫算法可在并行处理等领域得以越来越广泛的应用的前提。目前,并行免疫算法已成为免疫算法研究的一个重要方向。本文探索的课题就是将并行免疫算法融合在TSP问题的求解中。首先,本文综述了并行计算、基本免疫算法和并行免疫算法的发展及特点,给出了并行实验所需的硬件基础和软件设置,并重点介绍了PC机群及该并行平台上采用的并行编程环境MPI。其次,将TSP问题与图论结合,将其转化为求解哈密尔顿回路问题,并作形式化描述。再次,针对免疫算法求解到一定程度后往往对系统的反馈信息利用不足,尤其是在求解较大规模问题时往往效率不高的缺陷,提出了一种新型并行免疫算法。此算法基于一种主从-粗粒度模型,在保证群体的稳定性、多样性的同时提高了解的精确度和收敛速度。最后,将此算法应用于求解TSP问题,使用C语言编写程序并调试运行。实验结果表明,同其它算法相比较,本文提出的并行免疫算法提高了解精度和收敛速度,在求解较大规模TSP问题时表现出较强的搜索能力,在稳定性上也有良好表现,且求出最优解的机率较大。并行免疫算法的应用研究将有助于其他组合优化问题的解决。