旅行商问题(Traveling Salesman Problem，TSP)是一个经典的组合优化问题，是多种复杂问题的一种简化形式。TSP问题的搜索空间随着城市数的增加而增大，在庞大的空间中寻找最优解，往往需要大量的求解时间，因此寻求一种求解时间较短、精度较高的算法来解决此问题就成为广大科研工作者的研究热点。在学习和研究的过程中了解到影响遗传算法性能的参数主要有初始种群的质量、群体的大小、交叉概率和变异概率的值等。因此本文提出了一种求解TSP问题的改进的遗传算法。由于遗传算法的基本依据是模式定理和“构造块”。当它对大量的构造块进行选择和重组时，常常导致构造块的破坏，使算法收敛或者局部最优。因此，用分布估计算法来求解TSP问题。论文主要研究如下：（1）针对遗传算法求解TSP问题，提出了基于适应度对种群进行分级，采用小种群并行育种的方式。让适应度较高的个体用于实现最优解的开采以保证算法的收敛性；适应度较低的个体对空间进行探索，以保证种群的多样性，避免陷入局部最优解。（2）论文使用了一种混合交叉算子。即PMX和一种启发式交叉算子，既可保留父代中较好的模式，又可以较大概率生成优于父体的个体。（3）论文对变异算子进行了改进，使用了一种混合变异算法。即2-OPT和一种贪婪倒位变异算子。（4）分布估计算法的特点是采用统计学习的手段，建立描述解分布的概率模型。该方法有效的避免了遗传算法中构造块的破坏问题，为求解TSP问题提供了一种全新的进化算法。改进后的遗传算法用于求解TSP问题时，体现了算法搜索到最优解所需的时间较短，且解的精度较高的优点。分布估计算法求解TSP问题时，体现出比改进的遗传算法更好的收敛特性，和收敛到最优解所需的时间较短。