粒子群算法简介及使用

粒子群算法题目：求f (x)=兰x 2的最小值ii=11粒子群简介粒子群优化算法PSO也是起源对简单社会系统的模拟。最初设想是模拟鸟 群觅食的过程。粒子群优化算法是由Kennedy和Eberhart通过对鸟群、鱼群和人 类社会某些行为的观察研究，于1995年提出的一种新颖的进化算法。PSO算法属于进化算法的一种，和遗传算法相似，它也是从随机解出发， 通过迭代寻找最优解，它也是通过适应度来评价解的品质，但它比遗传算法规则 更为简单，它没有遗传算法的“交叉”和“变异”操作，它通过追随当前搜索 到的最优值来寻找全局最优。这种算法以其实现容易、精度高、收敛快等优点引 起了学术界的重视，并且在解决实际问题中展示了其优越性。2算法的原理PSO从这种模型中得到启示并用于解决优化问题。PSO中，每个优化问题 的潜在解都是搜索空间中的一只鸟，称之为粒子。所有的粒子都有一个由被优化 的函数决定的适值(fitness value)，每个粒子还有一个速度决定它们飞翔的方向 和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。PSO初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次 迭代中，粒子通过跟踪两个极值来更新自己；第一个就是粒子本身所找到的最优 解，这个解称为个体极值；另一个极值是整个种群目前找到的最优解，这个极值 是全局极值。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那 么在所有邻居中的极值就是局部极值。假设在一个D维的目标搜索空间中，有N个粒子组成一个群落，其中第，个粒子表示为一个D维的向量ii1i 2iD ，X 二(x ,x，x ) i 二 1,2,N第i个粒子的“飞行”速度也是一个D维的向量，记为ii1i 2iD ，V 二(V ,v，,v ) i 二 1,2,3第i个粒子迄今为止搜索到的最优位置称为个体极值，记为整个粒子群迄今为止搜索到的最优位置为全局极值，记为g 二(p ,p ，p )bestg1 g 2gD在找到这两个最优值时,粒子根据如下的公式(2.1)和(2.2)来更新自己的速度和位置:v 二 w * v + c rp- xidid 1 1ididid(2.1)idid id(2. 2)其中：C1和C2为学习因子，也称加速常数，r1和r2为0，1范围内的均匀随 机数。式(2.1)右边由三部分组成，第一部分为“惯性”或“动量”部分，反映了 粒子的运动“习惯”，代表粒子有维持自己先前速度的趋势；第二部分为“认知” 部分，反映了粒子对自身历史经验的记忆或回忆，代表粒子有向自身历史最佳位 置逼近的趋势；第三部分为“社会”部分，反映了粒子间协同合作与知识共享的 群体历史经验，代表粒子有向群体或邻域历史最佳位置逼近的趋势，根据经验， 通常C1 = C2 = 2。i =,D。vid是粒子的速度，vid丘vmax, vmax，Jax是常数， 由用户设定用来限制粒子的速度。r1和r2是介于0,1之间的随机数。探索是偏离原来的寻优轨迹去寻找一个更好的解，探索能力是一个算法的全 局搜索能力。开发是利用一个好的解，继续原来的寻优轨迹去搜索更好的解，它 是算法的局部搜索能力。如何确定局部搜索能力和全局搜索能力的比例，对一个 问题的求解过程很重要。带有惯性权重的改进粒子群算法。其进化过程为：(2.3)v (t +1)二 wv (t) + c r (t)(p (t) x (t) + c r (t)(p (t) x (t)jijlljij2 2gijx (t +1) - x (t) + v (t +1) /24) ijijij(24)在式(2.1)中，第一部分表示粒子先前的速度，用于保证算法的全局收敛性能; 第二部分、第三部分则是使算法具有局部收敛能力。可以看出，式(2.3)中惯性 权重w表示在多大程度上保留原来的速度。w较大，全局收敛能力强，局部收敛 能力弱；w较小，局部收敛能力强，全局收敛能力弱。当w二1时，式(2.3)与式(2.1)完全一样，表明带惯性权重的粒子群算法是基 本粒子群算法的扩展。实验结果表明，w在8 L2之间时，PSO算法有更快 的收敛速度，而当w L2时，算法则易陷入局部极值。3基本粒子群算法流程算法的流程如下： 初始化粒子群，包括群体规模N，每个粒子的位置X和速度V.Ii 计算每个粒子的适应度值F i；it 对每个粒子，用它的适应度值F i和个体极值p(i)比较，如果itbestF i p (i)，则用 Fiti替换掉 p (i)；itbestbest 对每个粒子，用它的适应度值Fiti和全局极值g 比较，如果bestF i p (i)则用 F i替 g ；itbestitbest 根据公式(2.1), (2.2)更新粒子的速度v和位置x ；ii 如果满足结束条件(误差足够好或到达最大循环次数)退出，否则返回。4参数的设定pso的参数主要包括最大速度、两个加速常数和惯性常数或收缩因等。1 群体大小mm是个整形参数，m很小的时候，陷入局优的可能性很大。当m很大时， PSO的优化能力很好，可是收敛速度将非常慢，并且当群体数目增长至一定的水 平时，再增长将不会有显著的作用。2 最大速度max的选择如式(2.1)所示的粒子速度是一个随机变量，由粒子位置更新公式(2.2)产生的 运动轨迹是不可控的，使得粒子在问题空间循环跳动。为了抑制这种无规律的跳 动，速度往往被限制在LVmax V max 内。Jax增大，有利于全局探索；Jax减小， 则有利于局部开发。但是Vmax过高，粒子运动轨迹可能失去规律性，甚至越过最 优解所在区域，导致算法难以收敛而陷入停滞状态；相反Vmax太小，粒子运动步 长太短，算法可能陷入局部极值。Vmax的选择通常凭经验给定，并一般设定为问 题空间的10 - 2%。3学习因子C1和C2式(1)中的学习因子C2和C2分别用于控制粒子指向自身或邻域最佳位置的运动。建议c1+ c2 - 4，并通常取c1 = c 2 = 2。Ratnaweera等人则提出自适应时变调整策略，即c1随着进化代数从2.5线性递减至0.5, $随着进化代数从0.5线性递增至2.5。与传统PSO取正数加速常数不同，Riget和Vesterstrom提出一 种增加种群多样性的粒子群算法，根据群体多样性指标调整加速常数的正负号, 动态地改变“吸引”和“扩散”状态，以改善算法过早收敛问题。4 惯性权值和收缩因子当PSO的速度更新公式采用式(1)时，即使vmax和两个加速因子选择合适， 粒子仍然可能飞出问题空间，甚至趋于无穷大，发生群体“爆炸”现象。有两种 方法控制这种现象：惯性常数和收缩因子。带惯性常数PSO的速度更新公式如 下：v t = wv t 1 + c r(p x t) + c r (t)(p x t) 11 cc I /1I 1ijij11ijij22ijij其中为惯性常数。建议随着更新代数的增加从0.9线性递减至0.4。近来， 通过采用随机近似理论分析PSO的动态行为，提出了一种随更新代数递减至0 的取值策略，以提高算法的搜索能力。带收缩因子PSO由Clerc和Kennedy提 出，其最简单形式的速度更新 公式如下：v t 二 xv t 1 + c r(pijij1 1 ijx t) + c r (t)(pij2 2ijx t)ij(4.2)2x =其中2 9 W 2 如，申=c1 + c2 4.0 ；通常申二 4从而 x 二 0.729,=1.49445虽然惯性权值和收缩因子对典型测试函数表现出各自的优势，但由于惯性常 数方法通常采用惯性权值随更新代数增加而递减的策略，算法后期由于惯性权值 过小，会失去探索新区域的能力，而收缩因子方法则不存在此不足。当惯性权重较大时，具有更好的搜索能力，而惯性权重较小时，具有更好的 开发能力。5 领域拓扑结构全局版本粒子群优化算法将整个群体作为粒子的邻域，速度快，不过有时会 陷入局部最优；局部版本粒子群优化算法将索引号相近或者位置相近的个体作为 粒子的邻域，收敛速度慢一点，不过很难陷入局部最优。6 停止准则一般使用最大迭代次数或者可以接受的满意解作为停止准则。7 粒子空间的初始化较好地选择粒子的初始化空间，将大大的缩减收敛时间。这个依赖于具体问 题。5方针实验1.完全模型：即按原公式进行速度更新。选择参数w=l, Cl=2, C2=2方针 的结果为：52.0.5图5-1102030405060708090100迭代次数2.只有自我认知：即速度上只考虑第一项和第二项。选择参数w=l, Cl=2,C2=0方针的结果为：c1= 2 ,c2=0,w=13.4i i i i i r2.7 -2.6 -/ -图 5-2-3.只有社会经验:即速度更新只考虑第一项和第三项。选择参数 w=1,C1=0,迭代友数C2=2方针的结果为:0102030405060708090100迭代次数4带有收缩因子的粒子群优化算法:选择参数w=0.729, Cl=1.494, C2=1.494方针的结果为:O论结6c1= 1.494 .c2=1.494,w=0 729102030406060708090100迭代次数5 4 64.3362.25由图5-1,图5-2，图5-3对比可知，自我认知的模型收敛最慢，只是因为不 同的粒子间缺乏信息交流，没有社会信息共享，导致找到最优概率变小。与此相 反社会经验模型可以很快的达到收敛，这是因为粒子之间社会信息共享导致进化 加快。但对于复杂问题只考虑社会经验，将导致粒子群过早收敛，从而陷入局优。 而只考虑个体经验，将使群体很难收敛进化速度过慢。相对而言，完全模型是较 好的选择。由图5-1和图5-4对比，改进型带有收缩因子的粒子群优化算法，拥有非常 好的收敛效果，收敛速度也十分的快。很快就就能求出最优值效果非常好。