《1 前言》

1 前言

从20世纪90年代初, 就产生了模拟自然生物群体 (swarm) 行为的优化技术。Dorigo等从生物进化的机理中受到启发, 通过模拟蚂蚁的寻径行为, 提出了蚁群优化方法;Eberhart和 Kennedy于1995年提出的粒子群优化算法是基于对鸟群、鱼群的模拟。这些研究可以称为群体智能 (swarm intelligence) 。通常单个自然生物并不是智能的, 但是整个生物群体却表现出处理复杂问题的能力, 群体智能就是这些团体行为在人工智能问题中的应用。粒子群优化 (PSO) 最初是处理连续优化问题的, 目前其应用已扩展到组合优化问题[1]。由于其简单、有效的特点, PSO已经得到了众多学者的重视和研究。

《2 PSO基本原理》

2 PSO基本原理

《2.1基本PSO原理》

2.1基本PSO原理

粒子群优化算法是基于群体的演化算法, 其思想来源于人工生命和演化计算理论。Reynolds对鸟群飞行的研究发现, 鸟仅仅是追踪它有限数量的邻居, 但最终的整体结果是整个鸟群好像在一个中心的控制之下, 即复杂的全局行为是由简单规则的相互作用引起的。PSO即源于对鸟群捕食行为的研究, 一群鸟在随机搜寻食物, 如果这个区域里只有一块食物, 那么找到食物的最简单有效的策略就是搜寻目前离食物最近的鸟的周围区域。PSO算法就是从这种模型中得到启示而产生的, 并用于解决优化问题。另外, 人们通常是以他们自己及他人的经验来作为决策的依据, 这就构成了PSO的一个基本概念。

PSO求解优化问题时, 问题的解对应于搜索空间中一只鸟的位置, 称这些鸟为“粒子” (particle) 或“主体” (agent) 。每个粒子都有自己的位置和速度 (决定飞行的方向和距离) , 还有一个由被优化函数决定的适应值。各个粒子记忆、追随当前的最优粒子, 在解空间中搜索。每次迭代的过程不是完全随机的, 如果找到较好解, 将会以此为依据来寻找下一个解。

令PSO初始化为一群随机粒子 (随机解) , 在每一次迭代中, 粒子通过跟踪两个“极值”来更新自己:第一个就是粒子本身所找到的最好解, 叫做个体极值点 (用pbest表示其位置) , 全局版PSO中的另一个极值点是整个种群目前找到的最好解, 称为全局极值点 (用gbest表示其位置) , 而局部版PSO不用整个种群而是用其中一部分作为粒子的邻居, 所有邻居中的最好解就是局部极值点 (用lbest表示其位置) 。在找到这两个最好解后, 粒子根据如下的式 (1) 和式 (2) 来更新自己的速度和位置。粒子i的信息可以用D维向量表示, 位置表示为 Xi= (xi1, xi2, ..., xiD) T, 速度为Vi= (vi1, vi2, ..., viD) T, 其他向量类似。则速度和位置更新方程为

vidk+1=vidk+c1rand1k(pbestidk-xidk)+c2rand2k(gbestdk-xidk)(1)xidk+1=xidk+vidk+1(2)

vidk是粒子i在第k次迭代中第d维的速度;c1, c2 是加速系数 (或称学习因子) , 分别调节向全局最好粒子和个体最好粒子方向飞行的最大步长, 若太小, 则粒子可能远离目标区域, 若太大则会导致突然向目标区域飞去, 或飞过目标区域[2]。合适的c1, c2可以加快收敛且不易陷入局部最优, 通常令c1=c2=2;rand1, 2 是[0, 1]之间的随机数;xidk是粒子i在第k次迭代中第d维的当前位置;pbestid是粒子i在第d维的个体极值点的位置 (即坐标) ;gbestd是整个群在第d维的全局极值点的位置。为防止粒子远离搜索空间, 粒子的每一维速度vd都会被钳位在[-vd max, +vd max]之间, vd max太大, 粒子将飞离最好解, 太小将会陷入局部最优[2]。假设将搜索空间的第d维定义为区间[-xd max, +xd max], 则通常vd max=kxd max, 0.1≤k≤1.0, 每一维都用相同的设置方法。基本PSO的流程可以描述为:

