遗传算法(Genetic Algorithm,简称GA)由John Holland于1975年提出,对于传统方法难于求解的组合优化、模式识别、图像处理等复杂问题,使用该算法求解能得到令人较为满意的解。近年来,遗传算法在解决连续变量的函数最优化问题和离散变量的组合最优化问题时表现出的鲁棒胜、全局性、隐并行性和自适应性使其成为一种应用日益广泛的智能优化算法。尽管遗传算法是模拟自然界生物进化过程与机制求解问题的一类自组织与自适应的人工智能技术,已广泛应用于计算机科学、人工智能、信息技术及工程实践。但是,相对于其鲜明的生物学基础,它的理论基础公认是不完善的,这种不完善主要表现在没有完整的理论解释算法的机理,缺少广泛而完整的有关GA收敛性理论,在算法性能方面还有不足之处,这促使研究者对GA的理论和性能作进一步的研究。旅行商问题(Traveling Salesman Problem, TSP)就是要决定一条经过图中所有顶点当且仅当一次且距离最短的回路,即距离最短Hamilton回路。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题,TSP是组合优化中最为著名NP问题,用常规的搜索方法无法有效地求解。但如今正迅速发展的按自然法则计算的思想在求解大规模组合优化问题时表现出非凡的潜力,其中的一个分枝----遗传算法,以其独有的魅力吸引了越来越多的研究者。本文在原有遗传算法的基础上提出了一种改进的遗传算法求解TSP问题,并进行了MATLAB仿真测试。其中在改进的策略中,提出K适应度选择算子,使种群的平均适应度大幅提高,有利于收敛速度加快;在交叉、变异算子中提出门限值D概念,防止在每次交叉中产生的子代退化现象和在每次变异过程中产生的早熟收敛现象,使其能够寻找到全局最优解。本文又使用改进型遗传算法对国际通用的TSP测试库TSPLIB中不同城市规模的数据进行测试,试验结果表明了改进算法的可行性和有效性。最后,本文将面向对象技术和XML技术相结合,以Microsoft Visual Studio 2005.NET为开发环境,C#为编程语言实现了改进遗传算法求解TSP问题的系统。