粒子群优化算法与蚁群算法PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,人工智能,粒群优化算法,蚁群算法理论,蚁群算法的研究与应用,1,粒子群优化算法,PSOParticle Swarm Optimization,2,背景,人工生命,：研究具有某些生命基本特征的人工系统。包括两方面的内容：,1,、研究如何利用计算技术研究生物现象；,2,、,研究如何利用生物技术研究计算问题,。,我们关注的是第二点。,如何利用生物技术研究计算问题是人工生命研究的重要方向，现已有了很多源于生物现象的计算技巧，例如人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。,3,背景,现在讨论另一种生物系统,-,社会系统：由简单个体组成的群落和环境及个体之间的相互行为。也可称为,群智能,(swarm intelligence),这些模拟系统利用局部信息从而可以产生不可预测的群行为。,目前计算智能领域有种基于群智能的算法,:,蚁群算法,(ant colony optimization),和粒子群算法,(particle swarm optimization),。,4,背景,我们经常能够看到成群的鸟、鱼或者浮游生物。这些生物的聚集行为有利于它们觅食和逃避捕食者。它们的群落动辄以十、百、千甚至万计，并且经常不存在一个统一的指挥者。,它们是如何完成聚集、移动这些功能呢？,5,6,背景,对鸟群行为的模拟,：,Reynolds,、,Heppner,和,Grenader,提出鸟群行为的,模拟。他们发现，鸟群在行进中会突然同步的改,变方向，散开或者聚集等。那么一定有某种潜在,的能力或规则保证了这些同步的行为。这些科学,家都认为上述行为是基于不可预知的鸟类社会行,为中的群体动态学。,在这些早期的模型中仅仅依赖个体间距的操作，,也就是说，这种同步是鸟群中个体之间努力保持,最优的距离的结果。,7,背景,对鱼群行为的研究：,生物社会学家,E.O.Wilson,对鱼群进行了研究。提出：“至少在理论上，鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验，这种受益超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散。”这说明，同种生物之间信息的社会共享能够带来好处。这是,PSO,的基础。,8,算法介绍,粒子群优化算法（,PSO,）是一种进化计算技术（,evolutionary computation,）,由,Eberhart,博士和,kennedy,博士于,1995,年提出,(Kennedy J,，,Eberhart R,Particle swarm optimization,Proceedings of the IEEE International Conference on Neural Networks,1995,19421948.),。源于对鸟群捕食的行为研究。,粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解,9,算法介绍,设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。,那么找到食物的最优策略是什么,？,最简单有效的就是搜寻目前离食物最近的鸟的,周围区域。,10,算法介绍,抽象：,鸟被抽象为没有质量和体积的微粒,(,点,),，并延伸到,N,维空间，粒子,I,在,N,维空间的位置表示为矢量,Xi,(,x,1,，,x,2,，,，,xn,),，飞行速度表示为矢量,Vi,(,v1,，,v2,，,，,v,n),每个粒子都有一个由目标函数决定的适应值,(fitness value),；,并且知道自己到目前为止发现的最好位置,(pbest),；,除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置,(gbest),(gbest,是,pbest,中的最好值,),。,粒子怎么样到达下一步的运动,？,11,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值”,(pbest,gbest),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,（,2,）式,12,算法介绍,Vi,是粒子的速度；,pbest,和,gbest,如前定义；,rand(),是介于（,0,、,1,）之间的随机数；,Xi,是粒子的当前位置；,c1,和,c2,是学习因子，通常取,c1,c2,2,；,在每一维，粒子都,有一个最大限制速度,Vmax,，如果某一维的速度超过设定的值,，那么这一维的速度就被限定为,Vmax,。（,Vmax 0,）,13,算法介绍,14,算法介绍,从社会学的角度来看，公式,(1),的第一部分称为记忆项，表示上次速度大小和方向的影响；公式第二部分称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的分；公式的第三部分称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。,粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。,以上面两个公式为基础，形成了后来,PSO,的标准形式,15,算法介绍,1998,年,shi,等人在进化计算的国际会议上,发表了一篇论文,A modified particle swarm,optimizer,对前面的公式,(1),进行了修正。引入惯性权重因子。,为非负数，称为惯性因子。,公式,(2),和,(3),被视为标准,pso,算法,。,16,算法介绍,值较大，全局寻优能力强，局部寻优能力弱；,值较小反之。,初始时，,shi,将 取为常数，后来实验发现，动,态 能够获得比固定值更好的寻优结果。动态,可以在,PSO,搜索过程中线性变化，也可根据,PSO,性能的某个测度函数动态改变。,目前，采用较多的是,shi,建议的线性递减权值,(linearly decreasing weight,LDW),策略。,17,算法介绍,通常由下式来确定,和是的最大最小值；和分别是当前叠代次数和最大叠代次数。,的引入使,PSO,算法性能有了很大提高，针对不同的搜索问题，可以调整全局和局部搜索能力，也使得,PSO,算法能成功的应用于很多实际问题。,典型取值,：,0.9,；,0.4,18,算法介绍,标准,PSO,算法的流程：,Step1:,初始化一群微粒,(,群体规模为,M),，包括随机位置和,速度；,Step2:,评价每个微粒的适应度；,Step3:,对每个微粒，将其适应值与其经过的最好位置,pbest,作比较，如果较好，则将其作为当前的,最好位置,pbest;,Step4:,对每个微粒，将其适应值与其经过的最好位置,gbest,作比较，如果较好，则将其作为当前的,最好位置,gbest;,Step5:,根据,(2),、,(3),式调整微粒速度和位置；,Step6:,未达到结束条件则转,Step2,。,19,算法介绍,迭代终止条件,根据具体问题一般选为最大迭代次数或,(,和,),微粒群迄今为止搜索到的最优位置满足预定最小适应阈值,。,20,全局和局部最优算法,权重因子，是调整粒子的自身经验与社会（群体）经验在其运动中所起的作用的权重。,如果,0,，则粒子没有自经验，只有“社会（,social-only,）经验”，它的收敛速度可能较快，但在处理较复杂的问题时，容易陷入局部最优点。,如果,0,，则粒子没有群体共享信息，只有“自身经验”，因为个体间没有交互，一个规模为,M,的群体等价于运行了,M,个单个微粒，因而得到解的几率非常小。,21,参数分析,参数有：群体规模,M,，惯性因子,w,，学习因子,c1,和,c2,最大速度,Vmax,，迭代次数,iter,。,群体规模,M,，,一般取,20,40,，对较难或特定类别的问题,可以取到,100,200,。,最大速度,Vmax,决定当前位置与最好位置之间的区域的,分辨率,(,或精度,),。如果太快，则粒子有可能越过极小,点,;,如果太慢，则粒子不能在局部极小点之外进行足,够的探索，会陷入到局部极值区域内。这种限制可以,达到防止计算溢出、决定问题空间搜索的粒度的目的。,22,参数分析,权重因子,包括惯性因子,w,和学习因子,c1,和,c2,。,w,使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。,c1,和,c2,代表将每个粒子推向,Pbest,和,gbest,位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。,23,参数分析,参数设置,：,如果令,c1,c2,0,，粒子将一直以当前,速度的飞行，直到边界。很难找到最优解。,如果,w,0,，则速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子则飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。,在加上第一部分后，粒子有扩展搜索空间的趋势，这也使得,w,的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。,w,较大时，具有较强的全局搜索能力；,w,较小时，具有较强的局部搜索能力,。,24,参数分析,通常设,c1,c2,2,。,Suganthan,的实验表明：,c1,和,c2,为常数时可以得到较好的解，但不一定必须等于,2,。,Clerc,引入收敛因子,(constriction factor)K,来保证,收敛性。,其中：,25,参数分析,通常取 为,4.1,则,K,0.729.,实验表明，与使,用惯性权重的,PSO,算法相比，使用收敛因子的,PSO,有更快的收敛速度。其实只要恰当的选取,和,c1,、,c2,，两种算法是一样的。因此使用收,敛因子的,PSO,可以看作使用惯性权重,PSO,的特,例。,恰当的选取算法的参数值可以改善算法的性能,26,蚁群算法理论,ant colony optimization,ACO,27,小蚂蚁，大智慧,蚂蚁在,8000,玩年之间就建立了自己的社会，而我们人类只有,5000,余年的文明史。人类的许多城市都有不少都市问题，可是小小的蚂蚁却能建立起组织完好的复杂的“社会”。有许多“蚂蚁城市”往往由,5000,万个成员组成，而在人口较为稠密的城市也不过,1000,多万人。,蚂蚁有四种不同的蚁型，即蚁后，雄蚁，工 蚁和兵蚁。不同的蚁型有不同的分工。蚁后称为“蚂蚁女王”，主要职责是产卵，繁衍后代和管理蚂蚁家族，它可根据食物多少来决定是否生育，还可以根据筑巢和建立新群体所需的蚂蚁数量来调节人口结构；雄蚁负责交配；工蚁负责筑巢，采集食物，饲喂幼蚁和蚁后等；兵蚁负责保卫群体。,尽管蚂蚁个体比较简单，但整个蚁群却表现为高度机构化的社会组织，在许多情况下能完成远远超过蚂蚁个体能力的复杂任务。这种能力来源于蚂蚁群体中的个体协作行为。其群体行为主要包括寻找食物，任务分配和构造墓地等三种。,28,在现实生活中，我们总可以观察到大量蚂蚁在巢穴与食物源之间形式近乎直线的路径，而不是曲线或者圆等其他形状。蚂蚁群体不仅能完成复杂的任务，而且还能适应环境的变换，如在蚁群运动线路上加上障碍，一开始各只蚂蚁分布是均匀的，不管路径长短，蚂蚁总是按照同等概率选择各条路径。,在蚂蚁运动的过程中，能够在其经过的路径上留下信息素，而且能够感知这种物质的强度及存在，并以此指导自己运动的方向，蚂蚁倾向于向信息素浓度高的方向移动，相等时间内较短路径上的信息素就遗留得较多，则选择的蚂蚁就变得多。,由于蚁群集体行为表现出一种信息正反馈信息，即某一路径走过的蚂蚁越多，则后来者选择的概率就大得多，蚂蚁个体之间就是通过这种信息交流机制来搜索食物，并沿着最短的路径前进。,迷人的蚂蚁,29,蚁群寻找食物的过程,30,蚁群觅食的双桥实验,31,蚁群算法的背景,蚁群算法,(ant colony optimization,ACO),，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。,蚁群算法是一种,模拟进化,算法，初步的研究表明该算法具有许多优良的性质。针对,PID,控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。,32,蚁群算法的由来：蚂蚁是地球上最常见、数量最多的昆虫种类之一，常常成群结队地出现在人类的日常生活环境中。这些昆虫的群体生物智能特征，引起了一些学者的注意。意大利学者,M.Dorigo,，,V.Maniezzo,等人在观察蚂蚁的觅食习性时发现，蚂蚁总能找到巢穴与食物源之间的最短路径。经研究发现，蚂蚁的这种群体协作功能是通过一种遗留在其来往路径上的叫做,信息素,(Pheromone),的挥发性化学物质来进行通信和协调的。化学通信是蚂蚁采取的基本信息交流方式之一，在蚂蚁的生活习性中起着重要的作用。通过对蚂蚁觅食行为的研究，他们发现，整个蚁群就是通过这种信息素进行相互协作，形成正反馈，从而使多个路径上的蚂蚁都逐渐聚集到最短的那条路径上。,背景,这样，,M.Dorigo,等人于,1991,年首先提出了蚁群算法。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。这是一种基于种群寻优的启发式搜索算法。它充分利用了生物蚁群能通过个体间简单的信息传递，搜索从蚁巢至食物间最短路径的集体寻优特征，以及该过程与旅行商问题求解之间的相似性。得到了具有,NP,难度的旅行商问题的最优解答。同时，该算法还被用于求解,Job-Shop,调度问题、二次指派问题以及多维背包问题等，显示了其适用于组合优化类问题求解的优越特征。,33,34,自然蚁群与人工蚁群算法,基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如,TSP,问题。,人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。,两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。,例如在,TSP,问题中，可以预先知道当前城市到下一个目的地的距离。,35,蚁群算法与,TSP,问题,1/3,TSP,问题表示为一个,N,个城市的有向图,G=,（,N,，,A,），,其中,城市之间距离,目标函数为 ，,其中 为城市,1,2,，,n,的,一个排列，。,36,蚁群算法与,TSP,问题,2/3,TSP,问题的人工蚁群算法中，假设,m,只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：,1,信息素值 也称信息素痕迹。,2,可见度，即先验值。,信息素的更新方式有,2,种，一是挥发，也就是所有路径上的信息素以一定的比率进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值,“,好,”,(,有蚂蚁走过,),的边增加信息素。,37,蚁群算法与,TSP,问题,3/3,蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。,蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。,38,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,1/12,初始的蚁群算法是基于图的蚁群算法，,graph-based ant system,简称为,GBAS,，是由,Gutjahr W J,在,2000,年的,Future Generation Computing Systems,提出的，课本的参考文献,2,。算法步骤如下：,STEP 0,对,n,个城市的,TSP,问题，,城市间的距离矩阵为 ，给,TSP,图中的每一条弧 赋信息素初值 ，假设,m,只蚂蚁在工作，所有蚂蚁都从同一城市 出发。,当前最好解是 。,39,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,2/12,STEP 1,（外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁,s,从起点 出发，用 表示蚂蚁,s,行走的城市集合，初始 为空集，。,STEP 2,(,内循环,),按蚂蚁 的顺序分别计算。当蚂蚁在城市,i,，若,完成第,s,只蚂蚁的计算。,否则，若,，则以概率 ，,到达,j,，,；若,则到达 重复,STEP 2,。,40,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,3/12,STRP 3,对 ，若 按 中城市的顺序计算,路径程度；若 ，路径长度置为一个无穷大值（即不可,达）。比较,m,只蚂蚁中的路径长度，记走最短路径的蚂蚁为,t,。,若 ，则 。用如下公式对,W,路径,上的信息素痕迹加强，对其他路径上的信息素进行挥发。,得到新的 ，重复步骤,STEP 1,。,41,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,4/12,在,STEP 3,中，挥发因子 对于一个固定的 ，满足,并且,经过,k,次挥发，非最优路径的信息素逐渐减少至消失。,42,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,5/12,以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市,i,到城市,j,的转移。,算法中包括信息素更新的过程,1,信息素挥发（,evaporation,）信息素痕迹的挥发过程是每个连接上的信,息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个,挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区,域的扩展。,2,信息素增强（,reinforcement,）增强过程是蚁群优化算法中可选的部分，,称为离线更新方式（还有在线更新方式）。这种方式可以实现由单个蚂,蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（,m,只蚂蚁）,中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，,挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的,信息素更新称为离线的信息素更新。,在,STEP 3,中，蚁群永远记忆到目前为止的最优解。,43,图的蚁群系统（,GBAS,）,6/12,可以验证，下式满足：,即 是一个随机矩阵。,四个城市的非对称,TSP,问题，距离矩阵和城市图示如下：,44,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,7/12,假设共,4,只蚂蚁，所有蚂蚁都从城市,A,出发，挥发因子,。此时，观察,GBAS,的计算过程。矩阵,共有,12,条弧，初始信息素记忆矩阵为：,45,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,8/12,执行,GBAS,算法的步骤,2,，假设蚂蚁的行走路线分别为：,当前最优解为，这个解是截止到当前的最优解，碰巧是实际,最优解,46,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,9/12,按算法步骤,3,的信息素更新规则，得到更新矩阵,这是第一次外循环结束的状态。,47,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,10/12,重复外循环，由于上一次得到的,W2,已经是全局最优解，因此按算法步骤,3,的信息素更新规则，无论蚂蚁如何行走，都只是对,W2,路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵,这是第一次外循环结束的状态。,48,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,11/12,重复外循环，由于,W2,全局最优解，,GBAS,只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：,49,初始的蚁群优化算法,基于图的蚁群系统（,GBAS,）,12/12,蚂蚁以一定的概率从城市,i,到城市,j,进行转移，信息素的更新在,STEP 3,完成，并随,K,而变化。假设第,K,次外循环后得到信息素矩阵,，得到当前最优解 。第,K,次循环前的信息素和最优解为 ，经过第,K,次外循环后，得到,。由于蚂蚁的一步转移概率是随机的，从 到,也是随机的，是一个马尔可夫过程。,