遗传算法是一类借鉴生物的进化规律(适者生存,优胜劣汰遗传机制)演化而来的随机搜索方法,具有隐并行性和全局寻优能力,鲁棒性强,操作简单。不需要确定的规则,采用概率化的寻优方法,能自动获取和优化搜索空间,自适应的调整搜索方向。遗传算法已被人们广泛地应用于组合优化,解决了许多传统优化方法难以解决的问题。旅行商问题就是组合优化中典型的NP难问题,应用遗传算法解决旅行商问题,不仅启发了其他问题的求解,更被广泛地应用于机器学习、信号处理、自适应控制和人工生命等领域。本文针对一类特殊的大规模TSP问题,提出了一个新的遗传算法,主要工作如下:1.结合带聚类特征的大规模旅行商问题,提出了一种在聚类过程中找到最优的簇的数目的方法,并据此将大规模TSP问题转化为若干个小规模问题。2.在聚类得到的各个簇中,设计了一种基于图论的交叉算子,在此基础上提出了一种改进的遗传算法,用该遗传算法求解各簇中的最优回路,并证明了算法的收敛性。3.提出了一种新的连接策略将各个簇中的最优回路连接成一个整体回路,在此基础上进行仿真实验,得到了较好的结果,证明以上的解决方案是有效的。