Step 1 初始化 初始搜索点的位置Xi0及其速度Vi0通常是在允许的范围内随机产生的, 每个粒子的pbest坐标设置为其当前位置, 且计算出其相应的个体极值 (即个体极值点的适应度值) , 而全局极值 (即全局极值点的适应度值) 就是个体极值中最好的, 记录该最好值的粒子序号, 并将gbest设置为该最好粒子的当前位置。

Step 2 评价每一个粒子 计算粒子的适应度值, 如果好于该粒子当前的个体极值, 则将pbest设置为该粒子的位置, 且更新个体极值。如果所有粒子的个体极值中最好的好于当前的全局极值, 则将gbest设置为该粒子的位置, 记录该粒子的序号, 且更新全局极值。

Step 3 粒子的更新 用式 (1) 和式 (2) 对每一个粒子的速度和位置进行更新。

Step 4 检验是否符合结束条件 如果当前的迭代次数达到了预先设定的最大次数 (或达到最小错误要求) , 则停止迭代, 输出最优解, 否则转到Step 2。

PSO的一些特点:

1) 基本PSO算法最初是处理连续优化问题的。

2) 类似于遗传算法 (GA) PSO也是多点搜索。

3) 式 (1) 的第一项对应多样化 (diversification) 的特点, 第二项、第三项对应于搜索过程的集中化 (intensification) 特点, 因此这个方法在多样化和集中化之间建立均衡[1]

PSO有全局版和局部版两种, 全局版收敛快, 但有时会陷入局部最优。局部版PSO通过保持多个吸引子来避免早熟, 假设每一个粒子在大小l的邻域内定义为一个集合

Νi={pbesti-l,pbesti-l+1,...,pbesti-1,pbesti,pbesti+1,...,pbesti+l-1,pbesti+l}(3)

Ni中选出最好的, 将其位置作为lbest代替公式中的gbest, 其他与全局版PSO相同。实验表明, 局部版比全局版收敛慢, 但不容易陷入局部最优[3]。在实际应用中, 可以先用全局PSO找到大致的结果, 再用局部PSO进行搜索。

《2.2二进制PSO》

2.2二进制PSO

最初的PSO是从解决连续优化问题发展起来的, Eberhart等又提出了PSO的离散二进制版, 用来解决工程实际中的组合优化问题[4]。他们在提出的模型中将每一维xid和pbestid限制为1或者为0, 而速度vid不作这种限制。用速度来更新位置时, 如果vid高一些, 粒子的位置xid更有可能选1, vid低一点则选0, 阈值在[0, 1]之间, 而有这种特点的函数就是Sigmoid函数:

sig(vidk)=1/(1+exp(-vidk))(4)

二进制版本PSO的公式为

ifρidk+1<sigvidk+1thenxidk+1=1;elsexidk+1=0(5)

向量ρidk+1的各个分量是[0, 1]之间的随机数[1]。为了防止Sigmoid函数饱和, 可以将vidk钳位在[-4.0, +4.0]之间。二进制PSO其他部分与基本连续PSO类似。实验结果显示, 在大多数测试函数中, 二进制PSO都比遗传算法速度快, 尤其在问题的维数增加时。

《2.3解决混和整数非线性规划 (MINLP) 问题的PSO》

2.3解决混和整数非线性规划 (MINLP) 问题的PSO

如果用离散数字来表达当前的位置和速度, 或者在速度更新完成后对整数变量进行取整运算, 则可以在算法中同时处理连续和离散变量。这就为解决MINLP等问题提供了广阔天地, 文献[5]中已将解决MINLP的PSO用于无功功率和电压的控制问题。

《3 PSO的变化和改进》

3 PSO的变化和改进

PSO与GA有很多共同之处, 两者都随机初始化种群, 使用适应值来评价系统和进行一定的随机搜索。但PSO是根据自己的速度来决定搜索, 没有GA的明显的交叉和变异。如果将pbest也看作是种群的成员, 那么PSO也有一种很弱形式的选择[6]。速度更新方程中如果没有vidk项, 可以解释为一种代数交叉, 而对vidk更好的理解是把每次迭代看成是一种不断适应的过程。GA中染色体共享信息, 故整个种群较均匀地向最优区域移动。在PSOgbest (或者lbest) 将信息传给其他粒子, 是单向的信息流动, 多数情况下, 所有的粒子可能更快地收敛于最优解。由于每个粒子在算法结束时仍然保持着其个体极值, 因此, 如将PSO用于调度和决策问题时, 可以给出多种有意义的选择方案。而基本遗传算法在结束时, 只能得到最后一代个体的信息, 前面迭代的信息没有保留。另外, PSO算法对种群大小不十分敏感, 即种群数目下降时性能下降不是很大。

