遗传算法是借鉴生物界自然选择和进化机制发展起来的全局的概率搜索算法。旅行销售商问题(TSP)是著名的NP完全难题，也是组合优化、计算机科学界经典的问题之一。本论文着重于对用遗传算法解TSP问题的近似求解的研究。论文中有意义的工作主要有以下几点：首先，本论文简介了简单遗传算法的基本原理、设计方法和基本步骤及其在TSP问题中的应用现状。并提出了根据种群中个体的分布情况和个体的多样性判定遗传算法的截止代数。其次，本论文通过仿真实例证明了遗传算法在解决NPC问题的领域内具有寻找最优解的能力。但是简单遗传算法具有收敛速度慢，易于陷入局部最优解的特点。本论文通过加入初始化启发信息和改进交叉算子的方法提高遗传算法的收敛性和解的精度。最后，本论文实现了粗粒度并行遗传算法。但是算法的收敛性和计算精度的提高并不明显有待于进一步的研究。