粒子群算法简介及使用

《粒子群算法简介及使用》由会员分享，可在线阅读，更多相关《粒子群算法简介及使用（12页珍藏版）》请在装配图网上搜索。

1、粒子群算法10题目：求的最小值r-l1粒子群简介粒子群算法是在1995年山Eberhart博士和Kennedy博士一起提出的，它源 于对鸟群捕食行为的研究。它的基本核心是利用群体中的个体对信息的共享从而 使整个群体的运动在问题求解空间中产生从无序到有序的演化过程，从而获得问 题的最优解。设想这么一个场景：一群鸟进行觅食，而远处有一片玉米地,所有的 鸟都不知道玉米地到底在哪里，但是它们知道自己当前的位置距离玉米地有多远。 那么找到玉米地的最佳策略，也是最简单有效的策略就是搜寻口前距离玉米地最 近的鸟群的周围区域。在PS0中，每个优化问题的解都是搜索空间中的一只鸟,称之为粒子，而问 题的最优解就对

2、应于鸟群中寻找的玉米地。所有的粒子都具有一个位置向量 （粒子在解空间的位置）和速度向量（决定下次飞行的方向和速度），并可以根 据H标函数来汁算当前的所在位置的适应值（fitness value），可以将其理解为 距离玉米地的距离。在每次的迭代中，种群中的例子除了根据自身的经验（历 史位置）进行学习以外，还可以根据种群中最优粒子的经验来学习，从而确定下 一次迭代时需要如何调整和改变飞行的方向和速度。就这样逐步迭代，最终整个 种群的例子就会逐步趋于最优解。PSO算法属于进化算法的一种，和遗传算法相似,它也是从随机解出发，通过 迭代寻找最优解，它也是通过适应度来评价解的品质,但它比遗传算法规则更为简

3、 单，它没有遗传算法的“交叉”和“变异”操作，它通过追随当前搜索到的最优值 来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引起了学术界 的重视，并且在解决实际问题中展示了其优越性。2算法的原理PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题的 潜在解都是搜索空间中的一只鸟,称之为粒子。所有的粒子都有一个由被优化的 函数决定的适值（fitness value），每个粒子还有一个速度决定它们飞翔的方向和距 离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子（随机解），然后通过迭代找到最优解。在每一次迭 代中，粒子通过跟踪两个极值来更新自己；

4、第一个就是粒子本身所找到的最优解, 这个解称为个体极值；另一个极值是整个种群口前找到的最优解，这个极值是全 局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在 所有邻居中的极值就是局部极值。假设在一个D维的目标搜索空间中，有N个粒子组成一个群落，其中第i个粒 子表示为一个D维的向量Xi =（召I，兀2,心）21,2,N第i个粒子的“飞行”速度也是一个维的向量，记为X =（忖畑）心123第个粒子迄今为止搜索到的最优位置称为个体极值，记为Pbest =Pa，、PilJ i = 2、N整个粒子群迄今为止搜索到的最优位置为全局极值，记为8best =（Pgl、P、P加）在找到这两个

5、最优值时,粒子根据如下的公式（2.1）和（2.2）来更新自己的速度 和位置：(2. 2)% = xid + %其中：5和5为学习因子迪称加速常数/和2为0,1范围内的均匀随机数。 式(2.1)右边由三部分组成,笫一部分为“惯性”或“动量”部分，反映了粒子的运 动“习惯”，代表粒子有维持自己先前速度的趋势；第二部分为“认知”部分，反 映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位置逼近的 趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的群体历史 经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验，通常 q=C2=2o / = 1,2,D。是粒子的速度, e

