pso粒子群算法概述课件

粒子群优化算法,PSO,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,粒子群优化算法（,PSO,）是一种进化计算技术（,evolutionary computation,）,由,Eberhart,博士和,kennedy,博士,于,1995,年提出,(,Kennedy J,，,Eberhart,R,Particle swarm optimization,Proceedings of the IEEE International Conference on Neural Networks,1995,19421948.,),。,源于对鸟群捕食的行为研究。粒子群优化算法的基本思想是通过群体中个体之间的协作和信息共享来寻找最优解,PSO,的优势在于简单容易实现并且没有,许多,参数的调节。目前已被广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。,算法介绍,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,算法介绍,设想这样一个场景：一群鸟在随机的搜索食物。,在这个区域里只有一块食物，所有的鸟都不知,道食物在那。但是它们知道自己当前的位置距,离食物还有多远。,那么找到食物的最优策略是什么,？,最简单有效的就是搜寻目前离食物最近的鸟的,周围区域。,算法介绍,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,抽象：,鸟被抽象为没有质量和体积的微粒,(,点,),，并延伸到,N,维空间，粒子,I,在,N,维空间的位置表示为矢量,Xi,(,x,1,，,x,2,，,，,x,N,),，飞行速度表示为矢量,Vi,(,v,1,，,v,2,，,，,v,N,),每个粒子都有一个由目标函数决定的适应值,(fitness value),，并且知道自己到目前为止发现的最好位置,(,pbest,),和现在的位置,Xi,这个可以看作是粒子自己的飞行经验除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置,(,gbest)(gbest,是,pbest,中的最好值,),这个可以看作是粒子同伴的经验粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。,算法介绍,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(1),式,(2),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,算法介绍,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,V,i,是粒子的速度；,pbest,和,gbest,如前定义；,rand(),是介于（,0,、,1,）之间的随机数；,X,i,是粒子的当前位置。,c1,和,c2,是学习因子，通常取,c1,c2,2,在每一维，粒子都有一个最大限制速度,Vmax,，如果,某一维的速度超过设定的,Vmax,，那么这一维的速度,就被限定为,Vmax,。（,Vmax,0,）,以上面两个公式为基础，形成了后来,PSO,的标准形式,算法介绍,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,算法介绍,从社会学的角度来看，公式,(1),的第一部分称为记忆项，,表示上次速度大小和方向的影响；公式第二部分称为自,身认知项，是从当前点指向粒子自身最好点的一个矢量，,表示粒子的动作来源于自己经验的部分；公式的第三部,分称为群体认知项，是一个从当前点指向种群最好点的,矢量，反映了粒子间的协同合作和知识共享。粒子就是,通过自己的经验和同伴中最好的经验来决定下一步的运,动。,以上面两个公式为基础，形成了后来,PSO,的标准形式,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,算法介绍,1998,年,shi,等人在进化计算的国际会议上,发表了一篇论文,A modified particle swarm,optimizer,对前面的公式,(1),进行了修正。引入,惯性权重因子。,（,3,）式,非负，称为惯性因子。,公式,(2),和,(3),被视为标准,pso,算法。,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,算法介绍,标准,PSO,算法的流程：,Step1:,初始化一群微粒,(,群体规模为,m),，包括随机位置和,速度；,Step2:,评价每个微粒的适应度；,Step3:,对每个微粒，将其适应值与其经过的最好位置,pbest,作比较，如果较好，则将其作为当前的,最好位置,pbest,;,Step4:,对每个微粒，将其适应值与其经过的最好位置,gbest,作比较，如果较好，则将其作为当前的,最好位置,gbest,;,Step5:,根据,(2),、,(3),式调整微粒速度和位置；,Step6,：未达到结束条件则转,Step2,。,算法介绍,迭代终止条件,根据具体问题一般选为最大迭代,次数,G,k,或,(,和,),微粒群迄今为止搜索到的最优位置,满足预定最小适应阈值,。,PSO,算法流程图和伪代码,应用举例,例,6.1,已知函数 ，,其中 ，用粒子群优化算法求解,y,的最小值。,运行步骤,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,局部和全局最优算法,方程,(2),和,(3),中,pbest,和,gbest,分别表示微粒群的局部和,全局最优位置，当,C1,0,时，则粒子没有了认知能力，,变为只有社会的模型,(social-only):,被称为全局,PSO,算法,.,粒子有扩展搜索空间的能力，具有,较快的收敛速度，但由于缺少局部搜索，对于复杂问题,比标准,PSO,更易陷入局部最优。,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,当,C2,0,时，则粒子之间没有社会信息，模型变为,只有认知,(cognition-only),模型：,被称为局部,PSO,算法。由于个体之间没有信息的,交流，整个群体相当于多个粒子进行盲目的随机,搜索，收敛速度慢，因而得到最优解的可能性小。,局部和全局最优算法,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,参数分析,参数有：群体规模,m,，惯性因子 ，学习因子,c1,和,c2,最大速度,V,max,，迭代次数,G,k,。,群体规模,m,一般取,20,40,，对较难或特定类别的问题,可以取到,100,200,。,最大速度,V,max,决定当前位置与最好位置之间的区域的,分辨率,(,或精度,),。如果太快，则粒子有可能越过极小,点,;,如果太慢，则粒子不能在局部极小点之外进行足,够的探索，会陷入到局部极值区域内。这种限制可以,达到防止计算溢出、决定问题空间搜索的粒度的目的。,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总数,权重因子,包括惯性因子 和学习因子,c1,和,c2,。使粒子,保持着运动惯性，使其具有扩展搜索空间的趋势，有,能力探索新的区域。,C1,和,c2,代表将每个粒子推向,Pbest,和,gbest,位置的统计加速项的权值。较低的值允许粒子,在被拉回之前可以在目标区域外徘徊，较高的值导致粒,子突然地冲向或越过目标区域。,参数分析,算法介绍,PSO,初始化为一群随机粒子,(,随机解,),。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个,“,极值,”,(,pbest,gbest,),来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,(2),式,(1),式,在式,(1),、,(2),中，,i,1,，,2,，,，,M,，,M,是该群体中粒子的总