改进的小生境粒子群优化算法

李娜��黄治国

摘要：传统的小生境粒子群优化算法（NPSO）需要两个参数的输入，一个是判断子群合并的阈值，另一个是子群产生的阈值。参数设置的不当，将直接影响计算结果。引入一个函数判断两个点是否在同一座山峰上，以克服NPSO算法需要输入参数的弊端。在程序运行时，无须严格限定小生境的半径，也不需太多的先验知识。实验结果证明，该算法合理有效，能够能快速有效地找到多峰函数的全局最优点。

关键词关键词：小生境；NPSO算法；粒子群优化算法；多峰值函数

DOIDOI：10.11907/rjdk.143736

中图分类号：TP312

文献标识码：A文章编号文章编号：16727800（2015）002004503

基金项目基金项目：中央高校基本科研业务费专项资金项目（CZY13007）

作者简介作者简介：李娜（1981-），女，河南商丘人，博士，中南民族大学计算机科学学院讲师，研究方向为智能计算。

1小生境PSO算法

小生境（Niche）是来自于生物学的一个概念，是指特定环境下的一种生存环境。生物在其进化过程中，一般总是与自己相同的物种生活在一起，共同繁衍后代，这些生物赖以生存的环境资源，称为小生境。人们把这种思想提炼出来，运用到优化算法中来。优化算法实现小生境的方法最早由Cavicchio 于1970 年提出，该方法叫做基于预选机制的小生境方法＼[1＼]；1975年DeJong提出了基于排挤机制的小生境实现方法＼[2＼]；Goldberg 在1987 年提出了基于共享机制的小生境实现方法＼[3＼]。随着研究的深入，越来越多的小生境实现方法被提出，小生境在优化算法中的应用也越来越广泛。文献＼[4＼]提出了小生境粒子群优化算法。在标准PSO算法中，种群中的粒子会不断向当前最优位置靠拢，算法迅速收敛，但同时种群的多样性也快速下降。在NPSO算法中，若某个粒子在连续几代的进化过程中，适应度值只有很细微的变化，那么该粒子和它的邻居将就会形成一个小生境粒子群，该粒子是这个小生境粒子群的中心。具体算法如下：

Step1：初始化主粒子群，并设置小生境的参数。

Step2：主粒子群中的粒子进行速度、位置和适应度值的更新。

Step3：对每个小生境粒子群中的粒子进行速度、位置和适应度值的更新。

Step4：根据小生境半径的设置，查看是否有需要合并的小生境粒子群。

Step5：查看主群中是否有粒子进入了小生境范围，若有，则将该粒子吸收进入小生境粒子群中。

Step6：搜索主群中是否有满足产生新的小生境的条件的粒子，若有满足条件的粒子，则建立以该粒子群为中心的新的小生境子粒子群。

Step7：返回至Step2，直到满足算法终止条件。

NPSO算法实现过程中，需要输入两个参数μ和δ，μ是判断子群是否合并的阈值，δ是判断子群是否产生的阈值，算法的实现效果依赖于参数的设置。在文献[5]中，小生境子粒子群的合并依赖于参数μ，如果该参数的选择不合适，算法很容易将处在不同山峰上的两个小生境子群合并，造成寻优效率下降；在文献[4]中，新的小生境子群的产生依赖于给定的参数δ，不同的参数其算法性能也不同，算法需要先验知识才能保持其稳定性。

2改进的小生境粒子群优化算法

在NPSO进化过程中，需要根据参数μ和δ的设定进行。若有一种简单的方法能够判断两个粒子是否在同一个山峰上，此方法可以大大提高NPSO算法的收敛速度和收敛性能，也可以避免算法过于依赖参数设置。文献[6]设计了一个hillvalley函数，能够判别搜索空间的任意两点是否在同一个山峰上。将此函数应用到遗传算法上可求解多峰值问题，本文将此函数与NPSO算法相结合，进行多峰函数的求解。

设搜索空间的任意两点e1和e2，hillvalley（e1，e2）为判断e1和e2是否在同一山峰上的函数，若e1和e2不存在适应度值同时小于e1和e2适应度值的内点，则e1和e2在同一个山峰上， hillvalley函数的返回值为0，否则hillvalley函数的返回值为非0值，则e1和e2不在同一个山峰上。e1和e2之间的内点由抽样向量samples确定：

iinterio=e1+（e2-e1）·samples[j]（1）

其中，j=1，…，L，L是抽样向量samples的长度，本文中L 的取值为5。

一维hillvalley函数如图1所示，图中e1、e2之间的内点i1、i2的适应度值均大于e1和e2的适应度值，不存在适应度值小于该两点的内点，判定e1和e2在同一个山峰；图中e3和e4之间的内点i3、i4、i5、i3的适应度值大于e3和e4的适应度值，而i4、i5的适应度值小于e3和e4的，故e3和e4不在同一座山峰上。将上述hillvalley函数应用到NPSO算法中，解决NPSO算法依赖参数设置的弊端，新算法称为改进的小生境粒子群优化算法（Improved Niche Particle Swarm Optimization，INPSO）。算法具体实现如下：

Step1：参数设置及主粒子群的初始化，主粒子群以认知模型进行更新。

Step2：判断主粒子群中的每一个粒子xi是否为潜在的最优解，如果是，则产生一个以xi为中心的小生境子粒子群。判断最优解时，设粒子xi的适应度值变化为σi，在算法进化过程中若在连续几代（本算法中设置是5代）内均满足σi<δ （δ设定的一个很小的阈值），则产生新的小生境子群。