PSO收敛快, 特别是在算法的早期, 但也存在着精度较低, 易发散等缺点。若加速系数、最大速度等参数太大, 粒子群可能错过最优解, 算法不收敛;而在收敛的情况下, 由于所有的粒子都向最优解的方向飞去, 所以粒子趋向同一化 (失去了多样性) , 使得后期收敛速度明显变慢, 同时算法收敛到一定精度时, 无法继续优化, 所能达到的精度也比GA[7], 因此很多学者都致力于提高PSO算法的性能。

《3.1收敛速度的改进》

3.1收敛速度的改进

《3.1.1 惯性权重 (inertia weight) 法 》

3.1.1 惯性权重 (inertia weight) 法

Shi等提出了惯性权重的方法[8]。惯性权重w是与前一次速度有关的一个比例因子, 而速度更新方程为

vidk+1=wvidk+c1rand1k(pbestidk-xidk)+c2rand2k(gbestdk-xidk)(6)

用惯性权重来控制前面的速度对当前速度的影响, 较大的w可以加强PSO的全局搜索能力, 而较小的w能加强局部搜索能力[9]。基本的PSO可以看作w=1, 因此在迭代后期缺少局部搜索能力。实验结果表明, w在[0.8, 1.2]之间PSO有更快的收敛速度。文献[10]中试验了将w设置为从0.9到0.4的线性下降, 使得PSO在开始时探索较大的区域, 较快地定位最优解的大致位置, 随着w逐渐减小, 粒子速度减慢, 开始精细的局部搜索 (这里w类似于模拟退火中的温度参数) 。该方法加快了收敛速度, 提高了PSO算法的性能。当待解问题很复杂时, 该法使得PSO在迭代后期全局搜索能力不足, 导致不能找到要求的最优解, 这可以用自适应改变惯性权重来克服。

《3.1.2 模糊惯性权重 (fuzzy inertia weight) 法 》

3.1.2 模糊惯性权重 (fuzzy inertia weight) 法

Shi等提出用模糊控制器来动态自适应地改变惯性权重的技术[11] 。控制器的输入是当前惯性权重w和当前最好性能评价值 (CBPE) , CBPE 衡量PSO目前找到的最好候选解的性能;输出是w的改变量。由于不同的问题有不同范围的性能评价值, 因此需要对CBPE进行如下的规范化

ΝCBΡE=CBΡE-CBΡEminCBΡEmax-CBΡEmin(7)

NCBPE是规范化后的评价值, CBPEmin和CBPEmax依问题而定, 且需事先得知或者可估计。

模糊w法与线性下降w方法的比较结果显示, 后者不知道应该降低w的合适时机, 而自适应模糊控制器能预测使用什么样的w更合适, 可以动态地平衡全局和局部搜索能力。但是由于需知道CBPEmin和CBPEmax等, 使得模糊权重法的实现较为困难, 因而无法广泛使用[3]

《3.1.3 压缩因子 (constriction factor) 法 》

3.1.3 压缩因子 (constriction factor) 法

Clerc得出结论:压缩因子有助于确保PSO算法收敛[12]。这种方法的速度更新方程为

vidk+1=χ(vidk+c1rand1k(pbestidk-xidk)+c2rand2(gbestdk-xidk))(8)

其中χ=2/|2-φ- (φ2-4φ) 1/2|为压缩因子, φ=c1+c2, 且φ>4。

约束因子法控制系统行为最终收敛, 且可以有效搜索不同的区域, 该法能得到高质量的解, 如果与此同时将每维vd max设置为一维搜索空间的大小xd max, 则可以得到更好的效果。

《3.1.4 选择 (selection) 法 》

3.1.4 选择 (selection) 法

