粒子群优化算法PSO

1、粒子群优化算法主要内容v1.产生背景v2.算法介绍v3.参数设置v4.在车辆优化调度中的应用粒子群算法的产生背景v粒子群算法源于复杂适应系统（Complex Adaptive System,CAS）。CAS理论于1994年正式提出，CAS中的成员称为主体。比如研究鸟群系统，每个鸟在这个系统中就称为主体。主体有适应性，它能够与环境及其他的主体进行交流，并且根据交流的过程“学习”或“积累经验”改变自身结构与行为。整个系统的演变或进化包括：新层次的产生（小鸟的出生）；分化和多样性的出现（鸟群中的鸟分成许多小的群）；新的主题的出现（鸟寻找食物过程中，不断发现新的食物）。 CAS的的4个基本特点个基本特

2、点（这些特点是粒子群算法发展变化的依据）：v 首先，主体是主动的、活动的。v 其次，主体与环境及其他主体是相互影响、相互作用的，这种影响是系统发展变化的主要动力。v 再次，环境的影响是宏观的，主体之间的影响是微观的，宏观与微观要有机结合。v 最后，这种建模方法还引进了随机因素的作用，使它具有更强的描述和表达能力。 粒子群算法就是对一个CAS鸟群社会系统的研究得出的。 粒子群算法(particle swarm optimization，PSO)由Kennedy和Eberhart在1995年提出，该算法模拟鸟集群飞行觅食的行为，鸟之间通过集体的协作使群体达到最优目的，是一种基于Swarm Inte

3、lligence的优化方法。同遗传算法类似，也是一种基于群体叠代的，但并没有遗传算法用的交叉以及变异，而是粒子在解空间追随最优的粒子进行搜索。PSO的优势在于简单容易实现同时又有深刻的智能背景，既适合科学研究，又特别适合工程应用，并且没有许多参数需要调整。 PSO算法简介 Bionic Computing Lab, 2005ionic omputing粒子群最佳化v原理我们可以设想这样一个场景，一群鸟在某区域随机搜寻食物。该区域只有一块食物。所有的鸟都不知道食物在哪里，但它们知道目前距离食物还有多远，那么找到食物的最佳策略是什么呢？最简单的方法就是找寻距离食物最近的鸟周围区域及根据自己飞行的经

4、验判断食物的所在。Bionic Computing Lab, 2005ionic omputingChung Yuan Christian University鳥群(魚群)行為算法介绍 v每个寻优的问题解都被想像成一只鸟，称为“粒子”。所有粒子都在一个D维空间进行搜索。v所有的粒子都由一个fitness function 确定适应值以判断目前的位置好坏。v每一个粒子必须赋予记忆功能，能记住所搜寻到的最佳位置。v每一个粒子还有一个速度以决定飞行的距离和方向。这个速度根据它本身的飞行经验以及同伴的飞行经验进行动态调整。 粒子群优化算法求最优解粒子群优化算法求最优解 D维空间中，有N个粒子； 粒子i

5、位置：x xi i=(xi1,xi2,xiD)，将xi代入适应函数f(xi)求适应值； 粒子i速度：v vi i=(vi1,vi2,viD) 粒子i个体经历过的最好位置：pbestpbesti i=(pi1,pi2,piD) 种群所经历过的最好位置：gbestgbest=(g1,g2,gD)通常，在第d（1dD）维的位置变化范围限定在 内， 速度变化范围限定在 内（即在迭代中若 超出了边界值，则该维的速度或位置被限制为该维最大速度或边界 位置） min,max,X,ddX,max,-V,max ddVidvid、xv粒子i的第d维速度更新公式： v 粒子i的第d维位置更新公式： 第k次迭代粒子

6、i飞行速度矢量的第d维分量 第k次迭代粒子i位置矢量的第d维分量 c1,c2加速度常数，调节学习最大步长 r1,r2两个随机函数，取值范围0，1，以增加搜索随机性 w 惯性权重，非负数，调节对解空间的搜索范围kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx11kkkidididxxvkidvkidxv粒子速度更新公式包含三部分： 第一部分为粒子先前的速度 第二部分为“认知”部分，表示粒子本身的思考，可理解为粒子i当前位置与自己最好位置之间的距离。 第三部分为“社会”部分，表示粒子间的信息共享与合作，可理解为粒子i当前位置与群体最好位置

