第3 章 粒子群优化 3.1 引 言 粒子群优化算法(PSO)起源于1994年提出的复杂适应系统理论(ComplexAdaptive System,CAS)。PSO 从鸟群种群行为特性中获得启发,通过模拟鸟群的行为方式,来发掘 同一鸟群同步飞行的模式,以及在最优形式重组时突然改变方向的模式,将其应用于求解优 化问题。 设想这样的一个场景:一群鸟在随机地寻找食物,在整个区域内只存在一块食物,所有 的鸟在初始时都不知道食物的位置,但它们知道自己的位置距离食物还有多远,那么最简单 的觅食策略就是“搜索目前距离食物最近的那只鸟的位置的周围区域”。 在PSO 中,每个优化问题的潜在解都可以理解成多维搜索空间上的一个点,即“粒子” (particle),所有粒子都有一个被目标函数决定的适应度值(fitnessvalue),影响它们移动的 方向和速度,决定它们移动的距离。然后粒子们就在这样的条件下开始追随当前的最优粒 子在解空间中进行搜索。 3.2 基本粒子群优化 PSO的基本思想是:通过群体中个体之间的协作和信息共享在给定的高维搜索空间中 搜寻最优解。PSO 中的粒子都存在一种基本行为:效仿别的粒子的成功行为,并继续保持 自身的成功行为。这种基本行为使得整个群体表现出能够搜寻最优解的群体行为。 一个PSO 维护了一群粒子,每个粒子代表一个潜在的解。和进化计算范式进行类比, 一个群类类似于一个种群,其中的每个粒子类似一个个体。每个粒子在高维搜索空间中飞 行,通过自身的经验和其周围个体的经验来不断调整自己的位置。令xi(t)表示粒子i 在时 刻t 时处于搜索空间中的位置,t 为离散的时间步。粒子的位置通过对当前位置增加速度 vi(t)来改变,即 xi(t+1)=xi(t)+vi(t+1) (3-1) 其中,xi(0)~U(xmin,xmax)。 速度向量v 是驱动优化过程的关键因素,它反映了粒子自身的经验累积,以及它邻域内 的各个粒子与它的交互信息。粒子自身的经验累积通常称为认知部分,与粒子到它找到过 的最佳位置(称为个体最佳位置)的距离成正比。交互信息则称为速度方程式的社会部分。 根据邻域的大小不同,将基本粒子群优化分成了全局最佳粒子群优化(gbestPSO)和局 42 群体智能导论 部最佳粒子群优化(lbestPSO)。 3.2.1 全局最佳粒子群优化 gbestPSO 是指每个粒子的邻域都是整个群体。gbestPSO 使用的社会网络是星型拓 扑结构(详见3.2.6节),粒子速度方程式中的社会部分代表着粒子从整个群体中获取到的 交互信息。因此,在gbestPSO 中,社会部分就是整个群体所找到的最佳位置,记作y^(t)。 对于gbestPSO,粒子i 的速度计算公式如下: vij(t+1)=vij(t)+c1r1j(t)[yij(t)-xij(t)]+c2r2j(t)[y^j(t)-xij(t)] (3-2) 式中,vij(t)表示粒子i 在时刻t 时在维度j 上的速度; xij(t)表示粒子i 在时刻t 时在维度j 上的位置; c1和c2分别界定了认知部分和社会部分贡献的加速常数(都为正数); r1j和r2j是处于区间[0,1]上的随机值,服从均匀分布,为算法引入了随机性。 yi表示粒子i 的个体最佳位置,是指从第一次迭代开始找到的最佳位置。在t+1时 刻,个体最佳位置可以按照如下公式进行计算: yi(t+1)= yi(t), f(xi(t+1))≥f(yi(t)) {xi(t+1), f(xi(t+1))0时,γ∈R,否则γ∈C。下面分情况进行讨论。 1.γ∈R (1).=0,可得递归轨迹方程式如下: x(t)=2x(t-1)-x(t-2) (3-24) 粒子的轨迹如下: x(t)= (x0 -p )v0t (3-25) 如果x0=p,则粒子会沿着初始方向一直移动下去。 (2).=4,可得递归轨迹方程式如下: x(t)=-2x(t-1)-x(t-2)+4p (3-26) 粒子的轨迹如下: x(t)=((x0 -p)+ (2(x0 -p)-v0)t)(-1)t +p (3-27) 如果x0=p,则轨迹方程式变成 x(t)=-v0t (-1)t +p (3-28) 由于(-1)t的存在,粒子将在连续的时间步上做相反方向的运动。 (3).>4,粒子轨迹如式(3-23)所示,粒子将做振动运动(以指数函数为界)。初始速度 v0越大,粒子的步长也会越大。 综上可知,当γ∈R时,粒子的步长的增大需要加以限制,以保证粒子不会偏离搜索空间。 第3 章　粒子群优化 51 2.γ∈C (1)0<.<4,轨迹方程式如下: x(t)=k2αt +k3βt (3-29) 式中, α =2-. +γ' 2 β=2-. -γ' 2 k3 = (x0 -p ) (γ'+.) 2γ' - v0 γ' k2 =x0 -p -k3 γ'=i |.2 -4.| 对于任意一个复数z∈C,它的模由l2范数度量,即 z = (R(z))2 + (G(z))2 (3-30) 需要注意的是,复数可以写成如下形式: zt =(z eiθ)t = z teiθt = z t(cosθt+isinθt) (3-31) 式中,θ=arg(z)。 若x0=p,则轨迹方程式变成 x(t)=2v0 γ' sinarctan γ't 2-. . è . . . ÷ . è . . . ÷ (3-32) 式(3-22)表明,一个具有复数值γ 的粒子的轨迹是一条正弦波,其中初始条件和参数的选 择将决定波的振幅和频率,其实决定的是粒子的方向和步长。振幅和频率的表达形式如下: A =2v0 γ' (3-33) V =arctan γ't 2-. . è . . . ÷ 2π (3-34) 周期T =1V ,轨迹方程式的周期性可以使粒子重复地搜索已经访问过的空间,除非其 邻域中的另一个粒子找到了更好的解。 (2).=2,由式(3-18)可得 x(t)=-x(t-2)+.p =v0sintπ 2 . è . . . ÷ +2p (3-35) (3)0<.<2或2<.<4,轨迹方程式如下: x(t)=Tssinθt+rccosθt (3-36) 式中, Ts =2v0 -.x0 -.p γ Tc =x0 -p θ=arctan γ 2-. . è . . . ÷ 52 群体智能导论 γ= |.2-4.| 当x0=p,0<.≤2-3和2+3<.<4 时,正弦波的振幅随着 . 的减小而增大,因为 γ' <1,频率也随着周期的增大而减小。 当2-3<.≤2 和2<.≤2+3 时,γ' >1,由于 的上界为5,正弦波的振幅接 近v0。 γ' 3.3.2 轨迹示例 下面是一个简化PSO 系统的部分粒子轨迹展示。这些图例展示出了一个简化粒子的 不同类型的行为,比如收敛、周期性和发散等行为。其中的参数.1和.2是随机选取的,由此 产生的轨迹图像展示出了随机粒子的探索能力。 为了简化模型,令y=0,y0, 0)10,1)10-9.1-10.2 1.^=初始条件为x(=x(=。由 此可以构建一个简单的模型。下面是模型的部分行为的图例展示。 如图3-5所示,简化的系统收敛到了一个平衡点。图3-5(a)显示的是粒子的探索行为, 在探索的初期,粒子需要覆盖尽可能多的搜索空间,随着时间步数的增大,振荡幅度逐渐减 小,直至归零。其中的参数ω=5,4。 0..1=.2<1. 图3- 5 简化PSO 系统的收敛行为 图36展示的是系统的周期性行为,粒子并没有收敛到平衡点。其中的参数ω=0, -1. .1=.2=1. 999 。 图3- 6 简化PSO 系统的周期性行为 第3 章　粒子群优化 53 图3-7展示的是系统的发散行为,在探索初期,粒子的振荡幅度很小,随着时间步数的 增大,振荡幅度逐渐变大,最后导致粒子偏离了搜索空间。 图3-7 简化PSO 系统的发散行为 3.4 收敛性证明 3.4.1 局部收敛性 关于基本PSO 优化的收敛性证明,证明基本PSO 不是一个局部最小化算法。首先考 虑单模最优化问题。 定义: x0 =argmax xi {f(xi)}, i=1,2,…,ns (3-37) 在最小化问题中,x0使得f 的值最大,因此x0表示种群中最差的粒子,作为初始位置。 定义紧集: L0 ={x ∈S:f(x)≤f(x0)} (3-38) 紧集表示的是所有满足f 值小于或等于f(x0)的粒子。 假设所有粒子都在函数f 的同一个“盆地”中,因此xi,yi∈L0。由速度方程式和位置 方程式可得,PSO 的方程式A 定义如下: A(y^t,xi,t)= y^t, f(g(xi,t))≥f(y^t) g(xi,t), f(g(xi,t))0,在max{ α ,β } <1时,受参数ω、.1、.2的值选择的影响。 证明: lim t→+∞ x(t)=lim t→+∞(k1 +k2αt +k3βt)=.1y +.2y^ .1 +.2 (3-45) 由递推关系可得 x(t+1)-x(t)=v(t+1) (3-46) 因此,当max{α ,β }<1时,有 lim t→+∞ v(t+1)=lim t→+∞(x(t+1)-x(t))=lim t→+∞(k2αt(α -1)+k3βt(β-1))=0 (3-47) 进一步,有 x(t+1)=x(t)+v(t+1)=x(t)+ωv(t)-x(t)(.1 +.2)+y.1 +y^.2 (3-48) 根据式(3-45)可得,在t 的极限情况下,x(t+1)=x(t)。根据式(3-46)可得,在t 的极 限情况下,v(t)=0。因此,在极限条件下,有 x(t)=x(t)-x(t)(.1 +.2)+y.1 +y^.2 →0 (3-49) 当x(t)=y=y^ 时,式(3-49)成立,系统将会收敛。需要注意的是,这个点不一定是一 个局部最优值。 根据上述证明可以发现,一旦算法达到如下状态,即x(t)=y=y^,表示算法不会取得 进步,则算法就会终止,但此状态中的y^不一定是全局最优值,可能只是一个局部最优值。 综上所述,基本PSO 并非是一个局部搜索算法,因为它不能保证从任意一个初始状态 都能收敛到一个局部最优值。 3.4.2 全局收敛性 3.4.1节已经证明了,基本PSO 不能保证收敛到一个局部极小值,因此也不能保证可以 收敛到全局极小值。在本节中继续讨论基本PSO 的全局收敛性。 由收敛性条件可知,任意一个集合A .S,必须有一个非零的概率被算法能够无限地进 行检查。因此,条件必须在所有时间步上都要满足,或者在有限个数的时间步上例外。由于 R...S,则存在一个非零的概率使得样本可以在S 的任何子集中产生,并且一个样本x'∈ R..最终会产生。同时,一个算法如果一致性地忽略搜索空间的任何区域,则不能保证可以 产生一个样本x'使得x'∈R..,除非算法有关于全局最小值的先验信息。因此,为了保证全 局最小值能够以渐近概率1被发现,一个算法必须可以产生遍布于S 的无限多的样本。 引理3.2 基本PSO 不满足全局搜索的收敛条件。 证明:令Mi,t表示粒子i 在第t 步的采样空间的支撑。所有粒子的采样空间的并集必 须覆盖S,即 第3 章　粒子群优化 55 S .∪ns i=1 Mi,t (3-50) 根据非齐次递推关系可得,Mi,t的计算公式如下: Mi,t =(1+ω -.1 -.2)xij,t -ωxij,t-2 +.1yij -.2y^j =xij,t-1 +ω (xij,t-1 -xij,t-2 ) +.1 (yij -xij,t-1 ) +.2 (^yj -xij,t-1 ) (3-51) 式中,xij,t表示第i 个粒子在时刻t 时处于维度j 时的值。同时注意0≤.1≤c1,0≤.2≤c2。 因此,Mi,t是一个超矩形,其中的参数由.1和.2决定,其中一个角定义为(.1,.2)= (0,0),另一个角定义为(.1,.2)=(c1,c2),很明显,当满足如下条件时, max{c1 yij -xij,t-1 ,c2 ^yj -xij,t-1 } <0.5×diameterj(S) (3-52) 有L(Mi,t∩S )