旅行商问题(Traveling salesman problem)是一个经典的组合优化问题,同时也是一个NP完全题,在周围的实际生活中应用非常普遍。比如应用在电路板的印刷制造、超大规模集成芯片制造、智能控制行业、机器人研究应用及控制等相关领域。考虑到其广泛的用途,因此,科学家、研究人员一直在试图寻求一种既能体现高质量的结果,同时也能快速收敛的最优或者近似计算算法。传统的相关领域的计算算法有分支定界法、支撑树加倍法、贪婪算法及局部收索法等,最近几年,一些地方出现了仿生算法,主要包括蚂蚁算法、模拟退火、遗传算法及神经网络等一些较为先进的算法,相比较传统的算法,这些算法的收敛程度一定程度上有了较大的改进,结果的质量也有所提高。遗传算法(Genetic Algorithm,简称GA)是通过模拟生物的自然选择与进化原理的基础上发展起来的全局性的概率搜索计算算法。在众多解决旅行商问题的方法中,遗传算法有着其他方法不具备的很多优点,对于中小规模旅行商问题,遗传算法可以得到最优解,对于大规模旅行商问题,可以得到近似最优解。在求解旅行商问题中,蚂蚁算法作为启发式算法,表现出优良的性能。较好路径上的外激素的浓度可以通过蚂蚁分泌外激素来加强,下一步所选择的路径按照路径上的外激素的浓度来被选择,进而越来越多的蚂蚁将会选择好的路径,较好的路径将会被更多的外激素所覆盖,所有的蚂蚁最终都集中到了好的路径上。整个算法的基本原理就是蚂蚁的这种基于外激素的正反馈原理,也是这个算法的关键之处所在。遗传算法具有快速的整体收索能力,但是对该系统运行过程中的反馈信息缺少充分的利用,结果会产生一些毫无用途的、繁琐的迭代,大大的降低了求解的效率。,蚁群算法是通过累积、更新外激素,最终达到收敛于最优路径的目的。因此,遗传算法具备分布式、并行性、全局性的收敛能力。但由于初外激素相对匮乏、结果导致算法进程缓慢。为了克服遗传算法和蚂蚁算法各自的缺陷,达到相互补充、优势互补,为此,本文采取先利用遗传算法进行随机搜索,迅速的、整体的产生收敛于相关问题的初始外激素分布的路线,接下来,充分利用蚁群的突出有点:正反馈机制、并行性及求解效率较高的特征,采取此混合后的计算算法,无论在时间效率,还是在求解质量上均属于的较优的启发式算法。通过对遗传算法和蚂蚁算法进行深入的研究、分析,最终本文将遗传算法与蚁群算法相结合并融合在TSP问题的求解中,进行的相关具体工作如下:1.通过查阅、阅读大量的专业文献资料,分析有关旅行商问题的产生的背景、国内、国际研究的进展状况、本文研究的目的、意义,同时提出本文的研究路线、方法及所要作的工作。2.分别阐述旅行商问题的概念、分类及旅行商问题相关的数学模型,具体介绍并分析几种经典的旅行商问题的求解算法,遗传算法和蚁群算法及其特点、基本原理、相关研究现状以及其相关改进算法3.通过以上内容的研究,概述了现有的混合遗传算法的基本规则,分析混合遗传算法的优缺点,通过分析研究几种解决旅行商问题的混合遗传算法,提出一种新的混合算法,并且对该算法的设计及编码方案进行详细的描述、分析,最后进行仿真实验,得出仿真实验结果,验证该混合算法的可行性、科学性,最终得出结论:新算法的优化效率和质量均优于基本蚁群算法和遗传算法。