粒子群算法(PSO)的数学原理

粒子群算法的起源

粒子群优化算法(Particle Swarm Optimization[PSO])是一种基于群体智能的启发式全局搜索算法,因为我的毕业设计需要用到,学习整理一下。

求函数最优值的问题,即求函数的最大或者最小值。粒子群算法通过粒子间的竞争和协作以实现在复杂搜索空间中寻找全局最优点。它具有易理解,易实现,全局搜索能力强等特点,倍受科学与工程的领域的广泛关注,已经成为发展最快的智能优化算法之一。 粒子群算法由Kennedy和Eberhart于1995年提出,它的基本思想源于对鸟群捕食行为的研究。具体来说,已知:

  • 在这块区域里面只有一块食物
  • 所有的鸟都不知道食物在哪里
  • 但是他们能感受到当前的位置距离食物还有多远

那么,找到食物的最优策略是什么呢?

通过与上述情景类比,研究人员发现了粒子群算法:

  • 目标函数只有一个极值
  • 函数的一组随机自变量的函数值不确定是极值
  • 但是N组函数的一组随机自变量对应的函数值通过比较大小,可以出最值

PS:我在学习的时候,看了半小时,都没有想出但是他们能感受到当前的位置距离食物还有多远这句话的具体含义。既然不知道食物的位置,又何来知道距离食物还有多远?后来想想,这句话还是稍微有些问题的,两者的类比还是有一些区别。

我现在对第三句话的理解是,目标函数是多元函数,我们可以初始化若干组自变量,于是可以得到函数值,找出这些函数值中的最值,再进行接下去的操作即可。

粒子群算法的数学描述

PSO从上述模型中得到启示并用于解决优化问题。PSO中,每个优化问题的潜在解都是搜索空间中的一只鸟,称之为粒子。所有的粒子都有一个由被优化的函数决定的适值(fitness value)[也就是每组自变量所对应的函数值],每个粒子还有一个速度决定他们飞翔的方向和距离。然后粒子们就追随当前的最优粒子在解空间中搜索。

PSO初始化为一组随机粒子[随机的一组自变量],然后通过迭代找到最优解。在每一次的迭代中,粒子通过跟踪两个极值来更新自己,第一个就是粒子本身所找到的最优解,这个解称为个体极值;另外一个极值是整个种群目前所找到的最优解,这个极值是全局极值。

假设在一个D维的目标搜索空间中([也就是D元函数]),有N个粒子组成一个群落,其中第i个粒子表示为一个D维的向量:

$$X_i=(x_{i1},x_{i2},…,x_{iD}), i=1,2,…,N$$

第i个粒子的飞行速度也是一个D维的向量,记为:

$$V_i=(v_{i1},v_{i2},…,v_{iD}), i=1,2,…,N$$

第i个粒子迄今为止搜索到的最优位置称为个体极值,记为:

$$P_{best}=(P_{i1},P_{i2},…,P_{iD}), i=1,2,…,N$$

整个粒子群迄今为止搜索到的最优位置为全局极值,记为:

$$g_{best}=(P_{g1},P_{g2},…,P_{gD})$$

在找到这两个最优值时,粒子需要根据如下公式来更新自己的速度和位置:

$$v_{id}=w\times v_{id}+c_1r_1(P_{id}-x_{id})+c_2r_2(P_{gd}-x_{id})$$

$$x_{id}=x_{id}+v_{id}$$

其中:c1和c2为学习因子,也称为加速常数acceleration constant,r1和r2为[0,1]范围内的均匀随机数。速度更新公式由三部分组成,第一部分为惯性,代表粒子有维持自己先前速度的趋势,第二部分为认知部分,反映了对自身历史经验的记忆,代表粒子有向自身历史最佳位置逼近的趋势,第三部分为社会部分,反映了粒子之间协同合作与知识共享的群体历史经验。

If you like my blog, please donate for me.