Angeline提出的混和PSO主要应用PSO的基本机制以及演化计算所采用的自然选择机制[6]。由于PSO搜索过程依赖pbest 和gbest, 所以搜索区域有可能被他们限制住了。自然选择机制的引入将会逐渐减弱其影响[1]。测试结果显示, 虽然在大多数测试函数中选择法取得了比基本PSO更好的效果, 却在Griewank函数上得到了较差的结果。因此该法提高了PSO的局部搜索能力, 但同时削弱了全局搜索能力[3]

《3.1.5 繁殖 (Breeding) 法 》

3.1.5 繁殖 (Breeding) 法

LØvbjerg等人将遗传算法中的复制和重组这些称为繁殖的操作加入到全局版PSO中, 该方法是对按概率Pi选出的粒子进行如下式

child1(Xi)=piparent1(Xi)+(1.0-pi)parent2(Xi)(9)child2(Xi)=piparent2(Xi)+(1.0-pi)parent1(Xi)(10)child1(Vi)=parent1(Vi)+parent2(Vi)|parent1(Vi)+parent2(Vi)||parent1(Vi)|(11)child2(Vi)=parent1(Vi)+parent2(Vi)|parent1(Vi)+parent2(Vi)||parent2(Vi)|(12)

的代数杂交操作, 产生子代的粒子取代父代。选择父代没有基于适应值, 防止了基于适应值的选择对那些多局部极值的函数带来潜在问题[3]pi是 (0, 1) 间的随机数 (经验值约为0.2) 。理论上讲繁殖法可以更好地搜索粒子间的空间, 2个在不同次优峰处的粒子经繁殖后, 可以从局部最优逃离。结果显示, 对单峰函数, 繁殖法虽略加快了收敛速度, 却不如基本PSO和GA找到的解好, 而对于多局部极值的函数, 繁殖PSO不仅加快了收敛速度, 而且找到了同样好或更好的解[13]

《3.2增加多样性的改进》

3.2增加多样性的改进

《3.2.1 空间邻域 (spatial neighborhoods) 法 》

3.2.1 空间邻域 (spatial neighborhoods) 法

基本的局部版PSO中 (见式 (3) ) 粒子的邻域是基于粒子序号划分的。Suganthan提出了基于粒子的空间位置划分的方案[14]。在迭代中, 计算每一个粒子与群中其他粒子的距离, 记录任何2个粒子间的最大距离为dmax。对每一粒子按照

Xa-Xb/dmax(13)

计算一个比值, 其中‖Xa-Xb‖是当前粒子a到粒子b的距离。而选择阈值frac根据迭代次数而变化。当另一粒子b满足‖Xa-Xb‖/dmax<frac时, 则b成为当前粒子的邻域。所有满足该条件的粒子组成Ni, 其他同原局部版PSO。应用改进的邻域规则, 且采用时变w的PSO在绝大多数测试中都取得了比全局版PSO更优良的性能。

《3.2.2 邻域拓扑 (neighborhood topologies) 法 》

3.2.2 邻域拓扑 (neighborhood topologies) 法

基本局部版PSO (见式 (3) ) 每个粒子左右两边的粒子都是它的邻居, 实际上这是应用了环形拓扑。Kennedy测试了如图2所示的几种邻域拓扑结构[15]

《图1》

图1 两种可能的邻域拓扑在有些边被随机改变前后的图形

图1 两种可能的邻域拓扑在有些边被随机改变前后的图形  

Fig.1 A diagrammatic representation of two possible neighbourhood topologies, before and after edges have been randomly exchanged

结果表明, 拓扑非常影响算法的性能, 且最佳的拓扑形式因问题而定。如对有很多局部最优的函数, 轮形拓扑邻域算法能得到最好的结果, Kennedy推测, 这是由于较慢的信息流动;而对于单峰函数, 星形拓扑邻域算法可以产生较好的结果, 因为它有较快的信息流动 (这里的拓扑都是在粒子序号空间下的拓扑) 。

《3.2.3 社会趋同 (social stereotyping) 法 》

3.2.3 社会趋同 (social stereotyping) 法

Kenney提出了混和空间邻域和环形拓扑方法的另一个局部PSO版本, 称为社会趋同法[16]。因为生活中人们往往是试图追随一个群体的共同观点, 而不是群体中某个人的立场。将该思想应用到PSO中, 即不用每个粒子的经验而是用它所属空间聚类的共同经验来更新自己。

