分类号： O157 单位代码：10110 学 号：s20240075中 北 大 学硕 士 学 位 论 文改进的混合型蚁群算法与其应用 改进的混合型蚁群算法与其应用 xxx硕士讨论生晶指导老师 xxx 教授 学科专业 应用数学 年 月 日图书分类号 O157 密级 非密 UDC 510 硕 士 学 位 论 文改进的混合型蚁群算法与其应用 晶 指导老师（、职称） xxx 教授 申请学位级别 理学硕士 专业名称 应用数学 论文提交日期 年月日 论文答辩日期 年月日 学位授予日期 年月日 论文评阅人 答辩委员会主席 年 月 日摘 要 旅行商问题（TSP）与车辆路径问题（VRP）自提出以来，许多学者进行了大量的理论讨论和实验分析，取得了非常显著的进展，已经成为了运筹学和组合优化问题领域的热点讨论问题
求解他们的算法主要有精确型算法、近似算法和启发式算法
在众多求解 TSP 算法中，蚁群算法具有较好的性能，该仿生智能算法和传统的算法截然不同，具有鲁棒性、正反馈、并行性和易与其他方法相结合等特点
自创立以来，无论理论讨论还是在应用方面都取得了突破性的进展，不但在求解以上两种问题上得到了最优解，而且在工件的排序问题、图着色问题、多目标函数等许多领域也取得了相当不错的效果，具有相当宽阔的进展前景
本文首先介绍了一种求解 TSP 问题的算法—改进的混合型蚁群算法，该算法在近邻法构造初始解的基础上，使用 2-opt 局部搜索法对当前解进行改进，在更新全局信息素时采纳基于排序的蚂蚁系统对排在前 2 名的蚂蚁更新全局信息素，且为全局信息素设置最大值和最小值，并使用 MATLAB 仿真求解了 kroa200 等 13 个经典 TSP 问题
通过仿真实验可以看出本文改进的算法在求解 TSP 问题时具有很好的效果，在求解很多问题时已经非常接近最优解或者优于最优解，和最优解相差的百分比基本都在1%以下，并和
