毕业论文蚁群算法的研究应用定稿精品范本模板Word文档下载推荐.docx

毕业论文蚁群算法的研究应用定稿精品范本模板Word文档下载推荐.docx

《毕业论文蚁群算法的研究应用定稿精品范本模板Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《毕业论文蚁群算法的研究应用定稿精品范本模板Word文档下载推荐.docx（45页珍藏版）》请在冰点文库上搜索。

群体智能的研究涉及到生物学、心理学、社会学、控制理论、决策理论等领域；

个体行为是构成群体行为的基础，个体之间的组织结构、个体行为之间的关系和群体行为的涌现机制是研究群体行为的关键要素。

目前主要研究仿生的群体优化算法，群体组织内部的通信机制及其应用方面,如微粒群算法、蚁群算法、群体机器人等。

群体智能应用于解决大多数优化问题或者能够转化为优化求解的问题，目前应用领域已经扩展到多目标优化、数据分类、数据聚类、模式识别、生物系统建模、机器人控制、决策支持以及仿真和系统辨识等方面.

集群是生物中常见的一种生存现象。

大自然中可以看到成群结队的大雁、鱼以及蚂蚁等动物，他们会暂时或永久的聚集成群。

蚂蚁算法是由意大利学者M.Dorigo，V。

Manierio，A。

Collorni等人于二十世纪九十年代提出的一种新型的模拟进化算法.经过研究发现，蚂蚁在觅食的过程中通过一种称之为信息素（Pheromone）的物质相互传递信息。

更具体地，蚂蚁在运动过程中能够在其所经过的路径上留下信息素，而且在运动过程中能够感受到这种信息素的存在及其强度，并以此指导自己的运动方向。

蚂蚁倾向于朝着信息素浓度高的方向前进，因此，由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象：

某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。

蚁群就是通过个体之间这种信息交换机制来彼此协作达到搜索食物的目的。

Colorni和Dorigo等人在研究该问题的基础之上提出了一类模拟自然界蚁群觅食行为的模拟进化算法—-蚁群算法。

蚁群通过信息交换与互相协作找到从蚁穴到食物源的最短路径的机制显然可以被借鉴来求解各种与最优路径相关的组合优化问题。

1.2国内外研究现状

1）群体算法研究

群体智能研究起源于对社会性昆虫（如蚂蚁、蜜蜂等）的群体行为的研究.现

有的对群体智能的研究,大都是从某一种有大量个体表现出来的群体行为出发,从它们的群体行为中提取模型，为这些行为建立一些规则,从而提出算法,应用于解决实际中的问题.群智能理论研究领域有两种主要的算法:

蚁群算法（ACO）和微粒群算法（PSO）。

前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题.微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。

a）蚁群算法（ACO）

蚂蚁个体在觅食过程中，会在自己经过的路径留下信息素，后面的蚂蚁个体通过感知信息素的浓度来决定自己的路径。

由于信息素随时间挥发，所以比较短的路径上信息素浓度也比较大。

因此，蚂蚁就可以通过这种方式找到更短的路径觅食，为解决各种寻优问题提供了一种新的方法.意大利学者MacroDorigo用于求解TSP问题，以后有用于求解二次分配问题、皇后问题、函数优化问题、背包问题。

b）微粒群优化算法（PSO）

PSO由JamesKennedy和R．C．Eberhart在1995年提出的，是一种基于种群寻优的启发式搜索算法,该算法源于对鸟群、鱼群觅食行为的模拟。

首先初始化一群随机粒子（随机解），然后通过迭代寻找最优解，每次迭代中，粒子通过跟踪两个极值（个体极值和全局极值）来更新自己的速度和位置。

应用在函数的优化问题,神经网络的训练。

2）群体机器人［14］

群体智能最初被应用于描述细胞机器人系统。

通过对蚂蚁等社会性昆虫行为研究，发现了社会性昆虫的自组织、自组装能力。

布鲁塞尔自由大学的MacroDorigo领导的项目Swarm-bots，其目标是建立一个由多个类似于昆虫且简单的机器人组成的群体，由多个简单机器人组成的群体机器人系统通过协调、协作可以完成单个机器人无法完成或难以完成的工作。

研究群体机器人系统，目标是建立经济、灵活、健壮的系统去完成复杂的任务，主要研究内容为群体机器人之间的交互、通信、协作与控制、机器人的自组装等。

3群体智能研究应用

随着群体智能理论和研究算法的进一步成熟,已经将其应用到一些工程优化问题中，并且已取得了明显的效果。

文献15采用PSO对神经网络进行了优化,并利用其设计了电力变压器的智能保护机制15。