7、之间的距离。kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx1111122V = V+C *r*(Pbest -X)+C *r *(gbest -X)kkkkiiiii区域最佳解全域最佳解运动向量惯性向量Bionic Computing Lab, 2005ionic omputingChung Yuan Christian University11X =X+Vkkkiii12NX = X ,X ,.,Xiiii12NV = V ,V ,.,ViiiiBionic Computing Lab, 2005ionic omputingChu

8、ng Yuan Christian University粒子群最佳化算法流程nInitial：初始化粒子群体（群体规模为n），包括随机位置和速度。nEvaluation：根据fitness function ，评价每个粒子的适应度。nFind the Pbest： 对每个粒子，将其当前适应值与其个体历史最佳位置（pbest）对应的适应值做比较，如果当前的适应值更高，则将用当前位置更新历史最佳位置pbest。nFind the Gbest：对每个粒子，将其当前适应值与全局最佳位置（gbest）对应的适应值做比较，如果当前的适应值更高，则将用当前粒子的位置更新全局最佳位置gbest。nUpdate

9、 the Velocity：根据公式更新每个粒子的速度与位置。n如未满足结束条件，则返回步骤2n 通常算法达到最大迭代次数 或者最佳适应度值的增量小于某个给定的阈值时算法停止。maxG粒子群优化算法流程图粒子群优化算法流程图 开始初始化粒子群计算每个粒子的适应度根据适应度更新pbest、gbest，更新粒子位置速度结束noyes达到最大迭代次数或全局最优位置满足最小界限？算法参数设置v1.群体规模 一般，待求解问题维数越高，所需的群体规模也越大，通常群体规模是问题维数的1.5倍左右。v2.最大速度 决定当前位置与最优位置之间区域的分辨率。如果太高，粒子可能会飞过好解；如果太小，粒子不能对局部最

10、优区间之外进行足够探索，导致陷入局部优值。maxVv3.加速度常数vc1、c2代表将每个粒子推向pbest和gbest位置的统计加速项的权重。较低的加速常数允许粒子在被拉回之前可以在目标区域外徘徊，而高的加速常数则导致粒子突然冲向或越过目标区域，形成较大的适应值波动。v若w=0，则速度只取决于粒子pbest和gbest，速度本身不具有记忆性。此时，粒子仅能探测有限区域，更像一个局部算法。v如果公式里没有后两部分，即c1=c2=0 若w1，则当前速度始终是初始速度的放大； 若w1，则当前速度从初始速度开始，呈几何级数衰减； 若w=1，则粒子一直以初始速度飞行，不会改变飞行的方向和速度的大小。v如

11、果c1=0，则粒子没有个体认知能力，只有“社会”模型。在粒子相互作用下，虽然可能探索新的解空间，但对复杂问题很容易陷入局部极值点。v如果c2=0，则粒子之间没有社会信息共享，只有“个体认知”模型。因为个体间没有交互，一个规模为m的群体等价于执行了m个粒子的单独搜索，因而得到最优解的概率大大减小。v一般取c1=c2=2.kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestxv4惯性权重 惯性权重w描述粒子上一代速度对当前代速度的影响。w值较大，全局寻优能力强，局部寻优能力弱；反之，则局部寻优能力强。当问题空间较大时，为了在搜索速度和搜索精度之

12、间达到平衡，通常做法是使算法在前期有较高的全局搜索能力以得到合适的种子，而在后期有较高的局部搜索能力以提高收敛精度。所以w不宜为一个固定的常数。v线性递减权值 wmax最大惯性权重，wmin最小惯性权重，run当前迭代次数，runmax为算法迭代总次数v模糊控制器自适应改变权重 Shi和Eberhart提出一个模糊系统来调节w，该系统包括9条规则，有两个输入和一个输出，每个输入和输出定义了三个模糊集。一个输入为当前代的全局最好适应值，另一个为当前的w；输出为w的变化。 maxmaxminmax()*runwwwwrunv收缩因子法速度更新公式为其中，收缩因子为K为受1 2 限制的w。1 2是需

