粒子群最佳化演算法 Particle Swarm Optimization (PSO)绪论绪论n粒子群最佳化算法 (简称为PSO)，是一种以群体为基础 (Population-based) 的最佳化搜寻技术n由 James Kennedy 和 Russell Eberhart 两位学者于1995年时所提出Bionic Computing Lab, 2005BBBionic ionic CCComputingomputing12/21/0512/21/05DM DM coursecourse粒子群最佳化Particle Swarms OptimizationParticle Swarms Optimization Russ EberhartRuss Eberhart整合群体行为、人类决策与鸟群行为发展而成称为整合群体行为、人类决策与鸟群行为发展而成称为整合群体行为、人类决策与鸟群行为发展而成称为整合群体行为、人类决策与鸟群行为发展而成称为粒子群算法。粒子群算法。粒子群算法。粒子群算法。【Eberhart, Kennedy, 1995Eberhart, Kennedy, 1995】绪论绪论nPSO是模拟鸟群觅食的社会行为所衍生n从1995年以来陆续有许多研究学者投入研究起源起源n提出算法的两位学者，由观察鸟群觅食的社会行为得到启发n鸟群于食物存在的空间中飞行觅食，一开始并不知道最佳的觅食点在哪个位置n每只鸟可能会凭借着自己的经验或是直觉，飞往它所觉得较佳的地点来搜寻食物起源起源n当其它鸟发现了更佳的觅食地点时，鸟群间会有某种类似广播的沟通行为，渐渐的将其它鸟群引领至较佳的地点。n这样的觅食行为是利用社会中所存在的互相影响的概念，来引领所有个体朝向最佳解位置。Bionic Computing Lab, 2005BBBionic ionic CCComputingomputing12/21/0512/21/05DM DM coursecourse鸟群(鱼群)行为Particle Swarms OptimizationParticle Swarms Optimization 师法大自然师法大自然Bionic Computing Lab, 2005BBBionic ionic CCComputingomputing12/21/0512/21/05DM DM coursecourse鸟群(鱼群)行为Particle Swarms OptimizationParticle Swarms Optimization 粒子群特性粒子群特性起源起源n粒子群的概念视为一个简单的社会系统n每只个体被视为问题的一个解答，称之为粒子(Particle)n每个粒子经由适应函数的衡量而具有一个适应値區域最佳解全域最佳解運動向量慣性向量Bionic Computing Lab, 2005BBBionic ionic CCComputingomputing12/21/0512/21/05DM DM coursecourseParticle Swarms OptimizationParticle Swarms Optimization crazinesscraziness动能向量概论动能向量概论PSO 向量示意图目前目前最佳解最佳解區域區域最佳解最佳解W*Rand()*( )*Rand()*( )=+2 2维简例维简例Bionic Computing Lab, 2005BBBionic ionic CCComputingomputing12/21/0512/21/05DM DM coursecourse粒子群最佳化Particle Swarms OptimizationParticle Swarms Optimization NoteNote合理解合理解目前最优解目前最优解区域最佳解区域最佳解全局全局区域区域符号说明npbest 代表粒子本身到目前为止所达到最佳解nPi 代表粒子最佳解的位置ngbest 即代表全体群体到目前为止最佳解nPg 代表全体最佳解的位置速度与位置速度：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原来位置 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. 依照下面的两个式子来改变粒子的速度和位置:6. 回到步骤2重复执行这些步骤，直到停止准则条件符合为止，通常停止准则会被设定为到达最大执行次数，或是达到所期望的适应值时。RastriginRastriginBionic Computing Lab, 2005BBBionic ionic CCComputingomputingChung Yuan Christian University12/21/0512/21/05DM DM coursecourse相关论文研讨Particle Swarms OptimizationParticle Swarms Optimization Performance testPerformance testRosenbrockRosenbrock粒子群优化算法的分析与改进粒子群优化算法的分析与改进粒子群优化算法的分析与改进粒子群优化算法的分析与改进Rosenbrock 函数Rastrigin 函数Schwefels function 搜尋過程最初狀態搜尋過程經過5代搜尋過程經過10代搜尋過程經過15代搜尋過程經過20代搜尋過程經過25代搜尋過程經過100代搜尋過程經過500代搜尋結果移動次數搜尋結果0416.2455995515.74879610759.40400615793.73201920834.813763100837.9115355000837.965771最佳解837.9658PSO 特性nPSO 算法类似 GA 算法n粒子拥有记忆性n粒子的特点为位置与速度n广域搜寻和区域搜寻n迭代演化后搜索到空间中的最佳解优点nPSO吸引人之处，在于只有少数的参数需要调整;n并且能加快速度收敛至最佳解;n可以被应用来解决大多数的最佳化问题。PSO与GA比较同异PSO1)由一组随机解开始2)经过不断搜寻，找出最佳解None , so easyGA1)Crossover2)MutationSo complex !PSO与GA比较-相同n相同的算法流程1.群体随机初始化2.对 群 体 内 每 一 个 体 计 算 适 应 值(FitnessValue)适应值与最佳解的距离直接有关3.群体根据适应值进行复制4.如果满足终止条件就停止，否则回到步骤2PSO与GA比较-相异nPSO没有遗传操作-交换（Crossover）、突变（Mutation）而是根据自己的速度来决定搜寻nPSO有记忆性PSO有广泛的应用领域n例如:系统设计、多目标最佳化、分类、型样识别、生物系统仿真、排程、游戏、机器人应用、决策制定、网络安全及路由选择、神经网络训练、仿真和识别等n而其相关的实例则包含了仿真控制器设计、工作排程、影像分割、语音识别、时间频率分析、烧烫伤诊断、手势姿势识别和自动目标侦测等问题上附录nDonCalculate fitness of particlenUpdate pbest if the current fitness is better than pbestnDetermine nbest for each particle: choose the particle with the best fitness value of all the neighbors as the nbestnFor each particlenCalculate particle velocity according to (1)nUpdate particle position according to (2)nWhile maximum iterations or minimum ncriteria is not attainedPSO 算法Step1:初始化 包括参数设定及随机初始化粒子的位置和速度。Setp2:计算每颗粒子的适应值。Step3: 每颗粒子与该粒子所经历的最佳评估值比较，若比粒子的最佳评估值佳，则以新的位置及评估值取代粒子的最佳解。Step4: 每颗粒子的最佳评估值与群体的最佳值比较，若粒子的最佳评估值比群体的最佳评估值佳，则以粒子的最佳解取代所有粒子的最佳解。Step5:根据公式（1）和（2）改变粒子的速度和位置；Step6:如未达到结束条件 则回到步骤2，若达到满足结束条件则输出最佳解。