毕业论文：蚁群算法的研究应用（定稿）汇.doc

第一章 绪论 1.1选题的背景和意义 受社会性昆虫行为的启发，计算机工作者通过对社会性昆虫的模拟产生了一系列对于传统问题的新的解决方法，这些研究就是群体智能的研究。群体智能作为一个新兴领域自从20世纪80年代出现以来引起了多个学科领域研究人员的关注，已经成为人工智能以及经济社会生物等交叉学科的热点和前沿领域。群体智能(Swarm Intelligence)中的群体(Swarm)指的是“一组相互之间可以进行直接通信或者间接通信(通过改变局部环境)的主体，这组主体能够合作进行分布问题求解，群体智能指的是无智能或者仅具有相对简单智能的主体通过合作表现出更高智能行为的特性;其中的个体并非绝对的无智能或只具有简单智能,而是与群体表现出来的智能相对而言的。当一群个体相互合作或竞争时，一些以前不存在于任何单独个体的智慧和行为会很快出现。 群体智能的提出由来已久,人们很早以前就发现,在自然界中,有的生物依靠其个体的智慧得以生存,有的生物却能依靠群体的力量获得优势。在这些群体生物中,单个个体没有很高的智能,但个体之间可以分工合作、相互协调,完成复杂的任务,表现出比较高的智能。它们具有高度的自组织、自适应性，并表现出非线性、涌现的系统特征。 群体中相互合作的个体是分布式的，这样更能够适应当前网络环境下的工作状态; 没有中心的控制与数据，这样的系统更具有鲁棒性，不会由于某一个或者某几个个体的故障而影响整个问题的求解。可以不通过个体之间直接通信而是通过非直接通信进行合作，这样的系统具有更好的可扩充性。由于系统中个体的增加而增加的系统的通信开销在这里十分小。系统中每个个体的能力十分简单，这样每个个体的执行时间比较短，并且实现也比较简单，具有简单性。因为具有这些优点，虽说群集智能的研究还处于初级阶段，并且存在许多困难，但是可以预言群集智能的研究代表了以后计算机研究发展的一个重要方向。 随着计算机技术的飞速发展，智能计算方法的应用领域也越来越广泛，当前存在的一些群体智能算法有人工神经网络,遗传算法,模拟退火算法，群集智能，蚁群算法,粒子群算等等。蚁群算法只是其中的一种。人工智能计算也有人称之为“软计算”，是们受自然（生物界）规律的启迪，根据其原理，模仿求解问题的算法。从自然界得到启迪，模仿其结构进行发明创造，这就是仿生学。这是我们向自然界学习的一个方面。另一方面，我们还可以利用仿生原理进行设计(包括设计算法)，这就是智能计算的思想。 群体智能的研究涉及到生物学、心理学、社会学、控制理论、决策理论等领域；个体行为是构成群体行为的基础，个体之间的组织结构、个体行为之间的关系和群体行为的涌现机制是研究群体行为的关键要素。目前主要研究仿生的群体优化算法，群体组织内部的通信机制及其应用方面，如微粒群算法、蚁群算法、群体机器人等。群体智能应用于解决大多数优化问题或者能够转化为优化求解的问题，目前应用领域已经扩展到多目标优化、数据分类、数据聚类、模式识别、生物系统建模、机器人控制、决策支持以及仿真和系统辨识等方面。 集群是生物中常见的一种生存现象。大自然中可以看到成群结队的大雁、鱼以及蚂蚁等动物，他们会暂时或永久的聚集成群。蚂蚁算法是由意大利学者M.Dorigo ,V. Manierio ,A. Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法。经过研究发现，蚂蚁在觅食的过程中通过一种称之为信息素（Pheromone）的物质相互传递信息。更具体地，蚂蚁在运动过程中能够在其所经过的路径上留下信息素，而且在运动过程中能够感受到这种信息素的存在及其强度，并以此指导自己的运动方向。蚂蚁倾向于朝着信息素浓度高的方向前进，因此，由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚁群就是通过个体之间这种信息交换机制来彼此协作达到有哪些信誉好的足球投注网站食物的目的。Colorni和Dorigo等人在研究该问题的基础之上提出了一类模拟自然界蚁群觅食行为的模拟进化算法——蚁群算法。蚁群通过信息交换与互相协作找到从蚁穴到食物源的最短路径的机制显然可以被借鉴来求解各种与最优路径相关的组合优化问题。 1.2国内外研究现状 1)群体算法研究 群体智能研究起源于对社会性昆虫(如蚂蚁、蜜蜂等)的群体行为的研究。现 有的对群体智能的研究，大都是从某一种有大量个体表现出来的群体行为出发，从它们的群体行为中提取模型，为这些行为建立一些规则，从而提出算法，应用于解决实际中的问题。群智能理论研究领域有两种主要的算法：蚁群算法(ACO)和微粒群算法（PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。 a)蚁群算法(AC