来源背景
为了说明粒子群优化算法的发展和形成背景,首先介绍一下早期的简单模型,即Boid(Bird-oid)模型。这个模型是为了模拟鸟群的行为而设计的,它也是粒子群优化算法的直接来源。
一个最简单的模型是这样的:每一个鸟的个体用直角坐标系上的点表示,随机地给它们赋一个初速度和初位置,程序运行的每一步都按照“最近邻速度匹配”规则,很快就会使得所有点的速度变得一样。因为这个模拟太简单而且远离真实情况,于是在速度项中增加了一个随机变量,即在迭代的每一步,除了满足“最近邻速度匹配”之外,每一步速度还要添加一个随机变化的量,这样使得整个模拟看起来更为真实。
Heppner设计了一个“谷地模型”来模拟鸟群的觅食行为。假设在平面上存在一个“谷地”,即食物所在地,鸟群开始时随机地分散在平面上,为了寻觅食物所在地,它们按照如下规则运动:
首先假设谷地的位置坐标为,单个鸟的位置和速度坐标分别为和,用当前位置到谷地的距离:
来衡量当前位置和速度的“好坏程度”,离谷地的距离越近,则越“好”,反之越“坏”。假设每一个鸟具有记忆能力,能够记住曾经达到的最好位置,记作pBest,并记a为系统规定的速度调节常数,rand为一个[0,1]间的随机数,设定速度项按照下述规则变化:
然后假设群体之间可以以某种方式通讯,每个个体能够知道并记住到当前为止整个群体的最好位置,记为gBest,记b为系统规定的速度调节常数,Rand为一个[0,1]间的随机数,则速度项在经过以上调整后,还必须按照下述规则变化:
在计算机上模拟的结果显示:当a/b较大时,所有的个体很快地聚集到“谷地”上;反之,粒子缓慢地摇摆着聚集到“谷地”的四周。通过这个简单的模拟,发现群体能很快地找到一个简单函数(2-1)的最优点。受该模型启发,Kennedy和Eberhart设计出了一种演化优化算法,并通过不断的试验和试错,最后将此算法的基本型固定为:
其中符号的意义同上。研究者认为每个个体被抽象为没有质量和体积,而仅仅具有速度和位置的微粒,故将此方法称为“粒子群”优化算法。
据此,可对粒子群算法小结如下:粒子群算法是一种基于种群的搜索过程,其中每个个体称作微粒,定义为在D维搜索空间中待优化问题的潜在解,保存有其历史最优位置和所有粒子的最优位置的记忆,以及速度。在每一演化代,微粒的信息被组合起来调整速度关于每一维上的分量,继而被用来计算新的微粒位置。微粒在多维搜索空间中不断改变它们的状态,直到到达平衡或最优状态,或者超过了计算限制为止。
问题空间的不同维度之间唯一的联系是通过目标函数引入的。很多经验证据已经显示该算法是一个非常有效的优化工具。微粒群优化算法的流程图见图2-1。
以下给出微粒群算法的比较完整的形式化表述。在连续空间坐标系中,微粒群算法的数学描述如下:设微粒群体规模为N,其中每个微粒在D维空间中的坐标位置向量表示为,速度向量表示为,微粒个体最优位置(即该微粒经历过的最优位置)记为,群体最优位置(即该微粒群中任意个体经历过的最优位置)记为。不失一般性,以最小化问题为例,在最初版本的微粒群算法中,个体最优位置的迭代公式为:
群体最优位置为个体最优位置中最好的位置。速度和位置迭代公式分别为:
由于初始版本在优化问题中应用时效果并不太好,所以初始算法提出不久之后就出现了一种改进算法,在速度迭代公式中引入了惯性权重ω,速度迭代公式变为:
虽然该改进算法与初始版本相比复杂程度并没有太大的增加,但是性能却有了很大的提升,因而被广泛使用。一般的,将该改进算法称为标准微粒群算法,而将初始版本的算法称为原始微粒群算法。
通过分析PSO算法的收敛行为,Clerc介绍了一种带收缩因子的PSO算法变种,收缩因子保证了收敛性并提高了收敛速度。此时的速度迭代公式为:
显然,迭代公式(2-7)和(2-8)并无本质区别,只要适当选取参数,二者完全相同。
微粒群算法有两种版本,分别称为全局版本和局部版本。在全局版本中,微粒跟踪的两个极值为自身最优位置pBest和种群最优位置gBest。对应的,在局部版本中,微粒除了追随自身最优位置pBest之外,不跟踪种群最优位置gBest,而是跟踪拓扑邻域中的所有微粒的最优位置nBest。对于局部版本,速度更新公式(2-7)变为:
其中为局部邻域中的最优位置。
每一代中任意微粒迭代的过程见图2-2所示。从社会学的角度来看速度迭代公式,其中第一部分为微粒先前速度的影响,表示微粒对当前自身运动状态的信任,依据自身的速度进行惯性运动,因此参数ω称为惯性权重(Inertia Weight);第二部分取决于微粒当前位置与自身最优位置之间的距离,为“认知(Cognition)”部分,表示微粒本身的思考,即微粒的运动来源于自己经验的部分,因此参数c1称为认知学习因子(也可称为认知加速因子);第三部分取决于微粒当前位置与群体中全局(或局部)最优位置之间的距离,为“社会(Social)”部分,表示微粒间的信息共享与相互合作,即微粒的运动来源于群体中其他微粒经验的部分,它通过认知模拟了较好同伴的运动,因此参数c2称为社会学习因子(也可称为社会加速因子)。
自从PSO算法被提出以来,由于它直观的背景,简单而容易实现的特点,以及对于不同类型函数广泛的适应性,逐渐得到研究者的注意。十余年来,PSO算法的理论与应用研究都取得了很大的进展,对于算法的原理已经有了初步的了解,算法的应用也已经在不同学科中得以实现。
PSO算法是一种随机的、并行的优化算法。它的优点是:不要求被优化函数具有可微、可导、连续等性质,收敛速度较快,算法简单,容易编程实现。然而,PSO算法的缺点在于:(1)对于有多个局部极值点的函数,容易陷入到局部极值点中,得不到正确的结果。造成这种现象的原因有两种,其一是由于待优化函数的性质;其二是由于微粒群算法中微粒的多样性迅速消失,造成早熟收敛。这两个因素通常密不可分地纠缠在一起。(2)由于缺乏精密搜索方法的配合,PSO算法往往不能得到精确的结果。造成这种问题的原因是PSO算法并没有很充分地利用计算过程中获得的信息,在每一步迭代中,仅仅利用了群体最优和个体最优的信息。(3)PSO算法虽然提供了全局搜索的可能,但是并不能保证收敛到全局最优点上。(4)PSO算法是一种启发式的仿生优化算法,当前还没有严格的理论基础,仅仅是通过对某种群体搜索现象的简化模拟而设计的,但并没有从原理上说明这种算法为什么有效,以及它适用的范围。因此,PSO算法一般适用于一类高维的、存在多个局部极值点而并不需要得到很高精度解的优化问题。
当前针对PSO算法开展的研究工作种类繁多,经归纳整理分为如下八个大类:(1)对PSO算法进行理论分析,试图理解其工作机理;(2)改变PSO算法的结构,试图获得性能更好的算法;(3)研究各种参数配置对PSO算法的影响;(4)研究各种拓扑结构对PSO算法的影响;(5)研究离散版本的PSO算法;(6)研究PSO算法的并行算法;(7)利用PSO算法对多种情况下的优化问题进行求解;(8)将PSO算法应用到各个不同的工程领域。以下从这八大类别着手,对PSO算法的研究现状作一梳理。由于文献太多,无法面面俱到,仅捡有代表性的加以综述。
简介概述
PSO
一是指工艺认证(Process Sign-Off),此为客户对供应商/代工厂进行的生产工艺流程的审核;
二是指微粒群优化算法。
工艺认证
英文名:Process Sign-Off
此为客户对供应商/代工厂进行的生产工艺流程的审核, 旨在确定客户对供应商/代工厂的要求,细化为证实和保证满足客户的质量系统要求所应具备的能力。
在产品或系统的有效期内任何产品或工艺需要更改,必须通过客户产品团队的评审以确定在风险值的基础上是否需要重新进行PSO认证。
PSO目的:在于验证供应商工艺能力,是验证供应商质量策划过程是否成功及在批量生产中是否具备批量生产合格产品的生产工艺的一种方法。
PSO是什么:PSO是系统和连贯地对供应商策划和实际实施的最高标定生产节拍下的生产工艺进行审核,包括人员、设施、设备、材料、方法、程序、软件水平和工装。客户的验证方法能确保供应商系统可接收并能生产出高质量的产品。
首先,文件需确保操作的方法都已记录并可供所有的员工参考。在培训新员工时,还可帮助有经验的员工解决一些不寻常的情况或变化。
其次,应亲临现场获得第一手资料。所以,作为PSO工作的一部分就是审核者亲临生产现场,至少目睹使用生产正式工装进行一批产品的生产。生产的节拍和质量必须满足客户的要求。
第三,对生产的产品进行测量和分析,亲临现场能看到生产过程中出现的特殊问题和生产效率的情况,收集数据并进行分析和归纳是获取真实质量和生产效率情况的手段。通过测量可以得出生产节拍,FTC,单位产品所需净生产时间及其它统计数据,从而证实供应商是否有能力生产出满足客户要求的产品。
最后,通过对产品的试验来证实供应商的体系是否有效,并且通过数据来表明产品满足了性能、工艺及材料技术条件中所包含的工程,质量,寿命和可靠性要求。
总而言之,PSO工作程序确保了供应商显示其满足PPAP要求的能力。
是谁:产品工作组(至少由供应商质量专家、工程师、供应商及其他合适的人员组成)。
何地:工艺认证的文件审核的预备会议最好是在供应商生产所在现场进行。如果产品工作组认为有必要时,现场工艺认证也可以在一级分供应商的生产现场进行。
何时:当产品工作组在预备会议中确认如下条件都已满足后,方可决定进行现场工艺认证的时间:
l 对供应商的文件已全部审核完毕并接受。
l 生产工装完成、定案并已在供应商现场安装和调试完毕,并且供应商自己的生产准备评估已经全部完成并有文件记录。
l 生产工序已确定并调试完毕,前期操作情况已经确定,并准备好按预先确定的抽样大小和生产节拍进行生产演示。
l 生产操作者已经培训并能在标定最大和持续的生产节拍下进行生产。