旅行商问题(Traveling Salesman Problem,TSP)就是要决定一条经过图中所有顶点当且仅当一次且距离最短的回路,即距离最短的Hamilton回路。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题,属于典型的NP问题。因此,对TSP问题有效求解算法的研究具有十分重要的意义。本文通过对遗传算法和TSP问题求解的相关方法的分析与研究,提出了一种求解TSP问题的改进遗传算法,并通过具体实例验证了改进算法的有效性。首先,问题的规模对于TSP问题的求解来说是一个很重要的因素,其时间复杂度将随着问题规模呈指数形式增长。因此,分块求解方法是求解TSP问题的一种可行的方法。本文提出了一种基于最小生成树的TSP问题分块求解算法,以此达到降低问题的规模、缩短算法运行时间的目的。其次,交叉算子是遗传算法的核心算子,是遗传进化的动力。本文在研究EAX交叉算法的基础上,通过对比分析,指出多个子环路合并为一个环路的算法是EAX算法的一个瓶颈。为此,本文提出了多阶段环路合并算法解决该问题。同时,改进EAX算法中的e-set选择策略,并对EAX算法的解采用混合的局部搜索算法来加以修正。最后,针对所提出的改进算法,本文选择TSPLIB中典型的TSP问题实例,进行实际验证。实验结果表明,本文所提出的改进算法能够有效地求解TSP问题,使求解效率得到了一定的提高。