遗传算法(Genetic Algorithm，简称GA)由John Holland于1975年提出，对于传统方法难于求解的组合优化、模式识别、图像处理等复杂问题，使用该算法求解能得到令人较为满意的解。近年来，遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时表现出的鲁棒性、全局性、隐并行性和自适应性使其成为一种应用日益广泛的智能优化算法。 TSP是组合优化中最为著名的问题，它综合了一大类组合优化问题的典型特征，并以不同的形式存在于超大规模集成芯片制造、印刷电路板设计、X—射线结晶学、机器人控制等高科技领域。 由NP完全理论可知，TSP属于NP难问题，用常规的搜索方法无法有效地求解。但如今正迅速发展的按自然法则计算的思想在求解大规模组合优化问题时表现出非凡的潜力，其中的一个分枝—遗传算法以其独有的魅力吸引了越来越多的研究者。 经典遗传算法的主要特点在于它的简单性和鲁棒性，几乎不需要知道所求问题的任何知识，但也正是由于这一点，遗传算法不能利用问题本身的信息，影响了求解具体问题时的效率。因此，在研究利用遗传算法求解TSP问题上我们存在很大的改进空间。 本文对遗传算法的理论与应用进行了一些研究和分析工作。首先介绍了遗传算法的理论和它在组合优化问题中的应用，然后针对TSP问题的求解进一步指出遗传算法存在易陷入早熟收敛和后期收敛速度慢的缺点，最后本文在原有遗传算法的基础上提出了一种改进的遗传算法。由于考虑到交叉算子和变异算子对算法的多样性影响，因此交叉算子和变异算子是本算法改进过程中主要关注的两个问题。本算法在交叉算子方面结合启发式交叉和边重组交叉算子设计出一种新的交叉算子；在变异算子设计上，采用了—种新的变异算子—转位算子。另外，在进化过程中算法引入自适应策略来控制遗传参数的变化，加快了种群的收敛速度。本文使用改进型遗传算法对国际通用的TSP测试库TSPLIB中不同城市规模的数据进行测试，实验数值结果证明了该算法的可行性和有效性。