遗传算法是一种模拟自然界生物进化的高效智能搜索方法。遗传算法具有简单、通用、鲁棒性强,应用范围广等众多特点。尽管在理论和应用等方面遗传算法存在一定的不足,但它在组合优化问题求解、自适应控制等众多领域的应用中已经充分表现出了其自身的特色和优势。TSP问题是计算机科学中的典型问题,也是组合优化中问题求解中的一个典型问题,同时TSP问题也是广大科研人员在组合优化领域中研究最多的问题。TSP问题是一个典型的NP难题,已经成为测试组合优化算法的标准问题,具有广泛的应用前景,引起了广大科研工作者的注意,多年来一直是众多学者的研究热点。本文就TSP问题和遗传算法的理论和应用进行了探讨。首先介绍了TSP问题,并分析了TSP问题的研究现状、数学模型和现有的一些TSP问题求解方法,针对不同的方法,做了简单的分析。其次介绍了遗传算法的产生与发展和研究现状,并详细介绍了遗传算法的思想、特点、基本原理和主要流程。最后在标准遗传算法的基础上,针对TSP问题的自身特点,提出了改进的遗传算法来求解TSP问题。在改进的遗传算法中,首先利用聚类的方法和最邻近法计算出遗传算法中使用的初始染色体群。将整个初始染色体群放到初始染色体池T中,并在初始染色体池中计算局部最优解Tm ax;然后对染色体池T进行改良生成新的染色体池T ’;接着用染色体池T ’中的最优解迭代局部最优解Tm ax,并对染色体池T ’进行变异操作,最后用变异的染色体池T ’迭代染色体池T ;或者对染色体池T ’与局部最优解Tm ax之间进行交叉操作并迭代染色体池T ,一直到符合停止条件为止。该方法能很好的继承父代的优秀基因段。通过仿真实验的验证表明该方法具有很好的可行性,并且效率较高。