粒子群优化算法PSOppt课件.ppt
《粒子群优化算法PSOppt课件.ppt》由会员分享,可在线阅读,更多相关《粒子群优化算法PSOppt课件.ppt(35页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、粒子群优化算法主要内容v1.产生背景v2.算法介绍v3.参数设置v4.在车辆优化调度中的应用粒子群算法的产生背景v粒子群算法源于复杂适应系统(Complex Adaptive System,CAS)。CAS理论于1994年正式提出,CAS中的成员称为主体。比如研究鸟群系统,每个鸟在这个系统中就称为主体。主体有适应性,它能够与环境及其他的主体进行交流,并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括:新层次的产生(小鸟的出生);分化和多样性的出现(鸟群中的鸟分成许多小的群);新的主题的出现(鸟寻找食物过程中,不断发现新的食物)。 CAS的的4个基本特点个基本特
2、点(这些特点是粒子群算法发展变化的依据):v 首先,主体是主动的、活动的。v 其次,主体与环境及其他主体是相互影响、相互作用的,这种影响是系统发展变化的主要动力。v 再次,环境的影响是宏观的,主体之间的影响是微观的,宏观与微观要有机结合。v 最后,这种建模方法还引进了随机因素的作用,使它具有更强的描述和表达能力。 粒子群算法就是对一个CAS鸟群社会系统的研究得出的。 粒子群算法(particle swarm optimization,PSO)由Kennedy和Eberhart在1995年提出,该算法模拟鸟集群飞行觅食的行为,鸟之间通过集体的协作使群体达到最优目的,是一种基于Swarm Inte
3、lligence的优化方法。同遗传算法类似,也是一种基于群体叠代的,但并没有遗传算法用的交叉以及变异,而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景,既适合科学研究,又特别适合工程应用,并且没有许多参数需要调整。 PSO算法简介 Bionic Computing Lab, 2005ionic omputing粒子群最佳化v原理我们可以设想这样一个场景,一群鸟在某区域随机搜寻食物。该区域只有一块食物。所有的鸟都不知道食物在哪里,但它们知道目前距离食物还有多远,那么找到食物的最佳策略是什么呢?最简单的方法就是找寻距离食物最近的鸟周围区域及根据自己飞行的经
4、验判断食物的所在。Bionic Computing Lab, 2005ionic omputingChung Yuan Christian University鳥群(魚群)行為算法介绍 v每个寻优的问题解都被想像成一只鸟,称为“粒子”。所有粒子都在一个D维空间进行搜索。v所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。v每一个粒子必须赋予记忆功能,能记住所搜寻到的最佳位置。v每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。 粒子群优化算法求最优解粒子群优化算法求最优解 D维空间中,有N个粒子; 粒子i
5、位置:x xi i=(xi1,xi2,xiD),将xi代入适应函数f(xi)求适应值; 粒子i速度:v vi i=(vi1,vi2,viD) 粒子i个体经历过的最好位置:pbestpbesti i=(pi1,pi2,piD) 种群所经历过的最好位置:gbestgbest=(g1,g2,gD)通常,在第d(1dD)维的位置变化范围限定在 内, 速度变化范围限定在 内(即在迭代中若 超出了边界值,则该维的速度或位置被限制为该维最大速度或边界 位置) min,max,X,ddX,max,-V,max ddVidvid、xv粒子i的第d维速度更新公式: v 粒子i的第d维位置更新公式: 第k次迭代粒子
6、i飞行速度矢量的第d维分量 第k次迭代粒子i位置矢量的第d维分量 c1,c2加速度常数,调节学习最大步长 r1,r2两个随机函数,取值范围0,1,以增加搜索随机性 w 惯性权重,非负数,调节对解空间的搜索范围kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx11kkkidididxxvkidvkidxv粒子速度更新公式包含三部分: 第一部分为粒子先前的速度 第二部分为“认知”部分,表示粒子本身的思考,可理解为粒子i当前位置与自己最好位置之间的距离。 第三部分为“社会”部分,表示粒子间的信息共享与合作,可理解为粒子i当前位置与群体最好位置
7、之间的距离。kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx1111122V = V+C *r*(Pbest -X)+C *r *(gbest -X)kkkkiiiii区域最佳解全域最佳解运动向量惯性向量Bionic Computing Lab, 2005ionic omputingChung Yuan Christian University11X =X+Vkkkiii12NX = X ,X ,.,Xiiii12NV = V ,V ,.,ViiiiBionic Computing Lab, 2005ionic omputingChu
8、ng Yuan Christian University粒子群最佳化算法流程1.Initial:初始化粒子群体(群体规模为n),包括随机位置和速度。2.Evaluation:根据fitness function ,评价每个粒子的适应度。3.Find the Pbest: 对每个粒子,将其当前适应值与其个体历史最佳位置(pbest)对应的适应值做比较,如果当前的适应值更高,则将用当前位置更新历史最佳位置pbest。4.Find the Gbest:对每个粒子,将其当前适应值与全局最佳位置(gbest)对应的适应值做比较,如果当前的适应值更高,则将用当前粒子的位置更新全局最佳位置gbest。5.U
9、pdate the Velocity:根据公式更新每个粒子的速度与位置。6.如未满足结束条件,则返回步骤2 通常算法达到最大迭代次数 或者最佳适应度值的增量小于某个给定的阈值时算法停止。maxG粒子群优化算法流程图粒子群优化算法流程图 开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest,更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限?算法参数设置v1.群体规模 一般,待求解问题维数越高,所需的群体规模也越大,通常群体规模是问题维数的1.5倍左右。v2.最大速度 决定当前位置与最优位置之间区域的分辨率。如果太高,粒子可能会飞过好解;如果太小,粒子不
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 粒子 优化 算法 PSOppt 课件
限制150内