粒子群优化算法PSO.ppt

粒子群优化算法 主要内容 1.产生背景 2.算法介绍 3.参数设置 4.在车辆优化调度中的应用 粒子群算法的产生背景 粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。 CAS的4个基本特点（这些特点是粒子群算法发展变化的依据）： 首先，主体是主动的、活动的。 其次，主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。 再次，环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。 最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。 粒子群算法就是对一个CAS－－－鸟群社会系统的研究得出的。 PSO算法简介 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Intelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行有哪些信誉好的足球投注网站。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。 原理 我们可以设想这样一个场景，一群鸟在某区域随机搜寻食物。该区域只有一块食物。所有的鸟都不知道食物在哪里，但它们知道目前距离食物还有多远，那么找到食物的最佳策略是什么呢？最简单的方法就是找寻距离食物最近的鸟周围区域及根据自己飞行的经验判断食物的所在。 算法介绍 每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有粒子都在一个D维空间进行有哪些信誉好的足球投注网站。 所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。 每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。 每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。 粒子群优化算法求最优解 粒子i的第d维速度更新公式： 粒子i的第d维位置更新公式： —第k次迭代粒子i飞行速度矢量的第d维分量 —第k次迭代粒子i位置矢量的第d维分量 c1,c2—加速度常数，调节学习最大步长 r1,r2—两个随机函数，取值范围[0，1]，以增加有哪些信誉好的足球投注网站随机性 w —惯性权重，非负数，调节对解空间的有哪些信誉好的足球投注网站范围 粒子速度更新公式包含三部分： 第一部分为粒子先前的速度 第二部分为“认知”部分，表示粒子本身的思考，可理解为粒子i当前位置与自己最好位置之间的距离。 第三部分为“社会”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。 算法流程 Initial： 初始化粒子群体（群体规模为n），包括随机位置和速度。 Evaluation： 根据fitness function ，评价每个粒子的适应度。 Find the Pbest： 对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最佳位置pbest。 Find the Gbest： 对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。 Update the Velocity： 根据公式更新每个粒子的速度与位置。 如未满足结束条件，则返回步骤2 通常算法达到最大迭代次数 或者最佳适应度值的增量小于某个给定的阈值时算法停止。 粒子群优化算法流程图 算法参数设置 1.群体规模 一般，待求解问题维数越高，所需的群体规模也越大，通常群体规模是问题维数的1.5倍左右。 2.最大速度 决定当前位置与最优位置之间区域的分辨率。如果太高，粒子可能会飞过好解；如果太小，粒子不能对局部最优区间之外进行足够探索，导致陷入局部优值。 3.加速度常数 c1、c2代表将每个粒子推向pbest和gbest位置的统计加速项的权重。较低的加速常数允许粒子在被拉回之