文献［16]利用PSO实现了对各种连续和离散控制变量的优化，从而达到了控制核电机组电流稳定输出电压的目的16。

蚁群优化算法为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。

比较典型的应用研究包括：

网络路由优化、数据挖掘以及一些经典的组合优化问题．蚁群算法在电信路由优化中己取得了非常显著的应用成果。

17—20HP公司和英国电信公司在90年代中后期都开展了这方面的研究，设计了蚁群路由算法（ACR）.Lumer和FaietaDeneubourg提出将蚁巢分类模型应用于数据聚类分析21.其基本思想是将待聚类数据随机地散布到一个二维平面内，然后将虚拟蚂蚁分布到这个空间内，并以随机方式移动，当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动，若运动路径附近的数据与背负的数据相似性高于设置标准则将其放置在该位置,然后继续移动，重复上述数据搬运过程。

按照这样的方法可实现对相似数据的聚类22。

吴斌等人又在简化分类模型的基础上系统地提出了一种基于群体智能的聚类算法23。

1.4蚁群算法的研究应用

蚁群算法（antcolonyalgorithm，简称ACA）是最近几年才提出来的一种新型的模拟进化算法.它是由意大利学者Pofigo等人受到人们对自然界中真实蚁群集体行为的研究成果的启发而首先提出来的.1⋯蚁群算法的应用进展以蚁群算法为代表的群智能已成为当今分布式人工智能研究的一个热点，许多源于蜂群和蚁群模型设计的算法己越来越多地被应用于企业的运转模式的研究.当前对蚁群算法的研究，不仅有算法意义上的研究，还有从仿真模型角度的研究，并且不断有学者提出对蚁群算法的改进方案。

从当前可以查阅的文献情况来看，研究和应用蚁群算法的学者主要集中在比利时、意大利、英国、法国、德国等欧洲国家，日本和美国在这一两年内也开始启动对蚁群算法的研究。

国内于1998年末才开始有少量公开报道和研究成果.美国五角大楼正在资助关于群智能系统的研究工作—群体战略，它的一个实战用途是通过运用成群的空中无人驾驶飞行器和地面车辆来转移敌人的注意力，让自己的军队在敌人后方不被察觉地安全进行。

英国电信公司和美国世界通信公司以电子蚂蚁为基础，对新的电信网络管理方法进行了试验。

群智能还被应用于工厂生产计划的制定和运输部门的后勤管理。

美国太平洋西南航空公司采用了一种直接源于蚂蚁行为研究成果的运输管理软件，结果每年至少节约了1000万美元的费用开支。

英国联合利华公司己率先利用群智能技术改善其一家牙膏厂的运转情况。

美国通用汽车公司、法国液气公司、荷兰公路交通部和美国一些移民事务机构也都采用这种技术来改善其运转的机能。

鉴于群智能广阔的应用前景，美国和欧盟均于近几年开始出资资助基于群智能模拟的相关研究项目,并在一些院校开设群体智能的相关课程。

国内，国家自然科学基金”十五"

期间学科交叉类优先资助领域中的认知科学及其信息处理的研究内容中也明确列出了群智能领域的进化、自适应与现场认知主题.

　　蚁群优化算法最初用于解决TSP问题，经过多年的发展,已经陆续渗透到其他领域中，如,图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。

蚁群算法在若干领域己获得成功的应用，其中最成功的是在组合优化问题中的应用。

5　本文的工作

本文选择了自然界的蚂蚁作为研究对象,通过研究蚂蚁的群体行为，首先对系统进行建模然后用计算机仿真的方法建立了一个具有蚂蚁所拥有特性的虚拟系统，并用图形化的方式进行了演示，通过系统运行演示蚂蚁复杂行为产生过程。

1）对蚁群的觅食行为等规律进行了分析,并建立了一种基于向量的数据模型，

模型由环境、主体、行为规则组成。

环境为蚁群生存的空间，主体间通过环境相互作用；

主体包括蚂蚁主体、窝主体、障碍物主体、信息素主体和食物主体；

行为规则有：

范围规则，环境规则，觅食规则，移动规则,避障规则，播撒信息素规则.通过对蚂蚁主体的属性和行为规则的抽取，模型尽可能地反映蚂蚁的主要属性。

2）然后利用Java技术进行软件设计，自下而上地构建了一个虚拟蚂蚁系统。

3）使用已建立好的系统模型进行了仿真,通过设置障碍物以及对参数的调整，来观察仿真结果所表现出来的不同群体行为,并对仿真的结果分析，来研究蚂蚁产生的复杂行为及其原因-—即个体与环境，以及个体之间的交互.