13、要预先设定的模型参数1 12 2()()ididididdidvK vr pbestxr gbestx1222,424K kk-111idid1 12 2v =wv()()kkididdidc r pbestxc r gbestx粒子群算法在车辆优化调度中的应用v物流配送车辆调度问题包括集货线路优化、货物配装及送货线路优化等, 是物流配送系统优化的关键。利用粒子群算法求解物流车辆调度问题的关键是解决针对调度问题的粒子编码和解码方法。配送车辆优化调度的数学描述v配送车辆优化调度问题一般描述为: 有一个中心仓库, 拥有K 辆车, 容量分别为qk ( k= 1, 2,K ) ; 有L 个收货点的运输

14、任务需要完成, 各收货点的货运量为gi ( i= 1, 2, L ) , 并且max gi max qk ; 配送车辆优化调度的目标是满足货运需求的车辆行驶路径最短。v将车辆任务点编号为0, 1,L , 其中: 0 为中心仓库; 1, 2,L 为收货点。定义变量如下: 为从任务点i到任务点j的运输成本（运输距离）Z为所有车辆行驶距离总和kifijcv该模型要求每个收货点都得到车辆配送服务, 并且限制每个收货点的需求只能由某一台车辆完成, 同时保证每条路径上各收货点的总需求量不超过此路径上配送车辆的容量。在满足上述条件的情况下, 使所有车辆行驶距离之和Z 最小。非满载车辆优化调度的数学模型为粒子

15、群算法设计v粒子编码设计 粒子的第一维用自然数1, 2, L 来表示L 个收货点, 按递增顺序排列; 粒子的第二维xi 用于映射分配给各收货点的车辆编号, xi 的元素xij 1, K + 1) 。粒子的第三维yi 用于映射各车辆的行驶距离。 一个完整的三维粒子可以表示为:v粒子解码过程 (1) 对粒子第二维向量xi 的元素xij 进行取整操作 int (xij) , 即可得到分配给收货点j 的车辆k 。 (2) 对于车辆k 的行驶路径, 按照粒子第三维向量y i 的元素yij 的大小顺序来确定, 即首先找出由车辆k 完成配送的收货点j , 然后按照j 所对应yij 的大小, 从小到大进行排序

16、, 从而确定车辆k的行驶路径。v例如, 假设一个有10 个收货点、4 台车辆的调度问题, 其第i 个粒子为: 根据解码过程对xi 进行取整操作后,可得到4台车辆在各收货点的分配情况, 即: 对于车辆2, 其经过的收货点有1、5、6, 然后根据各收货点对应的yij 值按照从小到大的顺序,可得到车辆2 的行驶路径为16 5。因此4 台车辆的行驶路径为: 车辆1, 0 4 7 0; 车辆2, 0 1 65 0；车辆3，0 8 9 20；车辆4， 0 10 30.算法流程v（1）算法初始化。设置最大迭代次数和粒子种群数等, 并生成初始种群。在初始种群的生成过程中, 每个粒子的第二维向量元素xij 随机

17、取值时, 应尽量保证 1, K 中的每个整数均被选取, 即保证每台车辆k均被分配给收货点。v( 2) 对粒子进行解码生成车辆调度方案, 并根据各收货点的位置计算粒子的适应值, 即车辆的总行驶距离。如果由粒子解码得到的调度方案不可行, 即违背了约束条件, 如某条路径上各收货点的总需求量超过此路径上配送车的容量, 或调度方案中有车辆未被分配给收货点等, 则将该粒子的适应值设为一个比最优调度适应值大得多的数。根据各粒子的适应值确定局部最优粒子和全局最优粒子。v( 3) 选择惯性权重PSO 模型, 即根据公式 对粒子的速度和位置进行更新。v( 4) 更新后的粒子中, 如果xij 超过了1,K +1)

18、的范围, 则在该范围内重新随机取值。v( 5) 判断迭代是否结束。如果结束, 则输出计算结果; 否则, 转向步骤( 2) 。1 12 2()()ididididdidvwvcr pbestxc r gbestxidididxxv算例v例如，包含1 个中心仓库、7 个收货点和3 台车辆( 假设车辆容量q 均为1) 的车辆优化调度问题( 最优调度方案的车辆行驶距离为217. 813 6) 进行计算, 各任务点(0为中心仓库,1 7为收货点)的坐标和货运量如表1 所示。v中心仓库0和7个收货点的平面分布如图所示。v采用粒子群算法和遗传算法同时对该算例进行计算, 设定两种算法的最大迭代次数为200, 粒子种群数为50。遗传算法中, 交叉概率