粒子群算法的改进及其在优化函数中的应用∗

马发民 张林 王锦彪

（1.商洛学院数学与计算机应用学院商洛726000）（2.中国民航大学计算机科学与技术学院天津300000）

粒子群算法的改进及其在优化函数中的应用∗

马发民1张林1王锦彪2

（1.商洛学院数学与计算机应用学院商洛726000）（2.中国民航大学计算机科学与技术学院天津300000）

针对粒子群优化算法自身的缺陷，即随着迭代次数的增大，种群多样性减小，引起早熟现象，从而可能出现局部最优结果。而生物免疫机制能够有效地克服这些缺点，因此将粒子群算法与免疫原理有机结合起来形成免疫粒子群优化算法（IMPSO）；其次对PSO算法的惯性系数和学习因子做了一定的改进；最后通过经典优化函数的计算，验证了算法改进的效果。

粒子群优化算法；免疫原理；免疫粒子群优化算法；惯性系数；学习因子

Class NumberTP301.6

1 生物免疫原理

免疫系统是生物必要的天然防御系统，它由一些具有免疫功能的组织、器官和细胞等组成，可以减免病原体对生物机体的侵害。生物免疫系统的免疫功能是通过淋巴细胞自我调节作用来实现的。免疫系主要有B和T两类淋巴细胞。产生抗体是B细胞的主要功能，而实现免疫调节是T细胞则主要功能。从生物学的角度来讲，免疫系统具有以下几点特性［7～9］：

1）多样性：多样性是通过细胞分裂和分化、细胞变以及抗体的基因重组等方式产生大量相异抗体以此来抵御各种抗原，这样保证了免疫抗体的种群多样性和丰富性。

2）免疫自我调节：免疫系统将免疫响应的强度限定在一定水平上从而维持免疫平衡的机制。通过对抗体的抑制和促进自我调节产生适当数量的必要抗体。

3）免疫记忆特性：作为记忆细胞而被保存下来的是产生抗体的小部分细胞，形同抗原一旦再次入侵，免疫记忆库中的相应记忆细胞会迅速激发而产生大量的抗体。此功能是中医临床用于接种某些传染性疾病的疫苗注射到未受感染的体内活性低，从而产生对此类传染病的抵抗能力。

免疫系统是维护生物体健康的防御系统，生物利用该系统抵抗各种病菌入侵，该系统通过识别“自我”和“异己”抗原、免疫应答排除抗原性异物，维持生理平衡。在免疫调节过程中，浓度较低且与抗原的亲力较大的抗体将会得到促进，反之，将会受到抑制，从而保证了抗体的多样性［7］。免疫系统受到抗原入侵后做出反应，部分抗体作为记忆细胞被保留，对于同类抗原再次入侵时激活相应的记忆细胞产生抗体。免疫接种是有选择、有目的地利用待求解问题中的某些特征信息，通过免疫选择抑制进化算法在优化过程中出现的早熟、种群多样性减弱的现象，提高进化算法的性能［6～9］。

2 结合免疫机制对粒子群算法的改进

在PSO算法中粒子的种群多样性影响全局搜索能力，分析标准PSO算法得出［1］，在算法迭代过程中，所有粒子都向着最优解的方向靠近，随着迭代的进行，粒子逐渐趋于同一化，种群多样性逐渐减小，迭代后期收敛速度明显减慢甚至导致出现早熟现象，同时算法收敛到一定精度，陷入局部最优无法继续优化。为了克服PSO算法这一先天的缺陷，在PSO算法中引入了免疫机制，用人工免疫系统求解优化问题时，满足约束条件的最优解即是抗原；在进化算法中，保持抗体的多样性可以防止算法因种群多样性减弱而出现早熟并陷入局部最优解。利用“优胜劣汰”的原则通过抗体和抗原之间的亲和力来选择有效抗体，特别是当备选抗体相差不大时，“优胜劣汰”的效果更明显，搜索效率会更高［4～6，9］。

借鉴该思想，在优化算法中建立免疫记忆库用来保存历次迭代中的全局最优个体。通过浓度选择，粒子更新，替换掉种群每代进化中较差个体，提高算法种群多样性，从而较大程度上降低算法陷入局部最优。粒子浓度选择公式如下

