遗传算法是模拟自然环境中生物的遗传和进化过程而形成的一种优化算法。它具有全局搜索能力、隐并行性、鲁棒性、操作简单等特点,常被用于解决一些传统优化方法难以解决的问题。旅行商问题(TSP)是组合优化领域中一个典型的NP难问题,它陈述起来简单,求解却很困难。但旅行商问题的求解不仅为其他算法提供了思想方法平台,同时也被广泛地应用于交通、物流、大规模生产、基因测序等领域,具有较高的理论和应用价值。本文主要针对对称型TSP,研究了TSP的遗传算法求解,主要工作如下:1、结合旅行商问题的特点,设计了一个新的遗传交叉算子,在此基础上提出了一种新的遗传算法,并且证明了算法的收敛性。2、针对一类特殊的大规模旅行商问题,首先,提出了一种新的聚类策略,将距离较近的点聚成一类,从而将大规模的TSP转化为若干个小规模问题;其次,给出了一种类的连接方法;最后,构造了求解这类特殊的大规模旅行商问题的有效算法。3、对提出的算法进行了数值模拟实验,得出了较为理想的结果,说明了本文所设计算法的有效性。