《3.3全局方法》

3.3全局方法

《3.3.1 序列生境技术 (SNT, sequential niche technique) 法 》

3.3.1 序列生境技术 (SNT, sequential niche technique) 法

Beasley等提出的最初使用在遗传算法中的序列生境技术可以系统地访问每一个全局极值[17]。其思想是在找到每一个极值后, 都用下降函数来自适应地改变适应值函数, 如此算法就不会再回到该极值。虽然将SNT引入PSO会带来诸如参数选择、引入更多局部极值等问题, 但是该法能够枚举所有全局极值, 在多目标优化问题上还是很有意义的[3]

《3.3.2 函数延伸 (function stretching) 法 》

3.3.2 函数延伸 (function stretching) 法

为了减小定位所有全局极值的花费, Parsopoulos等将自适应改变目标函数方法应用到了PSO中[9]。他提出一个两步的转化过程来改变目标函数, 以防止PSO返回已经找到的局部极值。该方法能跳出局部最优, 有效定位全局最优点, 有助于PSO稳定地收敛, 虽然增加了计算量, PSO的成功率却有明显的提高。但该方法不能枚举全部最优。

《3.4动态目标函数》

3.4动态目标函数

很多现实优化问题的目标函数是随时间变化的, 因此已经有很多学者开始致力于这方面的研究。Parsopoulos等的试验表明, 基本PSO就可以有效而稳定地在噪声环境中工作, 且在很多情况下, 噪声的存在还可以帮助PSO避免陷入局部最优[18]。Carlisle等的研究得出PSO不能跟随一个非静态的目标函数。Eberhart等提出一种动态惯性权重法以试图解决这一问题[2], 该方法令w=0.5+r (t) /2.0, r (t) 是 (0, 1) 间的随机数 (w的平均值为0.75) , 常数c1=c2=1.494, 这是受到Clerc压缩因子方法的启发而得出的。结果显示PSO能跟随非静态目标函数, 比进化规划和进化策略得到的结果精度更高[3]

《3.5其他改进》

3.5其他改进

《3.5.1 保收敛PSO (guaranteed convergence PSO) 》

3.5.1 保收敛PSO (guaranteed convergence PSO)

若粒子的当前位置恰是全局最好位置, 那么速度更新方程式 (6) 就只剩下vidk, 这将会导致早熟。文献[19]中提出一种确保PSO收敛到局部最优的改进方法 (GCPSO) , 其策略是对全局最好粒子用一个新的更新方程, 方程将该粒子的位置复位到全局极值点, 并且使其在全局最好位置附近产生一个随机搜索, 而其他粒子仍用原方程更新。该方法较基本PSO的在收敛速度上有很大提高, 尤其是当粒子数较少时, 在单峰函数中性能提高明显。但是该改进同基本PSO一样不能保证算法收敛到全局最优。

《3.5.2 协同PSO (cooperative PSO) 》

3.5.2 协同PSO (cooperative PSO)

文献[20]提出了一种协同PSO, 该方法是将n维向量分到n个粒子群中, 每个粒子群优化一维向量, 评价适应值时将分量合成一个完整向量。例如针对第j个粒子群, 除第j个分量外, 其他n-1个分量都设为最好值, 不断用第j个粒子群中的粒子替换第j个分量, 得到第j维的最好值, 其他维相同。为将有联系的分量划分在一个群, 可将n维向量分到k个粒子群来优化, 则前n mod k个粒子群是「n/k?维的, 后k- (n mod k) 个粒子群是?n/k?维的。称这种算法为CPSO-Sk, 它在某些问题上有更快的收敛速度, 但该算法容易被欺骗, 而GCPSO可以保证收敛到局部最优解, 因此作者又将这两种方法结合, 结果显示, 结合版拥有两者的优点, 取得了较好的效果[3]

《4 PSO的应用》

4 PSO的应用

