遗传算法(Genetic Algorithms,简称GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及其应用的研究是目前智能计算的研究热点之一。TSP问题(Traveling Salesman Problem)是已知有n个城市,现有一推销员必须遍访这n个城市,且每个城市只能访问一次,最后又必须返回出发城市。要安排其访问次序,使其旅行路线的总长度最短。TSP是经典的NP-hard组合优化问题之一,也是一个测试算法优劣性的标准问题,且现实中有很多应用问题都可归结或转化为TSP问题。故对此问题的求解具有理论与实用两方面的意义。传统的求解方法在面对较大规模的问题时,很不容易得到最优解。近年来,研究者们陆续采用了一些新的算法,如遗传算法、模拟退火、神经网络和蚂蚁算法等,取得了较好的效果。本文的主要工作和创新点:1、在设计交叉算子和变异算子的过程中,利用了最短路径的数学性质和统计学规律,设计出改进的启发式顺序交叉算子和启发式变异算子,并与既有的OX、CX、ERC等算子进行了比较和分析。对基因规模、变异概率和交叉概率随着代数的增加而变化的动态性质进行了实验。并对遗传算子、每代最优解的进入和退出演化过程的性能进行了分析。2、在程序实现时,大量利用了STL和Boost的既有数据结构和算法,并利用了设计模式的知识,使程序的实现更加灵活高效。3、将改进的遗传算法应用于机械加工的孔群加工顺序模拟中,取得了良好的效果。