粒子群算法简介

前言

本文内容借鉴于 刘衍民的博士论文:“粒子群算法的研究及应用”.

现有的大多数群智能算法,如:乌鸦算法、鸽子算法、蚁群算法、萤火虫算法和灰狼优化算法等，都可以归类为粒子群算法.(个人觉得,这些算法就是整个稀奇古怪的名字,颇有舞文弄墨,强造创新点之嫌,其算法本质仍为粒子群算法).

粒子群算法与遗传算法最大的不同之处在于,不使用交叉和变异等进化算法产生后代,而是根据种群中其他粒子的分布来更新粒子的位置.

粒子群算法及其基础理论

粒子群算法是一种基于种群的智能算法,种群中每个成员叫做粒子,代表着一个潜在的可行解,而食物的位置则被认为是全局最优解.在飞行过程中,群体中所有的粒子都具有记忆的能力,能对自身位置和自身经历过的最佳位置进行调整.为了实现接近食物位置这个目的,每个粒子通过不断地向自身经历过的最佳位置(pbest)和种群中最好的粒子位置(gbest)学习,最终接近食物位置.(p,表示personal,“自知部分”.g,表示global, “社会部分”).

下图给出了粒子速度和位置在第t代和第t+1代的调整示意图,其中五角星的位置为食物位置,v₁表示第t代"社会部分"学习引起粒子向gbest方向飞行的速度;v₂表示"自知部分"学习引起粒子向pbest方向飞行的速度;v₃表示粒子自身具有的速度.在v₁,v₂和v₃的共同作用下,最终粒子以速度v_t+1到达新的粒子位置.

粒子群算法的数学描述如下,假设种群规模为N,在迭代时刻t,每个粒子在D维空间中的坐标位置可以表示为:
$$\overline{x_i\left(t\right)}=\left(x_i^1,x_i^2,...x_i^d,...x_i^D\right)$$
粒子的速度表示为:
$$\overline{v_i\left(t\right)}=\left(v_i^1,v_i^2,...v_i^d,...v_i^D\right)$$
坐标位置$\overline{x_i\left(t\right)}$和速度$\overline{v_i\left(t\right)}$在t+1时刻,按照下述方式进行调整,
$$\overline{x_i}\left(t+1\right)=\overline{x_i}\left(t\right)+\overline{v_i}\left(t+1\right)$$

$$\overline{v_i}\left(t+1\right)=\overline{v_i}\left(t\right)+c_1\cdot r_1\left(\overline{p_i}\left(t\right)-\overline{x_i}\left(t\right)\right)+c_2\cdot r_2\left(\overline{p_g}\left(t\right)-\overline{x_i}\left(t\right)\right)$$

速度更新公式包括三部分:第一部分是$\overline{v_i\left(t\right)}$,它表示粒子先前的速度,具有自身开拓、扩大搜索空间、探索新的搜索区域的趋势，这使算法具有全局优化能力，但是在算法的迭代后期它可能影响局部精细搜索.第二部分是$\overline{p_i\left(t\right)}$,表示粒子i所经历的最优位置(pbest),称作粒子的"自知部分"学习,表示粒子本身的思考,即向自身学习的能力;第三部分是$\overline{p_g\left(t\right)}$表示种群中最好的粒子位置(gbest),称作粒子的"社会学习",表示粒子向整个种群学习的能力.

粒子速度更新的三部分共同决定了粒子在可行空间的搜索能力,其作用分别是:第一部分$\overline{v_i\left(t\right)}$,用来平衡全局和局部搜索的能力;第二部分是$\overline{p_i\left(t\right)}$使粒子有较强的局部搜索能力;第三部分$\overline{p_g\left(t\right)}$表现了粒子间的信息共享.另外,c₁和c₂表示粒子的加速常数,通常在[0,2]之间取值;r₁和r₂是两个在[0,1]之间均匀分布的随机数.

开发和探索

探索 (Exploration) 是指粒子在一定程度上离开原先的搜索轨迹，向新的方向进行搜索，体现了一种向未知区域开拓的能力，类似于全局搜索；开发 (Exploitation) 指粒子在一定程度上继续在原先的搜索轨迹上进行更细一步的搜索，主要指对探索过程中所搜索到的区域进行
更进一步的搜索，类似于局部搜索。