微粒群优化算法简介

高世博

摘 要：本文简要介绍了微粒群优化算法的原理，并对算法参数设置、核心思想等进行了分析，对算法在图像分割应用上的部分改进算法进行了简述，可为初次接触、学习、使用微粒群优化算法的研究者算法提供一定的帮助。

关键词：微粒群算法;优化算法;图像分割

1 引言

微粒群（Particle Swarm Optimization，PSO） 算法，也称为粒子群算法，是由Eberhart博士和Kennedy博士于基于对鸟群、鱼群等生物群体和人类社会行为的研究，在1995年的IEEE国际神经网络学术会议上提出的一种进化寻优算法。其基本概念源于对鸟群捕食行为简化社会模型的模拟，后来研究发现PSO是一种很好的优化工具，并被应用到各个领域。

2 微粒群算法原理简介

PSO算法中，每个优化问题的解都是搜索空间中的一只鸟，称之为“微粒”。所有的微粒都有一个被优化函数决定的适应度值，每个微粒有一个速度，决定他们飞翔的方向和距离。微粒群体根据自身所处位置，追随当前的最优微粒在解空间中搜索，达到寻优的目的。以最小优化问题为例，将PSO算法原理简介如下：

在PSO算法中，微粒的位置代表问题的可能解，通过计算微粒位置的适应度来衡量该位置的优劣。每个微粒根据自身和其它微粒的最佳位置，在解空间中向全局最优位置“飞行”，以搜索问题的最优解。

（4）式确保微粒以一定的速度飞行。

（5）式对微粒位置进行调节。

（6）式确保在指定的解空间中进行搜索。

算法程序结束条件为找到最优解（期望输出与寻优结果之差小于某一阈值ε）或达到最大迭代次数tmax。

以上各式中t表示迭代次数;ω为惯性权重，取定值或呈线性减少;c1、c2为加速常数，通常在0～2之间取值;r1、r2为两个相互独立的生成函数，产生在（0，1）之间的随机数。

3 微粒群算法参数简介

PSO算法参数包括群体规模m，惯性权重ω，最大速度Vmax，加速常数c1和c2，最大迭代代数tmax。

群体规模微粒数m：一般取20～40。对于大部分的问题10个微粒已经足够可以取得好的结果。微粒的范围由优化问题决定，每一维可设定不同的范围，对于大规模问题可选取相对大的值。

惯性权重ω ：惯性权重ω控制着微粒的先前速度对当前速度的影响程度，使微粒保持运动的惯性，使其有扩展搜索空间的趋势，从而有能力探索新的区域。惯性权重ω使算法具有全局搜索的能力，改变其取值可以调整算法全局和局部搜索能力的平衡。

最大速度Vmax ：最大速度决定在当前位置与最优位置之间区域的分辨率，决定微粒在一个循环中最大的移动距离，可以防止计算溢出，通常设定为微粒的范围宽度。同惯性权重ω一样，它也起着平衡全局和局部搜索能力的作用。一般将速度限值Vmax，d设置为每维变量的变化范围。

加速常数c1和c2：加速常数也称为学习因子，代表将每个微粒推向Pi和Pg位置的统计加速项的权重。低的c1和c2值允许微粒在被拉回来之前可以在目标区域外徘徊，而高的c1和c2值将导致微粒突然的冲向或者越过目标区域。学习因子c1和c2一般相同，范围在0和4之间。

最大迭代代数tmax ：根据不同的优化问题，为了实现对目标问题的优化，所需要的最大迭代次数也有所不同。合适的迭代次数需要程序设计者对具体解决的问题通过多次实验来确定。

适应度函数：适应度函数是确定微粒位置优劣的评判标准，根据处理问题的不同，需要选择的与处理问题相关的适应度函数。

4 微粒群算法核心思想讨论

（3）式体现了微粒群优化算法的核心思想，含三部分，第一部分为微粒先前行为的惯性，第二部分为“认知”部分，表示微粒本身的思考;第三部分为“社会”部分，表示微粒间的信息共享与相互合作，对其构成做如下讨论。

当c1=0，则微粒没有认知能力。在微粒的相互作用下，有能力到达新的搜索空间。它的收敛速度比标准版本更快，但是对复杂问题，比标准版本更容易陷入局部优值点。

当c2=0，则微粒之间没有社会信息共享。因为个体间没有交互，一个规模为m的群體等价于m个单个微粒的运行，因而得到解的几率非常小。

当c1=c2= 0，微粒将一直以当前的速度飞行，直到到达边界。由于它只能搜索有限的区域，将很难找到优化解。

当ω=0，则速度只取决于微粒当前的位置和它们历史最好位置Pi和Pg，速度本身没有记忆性，微粒群将收缩到当前的全局最好位置，变成一个局部优化算法，无法实现全局搜索寻优。

5 微粒群改进算法

微粒群算法提出后，在很多领域获得了广泛应用，但算法本身存在易早熟、收敛速度慢等不足。在图像分割处理中，就提出了很多改进算法，并取得了较好的应用效果。

刘洋提出，在算法运行的过程中设置一个辅助最优点Xbest，通过正交试验产生，用Xbest代替全局最优位置Pg，有效克服了算法搜索速度慢、易陷入局部最优等不足，获得了较高精度的图像分割结果。

胥田田等在算法的运行过程中，在每次迭代后的粒子群中设置粒子总数的30%认为是促进粒子群收敛的敏感粒子，根据敏感粒子适应度值与全局粒子适应度均值相比，确定算法是否陷入局部最优和出现早熟现象，从而决定是否需要初始化粒子位置及速度。结果表明此改进算法有效改善了标准粒子群算法难收敛、易早熟的缺点，在铁轨异物图像的分割应用中取得良好效果。

6 结束语

本文简要介绍了微粒群优化算法的原理、参数设置、核心理念及其在图像分割应用上的一些改进算法，希望对初次接触粒子群优化算法的研究者学习、使用微粒群优化算法提供一定帮助。

参考文献

[1]Kennedy J，Eberhart R.C.Particle Swarm Optimization [C].In： proc.IEEE Intl.conf.On Neural Networks，IV.Piscataway，NJ：IEEE Service Center，1995：1942-1948.

[2]武飞周，薛源.智能算法综述 [J].工程地质计算机应用，2005，（2）：9-15.

[3]曾建潮，介倩，崔志华.微粒群算法[M].北京：科学出版社，2004：12-53.

[4]沈洪远，彭小奇，王俊年，等.基于混沌序列的多峰函数微粒群寻优算法 [J].计算机工程与应用，2006，（7）：36-38.

[6]谢晓锋，张文俊，杨之廉.微粒群算法综述[J].控制与决策，2003，18（2）：129-134.

[5]Shi Y，Eberhart R C.Parameter selection in particle swarm optimization [C].In：Evolutionary programming VII： Proc.Ep98.New York：Springer-Verlag，1998：591-600.

[7]Kennedy J.Thinking is social： experiments with the adaptive culture model [J].Journal of conflict resolution，1998，42（1）：56-76.

[8]刘洋.基于改进粒子群优化算法的图像分割[J].吉林大学学报（理学版），2018，56（4）：956-964.

[9]胥田田，李积英，任臻，等.粒子群优化的改进Tsallis熵图像阈值分割[J].森林工程，2019，35（1）：47-52.