第二章群体智能理论及其研究方法

2。

1群体智能概述

群智能理论的基本原理30是以生物社会系统（Biologysocialsystem）作为依托，也就是由简单个体组成的群体与环境以及个体之间的互动行为。

这种生物社会性的模拟系统利用局部信息产生难以估量的复杂群体行为。

群体智能并不是所有生物种群都具有的特性，它是那些具有社会性特征的群居。

生物个体合作进行某些活动时才会产生的涌现现象。

关于群体智能行为的生物原型，Bonabeau描述了生物蚂蚁群体的一些行为，如觅食、劳动分工、尸体聚集、巢穴构造、合作运输等,并分别对其建模，然后设计了一系列算法、多主体系统（MAS）和多机器人系统31。

集中介绍了社会性昆虫的行为建模和蚁群优化算法及其性能。

Kennedy通过观察鸟群的协同运动，开创了微粒群优化这一新型群体智能方法的研究领域，并以此为基础提出了以下基本观点6：

1）人类智能的产生源于社会交往;

2）文化和认知是人类社交的结果。

对蚁群的研究,也属于群体智能的理论范畴。

群体智能研究成果和理论体系，可以用来指导我们对蚁群形成、组织体系、群体行为及其涌现出的群体智能的研究。

群体智能是一种通过模拟自然界生物群体行为来实现人工智能的方法.由单个简单个体完成的任务，可以涌现出复杂的智能,充分体现了整体和大于个体的叠加.群体智能利用群体优势,在没有集中控制，不提供全局模型的前提下，为复杂问题寻找解决方案32。

普遍意义上，群体智能强调个体行为的简单性、群体的涌现特性、以及自下而上的研究策略。

群体智能的本质是由许多简单个体组成的群体,群体之间能够通过简单的交互、合作和协作，来完成某一项任务。

群体智能在已有的应用领域中都表现出较好的寻优性能，因而引起了相关领域研究者的极大关注。

其中涌现是群体智能中一个比较重要的概念，群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序的行为。

这种大量个体表现出来的宏观有序行为就是涌现现象。

如果没有涌现现象，就无法体现智能。

因为涌现是简单的个体行为在特定组织结构下，积累到一定程度,所表现出来的整体现象，所以，对群体智能的研究必须既研究各个部分，又研究各个部分之间的相互作用关系33。

MillionasMM在1994年提出群体智能应遵循五条基本原则32,分别为：

1）邻近原则，动物群体能够进行简单的空间和时间计算；

2）品质原则,动物群体能够响应环境中的品质因子；

3）多样性反应原则，动物群体的行动范围不应该局限在小范围内;

4）稳定性原则，动物群体不应该在每次环境变化时都改变自身的行为；

5）适应性原则，在所需代价不太高的情况下，动物群体能够在适当的时候改变

自身的行为。

2群体智能的主要优缺点22

2.1群体智能的主要优点

群体智能具有以下优点：

1）群体中相互合作的智能体是分布的，这样更能够适应当前网络环境下的工作

状态。

2）没有中心控制与数据，这样的系统更具有鲁棒性，不会由于某一个或者某几

个智能体的故障而影响整个问题的求解。

3）可以不通过智能体间直接通信，而采用非直接通信进行合作，系统具有更好

的可扩充性，使得系统中由于智能体数量的增加而增加的系统通信耗费较小。

4）系统中每个智能体的能力非常简单，以至于每个智能体的执行时间都比较

短，且实现也较简单，具有简单性。

5）智能体相互作用能突现出整体的行为，系统所有上层智能行为都是通过智能

体的基本规则相互作用产生的，所以在多任务情况下，对于每一子任务可以分别编制、调试、学习。

6）群体智能中，信息处理原则是基于发生在实际生命中大量并行处理过程.群

体智能系统的强并行性大大地增强了系统的运算速度及能力。

7）人工生命中的一个重要原则，就是整体大于部分和的思想。

由于群体智能的整体行为是由智能体行为突现而产生的，智能体在相互作用中的负关系将会因智能体自身的相互作用规则而消减，正关系将得以增强。

对于智能体之间的冲突和任务协调等问题,由底层智能体相互作用的规则解决，减少上层对智能体之间的协作、协调控制，避免了上层控制干预下层动作的情况,使得每一层次的控制任务都非常清晰，增加了系统协作协调效率。

2.2群体智能系统的主要缺点

群体智能的研究还处于萌芽阶段,还存在很多不足,主要问题如下30：

