一种基于中间结构层的分层粒子群算法

刘 昕，皮建勇

(1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025；2.贵州大学 云计算与物联网研究中心，贵州 贵阳550025)

一种基于中间结构层的分层粒子群算法

刘 昕1,2，皮建勇1,2

(1.贵州大学 计算机科学与技术学院，贵州 贵阳 550025；2.贵州大学 云计算与物联网研究中心，贵州 贵阳550025)

针对标准粒子群算法易陷入局部极值和优化精度较低的缺点，结合复杂系统理论提出一种多层次粒子群算法，通过在算法结构中引入中间结构层，分别定义了进行大范围的较优值搜索的粒子和在较优值周围进行精细搜索的粒子，增加了粒子群的多样性，有效协调了粒子的寻优能力。采用了两种标准测试函数对算法性能进行了实验，结果表明，该算法可有效避免陷入局部最优，并在保证运行速度的同时提高了求解精度。

粒子群优化算法；分层结构；粒子群多样性

0 引言

粒子群算法是基于群体智能理论的优化算法，其原理和机制简单、清晰、易于实现，并且所需参数少、收敛速度快、鲁棒性强，是智能优化算法中的一个研究热点，目前已广泛应用于函数寻优、系统建模、决策支持以及模糊系统控制等诸多领域。

粒子群算法是典型的群智能算法，而群智能系统实际上是一类复杂系统，这类系统具有自适应性、涌现性和开放性，研究者通常会引入中间结构层来研究复杂系统。中间结构层属于一种模块化和损害控制策略，借助中间结构层可以更容易研究复杂系统中各组成部分之间相互作用所涌现出的特性与规律。

本文基于复杂系统理论，在粒子群算法中引入中间结构层，提出了一种多层次粒子群算法，此算法改进了粒子间信息的共享方式，增强了粒子多样性。实验证明，该算法在保证收敛速度的同时，可以有效跳出局部极值，并提高算法的全局搜索能力和求解精度。

1 标准粒子群算法

1.1 标准PSO

粒子群优化算法(Particle Swarm Optimization, PSO)是人们在研究鸟类的群体行为基础上提出的一种群智能算法，其基本思想是通过群体中个体之间的协作和信息共享来寻找最优解[1]。在算法中，每个优化问题的潜在解被抽象成D维搜索空间上的一个点，称之为“粒子”，粒子通过跟踪“个体极值(pbest)”和“全局极值(gbest)”来更新自己的位置。算法流程如下：

(1)初始化一群随机粒子(种群规模为m)，初始化内容包括粒子的速度信息与位置信息；

(2)计算每个粒子的适应值，即目标函数值；

(3)对每个粒子，将其适应值与其经过的最优位置作比较，适应度高的成为个体的当前Pbest；

(4)对每个粒子，将其适应值与群体所经过的最好位置作比较，适应度高的作为当前的全局最优解Gbest;

(5)根据速度和位置更新公式调整粒子速度和位置；

(6)未达到结束条件则转(2)。

算法终止条件一般为最大迭代次数或粒子群搜索到的最优位置，满足预定最小适应阈值。

在PSO中，速度决定了粒子运动的方向和速率，位置则是粒子所代表的解在解空间的位置，是评估该解质量的基础。

速度更新公式和位置更新公式如下:

(1)

(2)

其中i=1,2,…,m；d=1,2,…D。

式(1)的第一部分表示上次速度的影响，w是惯性权重，它使粒子保持运动惯性，使其有扩展搜索空间的趋势，有能力探索新的区域。第二部分来自于粒子个体的经验，是从当前点指向粒子历史最好点的一个矢量；第三部分是一个从当前点指向种群最好点的矢量，反映了粒子间的全局协同合作和知识共享。其中c1和c2代表加速系数，即个体经验与社会经验对粒子的影响程度。Rand是随机数。m为种群规模，一般设置在20～100之间，若侧重于减少运行时间，则种群规模可设为40左右，若偏向于高精度和高稳定性，则可设为60或80。

1.2 相关研究

PSO算法既有深刻的智能背景、适合科学研究，又简单易实现、适合工程应用。因此一经提出便引起信息和进化计算科学领域学者们的广泛关注，形成了一个新的热点，目前已有大量研究者从参数设置、拓扑结构等角度对传统PSO进行了研究与改进。

1.2.1 参数设置

粒子群算法所需参数少，但是对参数依赖性较大，因此相关参数的设定对PSO的优化性能有着重要影响。

惯性权重方面：研究表明较大的惯性权重有利于粒子群在更大的解空间内进行搜索，从而跳出局部最优值，而较小的惯性权重有利于算法的收敛。SHI等人提出了惯性权重随着迭代次数线性递减的模型。一般情况下将惯性权重的初始值设置为0.9，随着迭代次数递减到0.4，算法开始阶段，大的惯性权重可以使算法不容易陷入局部最优，到算法的后期，小的惯性权重可以使收敛速度加快，使收敛更加平稳[2]。

