机器学习论文张瑞

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年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征1，以

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

4、最初的算法模型基础上得到了很大的改进和拓展。 以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究2。美国五角大楼正在资助关于群智能系统的研究工作-群体战略（Swarm Strategy），它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。国内，国家自然科学基金”十五”期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、

5、自适应与现场认知主题。 多年来世界各地研究工作者对蚁群算法进行了精心研究和应用开发，该算法现已被大量应用于数据分析、机器人协作问题求解、电力、通信、水利、采矿、化工、建筑、交通5等领域。蚁群算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域已经获得成功的应用，其中最成功的是在组合优化问题中的应用。第2章 基本蚁群算法简介2.1 基本蚁群算法的原理2.1.1 蚁群行为描述根据仿生学家的长期研究发现：蚂蚁虽然没有视觉，但运动时会通过在路径上释放出一种特殊的分泌物信息素来寻找

6、路径。当它们碰到一个还没有走过的路口的时，就随机的挑选一条路径前行，同时释放出与路径长度有关的信息素。蚂蚁走的路径越长，则释放的信息量越小。当后来的蚂蚁再次碰到这个路口的时候，选择信息量较大路径的概率相对较大，这样便形成了一个正反馈机制。最优路径上的信息量越来越大，而其他路径上的信息量却会随着时间的流逝而逐渐消减，最终整个蚁群会找出最优路径。同时蚁群还能够适应环境的变化，当蚁群的运动路径上突然出现障碍物时，蚂蚁也能很快的重新找到最优路径。可见，在整个寻径过程中，虽然单只蚂蚁的选择能力有限，但是通过信息素的作用使整个蚁群行为找出最优路径。这里用人工蚂蚁觅食图来描述蚁群搜索原理。图 2.1 人工蚂

7、蚁觅食模拟图 2.2 人工蚂蚁觅食模拟图 2.3 人工蚂蚁觅食模拟图2.1中，设A点是蚁巢，D点是食物源，EF之间区域是障碍物。由于障碍物的存在，蚂蚁只能经由A经E或F到达D，或由D到达A，各点之间的距离如图2.1所示。假设每个时间单位有30只蚂蚁由A到达D点，有30只蚂蚁由D到达A点，蚂蚁过后留下的信息量为1。为了方便起见，设该物质停留时间为1。在初始时刻，由于路径BF、FC、BE、EC上均无信息存在，位于A和D的蚂蚁可以随机选择路径，从统计学的角度可以认为蚂蚁以相同的概率选择BE、FC、BE、EC，如图2.2所示。经过一个时间单位后，在路径BFC上的信息量是路径BEC上的信息量的2倍。又经

8、过一段时间，将有20只蚂蚁由B、F和C点到达D，如图2.3所示。随着时间的推移，蚂蚁将会以越来越大的概率选择路径BFC，最终将会完全选择BFC，从而找到由蚁巢到食物源的最短路径。2.1.2 基本蚁群算法的机制原理模拟蚂蚁群体觅食行为的蚁群算法是作为一种新的计算智能模式引入，该算法基于以下基本假设： 1.蚂蚁之间通过信息素和环境进行通信。每只蚂蚁仅根据其周围的局部环境作出反应，也只对其周围的局部环境产生影响。 2.蚂蚁对环境的反应由其内部模式决定。因为蚂蚁是基因生物，蚂蚁的行为实际上是其 基因的适应性表现，即蚂蚁是反应型适应性主体。 3在个体水平上，每只蚂蚁仅根据环境做出独立选择；在群体水平上，

9、单只蚂蚁的行为是随机的，但蚁群可通过自组织过程形成高度有序的群体行为。 由上述假设和分析可见，基本蚁群算法的寻优机制包含两个基本阶段：适应阶段和协作阶段。在适应阶段，各候选解根据积累的信息不断调整自身结构，路径上经过的蚂蚁越多，信息量越大，则该路径越容易被选择；时间越长，信息量会越小；在协作阶段，候选解之间通过信息交流，以期望产生性能更好的解。 蚁群算法实际上是一类智能多主体系统，其自组织机制使得蚁群算法不需要对所求的问题的每一方面都有详尽的认识。自组织本质上体现了从无序到有序的动态演化，其逻辑结构如下图所示。图 2.4 基本蚁群算法的逻辑结构由图2.4可见，先将具体的组合优化问题表述成规范的

