粒子群算法
Eberhart和Kennedy 1995 提出了粒子群优化Particle Swarm Optimization,PSO算法。PSO算法的运行机理不是依靠个体的自然进化规律,而是对生物群体的社会行为进行模拟,它最早源于对鸟群觅食行为的研究。在生物群体中存在着个体与个体、个体与群体间的相互作用、相互影响的行为,这种行为体现的是一种存在于生物群体中的信息共享机制。PSO算法就是对这种社会行为的模拟,即利用信息共享机制,使得个体间可以相互借鉴经验,从而促进整个群体的发展。此外,粒子群算法概念简单,容易实现,需要调节的参数偏少。因此,粒子群算法越来越受到人们的关注,其研究成为国内外的热点。但是在实际应用中发现粒子群优化易“早熟”,并且精度不高。基于此,大量学者对此算法进行了深入的研究,提出了许多改进方法和策略,如Shi和Eberhart 1998, Kennedy和Eberhart 2001, Clerc和Kennedy 2002, Trelea 2003, Voss 2005, Beheshti 2013, Mahmoodabadi等 2014。
PSO算法中每个粒子即解空间中的一个解,它根据自己的飞行经验和同伴的飞行经验来调整自己的飞行。每个粒子在飞行过程所经历过的最好位置,就是粒子本身找到的最优解。整个群体所经历过的最好位置,就是整个群体目前找到的最优解。前者叫作个体极值pBest,后者叫作全局极值gBest。每个粒子都通过上述两个极值不断更新自己,从而产生新一代群体。实际操作中通过由优化问题所决定的适应度函数值Fitness Value来评价粒子的“好坏”程度。显然,每个粒子的行为就是追随着当前的最优粒子在解空间中搜索。
在基本PSO中,先在可行解空间中随机初始化 N 个粒子构成初始种群,并为每个粒子随机初始化一个速度,每个粒子都对应优化问题的一个解,并由目标函数为之确定一个适应值,而速度用来决定粒子在解空间中的运动。在算法的每次迭代中,粒子将跟踪自身当前找到的最优解和种群当前找到的最优解,逐代搜索,直到最后得到最优解。在 D 维搜索空间中,记第 i 个粒子的位置 xi=xi1,xi2,…,xiD′ ,其“飞行”速度为 vi=vi1,vi2,…,viD′ 。每个粒子当前找到的极值为 pi=pi1,pi2,…,piD′ ,种群当前找到的全局极值为 pg=pg1,pg2,…,pgD′ 。下一代粒子的位置和速度为:
xi+1=xi+vi2.15
vi+1=wvi+c1r1pi-xi+c2r2pg-xi2.16
式中, d=1,2,…,D , i=1,2,…,N , N 是粒子个数; k 表示迭代的次数;w是惯性权重,它是微粒保持运动的惯性,使其有能力探索新的区域; c1 , c2 为学习因子,它是一个正常数,它们使每个微粒向pBest和gBest位置加速运动; r1,r2 是[0,1]之间的随机数。此外,粒子的速度 Vi 被一最大速度 Vmax 所限制。如果当前对粒子的加速导致它在某维的速度 Vid 超过了该维的最大速度 Vmax d ,则该维的速度被限制为该维的最大速度 Vmax d 。最大速度限制决定了粒子在解空间的搜索精度,如果 Vmax 太高,粒子可能会飞过最优解,如果 Vmax 太小,粒子则会陷入局部搜索空间而无法进行全局搜索。
|