NP问题是计算机科学中对一类复杂度很高的问题的统称。日常应用中有很多地方都会遇到各种NP问题或者NP完全问题。NP完全问题内在的同构特性使得只要解决了一个NP完全问题，其它的NP完全问题都可以经过某些途径转化而解决。本文就是基于这样一个前提，通过研究一种改进的遗传算法来解决NP完全问题中的一个经典问题——旅行商问题。在研究过程中，针对旅行商问题，本文设计了从问题域到算法域的编码和解码方法，应用“排列法”来初始化种群;并设计了两种染色体操作算子:顺序交换算子和合法交叉算子，代替了经典遗传算法中的交叉算子和变异算子，以保证种群在进化过程中染色体的合法性;在种群进化选择方面，重新设计了一种新的仿生程度较高的选择算子——“毁灭算子”，并将其与经典遗传算法中的“轮盘赌”选择法相结合，作为改进算法的选择算子。最后采用Java语言设计并实现了一个算法验证系统，并与经典遗传算法做了对比实验。相关实验结果表明:本文设计并实现的染色体操作算子的适应性强;相对于经典遗传算法，改进的遗传算法具有更快的收敛速度;大多数情况下，改进后的遗传算法得到的解比经典遗传算法得到的解更优。