1）群体智能的思想是根据对生物群体观察得来的,是概率算法，从数学上对于

它们的正确性与可靠性的证明仍比较困难.

2）这些算法都是专用算法,一种算法只能解决某一类问题，各种算法之间的相

似性很差。

3）系统高层次的行为是需要通过低层次智能体间的简单行为交互突现产生。

单

个个体控制的简单并不意味着整个系统设计的简单。

4）系统设计时也要保证多个智能体简单行为交互能够突现出所希望看到的高

层次复杂行为。

这可以说是群体智能中一个极为困难的问题。

2.3群体智能的底层机制研究31

2.3。

1自组织

自组织是一种动态机制，由底层单元的交互而呈现出系统的全局性的结构。

交互的规则仅仅依赖于局部信息，而不依赖于全局的模式f61。

自组织是系统自身涌现出的一种性质。

系统中没有一个中心控制模块，也不存在一个部分控制另一部分。

自组织的特点就是通过利用同一种介质或者媒体创建时间或空间上的结构。

比如蚂蚁筑的巢、寻找食物时的路径等。

正反馈群体中的每个具有简单能力的个体表现出某种行为，会遵循已有的结构或者信息指引自己的行动,并且释放自身的信息素，这种不断的反馈能够使得某种行为加强。

尽管一开始都是一些随机的行为，大量个体遵循正反馈的结果是呈现出一种结构。

自然界通过系统的自组织来解决问题。

理解了大自然中如何使生物系统自组织，就可以模仿这种策略使系统自组织。

3。

2间接通信

群体系统中个体之间如何进行交互是个关键问题.个体之间有直接的交流，.Grasse首先引入Stigmergy来解释白蚁筑巢中的任务协调6。

Stigmergy在宏观上提供了一种将个体行为和群体行为联系起来的机制.个体行为影响着环境，又因此而影响着其它个体的行为.个体之间通过作用于环境并对环境的变化作出反应来进行合作。

总而言之,环境是个体之间交流、交互的媒介。

从蚂蚁觅食到蚂蚁聚集尸体到蚂蚁搬运、筑巢，个体之间的通信机制总是离不开Stigmery机制，对于环境的作用,通常由各种各样的信息素来体现。

3.3涌现

群体智能中的智能就是大量个体在无中心控制的情况下体现出来的宏观有序

的行为。

这种大量个体表现出来的宏观有序行为称之为涌现现象。

没有涌现现象，

就无法体现出智能。

因此，涌现是群体智能系统的本质特征.只知道孤立的个体行为并不能了解整个系统的情况,仅仅研究孤立的部分无法有效地研究整体性质，因此,对涌现现象的研究必须既研究各个部分,又研究各个部分之间的相互作用34。

“遗传算法之父”约翰·

霍兰在文献34中对涌现现象进行了较为深入的探索。

他认为涌现现象的本质是“由小生大，由简入繁"

，并且把细胞组成生命体，简单的走棋规则衍生出复杂的棋局等现象都视为涌现现象.他认为神经网络、元胞自动机等可以算作涌现现象的模型.群体智能的涌现现象与系统论和复杂系统中阐述的涌现本质上是相同的，它是基于主体的涌现。

1979年霍夫施塔特对基于主体的涌现作了描述，整个系统的灵活的行为依赖于相对较少的规则支配的大量主体的行为。

研究群体智能系统，要弄清涌现现象的普遍原理，建立由简单规则控制的模型来描述涌现现象的规律。

2.4智能的研究方法

随着复杂系统以及复杂性研究热潮的到来,复杂系统的仿真问题逐渐成为该领域的热点问题之一。