结合免疫思想的改进PSO算法实现步骤如下：

1）确定参数值：学习因子c1和c2，种群规模为N，粒子（抗体）维度为n，最大迭代次数为runmax，免疫记忆库的记忆粒子个数为m。

初始化：随机产生N个粒子Xi及“飞行”速度Vi，Xi为待着陆航班的随机排列，Vi为随机产生的调整序，其含一个调整因子，将粒子i的初始化的位置记为历史最优位置pbesti，i=1，2，…，N，将初始化中位置整体最优的粒子记为全局最优gbest，形成初始粒子种群S0。

迭代计算形成免疫记忆库：根据式（3）和式（2）迭代计算，每次迭代将各粒子的迭代结果与当前的pbesti进行适应度值比较，若比当前pbesti优，则用本次迭代结果替换当前pbesti；同理选出适应度值最大的粒子和当前的全局最优粒子gbest比较，如果较优，则将其作为全局最优粒子，更新全局最优位置gbest，并将其加入到免疫记忆库中，如果记忆库已满，则将该粒子替换记忆库中适应度最差粒子。

图1加入免疫机制的粒子群算法流程图

2）粒子库的生成：（1）由粒子群优化算法速度和位置的更新产生N个粒子。（2）随机产生M个新粒子。

3）粒子浓度选择：用浓度选择式（1）计算步骤2）中生成的N+M个粒子的选择概率，根据大小选择N个粒子形成种群。

4）免疫选择：用记忆库中的m个粒子替换步骤2）中得到的N个粒子中适应度较差的m个粒子，得到更新后的种群Sk+1。

5）迭代终止判断：若达到最大迭代次数，或者相邻两次迭代结果误差，则终止迭代，否则转步骤3）。

3 对PSO算法系数的改进

3.1 对惯性权重的改进

惯性权重作为PSO算法最为重要的参数主要有两种情况：固定权重和时变权重。顾名思义固定权重在整个优化迭代过程中保持不变的常数权重值；而时变权重是迭代过程中在某个范围按照一定规律递减的权重［3］。为了避免算法过早收敛并加快收敛速度，Shi［2］等提出了惯性权重的方法，惯性权重决定了对粒子当前速度的继承，较大的惯性权重将使粒子具有较大的速度，从而具有较强的全局探索能力；较小的惯性权重将使粒子具有较强的局部开发能力。

不同的优化问题的惯性权重ω因优化目标和限制条件不同，所以递减的规律各不一样，对于不同问题的惯性权重ω不可能都是线性减小，特别是复杂函数优化时，即每个优化对象有自己相适应惯性权重下降曲线，寻找一条与优化对象相适应的惯性权重下降曲线是算法关键。

结合团队合作精神，即利用多条曲线减小函数，产生一组由大到小的变化曲线，把n个粒子均匀地分成l个子群，l为备选惯性权重曲线总数，根据这组曲线函数制定了一组ω，就同一优化问题的数据，进行了多次重复试验，经实验结果对比最后选取最为合适的ω。

其中s为［1，30］范围内的整数，run为当前迭代次数，runmax为最大迭代次数，s不同时有不同的曲线，当s确定之后，表达式也就确定下来，粒子群优化算法就可以按照备选惯性权重之中的某条惯性权重曲线进行计算了［10～11］。这条惯性权重曲线由下面算法自动确定。

粒子群的种群大小为n，惯性权重的曲线总数为l条，算法运行开始后粒子群分别按照各个惯性权重曲线独立运行计算，每到达规定的迭代步数后，评价各条惯性权重曲线的优劣性，删除性能最差的惯性权重曲线，此时粒子群重新独立运行剩余的3条惯性权重曲线，以此类推直到找一条较好的惯性权重下降曲线。

3.2 对学习因子的改进

同理学习因子c1，c2对继承个体最优和全局最优起着很大作用，c1越大，则受个体最优的影响越大，反之越小；c2越大，则受全局最优的影响越大，反之越小；算法开始迭代的时候，个体最优有利于全局搜索，迭代后期全局最优有利于局部搜索，所以个体最优和全局最优呈反比趋势更有利于算法搜索最优值。因此本文对学习因子c1，c2也做了相应的改进：

3.3 算法实现流程

