遗传算法是一种模拟自然界生物进化的搜索算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且已在众多领域得到了实际应用,取得了令人瞩目的成果,引起了广大学者和工程人员的关注。TSP问题是一个典型NP难题,具有广泛的应用,多年来一直是学者们研究的热点。由于大多数学者认为NP问题不存在多项式时间内的完全算法,因此设计TSP问题的近似算法具有非常重要的意义。TSP问题还成为了衡量近似算法效率的主要标准。本文对遗传算法的理论与应用进行了一些研讨。首先介绍了遗传算法的基本原理及其应用,其次分析了TSP问题的研究现状、数学模型、求解方法等,最后在标准遗传算法的基础上提出了改进的遗传算法。针对TSP问题的特点,在遗传算法的交叉过程中对边的邻接状况采用了新的评价标准,结合顺序交叉算子和贪婪策略,本文设计提出了两种新的交叉算子:顺序插入交叉算子与动态顺序插入交叉算子,它们有效地利用了局部信息,并且能很好地继承父代的优秀基因段,实例仿真表明了该算法的可行性和有效性。