TSP问题是最经典的NP-hard组合优化问题之一。实际中有很多应用问题都可归结或转化为TSP问题。由于其计算的复杂性较高,长期以来,研究者一直在寻求快速、高效的近似算法,以便在合理的时间内解决问题。传统的求解方法包括动态规划法、贪婪算法、局部搜索法和分支定界法等。在面对较大规模的问题时,使用这些方法得到的解比较粗糙。近年来,研究者们陆续采用了一些新的算法,如遗传算法、模拟退火、神经网络和蚂蚁算法等,取得了较好的效果。 遗传算法(GA)是借鉴生物选择和进化机制发展起来的一种高度并行、随机和自适应搜索算法。特别适合于处理传统搜索算法解决不好的复杂和非线形问题。它的两个最大的显著特点是隐含并行性和全局搜索。对遗传算法及应用的研究成为智能计算的研究热点之一。 本文结合遗传算法的主要工作如下: 1.详细地讨论和分析了遗传算法和单亲遗传算法应用于TSP问题的具体过程,与传统算法比较的优势所在以及还存在的不足。 2.针对以上算法的不足,在单亲遗传算法的基础上提出了一种改进的算法,该算法采用了新的编码方案,同时引入禁忌搜索思想,在提高收敛速度的同时避免了“早熟收敛”的现象。 3.设计了原型系统验证了该算法的有效性,经过充分的实验,在求解的速度和解的平均质量上与遗传算法和单亲遗传算法进行了对比,显示了较优越的特性。同时对该算法存在的问题进行了一定的分析,提出了进一步的研究的方向。