粒子群优化算法课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,粒子群优化算法（Particle Swarm Optimizer,PSO）,基于群智能方法的演化计算技术,粒子群优化算法（Particle Swarm Opti,1,粒子群优化算法,粒子群优化算法,(PSO),最初是由Kennedy和Eberhart博士于1995年受人工生命研究的结果启发，在模拟鸟群觅食过程中的迁徙和群集行为时提出的一种基于群体智能的演化计算技术。该算法具有并行处理、鲁棒性好等特点，能以较大概率找到问题的全局最优解，且计算效率比传统随机方法高。其最大的优势在于编程简单，易实现、收敛速度快，而且有深刻的智能背景，既适合科学研究，又适合工程应用。因此，PSO一经提出，立刻引起了演化计算领域研究者的广泛关注，并在短短几年时间里涌现出大量的研究成果，该算法目前已被“国际演化计算会议”列为讨论专题之一。,PSO,是受到鸟群或者鱼群社会行为的启发而形成的一种基于种群的随机优化技术。它是一类随机全局优化技术，通过粒子间的相互作用发现复杂搜索空间中的最优区域。该算法是一种基于群体智能的新型演化计算技术，具有简单易实现、设置参数少、全局优化能力强等优点。粒子群优化算法已在函数优化、神经网络设计、分类、模式识别、信号处理、机器人技术等许多领域取得了成功的应用。,粒子群优化算法 粒子群优化算法(PSO)最初是由Kenned,2,粒子群优化算法,产生背景,设想这样一个场景：一群鸟随机的分布在一个区域中，在这个区域里只有一块食物。所有的鸟都不知道食物在哪里。但是他们知道当前的位置离食物还有多远。那么找到食物的最优策略是什么呢。最简单有效的方法就是追寻自己视野中目前离食物最近的鸟。如果把食物当作最优点，而把鸟离食物的距离当作函数的适应度，那么鸟寻觅食物的过程就可以当作一个函数寻优的过程。由此受到启发，经过简化提出了粒子群优化算法。,粒子群优化算法产生背景,3,粒子群优化算法,PSO的缺点：,对于有多个局部极值点的函数，容易陷入到局部极值点中，得不到正确的结果。此外，由于缺乏精密搜索方法的配合，PSO方法往往不能得到精确的结果。再则，PSO方法提供了全局搜索的可能，但并不能严格证明它在全局最优点上的收敛性。因此，PSO一般适用于一类高维的、存在多个局部极值点而并不需要得到很高精度的优化问题。,粒子群优化算法PSO的缺点：,4,粒子群优化算法,PSO算法的基本思想,每个优化问题的潜在解都是搜索空间中的一只鸟，称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值（fitness value），每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子（随机解）。然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个“极值”来更新自己。第一个就是粒子本身所找到的最优解。这个解称为个体极值。另一个极值是整个种群目前找到的最优解。这个极值是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。,粒子群优化算法PSO算法的基本思想,5,粒子群优化算法,PSO算法是一种启发式的优化计算方法，其最大的优点：,易于描述，易于理解；,对优化问题定义的连续性无特殊要求；,只有非常少的参数需要调整；,算法实现简单，速度快；,相对其它演化算法而言，只需要较小的演化群体；,算法易于收敛，相比其它演化算法，只需要较少的评价 函数计算次 数就可达到收敛；,无集中控制约束，不会因个体的故障影响整个问题的求解，确保了系统具备很强的鲁棒性。,粒子群优化算法PSO算法是一种启发式的优化计算方法，其最大的,6,粒子群优化算法,基本模型,设群体规模为N，在一个D维的目标搜索空间中，群体中的第i(i=1，2，N)个粒子位置可以表示为一个D维矢量 ，同时用,表示第i个粒子的飞翔速度。用 表示第i个粒子自身搜索到的最好点。而在这个种群中，至少有一个粒子是最好的，将其编号记为g，则 就是当前种群所搜索到的最好点，即种群的全局历史最优位置。,粒子群优化算法基本模型,7,粒子群优化算法,粒子根据以下公式来更新其速度和位置：,（1）,（2）,其中i=1，2，N，j表示粒子的第j维，k表示迭代次数，为加速常数，一般在02之间取值。主要是为了调节粒子自身的最好位置飞行的步长，是为了调节粒子向全局最好位置飞行的步长。，为两个相互独立的随机函数。为了减少在进化过程中，粒子离开搜索空间的可能性，通常限定于一定范围内，即,粒子群优化算法粒子根据以下公式来更新其速度和位置：,8,粒子群优化算法,式(1)中其第一部分 为粒子先前的速度；其第二部分 为“认知”部分，它仅考虑了粒子自身的经验，表示粒子本身的思考，其第三部分 为“社会”部分，表示粒子间的社会信息共享，,粒子群优化算法式(1)中其第一部分 为粒子先前的速度,9,粒子群优化算法,基本粒子群算法的流程如下：,(1)依照初始化过程，对粒子群的随机位置和速度进行初始设定；,(2)计算每个粒子的适应值；,(3)对于每个粒子，将其适应值与所经历过的最好位置 的适应值进行比较，若较好，则将其作为当前最好位置；,(4)对于每个粒子，将其适应值与全局所经历过的最好位置 的适应值进行比较，若较好，则将其作为当前的全局最好位置；,(5)根据两个迭代公式对粒子的速度和位置进行进化；,(6)如未达到结束条件通常为足够好的适应值或达到一个预设最大代数(Gmax)，返回步骤(2)；否则执行步骤(7),(7)输出gbest.,粒子群优化算法基本粒子群算法的流程如下：,10,粒子群优化算法,流程图,粒子群优化算法流程图,11,粒子群优化算法,带惯性权重的粒子群算法,为了改变基本粒子群算法的收敛性能，Y.Shi与R.C.Eberhart在1998年的IEEE国际进化计算学术会议上发表了题为“A Modified Particle Swarm Optimization”的论文。首先在速度进化方程中引入惯性权重(inertia weight)w，即,（3）,粒子群优化算法带惯性权重的粒子群算法,12,粒子群优化算法,基本粒子群算法是w=1的特殊情况。把带惯性权重的微粒群算法称之为标准粒子群算法。由基本粒子群算法模型中粒子位置的进化方程可以看出，粒子在不同时刻的位置主要是由飞行速度决定的，也就是说粒子的飞行速度相当于搜索步长：,飞行速度的大小直接影响着算法的全局收敛性。当粒子的飞行速度过大时，各粒子初始将会以较快的速度飞向全局最优解邻近的区域，但是当逼近最优解时，由于粒子的飞行速度缺乏有效的控制与约束，则将很容易飞越最优解，转而去搜索其它区域，从而使算法很难收敛于最优解，陷入局部最优解；当粒子的飞行速度过小时，粒子在初期向全局最优解邻近区域靠近的搜索时间就需要很长。收敛速度慢，很难达到最优解。基于此现实情况，他们二人提出了标准的微粒群算法。,粒子群优化算法 基本粒子群算法是w=1的特,13,粒子群优化算法,式(3)中的w为惯性权重，它具有维护全局和局部搜索能力的平衡作用，可以使粒子保持惯性运动，使其有扩展搜索空间的趋势，有能力探索新的区域。对全局搜索，通常的好方法是在前期有较高的搜索能力以得到合适的粒子，而在后期有较高的开发能力以加快收敛速度。为此，可将w设定为随着进化而线性减少，例如由0.9 1.2等。有些学者在研究中曾论证出w的最佳值在0.8附近，这将为设计标准微粒粒子群算法参数时提供了有利的参考。一般人们认为较大的w提高了寻优时粒子的全局搜索能力，有利于提高寻优的成功率；较小的w则有利于粒子群在迭代运算时的快速聚集，有利于提高寻优的速度。,粒子群优化算法式(3)中的w为惯性权重，它具有维护全局和局部,14,粒子群优化算法,引入惯性权重w可消除基本粒子群算法对 的需要。当 增加时，可通过减少w来达到平衡搜索，而w的减少可使得所需的迭代次数变小。所以，可以将各维变量的 固定，而只对w进行调节。w越大，粒子的飞行速度就越大，它将以较大的步长进行全局搜索；w越小，粒子的速度步长越小，粒子趋向于进行精细的局部搜素。w的变化趋势正好相当于粒子速度的变化趋势。所以带惯性权重的粒子群算法的改进之处就是将二者结合起来以使粒子可以尽快的向最优解区域靠拢，而又不至于在到达最优解区域附近时飞越最优解。,目前关于粒子群算法的研究，一般都是将带惯性权重的粒子群算法作为最基本的PSO算法模型。,粒子群优化算法引入惯性权重w可消除基本粒子群算法对,15,预备知识,无约束最优化问题,其中 ，通常称变量,为决策变量(decision variables)，称 为目标函数(objective function)。,预备知识无约束最优化问题,16,预备知识,一般约束非线性优化问题的数学模型为：,可行集（域）,预备知识一般约束非线性优化问题的数学模型为：,17,预备知识,为等式约束，为不等式约束，等式约束和不等式约束统称为约束条件(constraint condition)。为英文“subject to”的缩写，表示“受限制于”,预备知识 为等式约束，,18,基本概念,若有 使得 ，均有 ，则称 为最优化问题 的（全局）最优解(global optimal solution)（点）或全局极小点。,若 使得 ，均有 ，则称为最优化问题 的严格全局极小点。,基本概念若有 使得 ，均,19,基本概念,若存在 的一个邻域 使得 均有 ，则称为最优化问题 的（局部）最优解(local optimal solution)（点）或局部极小点(local minimum point)，其中 而 为向量的模。,若 使得 ，均有 则称 为最优化问题 的严格局部极小点,点 称为最优解，其所对应的目标函数值 称为最优值，通常用 表示。,基本概念若存在 的一个邻域 使得,20,优化问题的分类,根据最优化问题是否有约束条件，可分为约束最优化问题和无约束最优化问题。,若目标函数和约束条件中出现的函数均为线性函数，称该最优化问题为线性规划（Linear Programming）问题，否则称为非线性规划（Nonlinear Programming）问题,即目标函数和约束条件中出现的函数至少有一个不是线性函数，称该最优化问题为非线性规划问题。,优化问题的分类根据最优化问题是否有约束条件，可分为约束最优化,21,优化问题的分类,若目标函数为二次函数，而约束条件为线性函数，称该最优化问题为二次规划（Quadratic Programming）问题，显然二次规划是最简单的一种非线性规划问题。,若优化变量只能取整数值时，称该最优化问题为整数规划（Integer Programming）问题，特别地，若整数规划问题中的优化变量只能取值为0或1，称之为0-1规划。,当目标函数不是数量函数而是向量函数时，称之为多目标函数，等等。,优化问题的分类若目标函数为二次函数，而约束条件为线性函数，称,22,最优化问题举例,例1曲线拟合问题,假设热敏电阻R是温度的函数，函数关系如下,其中 是待定参数。通过实验测定 和R的15组数据如,表1,：确定参数 使曲线尽可能地靠近所有的实验点。,最优化问题举例例1曲线拟合问题,23,最优化问题举例,利用最小二乘法原理求解，即确定参数的一组值，使其偏差的平方和,最小。即,最优化问题举例利用最小二乘法原理求解，即确定参数的一组值，使,24,最优化问题举例,例2 生产安排问题,某工厂生产甲、乙、丙三种产品，每件产品所消耗的材料、工时、盈利见,表2,已知该工厂每天的材料消耗不超过600千克，工时不超过1400小时，问每天生产甲、乙、丙三种产品各多少事的盈利最大？,最优化问题举例例2 生产安排问题,25,最优化问题举例,设每天生产甲、乙、丙三种产品分别,为 件，因此盈利 ，其相应的材料限制为,工时限制为,再考虑自然限制,因此生产安排问题就是在上述限制条件下，使其盈利达到最大。其数学表达式为：,最优化问题举例设每天生产甲、乙、丙三种产品分别,