机器学习课程论文.doc

机 器 学 习 （课程论文） 基于蚁群算法的TSP问题研究 摘 要 本文研究了基于蚁群算法解决TSP问题的原理，算法流程以及用Microsoft Visual Studio 2008程序的仿真。论文首先简单回顾了蚁群算法的历史、发展以及应用，然后详细介绍了基本蚁群算法的原理，包括基本蚁群算法的行为描述和机制原理。其次从基本蚁群算法的系统学特征出发，讨论它具有分布式，自组织，正反馈等特征。接着引出了基本蚁群算法解决的TSP问题，先讨论了组合优化问题，然后从TSP问题的定义，实用价值，理论意义的角度对TSP问题进行阐述。并且重点运用Microsoft Visual Studio 2008的仿真方法，实现了基于蚁群算法的仿真，给出了求解TSP问题的数学模型，实现步骤，描述了蚁群算法的优缺点。论文最后以Microsoft Visual Studio 2008仿真实验为基础，对蚁群算法的主要参数进行了详细的讨论，并且给出了优化的参数选择，解决了算法中存在的不足。论文实现了基于蚁群算法对TSP问题的求解和仿真。 关键字：蚁群算法，组合优化，信息素，TSP问题 目 录 摘 要 2 第1章 绪论 4 1.1 蚁群算法概况 4 1.2 论文的主要内容 4 第2章 基本蚁群算法简介 6 2.1 基本蚁群算法的原理 6 2.1.1 蚁群行为描述 6 2.1.2 基本蚁群算法的机制原理 8 2.2 基本蚁群算法的系统学特征 9 2.2.1 分布式 9 2.2.2 自组织 10 2.2.3 正反馈 10 第3章 组合优化以及TSP问题简介 11 3.1 组合优化简介 11 3.1.1 引言 11 3.1.2 组合优化问题 11 3.1.3 NP完全问题 12 3.2 TSP问题简介 12 3.2.1 TSP问题的定义 12 3.2.2 TSP的实用价值 12 3.2.3 TSP问题的理论意义 12 3.3 基本蚁群算法的数学模型 13 第4章 基本蚁群算法求解TSP 15 4.1 基本蚁群算法求解TSP的实现流程 15 4.1.1 基本蚁群算法的实现步骤 15 4.1.2 基本蚁群算法的结构流程 15 4.2 关键参数介绍 17 4.3 不同参数设置的试验 17 4.3.1 信息素挥发度的设置 17 4.3.2 蚁群数量的设置 17 4.3.3 启发式因子的设置 17 4.4 不同参数设置的试验结果和结论 18 4.4.1 信息素挥发度的选择设置 18 4.4.2 启发式因子的选择设置 21 结论与展望 26 绪论 蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素（Pheromone）的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。 蚁群算法概况 M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式有哪些信誉好的足球投注网站算法。它充分利用了生物蚁群能通过个体间简单的信息传递，有哪些信誉好的足球投注网站从蚁巢至食物间最短路径的集体寻优特征[1]，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。 蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及在有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时，具有贪婪启发式有哪些信誉好的足球投注网站特征的蚁群系统又能在有哪些信誉好的足球投注网站过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。 以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究[2]。美国五角大楼正在资助关于群智能系统的研究工作-群体战略（Swarm Strategy），它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车