1）设定参数s的一组值，s1，s2，…，sl共l个；2）初始化粒子群；

3）对所有粒子按照式（4～5），分别按照l条惯性权重曲线开始运行；

4）每到达规定的迭代步数后，评价各条惯性权重曲线的优劣性，删除性能最差的惯性权重曲线，此时粒子群重新独立运行剩余的l-1条惯性权重曲线，以此类推直到找一条较好的惯性权重下降曲线；

5）判断是否达到要求，如满足则结束，否则转步骤3）；

6）得到合适的s值，从而选取合适的惯性权重曲线。

3.4 改进粒子群算法在优化函数中的应用

选取的测试算例为两个经典的函数优化问题（求解最小值），分别为Keane's Bump优化问题和Griewank优化问题。通过对优化函数的测试验证了对PSO算法改进的效果。

为了更好地对比对粒子群算法的改进效果，最大迭代次数为：2000，学习因子c1=c2=2.05，惯性权重选取以下六组不同值：

1）定值0.7；

2）式（4）线性递减；

3）式（4）s=5；

4）式（4）s=9；

5）式（4）s=15；

6）式（4）s=20。

Keane's Bump函数

为了进一步确定s的值，把以上每条惯性权重分别作实验验证，平均运行100次，每10次作为一组对其平均值进行分析，表1对结果的最优值、最差值、平均值和方差以及收敛代数做了对比；图2对不同ω各运行10组后，对其结果的平均值做了折线走势对比。通过表1和图2的分析可得，当s=9所确定的ω最为理想。

表1 Keane's Bump函数结果分析表

图2Keane's Bump函数不同ω运行10组平均解分析

Griewank优化函数

约束条件为：-600≤xi≤600。

同样对Griewank优化函数也平均运行100次，每10次作为一组对其平均值进行分析，表2对结果的最优值、最差值、平均值和方差以及收敛代数做了对比；图3对不同ω各运行10组后，对其结果的平均值做了折线走势对比，详见表2和图3。

表2 Griewank函数结果分析表

图3Griewank函数10组平均结果分析

从表1和表2以及图2和图3的结果分析可以看出，在PSO算法中当学习因子确定时，对于表达式（4）所给出的不同惯性权重曲线变化，当s=9时效果最好。证明了改进的粒子群算法能够很好地平衡全局搜索和局部搜索，实现了快速、高效的收敛避免了早熟问题最终获得最优解，这有着很大的实际应用价值。

通过团体合作找到合适的ω，利用式（4）当s=9时的ω最为合适，在此条件下，利用式（5）将PSO算法中的学习因子改进成为曲线变化，并用到上述两个优化测试函数中来，得到如下分析结果。

表3 ω确定学习因子变动Keane's Bump函数结果分析表

表4 ω确定学习因子变动Griewank函数结果分析表

从表3和表4的函数优化数据分析可以看出，在ω确定的情况下，通过式（5）得出的学习因子，大大缩短平均收敛代数，从而减少计算时间，且结果更加理想。由此证明对粒子群算法的改进，在全局和局部优化搜索中能够快速收敛，高效避免早熟获得最优解，这对于研究PSO算法的实际意义较大。

4 结语

主要工作是对粒子群（PSO）算法的改进。首先综合考虑PSO算法随着迭代的进行，种群多样性逐渐降低，从而出现早熟、局部收敛的缺点，参考生物免疫系统，将免疫机制与PSO算法有机结合，得到改进的免疫粒子群优化算法。其次对改进粒子群算法中的系数惯性权重ω和学习因子c1，c2进行改进，利用团体合作思想找到合适的算法系数。最后通过经典优化函数的测试，证明了改进后的PSO算法，能够快速收敛，且有效避免早熟和局部最优的缺点，并最终获得最优解。

［1］R.C.Ebethart，J.Kennedy.A new optimizer using Particle swarm theory［C］//Proceednigs of the Sixth International Symposium on Micro Machine and Human Science，Na⁃goya，Japan，1995，6（1）：39-43.

［2］Russell C.Eberhart，Patrick K.Simpson，Roy Dobbins，Roy W.Dobbins.Computational Intelligence PC Tools［M］.Boston，MA：Academic Press Professional，1996.

