一种新的简化粒子群优化算法*

李晓静

（广西幼儿师范高等专科学校，广西　南宁　530022）

一种新的简化粒子群优化算法*

李晓静

（广西幼儿师范高等专科学校，广西南宁530022）

针对粒子群算法在寻优中存在早熟和收敛精度不高等问题，论文对粒子位置的更新策略以及更新公式进行改进，提出了一种新的简化粒子群优化算法（New Simple Particle Swarm Optimization，NSPSO），并将其在15个多极值基准函数进行全局最优化测试，实验结果表明，NSPSO算法收敛的精度大大提高了，而且算法收敛速度也很快，对于高、低维复杂函数的优化均适用.

粒子群优化算法；简化公式；群体智能；全局最优

0　引言

1995年，Kennedy和Eberhart发表研究论文首次提出了粒子群优化算法[1]（particle swarm optimization，PSO），该算法是通过观察鸟群集体出动捕食的相互协助行为而提出的一种仿生优化算法，该算法收敛速度和全局优化能力均表现良好.而且该算法与遗传算法相比，算法的参数更少，使用也更简单，因此算法自提出后已被广泛用于各种工程实践的优化问题.然而，这种随机算法本身的寻优过程均是利用迭代机制进行更新，算法往往快速收敛到一定程度之后就停滞了，即所谓“早熟”.因此算法对复杂问题的收敛精度不高.针对这个问题，很多学者对粒子群算法提出了许多改进的方案，如基于逃离局部最优的DPSO[2]，去掉了飞行速度项的一种简化粒子群算法[3]，通过释放因子增强可利用的种群信息的改进算法[4]，综合学习的粒子群算法[5]（CLPSO），以及其他的改进算法[6－8].这些改进算法都在一定程度提高了算法的收敛精度，但都还没有挖掘出粒子群算法最大潜力.

群智算法或者仿生算法都存在“早熟”现象，既能抑制算法过早出现“早熟”而又能保证算法的收敛是每种群智算法的改进目标，要达成这个目标就必须在算法收敛的同时，尽可能的保持算法种群的多样性.为此，笔者提出一种新的简化粒子群算法，即NSPSO算法.算法对粒子群算法的更新策略和更新公式进行一些改进，使改进后粒子群算法在迭代优化过程时，一定程度上保持了种群的多样性，同时算法还具有抛弃某些粒子收敛停滞位置寻找新位置的能力.

1　粒子群优化算法

由于PSO优化算法是从鸟群捕食行为的基础上提出的，因此在算法中的一个粒子相当于鸟群中的一只鸟.而每一只鸟出去捕食均可能找到食物，故每一个粒子（鸟）可以视为待优化问题的一个可能解（食物），算法寻优的过程就相当于鸟群寻找食物的过程.该算法搜寻的过程需要通过每个个体的个体极值与种群极值之间的信息分享来改变搜索的路径，算法中粒子的更新公式如下：

其中，m为种群数；n为解空间的维数；Xi＝（χi1，…，χin）为第i个粒子的目前位置；Vi＝（vi1，vi2，…，vin）表示第i个粒子的飞行速度；Pi＝（pi1，pi2，…，pin）为到目前为止粒子i搜索到的最好位置，称为个体极值；Pg＝（pg1，pg2，…，pgn）为到目前为止，整个找到的最好位置，称为种群极值.j为粒子位置（共n维）的第j维；k表示进化（搜索）的代数（轮数），c1和c2为记忆因子，r1和r2为两个0～1之间产生的随机数.

事实上，通过文献[9]证明：将粒子速度vid约束在[－vmax，vmax]等价于添加约束因子α的基础上，文献[3]通过严格数学推导，证明粒子群算法的速度参数对于算法进化是无关的.如若将速度这一参数直接去掉，整个算法收敛的精度与速度会受到影响.因此，算法中的更新公式可以简化为[2]：

（3）式右边的第1项表示过去搜索结果对现在的影响，ω为惯性系数；第2项则表示粒子的自身调节进化；第3项表示粒子间的信息交流.

2　粒子群优化算法的改进

2.1减少每个粒子的更新位置

从更新式（1）和式（2）均可知，在以往的粒子群算法中，每个粒子均以更新公式进行单点位置的更新.每一轮的寻优中，算法总是将粒子的位置一次性更新，使粒子个体大幅度向个体和种群的极值靠拢，如果寻优的问题不太复杂，一般的PSO算法均可以快速的找到最优解.但是，如果待解决的问题相对来说更加复杂，且具有多个极值点的时候，算法就极可能快速的陷入某个局部最优解而无法跳出来，最后种群中的个体都“聚集”在某一个点周围，即算法出现“早熟”现象.为此，笔者借鉴蜂群算法中更新策略，提出将PSO算法在每一轮中，仅利用随机的办法生成T（T取1～5）个位置，对每个粒子的T个位置进行更新.这样，粒子在迭代更新过程中可以比较某个位置的更新是否比不更新前的位置更具有优势，优化的过程更加具有针对性，粒子的位置也是部分的、慢慢的向最优个体靠拢.