加速系数方面：一般被设为相同的值，最常见的是2，另一个常见的取值为1.494 45。彭宇等人利用方差分析法分析了惯性权重和加速系数对算法性能的影响，并给出了这两种参数的设置参考原则[3]。ZHAN等提出了一种使用聚类的方法对进化状态进行判断并且对加速系数进行相应调整的方案[4]。

1.2.2 拓扑结构研究

在PSO算法中,粒子之间通过相互学习寻找最优解，这种学习通过共享粒子所发现的最优解来实现，所以粒子之间的信息共享方式对算法的性能有着至关重要的影响，粒子之间的信息共享方式体现为粒子群的邻域拓扑结构，因此，对粒子群的邻城拓扑结构进行研究也十分重要[5]。KENNEDY最早开始对PSO算法中的邻域结构进行研究，提出了几种经典的邻域拓扑，并从小世界网络模型出发，对PSO算法中的邻域拓扑进行了初步的探索[6]。MENDES较为系统地分析了粒子群体中的拓扑结构对PSO性能的影响，并肯定了粒子群的拓扑结构对PSO算法的鲁棒性和执行性能有直接的作用[7]，其研究发现，粒子个体间社会交互的平均连接度越高，群体中的信息传播速度就越快，但是发生早熟收敛的风险也越大[7]。

2 多层次粒子群算法

2.1 中间结构层

中间结构层是处理复杂系统的一种方法。复杂系统中，在组分和系统之间经常会涌现出一些中间结构，称为“集体”，一个集体可能具有复杂的内部结构，但外表上呈现为一个整体单位，作为一个单位与其他集体进行相互作用。

集体具有强的内聚和弱的外部耦合，比单个组分更适合作为“个体”来处理。借助集体，可能相互作用和不可能相互作用的组分之间有了一个确定的概念性区别，而集体构成的中间结构层可将复杂系统问题分解为更简单、易处理的两个部分：集体分析研究集体的内部结构和集体行为，系统分析研究集体对于系统整体行为的贡献。

由于粒子群属于一类复杂系统，本文将在粒子群系统中引入中间结构层，构成“基础粒子层-集体层-系统”的多层次粒子群结构，通过定义不同类型的集体达到增加粒子多样性的目的，并通过改进集体之间的交流方式改善粒子群算法的性能。

2.2 多层次PSO算法

2.2.1 算法思想

传统粒子群算法易于过早收敛，其主要原因在于进化过程中粒子的多样性损失过快，所有的粒子依循相同的方式飞行，很容易造成所有粒子搜寻方向雷同，所以本文通过定义不同类型的集体，使属于不同类型集体的粒子按照不同的搜索策略进化，来增强粒子的多样性，提升粒子的寻优能力。

首先定义F类集体，速度更新公式如下：

(3)

F类集体的目的是尽可能在解空间进行大范围的搜索，惯性权重将保持固定的较大值，为了避免过早陷入局部极值，F类集体的搜索策略注重于个体经验，而削弱全局经验的影响，即它将仅受到自身经验与集体内部产生的全局最优值的影响。

其次定义用于精细搜索的S类集体，速度更新公式如下：

(4)

S类集体的目的是帮助算法更好地收敛，惯性权重将保持固定的较小值，S类粒子参考所有类型的集体的社会经验产生的较优值，并在其周围进行精细搜索，最终得到全局最优值。

算法思想：由F类集体进行大范围的较优值搜索，并产生初步最优值FGBEST反馈给S类集体；而S类集体则在初步最优值周围进行精细搜索，并产生本次迭代的最终最优值SGBEST。之后的每次迭代中，F类集体继续寻找其他较优值，而S类集体综合考虑两类集体粒子产生的最优值，并在其附近进行精细搜索。

2.2.2 算法流程

(1)初始化一群随机粒子(种群规模为m)，初始化的内容包括粒子的速度和位置信息、粒子所属的集体类型；

(2)计算每个粒子的适应度(即目标函数值)；

(3)对每个粒子，将其适应值与其经过的最优位置作比较，适应度高的成为个体的当前Pbest；

(4)对F类粒子，将其适应值与集体所经过的最好位置作比较，适应度高的作为当前集体内的最佳位置即Fgbest，并反馈给S集体；对S类粒子，将其适应值与集体内所经过的最好位置比较，适应度高的作为集体内最佳位置即Sgbest；

(5)根据速度和位置更新公式调整粒子速度、位置；

(6)未达到结束条件则转(2)。

结束条件为最大迭代次数或Sgbest满足预定最小适应阈值。

3 实验

3.1 参数定义与测试函数

实验采用两种标准测试函数即Sphere函数、Griewank函数对算法进行性能测试，其中Sphere函数是单峰函数，主要用于测试算法的收敛速度和求解精度；Griewank函数是典型的非线性多模态函数，是具有广泛的搜索空间并且具有大量局部最优点的多峰函数，算法很容易陷入局部最优，此函数通常被认为是优化算法很难处理的复杂多模态问题，因此本文用Griewank函数测试算法的全局搜索能力。

