资源描述
*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第九讲,daili,粒子群算法,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第九讲,daili,粒子群算法,*,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,粒子群,优化,算法,（PS0）,Particle Swarm Optimization,智能算法,向大自然学习,遗传算法,(GA),物竞天择，设计染色体编码，根据适应值函数进行染色体选择、交叉和变异操作，优化求解,人工神经网络算法,(ANN),模仿生物神经元，透过神经元的信息传递、训练学习、联想，优化求解,模拟退火算法,(SA),模,模仿金属物质退火过程,解决最优化问题,的方法,传统搜索方法,保证能找到最优解,Heuristic Search,不能保证找到最优解,由Kennedy和Eberhart于1995年提出,群体迭代，粒子在解空间追随最优的粒子进行搜索.,简单易行,粒子群算法,:收,敛速度快,设置参数少,已成为现代优化方法领域研究的热点,粒子群算法发展历史简介,粒子群,算法的基本思想,粒子群算法的思想源于对鸟群捕食行为的研究,模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法,。,马良教授在他的著作蚁群优化算法一书的前言中写到,：,大自然对我们的最大恩赐！,“自然界的蚁群、鸟群、鱼群、,羊群、牛群、蜂群等，其实时时刻刻都在给予,我们以某种启示，只不过我们常常忽略了,大自然对我们的最大恩赐！,.”,粒子群,算法的基本思想,设想这样一个场景：,一群鸟在随机搜索食物,在这块区域里只有一块食物;,所有的鸟都不知道食物在哪里;,但它们能感受到当前的位置离食物还有多远.,已知,那么:找到食物的最优策略是什么呢？,搜寻目前离食物最近的鸟的周围区域,根据自己飞行的经验判断食物的所在。,PSO正是从这种模型中得到了启发,PSO的基础:,信息的社会共享,生物学家对鸟,(,鱼,),群捕食的行为研究,社会行为,(Social-Only Model),个体认知,(Cognition-Only Model),粒子群特性,算法介绍,每个寻优,的,问题解都被想像成一只鸟，称为,“,粒子,”,。所有粒子都在一个D维空间进行搜索。,所有的,粒子,都由一个,fitness function,确定适应值,以判断目前的位置好坏。,每一个,粒子,必须赋予记忆功能，能记住所搜寻到的最佳位置。,每一个,粒子,还有,一,个速度以决定飞行的距离和方向,。,这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。,粒子群优化算法求最优解,D维空间中，有N个粒子；,粒子i位置：,x,i,=(x,i1,x,i2,x,iD,)，将x,i,代入适应函数f(x,i,)求适应值；,粒子i速度：,v,i,=(v,i1,v,i2,v,iD,),粒子i个体经历过的最好位置：,pbest,i,=(p,i1,p,i2,p,iD,),种群所经历过的最好位置：,gbest,=(g,1,g,2,g,D,),通常，在第d（1,dD,）维的位置变化范围限定在 内，,速度变化范围限定在 内（即在迭代中若,超出了边界值，则该维的速度或位置被限制为该维最大速度或边界,位置）,粒子i的第d维速度更新公式：,粒子i的第d维位置更新公式：,第k次迭代粒子i飞行速度矢量的第d维分量,第k次迭代粒子i位置矢量的第d维分量,c1,c2加速度常数，调节学习最大步长,r1,r2两个随机函数，取值范围0，1，以增加搜索随机性,w 惯性权重，非负数，调节对解空间的搜索范围,粒子速度更新公式包含三部分：,第一部分为粒子先前的速度,第二部分为“认知”部分，表示粒子本身的思考，可理解为粒子i当前位置与自己最好位置之间的距离。,第三部分为“社会”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。,區域,最佳解,全域,最佳解,運動向量,慣性向量,Study Factor,p,g,算法流程,Initial,：,初始化粒子群体（群体规模为n），包括随机位置和速度。,Evaluation,：,根据,fitness function,，评价每个粒子的适应度。,Fin,d,the Pbest,：,对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最佳位置pbest。,Fin,d,the Gbest,：,对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。,Update the Velocity,：,根据公式,更新每,个粒子的,速度,与,位置。,如未满足结束条件，则返回步骤2,通常算法达到最大迭代次数 或者最佳适应度值的增量小于某个给定的阈值时算法停止。,粒子群优化算法流程图,开始,初始化粒子群,计算每个粒子的适应度,根据适应度更新pbest、gbest，更新粒子位置速度,结束,no,yes,达到最大迭代次数或,全局最优位置满足最小界限？,2,維簡例,Note,合理解,目前最優解,區域最佳解,全域,區域,粒子群,算法的,构成要素,-,群体大小,m,m,是一个整型参数,m,很小:,m,很大:,当群体数目增长至一定水平时，再增长将,不再有显,但收敛速度慢,著的作用,陷入局优的可能性很大,PSO的优化能力很好，,粒子群,算法的,构成要素,-,权重因子,权重因子：惯性因子 、学习因子,失去对粒子本身,的,速度的记忆,社会经验部分,前次迭代中自身的速度,自我认知部分,基本粒子群算法,粒子的速度更新主要由三部分组成：,惯性因子,粒子群,算法的,构成要素,-,权重因子,权重因子：惯性因子 、学习因子,社会经验部分,前次迭代中自身的速度,自我认知部分,粒子的速度更新主要由三部分组成：,学习因子,无私型粒子群算法,“只有社会，没有自我”,迅速丧失群体多样性，,易陷入局优而无法跳出,粒子群,算法的,构成要素,-,权重因子,权重因子：惯性因子 、学习因子,社会经验部分,前次迭代中自身的速度,自我认知部分,粒子的速度更新主要由三部分组成：,自我认知型粒子群算法,“只有自我，没有社会”,完全没有信息的社会共享，,导致算法收敛速度缓慢,学习因子,粒子群,算法的,构成要素,-,权重因子,权重因子：惯性因子 、学习因子,社会经验部分,前次迭代中自身的速度,自我认知部分,粒子的速度更新主要由三部分组成：,c,1,c,2,都不为0，,称为,完全型粒子群算法,完全型粒子群算法更容易保持收敛速度和搜索效果的均衡，是较好的选择,粒子群,算法的,构成要素,-,最大速度,但,在于维护算法的,探索能力,与,开发能力,的平衡,V,m,较大时，探索能力增强，,作用:,V,m,较小时，开发能力增强，,V,m,一般设为每维变量变化范围的1020.,但,粒子容易飞过最优解,容易陷入局部最优,粒子群,算法的,构成要素,-,邻域的拓扑结构,全局粒子群算法和局部粒子群算法,粒子群算法的邻域拓扑结构包括两种，,一种是将群体内,所有个体,都作为粒子的邻域，,另一种是只将群体中的,部分个体,作为粒子的邻域,群体历史最优位置,邻域拓扑结构,决定,由此，将粒子群算法分为,粒子群,算法的,构成要素,-,邻域的拓扑结构,全局粒子群算法,1.粒子自己历史最优值,2.粒子群体的全局最优值,局部粒子群算法,1.粒子自己历史最优值,2.,粒子邻域内粒子的最优值,邻域随迭代次数的增加线性变大，最后邻域扩展到整个,粒,子群,。,经过实践证明：全局版本的粒子群算法收敛速度快，但是容易陷入局部最优。局部版本的粒子群算法收敛速度慢，但是很难陷入局部最优。现在的粒子群算法大都在收敛速度与摆脱局部最优这两个方面下功夫。其实这两个方面是矛盾的。看如何更好的折中了。,粒子群,算法的,构成要素,-,停止准则,停止准则一般有如下两种：,最大迭代步数,可接受的满意解,粒子群,算法的,构成要素,-,粒子空间的初始化,较好地选择粒子的初始化空间，将大大缩短收,敛时间初始化空间根据具体问题的不同而不同，,也就是说，这是问题依赖的,从上面的介绍可以看到，粒子群算法与其他现代,优化方法相比的一个明显特色就是所需调整的,参数很,少,相对来说，,惯性因子,和,邻域定义,较为重要这些,为数不多的关键参数的设置却对算法的精度和效率有,着显著影响,3.,粒子群,算法示例,例,求解如下四维Rosenbrock函数的优化问题,种群大小,：,解,算法的相关设计分析如下,编码,：因为问题的维数是4，所以每个粒子的位置和,即算法中粒子的数量，取,速度均4 维的实数向量,设定粒子的,最大速度,：,初始位置：,设各粒子的初始位置 和初始速度 为：,对粒子群进行随机初始化,包括随机初始化各粒子的,位置,和,速度,初始速度：,设各粒子的初始位置 和初始速度 为：,对粒子群进行随机初始化,包括随机初始化各粒子的,位置,和,速度,初始速度：,初始位置：,计算每个粒子的适应值,按照,计算适应值,历史最优解,更新粒子的速度和位置：,取 ，,得到速度和位置的更新函数为,初始速度：,初始位置：,群体历史最优解：,个体历史最优解：,更新速度，得：,初始速度：,初始位置：,群体历史最优解：,个体历史最优解：,更新位置，得：,初始速度：,初始位置：,群体历史最优解：,个体历史最优解：,不强行拉回解空间,更新位置，得：,初始速度：,初始位置：,群体历史最优解：,个体历史最优解：,按照,计算适应值,重复上述步骤，将迭代进行下去,按照,计算适应值,历史最优解,从上述结果，可以看出，经过10000次迭代，,粒子群算法得到了比较好的适应值.,4.,粒子群,算法,流程,第2步 计算每个粒子的适应值,第1步 在初始化范围内，对粒子群进行随机初始化，,第5步 更新粒子的速度和位置，公式如下,第3步 更新粒子个体的历史最优位置,第6步 若未达到终止条件，则转第2步,包括随机位置和速度,第4步 更新粒子群体的历史最优位置,惯性权重,1998年，,Shi,和,Eberhart,引入了惯性权重,w,，并提出动态调整惯性权重以平衡收敛的全局性和收敛速度，该算法被称为标准,PSO,算法,惯性权重w描述粒子上一代速度对当前代速度的影响。w值较大，全局寻优能力强，局部寻优能力弱；反之，则局部寻优能力强。当问题空间较大时，为了在搜索速度和搜索精度之间达到平衡，通常做法是使算法在前期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度。所以w不宜为一个固定的常数。,线性递减权值,wmax最大惯性权重，wmin最小惯性权重，run当前迭代次数，run,max,为算法迭代总次数,较大的,w,有较好的全局收敛能力，较小的,w,则有较强的局部收敛能力。因此，随着迭代次数的增加，惯性权重,w,应不断减少，从而使得粒子群算法在初期具有较强的全局收敛能力，而晚期具有较强的局部收敛能力。,1999年，,Clerc,引入收缩因子以保证算法的收敛性。,速度更新公式为,其中，收缩因子K为受1 2 限制的w。1 2是需要预先设定的模,型,参数,收缩因子法控制系统行为最终收敛，且可以有效搜索不同区域，该法,能得到较高质量的解。,收缩因子法,PSO应用,PSO存在的问题（1）,PSO存在的问题（2）,PSO研究热点,PSO研究热点,PSO研究热点,Thank you!,
展开阅读全文