《粒子群优化算法》ppt课件-文库吧

【正文】

主体进行交流 ，在这种交流的过程中 “学习 ”或 “积累经验 ”，并且根据学到的经验改变自身的结构和行为方式。整个系统的演变或进化，包括新层次的产生，分化和多样性的出现，新的、聚合而成的、更大的主体的出现等等，都是在这个基础上出现的。 复杂适应系统（ CAS）续CAS的四个基本特点：v 首先， 主体 (Adaptive Agent)是主动的、活的实体； v 其次， 个体与环境 (包括个体之间 )的相互影响，相互作用，是系统演变和进化的主要动力 ；v 再次， 这种方法不象许多其他的方法那样，把宏观和微观截然分开，而是把它们有机地联系起来；v 最后， 这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。 PSO产生背景之二 :人工生命 人工生命 “是来研究具有某些生命基本特征的人工系统。人工生命包括两方面的内容： ① 研究如何利用计算技术研究生物现象； ② 研究如何利用生物技术研究计算问题 (Nature Computation)。 我们现在关注的是第二部分的内容。现在已经有很多源于生物现象的计算技巧，例如 , 人工神经网络是简化的大脑模型 . 遗传算法是模拟基因进化过程的。现在我们讨论另一种生物系统：社会系统，更确切地说，是由简单个体组成的群落与环境以及个体之间的互动行为，也可称做 群智能 。基本 PSO算法 粒子群优化算法源于 1987年 Reynolds对鸟群社会系统 boids的仿真研究， boids是一个 CAS。在boids中，一群鸟在空中飞行，每个鸟遵守以下三条规则：1）避免与相邻的鸟发生碰撞冲突；2）尽量与自己周围的鸟在速度上保持协调和一致；3）尽量试图向自己所认为的群体中靠近。 仅通过使用这三条规则， boids系统就出现非常逼真的群体聚集行为，鸟成群地在空中飞行，当遇到障碍时它们会分开绕行而过，随后又会重新形成群体。 基本 PSO算法（续） Reynolds仅仅将其作为 CAS的一个实例作仿真研究，而并未将它用于优化计算中 。 Kennedy和 Eberhart在中加入了一个特定点，定义为食物，鸟根据周围鸟的觅食行为来寻找食物。他们的初衷是希望通过这种模型来模拟鸟群寻找食源的现象，然而实验结果却揭示这个仿真模型中蕴涵着很强的优化能力，尤其是在多维空间寻优中。 基本 PSO算法 (续 ) PSO中，每个优化问题的解都是搜索空间中的一只鸟 。称 之为 “粒子 (Particle)”。所有的粒子都有一个由被优化的函数决定的适 应值， 每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索 . PSO 初始化为一群随机 粒子。 然后通过叠代找到最优解。在每一次叠代中，粒子通过跟踪两个 极值 来更新自己。第一个就是粒子本身所找到的最优解。这个解叫做个体极值 pBest. 另一个极值是整个种群目前找到的最优解。这个极值是全局极值 gBest。另外 ,也可以不用整个种群而只是用其中一部 分的邻居。基本 PSO算法 (续 ) PSO算法数学表示如下： 设搜索空间为 D维，总粒子数为 n。第 i个粒子位置表示为向量 Xi=( xi1, xi2,…, x iD )；第 i个粒子 “飞行 ”历史中的过去最优位置（即该位置对应解最优）为 Pi=( pi1,pi2,…,p iD )，其中第 g个粒子的过去最优位置 Pg为所有 Pi ( i=1, …,n )中的最优；第 i个粒子的位置变化率（速度）为向量 Vi=(vi1, vi2,…, v iD)。每个粒子的位置按如下公式进行变化（ “飞行 ”）：基本 PSO算法 (续 )（ 1）（ 2）其中， C1,C2为 正常数，称 为 加速因子； rand( )为 [0， 1]之 间的随机数； w称 惯 性因子， w较 大适于 对 解空 间进 行大范 围 探查 (exploration)， w较 小适于 进 行小范 围 开挖 (exploitation)。第 d（ 1≤d≤D） 维 的位置 变 化范 围为 [XMAXd , XMAXd]，速度变 化范 围为 [VMAXd , VMAXd]，迭代中若位置和速度超 过边界范 围则 取 边 界 值 。 基本 PSO算法 (续 ) 粒子群初始位置和速度随机产生，然后按公式 (1)(2)进行迭代，直至找到满意的解。目前，常用的粒子群算法将全体粒子群(Global)分成若干个有部分粒子重叠的相邻子群，每个粒子根据子群 (Local)内历史最优 Pl调整位置，即公式 (2)中 Pgd换为 Pld。 PSO与 EC的异同 首先， PSO和 EC所模拟的自然随机系统不一样。EC是模拟生物系统进化过程，其最基本单位是基因，它在生物体的每一代之间传播；而 PSO模拟的是社会系统的变化，其最基本单位是 “敏因 ”（Meme），这一词由 Dawkin在 《 The Selfish Gene》 一书中提出，它是指思想文化传播中的基本单位，个体在社会中会根据环境来改变自身的思想， Meme的传播途径是在个体与个体之间，在实际人类社会中它还可以在人脑与书本之间、人脑与计算机、计算机与计算机之间传播。 PSO与 EC的异同（续） 其次， EC中强调 “适者生存 ”，不好的个体在竞争中被淘汰； PSO强调 “协同合作 ”，不好的个体通过学习向好的方向转变，不好的个体被保留还可以增强群体的多样性。 EC中最好的个体通过产生更多的后代来传播自己的基因，而 PSO中的最佳个体通过吸引其它个体向它靠近来传播自己的敏因。PSO与 EC的异同（续） 再次， EC中的上一代到下一代转移概率只与上一代的状态相关，而与历史无关，它的个体只包含当前信息，其群体的信息变化过程是一个 Markov链过程；而 PSO中的个体除了有着位置和速度外，还有着过去的历史信息（ pBest、 gBest），也就是具有记忆能力，上一代到下一代转移概率不仅与上一代的状态相关，而且与过去的历史相关，如果仅从群体的位置及速度信息来看，群体的信息变化过程不是一个 Markov链过程。 PSO与 EC的异同（续） 最后， EC的迭代由选择、变异和交叉重组操作组成，而 PSO的迭代中的操作是 “飞行 ”。在某种程度上看， PSO的操作中隐含了选择、变异和交叉重组操作， gBest和pBest的更新可以类似一种弱选择；而粒子位置更新则类似于 3个父代： Xi、 gBest和pBest的之间重组，其中还包含了变异的成分。 PSO中所隐含的变异是有偏好的，而并非通常的完全随机变异，这与最近对实际生物系统变异行为的新研究成果相符。PSO与 EC的异同（续） EC和 PSO所分别模拟的两个伟大的自然随机系统： Evolution和 Mind之间存在着显著的差异，尽管它们都是基于群体的，都是由其中的随机成分带来创新，但其本质是不同的，因此不能将 PSO简单地归类于 EC中。 Particle Swarm研究热点 IEEE TRANSACTION ON EVOLUTIONARY COMPUTION于 2022年出版了第 3卷： SPECIAL ISSUE ON PSO。 Russell , Yuhui Shi在卷首语中指出了当前 PSO研究的几个主要方向及热点：1。算法分析；2。粒子群拓扑结构；3。参数选择与优化；4。与其他演化计算的融合；5。应用。粒子运动轨迹的分析 为了便于分析和表达，首先将问题空间简化为一维的，分别用 、 表示式（ ）中的 和 ，仅研究粒子群中的某一个粒子 i的运动过程，并暂时先假设 pBest、 gBest在粒子 i运动过程中不变，于是可得粒子 i运动的状态方程组（ ）和（ ），这将是本节分析和讨论的对象。 （ ） （ ） 粒子运动轨迹的分析（续） 将式（ ）和（ ）递推可得到： （ ） （ ） 由上可知，粒子的速度和位置变化过程均是二阶差分方程，本节将对它们做分析。粒子运动轨迹的分析（续） 对（ ）做 Z变换，由 Routh判据，二阶线性系统稳定的充分必要条件是特征方程各项系数均为正值，于是可得到差分方程（ ）稳定的条件为（取某一个条件等号时系统系统等幅周期振荡，速度不趋于无穷大，此处可认为临界稳定） （ ）粒子运动轨迹的分析（续） 当满足（ ）中条件均取严格不等号时，由 Z变换的终值定理可得： （ ） 也就是在不考虑随机量且 pBest、 gBest位置不变的假设下，当满足（ ）中严格不等于条件时，单个粒子的速度将趋向 0。 粒子运动轨迹的分析（续） 同理，对（ ）做 Z变换，由 Routh判据，可得到差分方程（ ）稳定的条件为： （ ）粒子运动轨迹的分析（续） 当满足条件（ ），由 Z变换的终值定理可得： （ ） 这说明，在不考虑随机量且 pBest、 gBest位置不变的假设下，当满足式（ ）中条件时，单个粒子的位置将趋向 粒子运动轨迹的分析（续） 本文以上分析方法所得到的结果（ ）式与文献[9]所得的最终结果（ ）式不一致，图 两种不同约束条件所得到的范围，细斜线左上方的灰色区域为本文所得到的单个粒子可收敛区域，而文献 [9]中（ ）式所对应的仅是粗实线上所有的点，显然本文约束条件（ ）式所得的范围比文献 [9]的范围大很多，并包含了文献 [9]的范围，而文献 [9]约束条件（ ）式的表达要比式（）复杂些。粒子运动轨迹的分析（续）图 两种不同约束条件得到的范围 粒子运动轨迹的分析（续） pBest、 gBest分别代表粒子的 “自身经验”和 “社会经验 ”，粒子通过它们和群体实现协同合作，因此其变化是不可忽视的。这个系统的输入的变化过程是未知的，而且与粒子本身的运动过程还存在着弱反馈关系，那么式（ ）所给出的粒子最终位置是否仅是一种理想状态的结果呢？ 当 pBest、 gBest发生变化时，粒子的位置是否能跟踪上是不肯定的。粒子运动轨迹的分析（续） pBest和 gBest的变化过程符合如下式（ ）（ ）的规律： （ ） （ ） 都是递减的，而且当优化问题的值空间有限且存在全局最优值时候，它们存在下界。 粒子运动轨迹的分析（续） 若 f(x)不是 （ NFL定理）中所说的欺骗函数和随机函数，而是第三类函数，而且 f(pi(t)),f(Pg(t))的变化 pi(t