6、 一,%汰是常数，由用户 设定用来限制粒子的速度。林和卩是介于0,1之间的随机数。探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全 局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它是 算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对一个问 题的求解过程很重要。带有惯性权重的改进粒子群算法。其进化过程为：Vy (f +1) = HWg (r) + c“ (0( ptj (/) 一 Xq (/) + c2r2 (r)( “0 (/) -Xjj (/)(.勺(f + l) =勺(/) + 片川 + 1)(24)在式(2.1)中，第一部分表示粒子

7、先前的速度，用于保证算法的全局收敛性能； 第二部分、第三部分则是使算法具有局部收敛能力。可以看出，式(2.3)中惯性权 重表示在多大程度上保留原来的速度。较大，全局收敛能力强,局部收敛能力 弱；较小，局部收敛能力强，全局收敛能力弱。当U1时，式(2.3)与式(2.1)完全一样，表明带惯性权重的粒子群算法是基本 粒子群算法的扩展。实验结果表明,在8-12之间时,PSO算法有更快的收敛 速度，而当w 12时，算法则易陷入局部极值。3基本粒子群算法流程算法的流程如下：初始化粒子群，包括群体规模,每个粒子的位置兀和速度叫计算每个粒子的适应度值Fi:对每个粒子，用它的适应度值化卩和个体极值几和(门比较，

8、如果恥 PM，则用用爪替换掉P畑G)；对每个粒子，用它的适应度值用亚和全局极值幻“比较，如果片卩 叽则用时替如； 根据公式(2.1) , (2.2)更新粒子的速度儿和位置心； 如果满足结束条件(误差足够好或到达最大循环次数)退出,否则返回口。4参数的设定PSO的参数主要包括最大速度、两个加速常数和惯性常数或收缩因等。1.群体大小mm是个整形参数,m很小的时候，陷入局优的可能性很大。当m很大时,PSO 的优化能力很好，可是收敛速度将非常慢,并且当群体数LI增长至一定的水平时, 再增长将不会有显著的作用。2.最大速度的选择如式(2.1)所示的粒子速度是一个随机变量，由粒子位置更新公式(2.2)产生

9、的 运动轨迹是不可控的，使得粒子在问题空间循环跳动。为了抑制这种无规律的跳 动，速度往往被限制在-V-xmax内。fax增大，有利于全局探索；fax减小，则有 利于局部开发。但是叫-过高，粒子运动轨迹可能失去规律性，其至越过最优解所 在区域，导致算法难以收敛而陷入停滞状态；相反卩-x太小，粒子运动步长太短，算 法可能陷入局部极值。缶、的选择通常凭经验给定，并一般设定为问题空间的 10-20%。3. 学习因子C1和C2式（1）中的学习因子5和5分别用于控制粒子指向自身或邻域最佳位置的运 动。建议e = 5 +c2 随着进化代数从2.5线性递减至0.5,5随着进化代数从0.5线性 递增至2.5。与

10、传统PSO取正数加速常数不同,Riget和Vesterstrom提出一种增加 种群多样性的粒子群算法，根据群体多样性指标调整加速常数的正负号，动态地改 变“吸引”和“扩散”状态,以改善算法过早收敛问题。4. 惯性权值和收缩因子当PSO的速度更新公式采用式时，即使-和两个加速因子选择合适，粒子 仍然可能飞出问题空间，其至趋于无穷大，发生群体“爆炸”现象。有两种方法控 制这种现象：惯性常数和收缩因子。带惯性常数PSO的速度更新公式如下：= my-1 + c（內一勺）+。2厂2（0（內 -（4 ）其中为惯性常数。建议随着更新代数的增加从0.9线性递减至0.4。近来，通 过采用随机近似理论分析PSO的

11、动态行为，提出了一种随更新代数递减至0的取 值策略，以提高算法的搜索能力。带收缩因子PSO lil Clerc和Kennedy提出，其 最简单形式的速度更新公式如下：2x =（、=其中2 0 Q02_40, = C|+C24O；通常 0 = 4.1 从而尤=0.729,C = 6 = 1.494451-O虽然惯性权值和收缩因子对典型测试函数表现出各自的优势,但山于惯性常 数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期山于惯性权值 过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足。当惯性权重较大时,具有更好的搜索能力，而惯性权重较小时，具有更好的开 发能力。5领域拓扑结构全

12、局版本粒子群优化算法将整个群体作为粒子的邻域，速度快,不过有时会陷 入局部最优；局部版本粒子群优化算法将索引号相近或者位置相近的个体作为粒 子的邻域，收敛速度慢一点，不过很难陷入局部最优。6.停止准则一般使用最大迭代次数或者可以接受的满意解作为停止准则。7粒子空间的初始化较好地选择粒子的初始化空间，将大大的缩减收敛时间。这个依赖于具体问 题。5方针实验1.完全模型：即按原公式进行速度更新。选择参数v=l,Cl=2,C2=2方针的结果为:V/ =-1 + c“(為一兀/)+ C2r2 5 - x. t)(4.2)HI 5-12.只有自我认知：即速度上只考虑第一项和第二项。选择参数w=l,Cl=2

13、,C2=0方针的结果为：34333.23 13埋购2 92.82 72625c1= 2 c2=0 w=1-11I11101 1 111111140迭f龍:徹60图5-23只有社会经验：即速度更新只考虑第一项和第三项。选择参数 w=l,Cl=0,C2=2方针的结果为:IH 5-34.带有收缩因子的粒子群优化算法：选择参数、v=0.729,Cl=1.494,C2=1.494方针的结果为：图546结论山图5-1,图5-2,图5-3对比可知，自我认知的模型收敛最慢，只是因为不同的粒 子间缺乏信息交流，没有社会信息共事，导致找到最优概率变小。与此相反社会经 验模型可以很快的达到收敛，这是因为粒子之间社会

14、信息共乍导致进化加快。但 对于复杂问题只考虑社会经验，将导致粒子群过早收敛，从而陷入局优。而只考虑 个体经验,将使群体很难收敛进化速度过慢。相对而言，完全模型是较好的选择。由图5-1和图5-4对比，改进型带有收缩因子的粒子群优化算法，拥有非常好 的收敛效果,收敛速度也十分的快。很快就就能求出最优值效果非常好。与遗传算法的比较共同点 种群随机初始化。 对种群内的每一个个体讣算适应值(fitness value)。适应值与最优解的 距离直接有关。 种群根据适应值进行复制。 如果终止条件满足的话，就停止,否则转步骤。从以上步骤，我们可以看到PSO和遗传算法有很多共同之处。两者都随机初 始化种群，而且

15、都使用适应值来评价系统，而且都根据适应值来进行一定的随机 搜索。两个系统都不是保证一定找到最优解。但是,PSO没有遗传操作如交叉 (crossover)和变异(mutation),而是根据自己的速度来决定搜索。粒子还有一个 重要的特点,就是有记忆。不同点与遗传算法比较,PSO的信息共享机制是很不同的。在遗传算法中，染色体 (chromosomes)互相共享信息，所以整个种群的移动是比较均匀的向最优区域移 动。在PSO中，只有gBest (orlBest)给出信息给其他的粒子，这是单向的信 息流动。整个搜索更新过程是跟随当前最优解的过程。与遗传算法比较，在大多 数的情况下，所有的粒子可能更快的收敛于最优解。优缺点演化计算的优势，在于可以处理一些传统方法不能处理的。例子例如不可导 的节点传递函数或者没有梯度信息存在。但是缺点在于：1. 在某些问题上性能并不是特别好。2. 网络权重的编码而且遗传算子的选择有时比较麻烦。最近已经有一些利用PSO来代替反向传播算法来训练神经网络的论文。研究 表明PSO是一种很有潜力的神经网络算法。PSO速度比较快而且可以得到比较好 的结果。而且还没有遗传算法碰到的问题。