2.2保持种群的多样性

将更新公式（3）改为：

对于式中u的数学描述如下：

其中，η＝1－0.9*（max＿iter-iter）/max＿iter为0.1～1线性递增；pneighbour个体neighbour的极值，且i≠neighbour；这样可以在种群搜索的初始阶段，算法注重种群搜索的速度，而到了搜索的后半程，算法则更注重种群的多样性，避免“早熟”.

2.3添加控制参数“limit”

用于记录某个粒子被更新的次数，若某个粒子连续经过limit次迭代更新之后，其个体极值依然没有得到改善，表明该粒子（解）已经陷入局部最优，那么就要放弃这个解，并重新随机生成一个新解来代替χi，这样使粒子在迭代进化过程中完成“自救”，并能增加种群的多样性.其中

改进算法的具体实现步骤如下：

1）给定算法的参数：种群规模m；记忆因子c1，c2；影响参数ω以及最大迭代次数Gmax.

2）在待解决问题的搜索范围内随机生成m个粒子的初始位置（每个粒子有n维）；

3）根据适应度函数公式，计算每个粒子的适应值；

4）以当前每个粒子的位置作为该粒子经历的最好位置P，并求出整个种群的最优位置Pg；

5）对于种群的所有粒子（for i＝1to m）；

6）对于粒子i，在1到n个位置间随机生成T个位置，并按公式（5）对该粒子的T个位置进行更新，并记sol为粒子i更新前的位置，sne为粒子i更新后的位置；

7）对于粒子i，计算其适应值，并与更新前的适应值进行比较，若它的适应值更好，就以更新后的位置sne作为粒子i这一轮迭代的位置，同时粒子i的控制参数“limit”归0；否则，以更新前的位置sol作为粒子i这一轮迭代的位置，同时粒子i的控制参数“limit”加1；

8）对于粒子i，将其适应值与它经历过的最好位置P的适应值进行比较，若较好，则将其更新位置P；

9）对于粒子i，比较其适应值和种群中的最好位置Pg的适应值，如果它的适应值更好，更新Pg；

10）每完成一轮迭代，判断是否有粒子的控制参数“limit”达到上限，若存在，则根据（6）式生成一个新的解代替它，并将其对应的控制参数归0；

11）判断是否满足停止条件，若满足，则输出最优值，否则转到5）.

3　仿真实验及结果分析

为了验证笔者提出的改进粒子群算法的性能，选取了多个经典测试函数对新算法进行测试，其表达式如下，并将之与几种有名的改进算法：CLPSO、IPSO[5]、HPSO[6]的结果进行比较.所用的测试函数及其搜索范围、最优点、初始化范围等信息见表1：

表1　测试函数的全局最优点、搜索范围以及初始化范围Tab.1　Test global optimum function，search range and initializing range

在改进算法中，实验计算需要确定的参数c1＝c2＝2；种群规模m＝50；最大迭代次数3500次；每个函数独立运行20次；测试函数的维数是30维.对于CLPSO、IPSO、HPSO等算法均采用各自文献中的默认参数，其中他们的最大迭代次数分别是5000次，4000次和200000次.其比较结果见表2：

表2　函数为30维的测试结果Tab.2　30－dimensional function test results

从表2可以看出，笔者提出的NSPSO算法对绝大部分函数的收敛精度远高于CLPSO、HPSO和IPSO算法，而且在15个测试函数中，笔者提出的NSPSO算法有9个函数搜索到理论优解，还有一个函数（Sphere函数）其精度也几乎达到了理论值，从而证明该算法稳定性和有效性.而HPSO算法只有在第3个测试函数Ackley上测试精度最好，但其耗费的迭代次数太大.

进一步地，为了观察该算法在迭代过程中适应度值的变化情况，将NSPSO算法和CLPSO在300维的Rastrigin函数、Ackley函数、Weierstrass函数以及Griewank函数上收敛过程进行对比.见图1～4.

