该文首先描述旅行推销员问题,并给出其数学模型.由于旅行推销员问题属于NP-难题,尽管有许多算法求解,但都未能找到最优解.由于它具有NP-难题的性质,因此,需另劈新路.在提出改进的遗传算法之前,先对传统的遗传算法进行介绍,并针对它存在的不足之处,提出好的解决方案.传统的遗传算法常采用城市次序编码和边编码.该文提出一种新的编码方式--矩阵编码,其优越性表现在比城市次序编码稳定,比边编码直观表示解,且矩阵形式易于判断个体对应的解是否合法和计算适应值.介绍的三种编码方法都会产生大量的非法个体,根据矩阵编码的特殊形式,提出一种比较好的修复办法--矩阵变异,在它的作用下,将存在的大量非法个体转化成合法个体,从而保证个体的多样性,扩大解空间,最终收敛到最优解.改进遗传算法求解TSP的程序在Matlab上实施.通过仿真结果表明,改进的遗传算法优于传统的遗传算法.