多智能体系统完教学课件电子教案.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第1章 多智能体系统概述,1.1 自然智能和人工智能,1.2 多智能体系统,1.3 多智能体系统的主要技术内容,1.4 Netlogo仿真工具,第1章 多智能体系统概述,依赖于表现智能的智能体不同，我们可以简单地把智能分为人工智能和自然智能（非人工智能）。现实中最普遍存在的就是大自然创造的各种智能体，也就是各种动物以及我们人类自己。自然智能特指大自然创造的智能现象。人工智能是由机器、设备或软件等人造对象所表现出的智能。,1.1.1 自然智能,自然智能包括：,（1）生物个体智能，由有机的生命形态个体所表现出的智能。,（2）人类个体智能，由人类个体所表现出的智能。,（3）群体智能，由众多智能个体的集合所表现出的智能,（4）系统智能，由多种有机或无机元素组成的复杂系统所表现出的智能。,1.1.1 自然智能,定义1.1生物智能（Biological Intelligence，BI）就是指各种生物个体所表现出来的，能够自主的对环境做出适应的反应行为。,1.生物个体智能,人类智能（human intelligence）是人类个体所表现出的智能。,定义1.2从感觉到记忆到思维这一过程，称为“智慧”，智慧的结果就产生了行为和语言，将行为和语言的表达过程称为“能力”，两者合称“智能”。,2.人类个体智能,群体智能是由众多智能个体的集合所表现出的智能。,定义1.3群体智能（Swarm Intelligence，SI）是指在集体层面表现的分散的、去中心化的自组织行为。,定义1.4涌现行为在全局状态中是显而易见的，它们没有明确地被编入程序，但它是个人之间局部互动的结果。根据观察者建立的一些指标，它被认为是有趣的。,3.群体智能,群体智能SI可以视为系统智能（System Intelligence，SI）的一个特殊情况。系统智能可以视为所有智能的根本模式，我们将从系统智能中揭示智能的真正来源。,系统智能是由多种有机或无机元素组成的复杂系统所表现出的智能。,4.系统智能,定义1.5如果一个系统能够独立而有效地解决某种问题，那么这个系统就是智能的。,诸如自然界的石、木、山、水等生态系统，乃至一个星球，它们都可以在科学现象的支配下，遵循自然规律，感应外界信息，交换物质能量，有序耗散运行。因此，物理实体系统也可以定义为是一种原始智能系统。,4.系统智能,1.1 自然智能和人工智能,1.2 多智能体系统,1.3 多智能体系统的主要技术内容,1.4 Netlogo仿真工具,第1章 多智能体系统概述,1.2.1 多智能体系统定义与特点,1.2.2 多智能体系统的形式化描述,1.2.3 多智能体系统理论的发展,1.2.4 多智能体系统应用,1.2 多智能体系统,智能分为自然智能和人工智能，相应地，智能体就分为自然智能体和人工智能体。一个自然智能体可以是人群中的个人、经济系统中的经营者、生态系统中的植物个体、动物个体等；人工智能体可以是交通流中的智能汽车，计算网络中的计算机，无人机等。,1.智能体,定义1.7任何可以被看作是通过传感器感知环境并且通过执行器作用于环境的实体都被称为智能体（Agent）。,1.智能体,定义1.8智能体的感知序列是该智能体所接收的所有数据完整的历史。,感知信息做为智能体的感知输入，而感知序列是感知信息的集合。一般而言，智能体在任何给定时刻的行动选择取决于到那个时刻为止智能体的整个感知序列。,1.智能体,定义1.9把任意给定感知序列集合到执行动作集合的映射称为智能体函数。,定义1.10智能体程序是在物理实体上运行的智能体函数的具体实现。,1.智能体,下面给出智能体程序的伪码表示：,function TABLE-DRIVEN-AGENT(percept)returns an action,static：percepts，一个序列，初始为空；,table:动作列表，以感知序列为索引，初始完全指定；,将percept加入到percepts中；,action=max-pxcor-boundary-width)set pcolor brown,if(pxcor=max-pycor-boundary-width)set pcolor brown,if(pycor=min-pycor+boundary-width)set pcolor brown,ask patches ,ifelse random 1=28 and pxcor=-3 and pycor 0;感知到视觉范围内有树,avoid-tree;3.2避开树,flock;3.3 给每只鸟调整一下方向 adjust-heading,repeat 5 ask boids fd 0.2 display;用来使海龟的动画更流畅。,;ask turtles fd 1 为了获得更高的效率，以牺牲平滑的动画为代价，用本行替换,tick,end,（,3,）,定义,go,函数,;3.1 这定义了机器人应该如何移动。,;这种行为来自Models库中的Look Ahead示例模型,;“向前看”:机器人会直接向前看，看是否有障碍物，距离由半径长度滑块确定，如果有，则随机旋转一个方向。,to make-move,let this-patch patch-ahead radius-length,ifelse(this-patch!=nobody)and(pcolor of this-patch=obstacles-colour),lt random-float 360;看见前面有一块障碍物，旋转一个随机数量。,fd 1 ;否则，继续前进是安全的。,if dust=1 set dust 0 set n n-1,end,3.1 集体运动和编队队形,3.2 基于人工势场的机器人避障模型,3.3 无人机追捕逃犯模型,第,3,章 一致性问题,1.,问题背景,3.3 无人机追捕逃犯模型,该模型描述了多个逃犯在受到无人机追捕时的行为。该模型通过模拟追捕无人机的群集机制，解释了逃犯的视觉和距离以及无人机的捕猎成功率的影响。逃犯和无人机都观察它们的环境以适应其他品种。当,无人机,总是移动或捕猎时，逃犯移动并观察无人机的环境。根据与,无人机,的距离，逃犯要么和其他逃犯一起在附近的环境中，要么试图逃离无人机。,1,.问题背景,1,.问题背景,2.,模型设计,3.3 无人机追捕逃犯模型,参数名称,参数说明,取值范围,number-drone,无人机数量,0100,number-person,逃犯数量,0100,vision,视觉距离,110,minimum-separation,最小距离,010,hunter-success-rate,追捕成功率,0100,movement-speed,移动速度,01,3.,主要算法代码,3.3 无人机追捕逃犯模型,breed drones drone;食肉动物,breed persons person;食草动物,globals eaten-person,;这里每只鸟有两个属性,;第一个属性是flockmates,表示在视野范围内，除自己以外所有的邻居鸟,;第二个属性是nearest-neighbor，表示离这只鸟最近的邻居,（,1,）,定义变量,persons-own,flockmates;视野内的鸟，鸟的感知范围,next-flockmate;最近的邻伴,flock-distance;聚集距离,flee-distance;逃离距离,person-viewing-distance;食草动物视觉距离,person-viewing-angle;食草动物视觉角度,drones-own,drone-viewing-distance;食肉动物视觉距离,drone-viewing-angle;食肉动物视觉角度,（,1,）,定义变量,to setup,clear-all,make-drone number-drone;2.1,make-person number-person ;2.2,ask patches set pcolor white,set eaten-person number-person,reset-ticks,end,（,2,）,定义,s,etup函数,;2.1 设置场景,to setup-patches,ask patches set pcolor white,end,;2.2设置全部变量,to setup-globals,set fires-left-in-sim number-of-fires,set dead-trees 0,set saved-trees 0,end,（,2,）,定义,s,etup函数,;2.1制造无人机,to make-drone number,create-drones number,set color red,set shape drone,setxy pxcor pycor,set size 1.5,if not any?drones-on patch-ahead 1 fd random 2+1,set drone-viewing-distance 12,set drone-viewing-angle 110,end,（,2,）,定义,s,etup函数,;2.2创建人员,to make-person number,create-persons number,set color blue,set shape person,setxy pxcor pycor,if not any?persons-on patch-ahead 1 fd random 10+10,set person-viewing-distance vision,set person-viewing-angle 360,set flock-distance(vision*0.75),set flee-distance(vision*0.5),end,（,2,）,定义,s,etup函数,（,3,）,定义,go,函数,;3.每一个时间步，食草动物通过观察，聚集或逃离,食肉动物寻找猎物。,to go,ask persons,if observe-for-predators flock-distance flock;3.1感知并3.2聚集,if observe-for-predators flee-distance flee ;3.1感知并3.3逃离,move ;3.4移动,ask drones,hunt;3.5 寻找猎物,move;3.4移动,tick,end,下课了,第4章 蚁群自组织与共识自主性,4.1 蚁群优化概述,4.2 蚁群算法的基本实现技术,4.3 蚁群觅食问题,4.4 月球岩石搜索机器人路径规划,第4章 蚁群自组织与共识自主性,4.1 蚁群优化概述,4.1.1 引言,4.1.2 蚁群算法工作原理,4.1.3 蚁群算法的基本流程,4.1.4 蚁群算法应用,当一只蚂蚁发现食物后，会把它带回蚁巢，同时沿途释放信息素吸引其他同伴。所以途中蚂蚁越多，信息素也就越强。这种信息素就是蚂蚁家族在其演化过程中所形成的一种信息传递方式，也是一种非常有效的产生共识的方式。,同样，我们人类演化出来的语言、文字、肢体语言，我们创造的红绿交通灯、人机交互用的键盘、屏幕，以及各种各样的标准、规则、法律等等，都是共识的不同呈现方式。,1.蚁群算法简介,蚂蚁是一种社会化的动物，通过高度的社会化来进行组织和分工协作，从而完成一些无法通过单个蚂蚁来完成的任务。蚁群算法就是根据蚂蚁种群的觅食行为、任务分配行为和巢穴清理行为等蚁群的生物原型而发展起来的。,2.蚁群算法生物原型,（1）AS蚁群算法,（2）ACS蚁群算法,（3）MMAS蚁群优化算法,3.蚁群算法的发展,4.1 蚁群优化概述,4.1.1 引言,4.1.2 蚁群算法工作原理,4.1.3 蚁群算法的基本流程,4.1.4 蚁群算法应用,1.蚁群优化原理,蚁群算法的机制原理描述如下：信息素和周边环境是联结蚂蚁的重要组成部分。面对不同的环境，反应也各有不同，造成的影响也不尽相同。,1.蚁群优化原理,将图4.1蚁群行为等效成图4.2的赋权图。,1.蚁群优化原理,蚁群算法中的人工蚂蚁具有如下的特征：,（1）系统性,（2）自组织性,（3）正反馈,（4）负反馈,（5）分布并发性,2.蚁群算法的特点,4.1 蚁群优化概述,4.1.1 引言,4.1.2 蚁群算法工作原理,4.1.3 蚁群算法的基本流程,4.1.4 蚁群算法应用,（1）感知范围,域,蚂蚁观察到的范围是一个方格世界，相关参数为速度半径，一般为3，可观察和移动的范围为3x3方格。,1.蚁群的规则,（2）环境信息,蚂蚁所在环境中有障碍物、其他蚂蚁、信息素，其中信息素包括食物信息素（找到食物的蚂蚁留下的）、窝信息素（找到窝的蚂蚁留下的），信息素以一定速率消失。,1.蚁群的规则,（3）觅食规则,蚂蚁在感知范围内寻找食物，如果感知到就会过去；否则朝信息素多的地方走，每只蚂蚁会以小概率犯错误，并非都往信息素最多的方向移动。蚂蚁找窝的规则类似，仅对窝信息素有反应。,1.蚁群的规则,（4）移动规则,蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。,1.蚁群的规则,（5）避障规则,当蚂蚁待移动方向有障碍物时，将随机选择其他方向；当有信息素指引时，将按照觅食规则移动。,1.蚁群的规则,（6）散发信息素规则,在刚找到食物或者窝时，蚂蚁散发的信息素最多；当随着走远时，散发的信息素将逐渐减少。,1.蚁群的规则,for ant in colony do/蚁群中每条蚂蚁都逐个更新自己路径经过边上的的信息素,tour=ant.getTour()；/蚂蚁计算路径的总长度,pheromoneToAdd=getParam(Q)/tour.distance()；/蚂蚁计算信息素的更新值,for nodeIndex in tour do/回溯路径中的每个城市,if lastnode(nodeIndex)do/如果节点是路径上的最后节点，取出它和第一个节点间的边,edge=getEdge(nodeIndex,0),else,edge=getEdge(nodeIndex,nodeIndex+1)/否则，取当前节点和路径下一个节点间的边,currentPheromone=edge.getPheromone()；/获得边上之前的信息素,edge.setPheromone(currentPheromone+pheromoneToAdd)/原有信息素加更新后新信息素,end for/ant路径上所有的边的信息素更新完毕,end for/蚁群中所有蚂蚁都处理完毕,2.算法步骤,4.1 蚁群优化概述,4.1.1 引言,4.1.2 蚁群算法工作原理,4.1.3 蚁群算法的基本流程,4.1.4 蚁群算法应用,觅食问题，又被称为搜索问题,多机器人队形控制,多机器人地图构建,路径规划,追捕策略,多机器人协作物体操作,多目标观测问题,机器人足球,4.1 蚁群优化概述,4.2 蚁群算法的基本实现技术,4.3 蚁群觅食问题,4.4 月球岩石搜索机器人路径规划,第4章 蚁群自组织与共识自主性,转移概率就是蚂蚁从一个点出发如何判断选择下一个目的地的过程。在行进过程中，蚂蚁是以先行蚂蚁走过路径所留下来的信息素作为自己的运行指引，蚂蚁趋向于选择信息素浓度更大的方向行进。,4.2.1 蚁群算法中的转移概率,在寻找最优路径的过程中，蚂蚁在经过的路段上留下信息素作为沟通协调机制，它告诉经过这里的蚂蚁一些经验，帮助它们判断该走那条路比较合适。信息素越多的路段上被蚂蚁选中的概率就增大，但是信息素在路段上不是一直增大的，它会随着时间的推移而不断挥发，以此来降低信息素的浓度和数量，避免蚂蚁寻找最优路径的过程中陷入了局部最优。这种信息素的挥发机制增强了蚂蚁的全局搜索能力。而且，经过蚂蚁数量少的路径上信息素挥发的更快，蚂蚁走的多的路径信息素会越来越多，这种机制增强了蚁群算法的正反馈机制，使得蚂蚁群体逐渐趋向于最终的一条最优路径的附近。,4.2.2 信息素更新机制,在不同的算法模型里，和 的表达的形式有所区别，要视具体问题来具体对待。目前为止，普遍接受的模型有三种，分别是蚁密系统模型、蚁周系统模型和蚁量系统模型。,4.1 蚁群优化概述,4.2 蚁群算法的基本实现技术,4.3 蚁群觅食问题,4.4 月球岩石搜索机器人路径规划,第4章 蚁群自组织与共识自主性,1.,问题背景,4.3 蚁群觅食问题,蚂蚁离开它们的巢穴，到处乱走寻找食物。蚂蚁在觅食和筑巢的过程中会释放出一种挥发性化学物质信息素。这种化学物质可以被其他蚂蚁用它们的触须感知到，并作为刺激其他蚂蚁跟随化学物质的踪迹。随着许多蚂蚁开始跟随这条路径，路径上的化学沉积物得到加强。其他蚂蚁的旅行频率起到了正反馈的作用，蚁群的浓度沿着化学路径增加。,1,.问题背景,实验1：同时为蚁群提供从巢穴到食物来源的两条等长等形桥；,实验2：有两个桥，一个桥的长度是另一个桥的两倍；,实验3：实验开始30分钟后出现了短分枝的桥。,1,.问题背景,在第一种情况下，蚂蚁随意选择了任何一条路径，并通过频繁地在这条路径上移动而强化了化学物质的沉积。在第二种情况下，蚁群在两种选择中选择了最短路径；在第三个实验中，因为当最短的分枝被展示出来的时候，蚂蚁已经在最长的树枝上建立了化学痕迹。在化学物质没有蒸发的情况下，蚂蚁继续选择最长的路径，留下最短的路径。,1,.问题背景,在模型中，最初我们会在模拟世界的中心有一个巢穴，巢穴周围有两堆食物来源。虽然每只蚂蚁都遵循一套简单的规则，但整个蚁群的行为却很复杂。这背后的原理是，当每只蚂蚁找到了一块食物，它会把食物带回蚁穴，并在移动的过程中释放出一种叫做信息素的化学物质。当其他蚂蚁“嗅”到这种信息素时，它们会跟随它走向食物。随着越来越多的蚂蚁把食物带到蚁穴，它们加强了信息素的踪迹。,1,.问题背景,2.,模型设计,4.3 蚁群觅食问题,3.,主要算法代码,4.3 蚁群觅食问题,patches-own,chemical ;在这个地块上的化学物质数量,food ;这片土地上的食物量(0,1,or 2),nest?;巢穴上为真，其他地方为假,nest-scent ;离巢越近，数字越高,food-source-number ;编号(1、2或3)以确定食物来源,（,1,）,定义变量,;2.初始化按钮 setup 代码,to setup,clear-all,set-default-shape turtles bug,setup-agents ;2.1创建智能体,setup-patches ;2.2设置环境变量,set TFood 0,set AntsWithFood 100,set count-ant 0,reset-ticks,end,（,2,）,定义,s,etup函数,;2.1创建智能体,to setup-agents,create-turtles population ,set size 2,set color red ;红色=不携带食物,end,;2.2设置环境变量,to setup-patches,ask patches ,setup-nest ;2.2.1 设置巢穴环境,setup-food ;2.2.2 设置食物,recolor-patch;2.2.3 重新着色,end,（,2,）,定义,s,etup函数,;2.2.1 设置巢穴环境,to setup-nest ;patch procedure,set nest?(distancexy 0 0)4;设置nest？变量在巢穴中为真，在其他地方为假,set nest-scent 200-distancexy 0 0;把巢的气味散布到整个世界靠近巢的地方更强烈,end,;2.2.2 设置食物,to setup-food ;patch procedure,;setup food source one on the right,if(distancexy 15 0)4 ;在右侧设置食物源1,set food-source-number 1,if(distancexy-15 0)0 ,set food one-of 1 2,end,（,2,）,定义,s,etup函数,;2.2.3 重新着色,to recolor-patch ;patch procedure,;给巢穴和食物来源着色,ifelse nest?,set pcolor violet,ifelse food 0 ,if food-source-number=1 set pcolor blue,if food-source-number=2 set pcolor green ,set pcolor scale-color green chemical 0.1 5,end,（,2,）,定义,s,etup函数,（,3,）,定义,go,函数,to go,ask turtles,if who=ticks stop,ifelse color=red;任务分配与转换，红色为搜索蚁，橙色为运输蚁,look-for-food ;3.1红色蚂蚁没有携带食物，寻找食物(搜索蚁),return-to-nest ;3.2 携带食物，把食物带回巢穴去(运输蚁),wiggle ;3.3随机摆动,fd 1;前进，随机探索,diffuse chemical(diffusion-rate/100);更新信息素1：信息素扩散,ask patches,set chemical chemical*(100-evaporation-rate)/100 ;更新信息素2：缓慢蒸发信息素,recolor-patch,tick,end,4.1 蚁群优化概述,4.2 蚁群算法的基本实现技术,4.3 蚁群觅食问题,4.4 月球岩石搜索机器人路径规划,第4章 蚁群自组织与共识自主性,1.,问题背景,4.4 月球岩石搜索机器人路径规划,如图4.7所示，月球表面分布着一些黄色的岩石，本模型模拟机器人在月球表面寻找岩石。机器人使用蚁群算法，主要功能包括：,当机器人发现一块石头时，它应该检查附近是否有其他石头，如果有，就打开信息素。这样的话，它就能在返回基地的路上留下踪迹，向其他机器人发出信号，表明小路的尽头有岩石，让其他机器人跟随返回基地。,1,.问题背景,1,.问题背景,2.,模型设计,4.4 月球岩石搜索机器人路径规划,参数名称,参数说明,取值范围,numberOfRobots,机器人数量,120,maxAngle,个体 Agent最大摆角度,090,singleRocks,单个岩石数,1100,clusterRocks,簇岩石数,050,largeClusterRocks,大簇岩石数,020,pheromoneDuration,信息素持续期,0500,percentChanceToFollowPheromone,跟踪信息素的概率百分比,0100,3.,主要算法代码,4.4 月球岩石搜索机器人路径规划,robots-own;每个机器人都知道一些关于自己的信息,searching?;它是否处于搜索状态?,returning?;它是否处于返回状态?,usingPheromone?;它使用信息素吗?,（,1,）,定义变量,patches-own;每个地块都知道一些关于自己的信息,baseColor;它们开始的颜色。,pheromoneCounter;2)在信息素蒸发之前它们还剩多少时间。,初始化环境场景,import moon.png 导入月球的背景图像,setup-globals-and-patches 设置全局变量及背景,setup-robots设置机器人,（,1,）,定义变量,to setup,ca;清除所有数据，重新开始,bitmap:copy-to-pcolors bitmap:import moon.png true;导入月球的背景图像,setup-globals-and-patches;2.1 设置全局变量及背景,setup-robots;2.2设置机器人,reset-ticks,end,（,2,）,定义,s,etup函数,;2.1 设置全局变量及背景,to setup-globals-and-patches,set numberOfRocks 0;将全局numberOfRocks设置为0,ask patches;补丁会记住它们的初始颜色 Patches remember their starting color,set baseColor pcolor,set pheromoneCounter 0;2)补丁上还没有信息素，所以将计数器设置为0。,let targetPatches singleRocks,while targetPatches 0;设置一些随机的黄色补丁来代表岩石。,ask one-of patches,if pcolor!=black and pcolor!=yellow,set pcolor yellow,set targetPatches targetPatches-1,set numberOfRocks(numberOfRocks+singleRocks),let targetClusters clusterRocks,while targetClusters 0;制作5块岩石组成的簇。Make some clusters of 5 rocks.,ask one-of patches,if pcolor!=black and pcolor!=yellow,and pcolor of neighbors4!=black and pcolor of neighbors4!=yellow,set pcolor yellow,ask neighbors4 set pcolor yellow,set targetClusters targetClusters-1,set numberOfRocks(numberOfRocks+(clusterRocks*5),;3)Create some larger clusters of 29 rocks.,let targetLargeClusters largeClusterRocks,while targetLargeClusters 0,ask one-of patches,if pcolor!=black and pcolor!=yellow and pcolorof patches in-radius 3!=black,and pcolor of patches in-radius 3!=yellow,set pcolor yelLow,ask patches in-radius 3,set pcolor yellow,set targetLargeClusters targetLargeClusters-1,set numberOfRocks numberOfRocks+(LargeClusterRocks*29),ask patches;设置背景颜色。,if distancexy 0 0=0 set pcolor green,end,（,2,）,定义,s,etup函数,;2.2设置机器人,to setup-robots,create-robots numberOfRobots;根据滑动条创建一些机器人。设置它们的属性和机器人自己的变量值。,set shape robot,set size 8,set searching?true,set returning?false,set usingPheromone?false;1)机器人开始时不使用信息素。,end,（,2,）,定义,s,etup函数,（,3,）,定义,go,函数,to go,if ticks=10000 stop,if(numberOfRocks 0);运行程序，直到收集到所有岩石,ask robots,if usingPheromone?and not returning?,check-for-trails ;3.1检测机器人轨迹,if searching?,look-for-rocks;3.2寻找岩石,if returning?,return-to-base;3.3返回基地,wiggle;3.4 机器人移动。,update-pheromone;3.5 更新信息素,update-robot-state;3.6更新机器人状态,tick;advance the clock,end,下课了,第5章 飞鸟与粒子,5.1 粒子群算法概述,5.2 粒子群算法的基本实现技术,5.3 车辆加速度参数优化问题,5.4 公共建筑物人员疏散问题,第5章 飞鸟与粒子,5.1 粒子群算法概述,5.1.1 引言,5.1.2 粒子群算法的基本流程,5.1.3 粒子群算法应用,在PSO中，每个优化问题的解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都具有一个位置向量（粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根据目标函数来计算当前的所在位置的适应值（fitness value）。,5.1.1 引,言,PSO也是起源对简单社会系统的模拟，最初设想是模拟鸟群觅食的过程，但后来发现PSO是一种很好的基于迭代的优化工具。系统初始化为一组随机解，通过迭代搜寻最优值。但是并没有遗传算法用的交叉（crossover）以及变异（mutation）。而是粒子在解空间追随最优的粒子进行搜索。,5.1.1 引,言,在PSO中，每一个优化问题的潜在解都能够想象成d维搜索空间上的一个点，我们称之为“粒子”（Particle），全部的粒子都有一个被目标函数决定的适应值（FitnessValue），每一个粒子速度决定他们飞行的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。Reynolds对鸟群飞行的研究发现。鸟仅仅是追踪它有限数量的邻居但最终总体结果是整个鸟群好像在一个中心的控制之下，即复杂的全局行为是由简单规则的相互作用引起的。,5.1.1 引,言,例如，寻找函数F(x,y)=x2+y2,x和y的取值范围在-6,6平面区域A内。,为了得到该函数的最大值，我们在A区域内随机的分布一些点，并且计算这些点的函数值，同时给这些点设置一个速度。下面这些点就会按照一定的公式更改自己的位置，到达新位置后，再计算这些点的值，然后再按照一定的公式更新自己的位置。直到最后在x=y=0这个点停止自己的更新。最后所有的点都集中在最大值的地方。,5.1.2 粒子群算法的基本流程,粒子群算法的伪代码如下,For each particle,Initialize particle,END,Do,For each particle,Calculate fitness value,If the fitness value the best fitness value(pBest)in history,set current value as the new pBest,End,Set gBestthe best fitness value of all the particles,For each particle,Calculate particle velocity,Update particle position,End,While maximum iterations or minimum error criteria is not attained,5.1.2 粒子群算法的基本流程,标准PSO的算法流程如下：,1.初始化,首先，我们设置最大迭代次数，目标函数的自变量个数，粒子的最大速度，位置信息为整个搜索空间，我们在速度区间和搜索空间上随机初始化速度和位置，设置粒子群规模为M，每个粒子随机初始化一个速度。,2.个体极值与全局最优解,定义适应度函数，个体极值为每个粒子找到的最优解，从这些最优解找到一个全局值，称为本次全局最优解。与历史全局最优比较，进行更新。,更新速度和位置的公式,.,3.终止条件,（1）达到设定迭代次数；,（2）代数之间的差值满足最小界限,5.1.2 粒子群算法的基本流程,PSO的优势在于容易实现并且没有许多参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。,随着PSO的不断发展，研究者己尝试着将其用于各种工程优化问题。例如将粒子群优化算法应用于分时供电优化调度系统，获得最优分时供电方案以指导生产；应用粒子群算法解决互联网络服务质量路由问题。PSO算法还在多峰值函数优化、多目标优化和约束优化等方面取得了很好的效果，利用PSO实现了对各种连续和离散控制变量的优化。,PSO在人工神经网络优化方面取得了良好的效果，利用PSO实现了对人工神经网络权值和网络模型结构的优化。,5.1.3 粒子群算法应用,5.1 粒子群算法概述,5.2 粒子群算法的基本实现技术,5.3 车辆加速度参数优化问题,5.4 公共建筑物人员疏散问题,第5章 飞鸟与粒子,5.2 粒子群算法的基本实现技术,5.2.1 标准PSO算法及其扩展,5.2.2 解的空间表示与参数选择,5.2.3 适应度评价函数,PSO算法是基于群体的，根据对环境的适应度将群体中的个体移动到好的区域。然而它不对个体使用演化算子，而是将每个个体看作是D维搜索空间中的一个没有体积的微粒（点），在搜索空间中以一定的速度飞行，这个速度根据它本身的飞行经验和同伴的飞行经验来动态调整。第i个微粒表示为Xi=（xi1,xi2,xiD），它经历过的最好位置（有最好的适应值）记为Pi=（pi1,pi2,piD），也称为pbest。在群体所有微粒经历过的最好位置的索引号用符号g表示，即Pg，也称为gbest。微粒i的速度用Vi=（vi1,vi2,viD）表示。对每一代，它的第d维（1 d D）根据如下方程进行变化：,vid=wvid+c1rand（）（pid-xid）+c2Rand（）（pgd-xid）（5-1）,xid=xid+vid （5-2）,其中w为惯性权重（inertia weight），c1和c2为加速常数（acceleration constants），rand（）和Rand（）为两个在0,1范围里变化的随机值。,1.PSO核心算子,在全局版的标准粒子群算法中，每个粒子的速度的更新是根据两个因素来变化的，这两个因素是：粒子自己历史最优值pi和粒子群体的全局最优值pg。,如果改变粒子速度更新公式，让每个粒子的速度的更新根据以下两个因素更新：,A.粒子自己历史最优值pi。,B.粒子邻域内粒子的最优值pnk。,其余保持跟全局版的标准粒子群算法一样，这个算法就变为局部版的粒子群算法。,2.标准的粒子群算法（局部版本）,标准粒子群算法的变形主要是对标准粒子群算法的惯性因子、收敛因子（约束因子）、“认知”部分的c1，“社会”部分的c2进行变化与调节，希望获得好的效果。,2007年希腊的两位学者提出将收敛速度比较快的全局版本的粒子群算法与不容易陷入局部最优的局部版本的粒子群算法相结合的办法，利用的公式是,v=n*v(全局版本)（1n）*v(局部版本)速度更新公式，v代表速度（5-3）,w（k1）=w(k)v 位置更新公式（5-4）,该算法在文献中讨论了系数n取各种不同情况的情况，并且运行来了20000次来分析各种系数的结果。,3.标准粒子群算法的变形,粒子群算法的混合主要是将粒子群算法与各种算法相混合，例如将它与模拟退火算法或单纯形方法相混合。最多的是将它与遗传算法的混合。根据遗传算法的三种不同算子可以生成3种不同的混合算法。,4.粒子群算法的混合,Eberhart等又提出了PSO的离散二进制版，用来解决工程实际中的组合优化问题。他们在提出的模型中将粒子的每一维及粒子本身的历史最优、全局最优限制为1或0，而速度不作这种限制。用速度更新位置时，设定一个阈值，当速度高于该阈值时，粒子的位置取1，否则取0。二进制PSO与遗传算法在形式上很相似，但实