TSP（ traveling salesman problen，旅行商问题）是典型的NP完全问题，即其最坏情况下的时间复杂度随着问题规模的增大按指数方式增长，到目前为止还未找到一个多项式时间的有效算法。 TSP问题可描述为：已知n个城市相互之间的距离，某一旅行商从某个城市出发访问每个城市一次且仅一次，最后回到出发城市，如何安排才使其所走路线最短。简言之，就是寻找条最短的遍历n个城市的路径，或者说搜索自然子集X={1,2，…，n}（X的元素表示对n个城市的编号）的一个排列x（X）={V1，V2，…，Vn}，使T4=∑d（v,Vm）+d（Vnv1） 取最小值，其中d（V,V+1）表示城市V；到城市V艹1的距离。 TSP问题并不仅仅是旅行商问题，其他许多的NP完全问题也可以归结为TSP问题，如邮路问题、装配线上的螺母问题和产品的生产安排问题等，使得TSP问题的有效求解具有重要的意义。

（1）编码采用整数排列编码方法。对于n个城市的TSP问题，染色体分为n段，其中每一段为对应城市的编号，如对10个城市的TSP问题{1,2,3,4,5,6,7,8,9,10}，则1102|4|5|6|8|79|3就是一个合法的染色体。 （2）种群初始化在完成染色体编码以后，必须产生一个初始种群作为起始解，所以首先需要决定初始化种群的数目。初始化种群的数目一般根据经验得到，一般情况下种群的数量视城市规模的大小而确定，其取值在50~200之间浮动。 （3）适应度函数设k1|k2|…k…|k。为一个采用整数编码的染色体，D，为城市k到城市k的距离则该个体的适应度为 即适应度函数为恰好走遍n个城市，再回到出发城市的距离的倒数。优化的目标就是选择适应度函数值尽可能大的染色体，适应度函数值越大的染色体越优质，反之越劣质 （4）选择操作选择操作即从旧群体中以一定概率选择个体到新群体中，个体被选中的概率跟适应度值有关，个体适应度值越大，被选中的概率越大。 （5）交叉操作采用部分映射杂交，确定交叉操作的父代，将父代样本两两分组，每组重复以下过程（假定城市数为10）： ①产生两个【1,10区间内的随机整数n1和r2，确定两个位置，对两位置的中间数据进行交叉，如r1=4，r2=7