《《粒子群算法》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《粒子群算法》PPT课件.ppt（38页珍藏版）》请在三一办公上搜索。
1、粒子群最佳化演算法 Particle Swarm Optimization(PSO),绪论,粒子群最佳化算法(简称为PSO)，是一种以群体为基础(Population-based)的最佳化搜寻技术由 James Kennedy 和 Russell Eberhart 两位学者于1995年时所提出,Russ Eberhart,整合群体行为、人类决策与鸟群行为发展而成称为粒子群算法。【Eberhart,Kennedy,1995】,绪论,PSO是模拟鸟群觅食的社会行为所衍生从1995年以来陆续有许多研究学者投入研究,起源,提出算法的两位学者，由观察鸟群觅食的社会行为得到启发鸟群于食物存在的空间中飞行觅
2、食，一开始并不知道最佳的觅食点在哪个位置每只鸟可能会凭借着自己的经验或是直觉，飞往它所觉得较佳的地点来搜寻食物,起源,当其它鸟发现了更佳的觅食地点时，鸟群间会有某种类似广播的沟通行为，渐渐的将其它鸟群引领至较佳的地点。这样的觅食行为是利用社会中所存在的互相影响的概念，来引领所有个体朝向最佳解位置。,师法大自然,粒子群特性,起源,粒子群的概念视为一个简单的社会系统每只个体被视为问题的一个解答，称之为粒子(Particle)每个粒子经由适应函数的衡量而具有一个适应値,區域最佳解,全域最佳解,運動向量,慣性向量,动能向量概论,PSO 向量示意图,目前最佳解,區域最佳解,W*,*Rand()*(),*
3、Rand()*(),=,+,+,2维简例,Note,合理解,目前最优解,区域最佳解,全局,区域,符号说明,pbest 代表粒子本身到目前为止所达到最佳解Pi 代表粒子最佳解的位置gbest 即代表全体群体到目前为止最佳解Pg 代表全体最佳解的位置,速度与位置,速度：vid(t+1)=wxvid(t)+c1xrand()xpid(t)-xid(t)(t)+c2xrand()xPgd(t)-xid(t)(t),v-速度w-惯性权重C-学习因子pid-个体最佳解Pgd-全局最佳解,原来速度 vid,过去自身经验,同伴飞行经验,运动向量,目前的个体最佳解pbest,目前的全局最佳解gbest,原来位置
4、 xid(t),新位置 xid(t+1),原来速度 vid(t),新速度 vid(t+1),位置：xid(t+1)=xid(t)+vid(t+1),PSO 流程,以任意的位置和速度来初始化粒子,评估各个粒子的适应值,更新 pbest 与 gbest 值,更新各个粒子位置及速度,开始,满足终止条件,结束,否,是,PSO 算法,1.以任意的位置和速度来初始化粒子2.利用适应函数计算每个粒子的适应値3.将粒子的适应值和pbest 值作比较，假如优于pbest 值，则更新pbest 值及其位置4.将粒子的适应值和gbest 值作比较，如果优于gbest 值，则更新gbest 值及其位置5.依照下面的两
5、个式子来改变粒子的速度和位置:6.回到步骤2重复执行这些步骤，直到停止准则条件符合为止，通常停止准则会被设定为到达最大执行次数，或是达到所期望的适应值时。,Rastrigin,Performance test,Rosenbrock,粒子群优化算法的分析与改进,Rosenbrock 函数,Rastrigin 函数,Schwefels function,搜尋過程最初狀態,搜尋過程經過5代,搜尋過程經過10代,搜尋過程經過15代,搜尋過程經過20代,搜尋過程經過25代,搜尋過程經過100代,搜尋過程經過500代,搜尋結果,PSO 特性,PSO 算法类似 GA 算法粒子拥有记忆性粒子的特点为位置与速度
6、广域搜寻和区域搜寻迭代演化后搜索到空间中的最佳解,优点,PSO吸引人之处，在于只有少数的参数需要调整;并且能加快速度收敛至最佳解;可以被应用来解决大多数的最佳化问题。,PSO与GA比较,PSO与GA比较-相同,相同的算法流程1.群体随机初始化2.对群体内每一个体计算适应值(FitnessValue)适应值与最佳解的距离直接有关3.群体根据适应值进行复制4.如果满足终止条件就停止，否则回到步骤2,PSO与GA比较-相异,PSO没有遗传操作-交换（Crossover）、突变（Mutation）而是根据自己的速度来决定搜寻PSO有记忆性,PSO有广泛的应用领域,例如:系统设计、多目标最佳化、分类、型
7、样识别、生物系统仿真、排程、游戏、机器人应用、决策制定、网络安全及路由选择、神经网络训练、仿真和识别等而其相关的实例则包含了仿真控制器设计、工作排程、影像分割、语音识别、时间频率分析、烧烫伤诊断、手势姿势识别和自动目标侦测等问题上,附录,DoCalculate fitness of particleUpdate pbest if the current fitness is better than pbestDetermine nbest for each particle:choose the particle with the best fitness value of all the n
8、eighbors as the nbestFor each particleCalculate particle velocity according to(1)Update particle position according to(2)While maximum iterations or minimum criteria is not attained,PSO 算法,Step1:初始化 包括参数设定及随机初始化粒子的位置和速度。Setp2:计算每颗粒子的适应值。Step3:每颗粒子与该粒子所经历的最佳评估值比较，若比粒子的最佳评估值佳，则以新的位置及评估值取代粒子的最佳解。Step4:每颗粒子的最佳评估值与群体的最佳值比较，若粒子的最佳评估值比群体的最佳评估值佳，则以粒子的最佳解取代所有粒子的最佳解。Step5:根据公式（1）和（2）改变粒子的速度和位置；Step6:如未达到结束条件 则回到步骤2，若达到满足结束条件则输出最佳解。,
