粒子群优化算法

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,粒子群优化算法PSOParticle Swarm Optimization,背景,人工生命：研究具有某些生命根本特征的人工系统。包括两方面的内容：,1、研究如何利用计算技术研究生物现象；,2、研究如何利用生物技术研究计算问题。,我们关注的是第二点。,如何利用生物技术研究计算问题是人工生命研究的重要方向，现已有了很多源于生物现象的计算技巧，例如人工神经网络是简化的大脑模型，遗传算法是模拟基因进化过程的。,背景,现在讨论另一种生物系统-社会系统：由简单个体组成的群落和环境及个体之间的相互行为。也可称为,群智能(swarm intelligence),这些模拟系统利用局部信息从而可以产生不可预测的群行为。,目前计算智能领域有种基于群智能的算法:蚁群算法(ant colony optimization)和粒子群算法(particle swarm optimization)。,背景,我们经常能够看到成群的鸟、鱼或者浮游生物。这些生物的聚集行为有利于它们觅食和逃避捕食者。它们的群落动辄以十、百、千甚至万计，并且经常不存在一个统一的指挥者。,它们是如何完成聚集、移动这些功能呢？,背景,对鸟群行为的模拟：,Reynolds、Heppner和Grenader提出鸟群行为的,模拟。他们发现，鸟群在行进中会突然同步的改,变方向，散开或者聚集等。那么一定有某种潜在,的能力或规那么保证了这些同步的行为。这些科学,家都认为上述行为是基于不可预知的鸟类社会行,为中的群体动态学。,在这些早期的模型中仅仅依赖个体间距的操作，,也就是说，这中同步是鸟群中个体之间努力保持,最优的距离的结果。,背景,对鱼群行为的研究：,生物社会学家对鱼群进行了研究。提出：“至少在理论上，鱼群的个体成员能够受益于群体中其他个体在寻找食物的过程中的发现和以前的经验，这种受益超过了个体之间的竞争所带来的利益消耗，不管任何时候食物资源不可预知的分散。这说明，同种生物之间信息的社会共享能够带来好处。这是PSO的根底。,算法介绍,粒子群优化算法PSO是一种进化计算技术evolutionary computation,由Eberhart博士和kennedy博士于1995年提出(Kennedy J，Eberhart R,Particle swarm optimizationProceedings of the IEEE International Conference on Neural Networks199519421948.)。源于对鸟群捕食的行为研究。,粒子群优化算法的根本思想是通过群体中个体之间的协作和信息共享来寻找最优解,算法介绍,设想这样一个场景：一群鸟在随机的搜索食物。在这个区域里只有一块食物，所有的鸟都不知道食物在那。但是它们知道自己当前的位置距离食物还有多远。,那么找到食物的最优策略是什么,？,最简单有效的就是搜寻目前离食物最近的鸟的,周围区域。,算法介绍,抽象：,鸟被抽象为没有质量和体积的微粒(点)，并延伸到N维空间，粒子,I,在N维空间的位置表示为矢量,Xi,(,x,1，,x,2，,xn,)，飞行速度表示为矢量,Vi,(,v1,，,v2,，,v,n),每个粒子都有一个由目标函数决定的适应值(fitness value)；,并且知道自己到目前为止发现的最好位置(pbest),；,除此之外，每个粒子还知道到目前为止整个群体中所有粒子发现的最好位置(gbest),(gbest是pbest中的最好值)。,粒子怎么样到达下一步的运动,？,算法介绍,PSO初始化为一群随机粒子(随机解)。然后通过迭代找到最优解。在每一次的迭代中，粒子通过跟踪两个“极值(pbest,gbest)来更新自己。,在找到这两个最优值后，粒子通过下面的公式来更新自己的速度和位置。,在式(1)、(2)中，,i,1，2，M，M是该群体中粒子的总数,算法介绍,Vi 是粒子的速度；,pbest和gbest如前定义；,rand()是介于0、1之间的随机数；,Xi 是粒子的当前位置；,c1和c2是学习因子，通常取c1 c22；,在每一维，粒子都有一个最大限制速度Vmax，如果某一维的速度超过设定的值，那么这一维的速度就被限定为Vmax。Vmax 0,算法介绍,算法介绍,从社会学的角度来看，公式(1)的第一局部称为记忆项，表示上次速度大小和方向的影响；公式第二局部称为自身认知项，是从当前点指向粒子自身最好点的一个矢量，表示粒子的动作来源于自己经验的分；公式的第三局部称为群体认知项，是一个从当前点指向种群最好点的矢量，反映了粒子间的协同合作和知识共享。,粒子就是通过自己的经验和同伴中最好的经验来决定下一步的运动。,以上面两个公式为根底，形成了后来PSO 的标准形式,算法介绍,1998年shi等人在进化计算的国际会议上,发表了一篇论文?A modified particle swarm,optimizer?对前面的公式(1)进行了修正。引入惯性权重因子。,为非负数，称为惯性因子。,公式(2)和(3)被视为标准pso算法,。,算法介绍,值较大，全局寻优能力强，局部寻优能力弱；,值较小反之。,初始时，shi将 取为常数，后来实验发现，动,态 能够获得比固定值更好的寻优结果。动态,可以在PSO搜索过程中线性变化，也可根据PSO,性能的某个测度函数动态改变。,目前，采用较多的是shi建议的线性递减权值,(linearly decreasing weight,LDW)策略。,算法介绍,通常由下式来确定,和是的最大最小值；和分别是当前叠代次数和最大叠代次数。,的引入使PSO算法性能有了很大提高，针对不同的搜索问题，可以调整全局和局部搜索能力，也使得PSO算法能成功的应用于很多实际问题。,典型取值,：,0.9；0.4,算法介绍,标准PSO算法的流程：,Step1:初始化一群微粒(群体规模为M)，包括随机位置和,速度；,Step2:评价每个微粒的适应度；,Step3:对每个微粒，将其适应值与其经过的最好位置,pbest作比较，如果较好，那么将其作为当前的,最好位置pbest;,Step4:对每个微粒，将其适应值与其经过的最好位置,gbest作比较，如果较好，那么将其作为当前的,最好位置gbest;,Step5:根据(2)、(3)式调整微粒速度和位置；,Step6:未到达结束条件那么转Step2。,算法介绍,迭代终止条件,根据具体问题一般选为最大迭代次数或(和)微粒群迄今为止搜索到的最优位置满足预定最小适应阈值,。,全局和局部最优算法,权重因子，是调整粒子的自身经验与社会群体经验在其运动中所起的作用的权重。,如果0，那么粒子没有自经验，只有“社会social-only经验，它的收敛速度可能较快，但在处理较复杂的问题时，容易陷入局部最优点。,如果0，那么粒子没有群体共享信息，只有“自身经验，因为个体间没有交互，一个规模为M的群体等价于运行了M个单个微粒，因而得到解的几率非常小。,参数分析,参数有：群体规模M，惯性因子 w ，学习因子c1和c2,最大速度Vmax，迭代次数iter。,群体规模M，一般取2040，对较难或特定类别的问题,可以取到100200。,最大速度Vmax决定当前位置与最好位置之间的区域的,分辨率(或精度)。如果太快，那么粒子有可能越过极小,点;如果太慢，那么粒子不能在局部极小点之外进行足,够的探索，会陷入到局部极值区域内。这种限制可以,到达防止计算溢出、决定问题空间搜索的粒度的目的。,参数分析,权重因子,包括惯性因子 w和学习因子c1和c2。w使粒子保持着运动惯性，使其具有扩展搜索空间的趋势，有能力探索新的区域。c1和c2代表将每个粒子推向Pbest和gbest位置的统计加速项的权值。较低的值允许粒子在被拉回之前可以在目标区域外徘徊，较高的值导致粒子突然地冲向或越过目标区域。,参数分析,参数设置：如果令c1c20，粒子将一直以当前,速度的飞行，直到边界。很难找到最优解。,如果w 0，那么速度只取决于当前位置和历史最好位置，速度本身没有记忆性。假设一个粒子处在全局最好位置，它将保持静止，其他粒子那么飞向它的最好位置和全局最好位置的加权中心。粒子将收缩到当前全局最好位置。,在加上第一局部后，粒子有扩展搜索空间的趋势，这也使得w的作用表现为针对不同的搜索问题，调整算法的全局和局部搜索能力的平衡。w较大时，具有较强的全局搜索能力；w较小时，具有较强的局部搜索能力。,参数分析,通常设c1c22。Suganthan的实验说明：c1和c2,为常数时可以得到较好的解，但不一定必须等于2。,Clerc引入收敛因子(constriction factor)K来保证,收敛性。,其中：,参数分析,通常取 为4.1,那么K0.729.实验说明，与使,用惯性权重的PSO算法相比，使用收敛因子的,PSO有更快的收敛速度。其实只要恰当的选取,和c1、c2，两种算法是一样的。因此使用收,敛因子的PSO可以看作使用惯性权重PSO的特,例。,恰当的选取算法的参数值可以改善算法的性能,