组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法求解，属于NP问题。随着问题规模的扩大，问题空间呈现组合爆炸特征，无法用常规的方法求解。旅行商问题(TSP)就是一个经典的组合优化问题，属于NP完全问题。 遗传算法是一种新兴的搜索寻优技术，它模拟达尔文的进化论，根据“优胜劣汰”的原则，借助选择、交叉、变异等操作逐步逼近最优解。具有隐并行机制和自适应性，因此他非常适合于多维，非线性和具有多峰值的问题。遗传算法早在六十年代由J．H．Holland等人提出，并在八十年代得以完善，发展成为标准式的遗传算法，从九十年代中期得到广泛研究与应用。遗传算法具有全局优化性和易操作性。最初应用于非数值计算方面，直到近几年才转向于TsP问题，并取得了一定的成果，吸引了越来越多的研究者，逐渐成为人工智能领域的一个研究热点。 本文以近年来国内外学者提出的遗传算法为基础，分析了基本遗传算法易于出现收敛缓慢现象的主要原因，并针对此引入导师证明的一个重要结论作为指导思想，在遗传算法中初始化、交叉和变异算子上进行了改进，有效地加快了收敛速度。并将改进后算法应用于求解TsPLIB中的两个问题，实验结果表明，改进后算法加快了算法的收敛速度，改善了求解的性能。