Step3：对每一个子群中的粒子进行迭代。

Step4：对所有子群进行合并操作，当任意两个子群的最优粒在同一个山峰时，合并这两个子群。假设子群Di（i≥1） 的最优粒子xm，子群Dj（j≥1）的最优粒子xn处于同一山峰时，即hillvalley（xm， xn）=0时，合并两个子群。合并后的子群粒子数目变大，保留适应度值较好的R个粒子，其余粒子移到主粒子群中。

Step5：对每个子群进行吸收粒子的操作，主群中的粒子xm移动到小生境的Di（i≥1）范围内，即对于任意xm∈Di 都有hillvalley（xm， xn）=0，且Di中的粒子数目小于R，则粒子xm被吸收到小生境子粒子Di中，若Di中的粒子数目等于R，用xm替换Di中适应度值最小的粒子。

Step6：判断是否满足终止条件，若不满足转到Step2。

图1hillvalley函数

3实验分析

为了验证INPSO算法的有效性，针对3个典型的多峰函数做了两组实验，第一组实验测试算法能否搜索到多峰函数的所有山峰；第二组实验测试算法的精度。测试函数如下：

（1）f1（x）=xsin（10πx）+2.0，x∈（-1，2） 。该函数具有17的局部最大值，这些峰值大小不等，间隔相等，当x=1.850 549时，函数有全局最大值[7]为3.850 274。

（2）f2（x）=∑5i=1icos[（i+1）x+i]，x∈（-10，10） 。

函数具有19个局部极大值，当x=-7.083 5、-0.800 3、5.482 9时，函数有3个全局最大值：14.508 008。

（3）f3（x，y）=cos（x）2+sin（y）2，x∈（-5，5），y∈（-5，5） 。函数具有12个局部极大值2。

测试中的参数设置为：迭代次数50，惯性权重ω=0.729 ，学习因子c1=c2=1.49，实验结果为30次独立实验的平均值。

第一组实验是为了验证新算法的有效性，函数f1和f2的初始种群规模为100，函数f3的初始种群规模为80。

图2小生境子群最优值

3个函数运行的结果如图2所示，其结果是30次运行结果的平均值。图中星星表示粒子，a、b、c图是函数的图形表示，d、e、f图是小生境子群中最优粒子在图形中的位置。d图是函数f1的运行结果，基本上最优的粒子都爬到了山峰的顶端。e是函数f2的运行结果，所有的峰值都有粒子。f1和f2是的维度是一维，函数f3的维度设定为二维。f图是函数f3的俯视效果图，图上的白色星星表示粒子。从图形上可以看出粒子处在山峰的顶端位置，本算法能够找到所有的峰值。因此，本算法对多元函数仍然适用。

第二组实验是为了验证新算法的有效性，将本文所得测试结果与NPSO算法＼[8＼]所得结果进行对比分析。参数的设置和第一组实验中的参数设置基本相同，个别参数设置如表1所示。本文INPSO算法不需要设置参数，是否合并两个子群由hillvalley判断两个子群中的最优粒子是否在同一山峰上实现。两种算法的实验对比结果如表2所示。

2上都得到了较好的结果，收敛率是100，而在二维函数运行上INPSO算法每次都能搜索到函数的全部峰值，而NPSO算法只有26次找到全部峰值，收敛率87%。另外，INPSO算法搜索到每个峰值的平均位置偏差要比NPSO算法要小，说明本文提出的INPSO算法的精确度高于NPSO算法。

4结语

本文引入一个函数判断两个粒子是否在同一座山峰上，克服了NPSO算法需要输入两个参数的弊端。通过对3个典型函数的优化实验可以看出，本文所提出的算法能够找到多峰函数的所有峰值，并且在平均偏离度和收敛率上都优于NPSO方法，是一种有潜力的优化方法。改进后的小生境粒子群算法有更强的全局搜索能力和更高的收敛速度，能够高效地寻找到多个全局最优值 是一种寻优能力、效率和可靠性更高的优化算法，其综合性能比基本NPSO 算法有显著提高。

参考文献参考文献：

＼[1＼]CAVICCHIO D J.Adaptive search using simulated evolution＼[D＼].Michigan，Arbor Illinois：University of Michigan， 1970.

＼[2＼]DeJong K A.An analysis of the behavior of a class of genetic adaptive systems＼[D＼]. Michigan： University of Michigan， 1975.

＼[3＼]GOLDBERG D E，RicharDson J J. Genetic algorithms with sharing for muhimodal function optimization＼[C＼].Proc of the 2rid International Conference on Genetic Algorithms，1987：2736.

＼[4＼]BRITS R， ENGELBRECHT A P， VAN DEN BERGH F.A niching particle swarm optimizer＼[C＼].Proc of the 4th AsiaPacific Conf On Simulated Evolution and learning，2002： 692696.

＼[5＼]王俊年，申群太，沈洪远，等.一种基于聚类的小生境微粒群算法＼[J＼].信息与控制，2005，35（6）：680684.

＼[6＼]R K URSEM.Multinational evolutionary algorithms＼[C＼].Washington：Proceedings of Congress of Evolutionary Computation，1999（3）：16331640.

＼[7＼]王小平，曹立明.遗传算法——理论、应用与软件实现＼[M＼].西安：西安交通大学出版社，2002.

＼[8＼]S W.MAHFOUD.A comparison of parallel and sequential niching methods＼[C＼].California：Proceedings of the Sixth International Conference on Genetic Algorithms，1995：136143.

责任编辑（责任编辑：孙娟）