［2］Shi Y，Eberhart R C.Fuzzy Adaptive Particle Swarm Opti⁃mization［C］//Proceedings of the 2001 Congress on Evolu⁃tionary Computation.Piscataway，NJ：IEEE Press，2001，9（2）：101-106.

［3］陈贵敏，贾建援，韩琪.粒子群优化算法的惯性权值递减策略研究［J］.西安交通大学学报，2006，40（1）：54-56. CHEN Guimin，JIA Jianyuan，HAN qi.Study On inertia weight decreasing strategy of Particle swarm optimization［J］.Xi'an Jiaotong University，2006，40（1）：54-56.

［4］Clerc，M.The swarm and queen：towards a deterministic and adaptive particle swarm optimization［C］//Proceedings of the IEEE Congress on Evolutionary Computation，1999，7（2）：1951-1957.

［5］薛文涛.基于免疫的智能优化算法理论及应用研究［D］.南京：南京理工大学，2008. XUE Wentao.Theory and Application of Intelligent Opti⁃mization Algorithm Based on Immune［D］.Nanjing：Nan⁃jing University of Science and Technology，2008.

［6］贾岩峰.基于免疫算法的粒子群优化算法的研究［D］.吉林：东北电力大学，2006. JIA Yanfeng.Research On Particle Swarm Optimization Algorithm Based On Immune Algorithm［D］.Jilin：North⁃east Dianli University，2006.

［7］刘红.免疫系统的现代概念（上）［J］.肾脏病与透析肾移植杂志，2001，10（1）：53-57. LIU Hong.Modern Conception of Immune System（the First）［J］.Kidney Disease and Dialysis Transplant Jour⁃nal，2001，10（1）：53-57.

［8］肖人彬，王磊.人工免疫系统：原理、模型、分析及展望［J］.计算机学报，2002，12（25）：1281-1291. XIAO Renbin，WANG lei.Artificial Immune System：prin⁃ciple，model，analysis and prospect［J］.Chinese Journal of Computer，2002，12（25）：1281-1291.

［9］孙晓亮，邵定宏.基于疫苗接种的免疫算法［J］.计算机工程与设计，2007，28（16）：3960-3962. SUN Xiaoliang，SHAO Dinghong.Immune Algorithm Based On Vaccination［J］.Computer Engineering And De⁃sign，2007，28（16）：3960-3962.

［10］雷开友.粒子群算法及其应用研究［D］.四川：西南大学计算机与信息科学学院，2006. LEI Kaiyou.Research On Particle Swarm Optimization Algorithm And Its Application［D］.Sichuan：The school of Computer and Information Science in Southwest Uni⁃versity，2006.

［11］Clerc，M.，Kennedy，J.The Particle swarm-explosion，stability，and convergence in a multidimensional com⁃plex space［J］.IEEE Transactions on Evolutionary Com⁃putation，6（1）：58-73.

Improvement of Particle Swarm Algorithm and Its Application in Optimization Function

MA Famin1ZHANG Lin1WANG Jinbiao2
（1.Institute of Mathematics and Computer Application，Shangluo University，Shangluo726000）（2.College of Computer Science and Technology，Civil Aviation University of China，Tianjin300000）

The defection of particle swarm optimization algorithm means that an increase in iterations decreases swarm diversi⁃ty and causes prematurity，thus probably producing local optimization results.However，immune mechanism of biology is capable of effectively overcoming these shortcomings.Firstly particle swarm algorithm is organically combined with immune principle to form immune particle swarm optimization algorithm（IMPSO），then certain improvements will be made in inertia coefficient and learning factor of PSO algorithm and finally effect of algorithm improvement will be verified through calculation of typical optimization func⁃tion.

particle swarm optimization algorithm，immune theory，immune particle swarm optimization algorithm，inertia coefficient，learning factor

TP301.6

10.3969/j.issn.1672-9722.2017.07.003

2017年1月18日，

2017年2月20日

国家自然科学基金项目（编号：60472121）；商洛学院自然科学研究项目（编号：15SKY007）资助。

马发民，男，硕士，讲师，研究方向：神经网络、智能优化算法。张林，男，硕士，教授，研究方向：神经网络、仿

生算法。王锦彪，男，硕士，教授，研究方向：蚂蚁算法、智能优化算法。