10、格式，然后利用蚁群算法在“探索”和“利用”之间根据信息素这一反馈载体确定决策点，同时按照相应的信息素更新规则对每只蚂蚁个体的信息素进行增量构建，随后从整体角度规划出蚁群活动的行为方向，周而复始，即可求出组合优化的最优解。2.2 基本蚁群算法的系统学特征基本蚁群算法在系统学上表现以下三个特征：分布式，自组织，正反馈。三者表现出一个整体，相辅相成。2.2.1 分布式自然界中的真实蚁群行为也出现了分布式。当蚁群需要完成某项工作时，其中的许多蚂蚁都为共同目的进行着同样的工作，而最终任务的完成不会由于某些个体的的缺陷而受到影响。 蚁群算法作为对蚁群觅食行为的抽象，也体现了群体行为的分布式特征。每只人工蚂

11、蚁在问题空间的多个点同时开始相互独立地构造问题解，而整个问题的求解不会因为某只人工蚂蚁无法成功获得解而受到影响。 具体到不同的优化问题而言，蚁群算法体现出的分布式特征就具有了更加现实的意义。因为所有的仿生优化算法均可看做按照一定规则的问题解空间搜索最优解的过程，所以搜索点的初始选取就直接关系到算法求解结果的优劣和算法寻优效率。当求解许多复杂问题时，从一点出发的搜索受到局部特征的限制，可得不到所求问题的满意解；而基本蚁群算法则可看做是一个分布式的多智能系统，它在问题空间的多点同时独立地进行解搜索，不仅使得算法具有较强的全局搜索能力，也增加了算法的可靠性。2.2.2 自组织基本蚁群算法的另一个重要

12、特征是自组织。自组织的概念是随着系统科学的发展而建立起来的。通常把系统论中的组织行为分为自组织和他组织两大类4。其根本区别在于组织力或组织指令是来自于系统内部还是来自于系统外部，前者称为自组织，而后者即为他组织。如果系统在获得时间的、空间的或者功能的结果过程中，没有外界的特定干预，则称为系统是自组织的。 从抽象意义上讲，自组织就是在没有外界作用下使得系统从无序到有序的进化过程。基本蚁群算法体现了这一过程，以蚁群优化为例，当算法开始的初期，单只人工蚂蚁无序地寻找解，经过一段时间的算法演化，人工蚂蚁越来越趋向于寻找到接近最优解的一些解，这恰恰体现了从无序到有序的自组织进化。 自组织大大增强了算法的

13、鲁棒性5（在这里可以理解为算法抗干扰性,就是指不是针对具体问题算法也同样可以求解,极大的体现了蚁群算法的抗干扰能力），传统的算法都是针对某一具体问题而设计的，这往往建立在对该问题有了全面清晰认识的基础上，通常很难适应其他问题。而自组织的蚁群算法不需要对待求解问题的所有问题的所有方面都有所认识，因而较容易应用到一类问题中。2.2.3 正反馈反馈是控制论中的重要概念，它代表信息输入对输出的反作用。在系统学上认为，反馈就是把系统现在的行为作为影响系统未来行为的原因。反馈分正反馈和负反馈两种，前者指的是以现在的行为去加强未来的行为，而后者则是以现在的行为去削弱未来的行为。 由自然界中真实蚂蚁的觅食行为可见，蚂蚁能够最终找到最短路径，直接依赖于最短路径上信息素的堆积，而信息素的堆积却是一个正反馈的过程，对于基本蚁群算法而言，初始时在环境中存在完全相同的信息量，给系统一个微小的扰动，使得各个边上的信息量大小不同，蚂蚁构造的解就存在了优劣。算法采用的反馈方式是在较优解经过的路径留下更多的信息素，更多的信息素又吸引了更多的蚂蚁，这个正反馈的过程使得初始值不断地扩大，同时又引导整个系统向着最优解的方向进化。 单一的正反馈或者负反馈存在于线形系统之中，是无法实现系统的自我