国内外研究表明，传统的建模方法（诸如还原论方法、归纳推理方法等）已经不能很好地刻画复杂系统,需要采用新的建模理论与仿真方法[1］。

而多Agent的建模理论和仿真技术是最具活力、最有影响的方法之一，适合于复杂系统的研究。

其基本思想是通过模拟现实世界,将复杂系统划分为与之相应的Agent（每个Agent具有各自的数据、知识、模型以及接口等）,以自底向上的方式，从研究个体微观行为着手,进而获得系统宏观行为［2］。

生态学理论体系认为，生态学应当借鉴生物进化理论，把生态系统作为由多Agent组成的复杂系统进行研究[3］。

在这种研究方法中将组成生态系统的个体看作是具有认知与适应学习能力的Agent。

通过Agent个体的简单行为，个体之间以及个体与环境之间的交互与协调,最终形成复杂的生态现象.这种思想和基于Agent建模仿真技术的思路不谋而合,因此，多Agent仿真方法比传统的仿真模型更适合用来研究人工生态系统，对人工生态系统及其理论模型、生成方法与实现技术的研究具有重要意义[4].本文以蚂蚁觅食过程这一典型的生态系统为研究对象进行仿真研究,结果表明基于多Agent的仿真方法非常适合于这一类复杂系统的研究，具有很大的发展空间.

本文用多Agent方法有效地为蚁群系统建立模型，实现对于蚁群行为的模拟，并从中抽象、提取出一些蚁群的相关知识。

本文选择了自然界的蚂蚁作为研究对象，通过多Agent系统来研究蚂蚁的群体行为，其中把个体蚂蚁看作Agent，鱼群仿真系统就可以看作是一个多Agent系统.基于Agent的建模就是把Agent作为系统的基本抽象单位,采用相关的Agent技术，先建立组成系统的每个个体的Agent模型，然后采用合适的KS体系结构来组装这些个体Agent,最终建立整个系统模型。

2.4。

1多Agent系统（Multi-AgentSystem，MAS）

1）多Agent定义

Wooldridge对Agent的定义为：

Agent是一个被置于某个环境中的计算机系统，为了实现其设计的目标，Agent能在环境中自主行为35。

而多Agent系统则更侧重于Agent之间的组织关系，后续研究更是演变到社会学和生命科学，和人工生命中“群"

的概念有所交叉。

MAS为表示社会和自然科学问题提供了一种方法。

41

a）硬件Agent的交互（群体机器人）；

b）交互式软件机器人系统，解决分布式规划任务；

c）仿真Agent。

MAS是增强个体的自治性和组织性的计算机工具。

MAS主要应用于通信、网络和物理Agent，例如机器人。

还有一大批的学者研究。

Agent对生态系统和社会系统的模拟。

2）动物群体和多Agent系统41

多Agent系统源于人工智能学科,agent智能主体，主要指能在某特定环境中,能根据环境变化，灵活、自主的采取行动,以满足系统目标的计算。

通常，智能主体具备感知、推理、学习、自适应和协作能力。

Agent主要表现出反应性（能够有选择的感知和决策）、自主性（能主动、自治的行为）、协作性（能与其它主体进行交互，并协同工作）、适应性（能够根据经验学习和改进）。

而MAS则是通过多个Agent之间的合作，以解决单一主体的能力和知识所不能处理的复杂问题的分布式系统.其中，多主体系统不存在全局控制，知识和数据都是分散的，计算也异步执行.多主体系统主要研究的问题主要包括【341：

主体的结构、知识、行为等各个方面的性质；

主体系统的整体性质，多主体的组织结构、主体间的协调、协同、协商行为：

系统组织方法的研究。

1990年，Malone提出了一个类似群体的概念“群体组织”.如果许多主体组成的群体以一种方式系统的关联在一起，使得联合行动比各自行动更加谐调和高效。

群体组织依赖于主体谐调其活动,主要借鉴动物或人类组织学原理来设计和构造主体的组织结构。

1992年，Matsuda提出了类似于群体智能“组织智能”概念,通过组织智能模型集成人和基于机器的知识处理和问题求解能力。

个体Agent的感知、推理、交互能力，多Agent系统的分布式结构和所表现出的组织智能，都有力的表明了多agent系统和鱼群的相似性.运用多Agent方法和技术，将能有效的为群体系统建立模型，实现对群体行为的模拟,并从中抽象、提取有待进一步发掘的群体知识。

5基于主体的建模的实现方法

对群体智能系统提出较为通用的模型将是今后研究的一个重点。

该模型用来反映智能在群体系统中如何涌现的过程.建立这个模型，首先需要对群体系统的基本的特征和机制有相当地理解。

在此基础上，构建个体之间能够交互，具有一定学习能力的智能系统，进而解决具体的问题。

5.1利用仿真平台

为了减少基于主体建模仿真实现中的重复工作，提高模型之间的互通性,出现了一些建模仿真平台。

国内有国防科技大学开发的JCass仿真平台，中科院计算所史忠植等研制的MAGE系统等。

国外的仿真平台有Swarm、Ascape、Starlogo、Repast、Projek和TNG-lab等.

5.2面向对象技术

面向对象编程中的对象和主体（Agent）有很多的相似之处,它们都是实体的属

性和行为的封装。

并且对于面向对象和基于主体建模来说，实体及其交互关系的描述是一个共同的核心问题。

由于两者之间有很多的相似性，有很多基于主体的模型是用面向对象语言实现的，例如用C++、Java等。

本文选取Java技术设计软件来实现