遗传算法(Genetic Algorithms)是一种模仿生物自然进化过程的随机搜索和优化算法,其优势在于可以高效的处理传统搜索方法难以求解决的非线性问题.遗传算法具有全局优化性和易操作性,由于其不受搜索空间的限制性假设的约束,具有广泛的适应性、并行性等特点,目前被广泛应用于函数优化、机器学习、模式识别等众多领域,并逐渐成为人工智能领域的一个研究热点.　　TSP问题是一个经典的组合优化问题中的NP难问题,有效地解决TSP问题在可计算理论上有着重要的理论价值,同时也有着极高的实际应用价值.而且遗传算法在 TSP问题求解问题的应用研究,对于构造合适的遗传算法框架、建立有效的遗传操作等都有重要意义.　　本文从求解TSP问题出发对遗传算法作了细致地分析及研究.首先介绍了遗传算法的理论及应用领域;然后针对TSP问题的求解进一步指出遗传算法求解TSP问题一大难题是如何快速收敛到最优解并防止”早熟”现象发生.为了解决这一难题,本文对群体、遗传算子作了详细地讨论,得出解决”早熟”现象的一些微观策略;对于遗传算法在进化后期局部搜索能力较差,可以适当的加入局部搜索算法提高其运行效率.根据这些策略对遗传算法进行改进:结合TSP问题最优路径中一般包含城市与其最近城市相连的特点,提出了两点插入变异算子,改进了启发式交叉算子,并根据个体适应度与群体平均适应度的比较赋予不同的变异概率,使得较好的个体探测路径,较差的个体开发新个体.另外,对初始群体进行局部优化提高其质量加快算法的收敛速度;若最优个体连续几代一直保留,则采用局部微调对其进行局部搜索,从而使得子代中最优个体跳离局部解.通过仿真实验,改进的算法能较快地收敛到TSP问题的已知最优解;其测试结果与国际标准测试库TSPLIB中的最优路径相比,或接近或优于。