从图1～4的收敛曲线对比可以看出，对更高维的测试函数进行全局寻优时，NSPSO算法的收敛曲线在搜索开始后就迅速下降，随着搜索的进一步深入，笔者提出的NSPSO算法与CLPSO算法的收敛曲线的距离也越来越大（即两种算法收敛精度差距越来越大：NSPSO算法收敛速度明显快于CLPSO算法）.进一步地，从图中我们还可以看出，NSPSO算法的曲线是一直平滑的，而CLPSO的收敛曲线则在搜索的初始阶段和搜索的中期均出现一定的不规则阶梯型，即搜索出现停滞现象，这说明该算法在搜索过程中在不停的陷入局部最优解，为此，算法不得不花费一定的搜索时间逃出局部最优解，因此该算法的收敛速度和收敛精度均逊于提出的NSPSO算法.

图1　NSPSO和CLPSO对300维Rastrigin函数的收敛曲线对比图Fig.1　NSPSO and CLPSO convergence curve 300 Victoria Rastrigin function comparison chart

图2　NSPSO和CLPSO对300维Ackley函数的收敛曲线对Fig.2　NSPSO and CLPSO convergence curve dimensional Ackley function 300Comparison Chart

图3　NSPSO和CLPSO对300维Griewank函数的收敛曲线对比图Fig.3　NSPSO and CLPSO convergence curve 300 Victoria Griewank function comparison chart

图4　NSPSO和CLPSO对300维Weierstrass函数的收敛曲线对比图Fig.4　NSPSO and CLPSO convergence curve 300 Victoria Weierstrass function comparison chart

4　结论

笔者提出了一种简化的粒子群改进算法（NSPSO算法），该算法不仅去掉了标准PSO算法中的粒子飞行速度项V部分，而且也抛弃了标准PSO算法中的向个体极值靠拢和向种群极值靠拢的部分，取而代之的是论文提出的粒子更新方法：粒子以一定概率选择向其他粒子或种群极值进行部分维数邻域搜索新的位置，若搜索到的位置更好则更新粒子的位置，否则粒子的位置不更新.同时，论文还添加一个控制参数用以判断是否放弃粒子目前的位置而重新生成新的位置.实验结果表明，改进算法的全局寻优能力与其他改进算法相比具有较大优势，而且笔者的改进算法NSPSO收敛速度也快、精度也高，对于高、低维的复杂函数优化问题均可行.

[1]Kennedy J，Eberhart R.Particle Swarm optimization[C].In：IEEE Int 1Conf on Neural Networks.Perth，Austraial，1995：1942－1948.

[2]Omranpour H.，Ebadzadeh M.，Shiry S.et al.，Dynamic Particle Swarm Optimization for Multimodal Function[J].Artificial Intelligence，2012，1（1）：1－10.

[3]胡旺，李志蜀.一种更简化而高效的粒子群优化算法[J].软件学报，2006，18（4）：861－868.

[4]任小波，杨忠秀.粒子群优化算法的改进[J].计算机工程.2010，36（7）：205－207.

[5]Liang J J，Qin A K，Suganthan P N，et al.Comprehensive learning particle swarm optimizer for global optimization of multimodal functions [C].IEEE Transactions on Evolutionary Computation，2006，10（3）：281－295.

[6]纪震，周家锐，廖惠连，等.智能单粒子优化算法[J].计算机学报，2010，33（3）：556－561.

[7]Chen Chia－Chong.Hierarchical Particle Swarm Optimization for Optimization Problems[J].Tamkang Journal of Science and Engineering，2009，12（3）：289－298.

[8]刘爱军，杨育，李斐，等.混沌模拟退火粒子群优化算法研究及应用[J].浙江大学学报：工学版，2013，47（10）：1722－1730.

[9]Clerc M.The swarm and the queen：Towards a deterministic and adaptive particle swarm optimization[C].Proc.The Congress on Evolutionary Computation.Washington，1999：1951－1957.

[责任编辑 苏 琴][责任校对 黄招扬]

A New Simplified Particle Swarm Optimization

LI Xiao-jing
（Guangχi College for Preschool Education，Nanning530022，China）

Concerning the problems of premature and low convergence accuracy for the particle？swarm？algorithm in search of optimization，update strategy and formula of the particle position have been made improvements in this paper，and a new simple particle swarm optimization（NSPSO）is proposed. Through global optimization tests in 15multiple maximum benchmark functions，the experimental results show the convergence accuracy of NSPSO has improved greatly and the rate of convergence become faster，which can be applied in the optimization for high and low dimensional complicated functions.

particle swarm optimization；Simplified formula；swarm intelligence；global optimality

TP18

A

1673－8462（2015）01－0083－07

2014-09-10.

广西青年基金项目（2013GXNSFBA019227）；国家自然科学基金项目（41065002）.

李晓静（1982-），女，河南许昌人，硕士，广西幼儿师范高等专科学校讲师，研究方向：数据挖掘、应用数学.