Sphere函数表达式如下：

(5)

Griewank函数表达式如下：

(6)

3.2 集体内粒子数对多层次PSO的影响

多层次粒子群算法中，粒子分为在解空间内迅速进行大范围搜索的F集粒子、在初步较优值周围进行精细搜索的S集粒子。本文在粒子群种群数目为30、60、90的情况下，对两种类型粒子的数量对算法性能的影响做了实验。实验平台为MATLAB2012，S集体的w=0.9，c1=c2=0.5；S集的w=0.4，c1=c2=1.494 45；算法最大迭代次数为1 000次；对每个函数的测试均运行50次，结果取平均值。实验结果如表1、表2所示。

表1 Sphere函数

注：F集粒子数量为：mF，S集粒子数量为：mS

表2 Griewank函数

实验结论：

(1)在种群规模不变的情况下，用于快速搜索的F集粒子少于精细搜索的S集粒子时，寻优精度较高，当F集体粒子与S集体粒子数量之比为1：2时，算法精度达到最高，但当F集粒子数量继续减少时，寻优能力会有所降低。

(2)由于两类集体内粒子数量之比的变化不会影响粒子群总体规模，因此对运行时间没有显著影响。

(3)当粒子规模逐渐增大时，解的质量会有所提高，但相应运行时间会有所增加。

3.3 与标准PSO的对比实验

图1 sphere函数

对比实验中，种群规模取100，F集体粒子数量与S集体粒子数量为1:2；最大迭代次数为500次；其他参数设定如3.2。实验结果如图1和表3所示。

表3 Sphere函数实验结果

从图1可以看出，多层次PSO在迭代至200次左右时即找到了全局最优值，而标准PSO是在400次之后，说明多层次PSO的收敛能力强于标准PSO，并且通过表3的实验数据可以看出多层次PSO的求解精度高于标准PSO。

从图2中可以看出，多层次PSO在算法前期的寻优精度和速度都强于标准PSO，并且由于多峰函数具有多个局部最优点，因此标准版PSO在迭代至230代左右时陷入了局部极值，而多层次PSO可以跳出局部极值继续寻优，从表4实验数据可以得出多层次PSO最终得到的最优值的质量远远高于标准PSO。

图2 Griewank函数

算法最优解运行时间/s标准PSO1．31E⁃014．046E⁃01改进多层次PSO1．21E⁃034．255E⁃01

4 结论

本文提出了一种多层次的粒子群算法，通过引入中间结构层构造了不同类型的粒子，从而增加了粒子多样性。实验证明，此改进方法能使算法有效跳出局部极值，并在保证收敛速度的同时提高了求解精度。

[1] 黄少荣.粒子群优化算法综述[J].计算机工程与设计, 2009, 30(8):1977-1980.

[2] 杨维，李歧强.粒子群优化算法综述[J].中国工程科学，2004，6(5)：87-94.

[3] 陈贵敏，贾建援，韩琪.粒子群优化算法的惯性权值递减策略研究[J].西安交通大学学报，2006，40(1)：53-56.

[4] 胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报，2007，18(4)：861-868.

[5] 王伟,李枚毅,彭霞丹.一种双层可变子群的动态粒子群优化算法[J].小型微型计算机系统,2012, 33(1):145-150.

[6] 朱艳伟,石新春,但扬清,等.粒子群优化算法在光伏阵列多峰最大功率点跟踪中的应用[J].中国电机工程学报, 2012, 32(4):42-48.

[7] 王雪飞,王芳,邱玉辉.一种具有动态拓扑结构的粒子群算法研究[J].计算机科学,2007, 34(3):205-207.

Hierarchic particle swarm algorithm based on layer of intermediate structure

Liu Xin1,2，Pi Jianyong1,2

(1.College of Computer Science and Technology，Guizhou University，Guiyang 550025，China ；2.Research Centre of Cloud Computing and Internet of Things，Guizhou University，Guiyang 550025，China )

A hierarchic particle swarm algorithm(PSO) is proposed in order to overcome the weak ability of local search of standard PSO algorithm. The proposed algorithm based on layer of intermediate structure and the particles is divided into two types. One type is used to search optimum solution fast,the other type is used to search optimum solution carefully. This method can increase diversity of particles and reduce the possibility of local minimum. The experiment performance of the propose algorithm is compared with the performance of the standard PSO using two benchmark functions.The experimental simulation results indicates that the hierarchic particle swarm algorithm can escape from local optimal solutions efficiently and the global search ability is better than standard PSO.

particle swarm algorithm; layered structure; diversity of particle swarm

TP301

A

10.19358/j.issn.1674- 7720.2017.04.008

刘昕，皮建勇.一种基于中间结构层的分层粒子群算法[J].微型机与应用，2017,36(4)：25-28.

2016-09-22)

刘昕(1992-)，女，硕士研究生，主要研究方向：群智能理论。

皮建勇(1973-)，男，博士，副教授，主要研究方向：数据挖掘、人工智能、分布式并行计算。