机器学习论文张瑞

《机器学习论文张瑞》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.0成绩:机器学习姓名：张瑞班号：05071402学号：2014301384目录第1章绪论1.1蚁群算法概况第2章基本蚁群算法简介2.1基本蚁群算法的原理2.1.1蚁群行为描述2.1.2基本蚁群算法的机制原理2.2基本蚁群算法的系统学特征2.2.1分布式2.2.2自组织2.2.3正反馈第1章绪论蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者M.Dorigo，V.Maniezzo等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之

2、间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做信息素（Pheromone）的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。1.1蚁群算法概况M.Dorigo等人于1991年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生

3、物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征[1]，以及该过程与旅行商问题求解之间的相似性。得到了具有NP难度的旅行商问题的最优解答。同时，该算法还被用于求解Job-Shop调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。蚁群算法之所以能引起相关领域研究者的注意，是因为这种求解模式能将问题求解的快速性、全局优化特征以及在有限时间内答案的合理性结合起来。其中，寻优的快速性是通过正反馈式的信息传递和积累来保证的。而算法的早熟性收敛又可以通过其分布式计算特征加以避免，同时

4、，具有贪婪启发式搜索特征的蚁群系统又能在搜索过程的早期找到可以接受的问题解答。这种优越的问题分布式求解模式经过相关领域研究者的关注和努力，已经在最初的算法模型基础上得到了很大的改进和拓展。以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究[2]。美国五角大楼正在资助关于群智能系统的研究工作-群体战略（SwarmStrategy），它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行

5、。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题。多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通[5]等领域。蚁群算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题

6、、车辆调度问题等。蚁群算法在若干领域已经获得成功的应用，其中最成功的是在组合优化问题中的应用。第1章基本蚁群算法简介1.1基本蚁群算法的原理1.1.1蚁群行为描述根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放出一种特殊的分泌物——信息素来寻找路径。当它们碰到一个还没有走过的路口的时，就随机的挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其

7、他路径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快的重新找到最优路径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群行为找出最优路径。这里用人工蚂蚁觅食图来描述蚁群搜索原理。图2.1人工蚂蚁觅食模拟图2.2人工蚂蚁觅食模拟图2.3人工蚂蚁觅食模拟图2.1中，设A点是蚁巢，D点是食物源，EF之间区域是障碍物。由于障碍物的存在，蚂蚁只能经由A经E或F到达D，或由D到达A，各点之间的距离如图2.1所示。

8、假设每个时间单位有30只蚂蚁由A到达D点，有30只蚂蚁由D到达A点，蚂蚁过后留下的信息量为1。为了方便起见，设该物质停留时间为1。在初始时刻，由于路径BF、FC、BE、EC上均无信息存在，位于A和D的蚂蚁可以随机选择路径，从统计学的角