旅行商(TSP)问题是组合优化领域中的一个典型问题,涉及求多个变量的函数的最小值。虽然它陈述起来很简单,但求解却很困难,并且已经被证明是NP完全问题。但它确实广泛存在,且是诸多领域内出现的多种复杂问题的集中概括和简化形式。快速、有效地解决TSP问题有着较高的理论意义和实际应用价值,这就是本文提出的用改进遗传算法求解TSP问题的目的。近代科学技术发展的显著特点之一是生命科学与工程技术的相互交叉、相互渗透和相互促进。本文根据TSP问题的特点和当前研究情况,选用遗传算法来对它进行求解。论文首先介绍了遗传算法的原理及基本实现技术,并着重阐述了遗传算法的特性,再具体地针对传统遗传算法进行相应的改进。传统遗传算法在求解TSP问题时通常采用城市次序编码法和边编码法。本文提出了一种新的编码方式——矩阵编码,它比边编码更形象、直观地描述TSP对象,比城市遍历编码法更稳定,并且更容易判断个体的合法性和计算其适应度。针对编码产生的大量非法个体,根据矩阵编码的特殊形式,提出了一种较好的修复办法——矩阵变异,在它的作用下,将存在的非法个体转化为合法个体,并扩大了搜索空间,保证了个体的多样性,最终收敛到最优解。最后用Matlab6.5进行仿真,实验结果表明,本文提出的改进遗传算法在寻优时间上优于传统的边编码的遗传算法,并且收敛到全局最优解的几率高。