PSO的优势在于算法的简洁性, 易于实现, 没有很多参数需要调整, 且不需要梯度信息。PSO是非线性连续优化问题、组合优化问题和混合整数非线性优化问题的有效优化工具[1]。目前已经广泛应用于函数优化、神经网络训练、模糊系统控制以及其他遗传算法的应用领域。PSO最初应用到神经网络训练上, 在随后的应用中, PSO又可以用来确定神经网络的结构。作为演化神经网络的例子, Eberhart等已经成功用PSO来分析人类的帕金森综合症等颤抖类疾病[21];Tandon用PSO训练控制铣削过程的神经网络[22];文献[23]中用改进的速度更新方程训练模糊神经网络。Parsopoulos等将PSO用于解决多目标优化问题、最小最大化问题、整数规划问题和定位所有全局极值等问题。

一般说来, PSO比较有潜力的应用包括系统设计、多目标优化、分类、模式识别、调度、信号处理、决策、机器人应用等。其中具体应用实例有:模糊控制器设计、车间作业调度、机器人实时路径规划、自动目标检测、时频分析等[2]

《5 仿真》

5 仿真

为了检验算法的性能, 笔者按照图2的流程框图编写了仿真程序, 对两例优化问题进行求解。

《图2》

图2 PSO流程图

图2 PSO流程图  

Fig.2 PSO flow chart

例1 混合整数优化问题[24]

minx,yf(x,y)=0.6224(0.0625y1)x1x2+1.7781(0.0625y2)x12+3.1661(0.0625y1)2x2+19.84(0.0625y1)2x1s.t.g1(x,y)=0.0193x1-0.0625y10g2(x,y)=0.00954x1-0.0625y20g3(x,y)=750×1728-πx12x2-4πx13/30g4(x,y)=x2-2400

表1是各种算法对例1的仿真计算结果。采用线性下降惯性权重从0.9到0.4的PSO和压缩因子c1=c2=2.05的PSO两种方法, 得到了同样好的结果, 惯性权重法得到该解的概率更高。

表1 仿真例1的各种算法计算结果比较

Table 1 Comparison among the results of various algorithms in example 1

《表1》


IDCNLPSAMVEPMIHDE空间收缩PSO

x1
48.380 758.290 051.195 848.576 542.006 042.098 44

x2
111.744 943.693 090.782 1110.055 9183.047 3176.636 66

y1
181816151313

y2
101010877

g1
-0.191 3-0.025 0-0.011 90.000 0-0.001 8-6.790×10-8

g2
-0.163 4-0.068 9-0.136 6-0.036 6-0.036 8-0.035 88

g3
-75.87506.5496-13584.56310.0000-29169.0801-0.07965

g4
-128.255 1-196.307 0-147.217 9-129.944 1-56.952 7-63.363 34

f
8048.61907197.77108.61606370.70356193.77886059.71533

例2 Schaffe提出的实例[25]

minf(x)=sin2x12+x22-0.5[1+0.001(x12+x22)]2|xi|100

已知全局最优点是 (0, 0) , f (x) 为 -0.5。由于其强烈的振荡性以及全局最优点被无限个局部最优点包围的特性, 一般优化算法很难找到它的全局最优值。PSO算法的运行结果如表2。两种方法都只需要迭代200次, 即可找到以上最优值, 且耗时只有十几毫秒。

表2 仿真例2的PSO算法计算结果

Table 2 Results of the PSO simulated procedure in example 2

《表2》


惯性权重0.9~0.4线性下降的PSO使用约束因子的PSO

x1
-3.416 583×10-5-5.412 430×10-5

x2
-2.828 398×10-6-2.138 258×10-7

f (x)
-0.5-0.5

2个实例的仿真表明, 用基本PSO很难得到满意的结果, 而这里采用的两种改进方案都十分简单、有效。

《5 结语》

5 结语

粒子群优化算法是一种新兴的有潜力的演化算法, 但还存在一些问题, 在这一点上它与遗传算法很类似。

1) PSO在实际应用中被证明是有效的, 并没有给出收敛性、收敛速度估计等方面的数学证明。文献[12,26]中对收敛性等做了一些研究, 但是目前其理论和数学基础的研究还很不够。

2) 利用不同问题的特点设计出相应有效的算法, 是非常有意义的工作。因此当前针对具体应用问题深化研究PSO算法是值得提倡的工作。

3) 应该致力于补充和扩展PSO与其他算法或技术的结合, 解决PSO易陷入局部最优的问题。

目前我国已有学者开始了对PSO的研究[7,27], 希望PSO可以为优化研究工作带来更多的新思路。