粒子群优化算法PSO

粒子群优化算法主要内容1.产生背景2.算法介绍3.参数设置4.在车辆优化调度中的应用粒子群算法的产生背景粒子群算法源于复杂适应系统（ComplexAdaptiveSystem,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。CAS的4个基本特点（这些特点是粒子群算法发展变化的依据）：首先，主体是主动的、活动的。其次，主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。再次，环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。粒子群算法就是对一个CAS－－－鸟群社会系统的研究得出的。粒子群算法(particleswarmoptimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于SwarmIntelligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。PSO算法简介BionicComputingLab,2005BionicComputing12/03/12粒子群最佳化ParticleSwarmsOptimizationRussEberhart整合群体行为、人类决策与鸟群行为发展成为粒子群演算法。【Eberhart,Kennedy,1995】原理我们可以设想这样一个场景，一群鸟在某区域随机搜寻食物。该区域只有一块食物。所有的鸟都不知道食物在哪里，但它们知道目前距离食物还有多远，那么找到食物的最佳策略是什么呢？最简单的方法就是找寻距离食物最近的鸟周围区域及根据自己飞行的经验判断食物的所在。BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse鳥群(魚群)行為ParticleSwarmsOptimization粒子群特性算法介绍每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有粒子都在一个D维空间进行搜索。所有的粒子都由一个fitnessfunction确定适应值以判断目前的位置好坏。每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。粒子群优化算法求最优解D维空间中，有N个粒子；粒子i位置：xi=(xi1,xi2,…xiD)，将xi代入适应函数f(xi)求适应值；粒子i速度：vi=(vi1,vi2,…viD)粒子i个体经历过的最好位置：pbesti=(pi1,pi2,…piD)种群所经历过的最好位置：gbest=(g1,g2,…gD)通常，在第d（1≤d≤D）维的位置变化范围限定在内，速度变化范围限定在内（即在迭代中若超出了边界值，则该维的速度或位置被限制为该维最大速度或边界位置）min,max,[X,]ddX,max,[-V,]maxddVidvid、x粒子i的第d维速度更新公式：粒子i的第d维位置更新公式：—第k次迭代粒子i飞行速度矢量的第d维分量—第k次迭代粒子i位置矢量的第d维分量c1,c2—加速度常数，调节学习最大步长r1,r2—两个随机函数，取值范围[0，1]，以增加搜索随机性w—惯性权重，非负数，调节对解空间的搜索范围kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx11kkkidididxxvkidvkidx粒子速度更新公式包含三部分：第一部分为粒子先前的速度第二部分为“认知”部分，表示粒子本身的思考，可理解为粒子i当前位置与自己最好位置之间的距离。第三部分为“社会”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置之间的距离。kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx1111122V=V+C*r*(Pbest-X)+C*r*(gbest-X)kkkkiiiii区域最佳解全域最佳解运动向量惯性向量BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourseParticleSwarmsOptimization11X=X+Vkkkiii12NX=X,X,...,Xiiii12NV=V,V,...,Viiii2維簡例BionicComputingLab,2005BionicComputingChungYuanChristianUniversity12/21/05DMcourse粒子群最佳化ParticleSwarmsOptimizationNote合理解目前最優解區域最佳解全域區域算法流程1.Initial：初始化粒子群体（群体规模为n），包括随机位置和速度。2.Evaluation：根据fitnessfunction，评价每个粒子的适应度。3.FindthePbest：对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最佳位置pbest。4.FindtheGbest：对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。5.UpdatetheVelocity：根据公式更新每个粒子的速度与位置。6.如未满足结束条件，则返回步骤2通常算法达到最大迭代次数或者最佳适应度值的增量小于某个给定的阈值时算法停止。maxG粒子群优化算法流程图开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest，更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限？算法参数设置1.群体规模一般，待求解问题维数越高，所需的群体规模也越大，通常群体规模是问题维数的1.5倍左右。2.最大速度决定当前位置与最优位置之间区域的分辨率。如果太高，粒子可能会飞过好解；如果太小，粒子不能对局部最优区间之外进行足够探索，导致陷入局部优值。maxV3.加速度常数c1、c2代表将每个粒子推向pbest和gbest位置的统计加速项的权重。较低的加速常数允许粒子在被拉回之前可以在目标区域外徘徊，而高的加速常数则导致粒子突然冲向或越过目标区域，形成较大的适应值波动。若w=0，则速度只取决于粒子pbest和gbest，速度本身不具有记忆性。此时，粒子仅能探测有限区域，更像一个局部算法。如果公式里没有后两部分，即c1=c2=0若w1，则当前速度始终是初始速度的放大；若w1，则当前速度从初始速度开始，呈几何级数衰减；若w=1，则粒子一直以初始速度飞行，不会改变飞行的方向和速度的大小。如果c1=0，则粒子没有个体认知能力，只有“社会”模型。在粒子相互作用下，虽然可能探索新的解空间，但对复杂问题很容易陷入局部极值点。如果c2=0，则粒子之间没有社会信息共享，只有“个体认知”模型。因为个体间没有交互，一个规模为m的群体等价于执行了m个粒子的单独搜索，因而得到最优解的概率大大减小。一般取c1=c2=2.kk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx4．惯性权重惯性权重w描述粒子上一代速度对当前代速度的影响。w值较大，全局寻优能力强，局部寻优能力弱；反之，则局部寻优能力强。当问题空间较大时，为了在搜索速度和搜索精度之间达到平衡，通常做法是使算法在前期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度。所以w不宜为一个固定的常数。线性递减权值wmax最大惯性权重，wmin最小惯性权重，run当前迭代次数，runmax为算法迭代总次数模糊控制器自适应改变权重Shi和Eberhart提出一个模糊系统来调节w，该系统包括9条规则，有两个输入和一个输出，每个输入和输出定义了三个模糊集。一个输入为当前代的全局最好适应值，另一个为当前的w；输出为w的变化。maxmaxminmax()*run收缩因子法速度更新公式为其中，收缩因子为K为受φ1φ2限制的w。φ1φ2是需要预先设定的模型参数1122[()()]ididididdidvKvrpbestxrgbestx1222,,424Kkk-111idid1122v=wv()()kkididdidcrpbestxcrgbestx粒子群算法在车辆优化调度中的应用物流配送车辆调度问题包括集货线路优化、货物配装及送货线路优化等,是物流配送系统优化的关键。利用粒子群算法求解物流车辆调度问题的关键是解决针对调度问题的粒子编码和解码方法。配送车辆优化调度的数学描述配送车辆优化调度问题一般描述为:有一个中心仓库,拥有K辆车,容量分别为qk(k=1,2,…K);有L个收货点的运输任务需要完成,各收货点的货运量为gi(i=1,2,…L),并且max{gi}≤max{qk};配送车辆优化调度的目标是满足货运需求的车辆行驶路径最短。将车辆任务点编号为0,1,…L,其中:0为中心仓库;1,2,…L为收货点。•定义变量如下:•为从任务点i到任务点j的运输成本（运输距离）•Z为所有车辆行驶距离总和kifijc该模型要求每个收货点都得到车辆配送服务,并且限制每个收货点的需求只能由某一台车辆完成,同时保证每条路径上各收货点的总需求量不超过此路径上配送车辆的容量。在满足上述条件的情况下,使所有车辆行驶距离之和Z最小。非满载车辆优化调度的数学模型为粒子群算法设计粒子编码设计粒子的第一维用自然数1,2,…L来表示L个收货点,按递增顺序排列;粒子的第二维xi用于映射分配给各收货点的车辆编号,xi的元素xij∈[1,K+1)。粒子的第三维yi用于映射各车辆的行驶距离。一个完整的三维粒子可以表示为:粒子解码过程(1)对粒子第二维向量xi的元素xij进行取整操作int(xij),即可得到分配给收货点j的车辆k。(2)对于车辆k的行驶路径,按照粒子第三维向量yi的元素yij的大小顺序来确定,即首先找出由车辆k完成配送的收货点j,然后按照j所对应yij的大小,从小到大进行排序,从而确定车辆k的行驶路径。例如,假设一个有10个收货点、4台车辆的调度问题,其第i个粒子为:根据解码过程对xi进行取整操作后,可得到4台车辆在各收货点的分配情况,即:对于车辆2,其经过的收货点有1、5、6,然后根据各收货点对应的yij值按照从小到大的顺序,可得到车辆2的行驶路径为1→6→5。因此4台车辆的行驶路径为:车辆1,0→4→7→0;车辆2,0→1→6→5→0；车辆3，0→8→9→2→0；车辆4，0→10→3→0.算法流程（1）算法初始化。设置最大迭代次数和粒子种群数等,并生成初始种群。在初始种群的生成过程中,每个粒子的第二维向量元素xij随机取值时,应尽量保证[1,K]中的每个整数均被选取,即保证每台车辆k均被分配给收货点。(2)对粒子进行解码生成车辆调度方案,并根据各收货点的位置计算粒子的适应值,即车辆的总行驶距离。如果由粒子解码得到的调度方案不可行,即