一种改进的粒子群优化算法



一种改进的粒子群优化算法

主要研究信息安全、计算机视觉。

徐仙伟，杨雁莹，曹霁

(南京森林警察学院信息技术系，南京 210023)

摘要：标准粒子群算法能够解决各类优化问题，得到了广泛的应用，也引起很多研究人员的关注。为了提高全局搜索能力，使其不易陷入局部最优，提出了一种新的优化策略。首先，采用了佳粒子的概念，每次更新时，对所有粒子进行排序；然后，在此基础上，对所有的粒子进行评估，衡量每个粒子是否可以保留；最后，删除那些不符合保留要求的粒子，同时生成相应数目的新的粒子，以保持种群的规模，从而提高种群的整体适应性能。实验数据表明，新算法提高了算法的性能，具有更好的全局性能。

关键词：粒子群算法；优化；淘汰

0引言

1995年，受到自然界鸟群运动模型的启发，Kennedy和Eberhart[1]提出了一种基于鸟群运动的优化搜索算法——粒子群优化算法(Particle Swarm Optimization， PSO)。这种算法的思路是把所求的解在问题空间中可能的位置，视为鸟群在运动模型中的栖息地，然后通过个体之间的信息传递，逐步把求解过程中较好的解出现的可能性提高，并且引导群体中所有的粒子都向着可能的解的位置不断靠拢聚集[1-4]。

经典PSO算法是一种基于智能群体方法的计算技术，优势在于简单而又容易实现，同时又有深刻的生物背景，更进一步而言，也包括其没有许多参数需要调整，具有较高的使用价值。大量的研究表明经典PSO算法对于单目标优化问题而言，与其他演化算法相比较，其收敛速度更快，需要设置的参数更少，数学描述更加简单[4]。因此，经典PSO算法得到了很多学者的广泛研究，在很多领域得到了应用，产生了很多研究成果。经过反复的讨论和研究，证明PSO算法能够适用于各类优化的问题，具备明显的性能优势。

但是，在PSO算法被广泛应用于各类科学问题求解的同时，其缺陷也逐渐显现[5-6]。为此针对不同的应用领域，当前研究人员提出了各种改进措施，主要包括基于惯性权值的改进方法、基于加速因子的改进方法、基于邻近群拓扑的改进方法、基于种群规模的改进方法、混合粒子群优化算法的改进方法等[7]。尽管每种改进方法从不同角度对PSO算法进行了优化，取得了一定的效果，但仍然做不到面面俱到。总体来讲，目前PSO算法中最突出的问题有：1)算法易陷入局部极值，造成过早收敛；2)在多维复杂空间的进化过程中有一定的局限性，使得解的精确度难以稳定提高等[8]。

本文为了进一步提高经典PSO算法的全局搜索能力，使其不易陷入局部最优，提出了一种新的优化策略。其主要思想为：首先，采用了佳粒子的概念，每次更新时，对所有粒子进行排序；然后，在此基础上，对所有的粒子进行评估，衡量每个粒子是否可以保留；最后，删除那些不符合保留要求的粒子，同时生成相应数目的的新的粒子，以保持种群的规模，从而提高种群的整体适应性能。并通过实验仿真得到的实验数据表明，新算法提高了算法的性能，具有更好的全局性能。

1标准粒子群优化算法

1.1标准粒子群优化算法

PSO算法数学模型如下：

设种群的规模为M，决策空间的维度为n，我们表示编号为i的粒子，在t时刻的坐标位置为

(1)

其更新速度为

(2)

表示第i的粒子在t时刻的第j(j=1,2,…,n)维子空间中的位移速度、位置为：

(3)

(4)

(5)

其中，ω是惯性权值。c1、c22个加速因子是在0到1之间的2个随机数，正常情况下会使用一个常量vmax来限制它们的最大速度。gj是全局的极值gbest，是整个群体中的历史最优位置。同时，gj表示局部粒子群的历史最优位置时改为lj，表示局部极值lbest。而使用gbest还是lbest是由算法的邻近拓扑结构决定。pij是gbest，即为粒子当前最优位置[7]。

标准粒子群算法流程如下[7-10]：

步骤1：初始化，设置规模种群，随机设置粒子的初始位置、初始速度等参数。

步骤2：评估，计算每个粒子的适应程度，计算每个粒子的目标函数。

步骤3：更新并计算每个粒子的pbest。

步骤4：更新并计算整个群体的gbest。

步骤5：采用式(3)～(5)，计算和更新所有粒子的位置、速度参数。

步骤6：检查终止条件。如果如下条件之一：1)超过最大迭代次数预设阈值；2)已经获得预设的适应度范围；3)最优解的变化已经停滞，那么终止迭代，执行步骤7，否则，返回步骤2。

步骤7：结束算法，输出最优的位置。

1.2佳粒子、佳粒子距

定义如下：佳粒子[7]的定义是新粒子群中的适应度最大的、也是位置为第一个的粒子。佳粒子距[7]的定义是第i个粒子在新粒子集中的位置，记为di。

2改进算法

为了防止粒子群算法陷入局部最优、并提高速度，利用佳粒子距，改进算法设计如下：

步骤2：评估每个粒子在连续kt次中的表现。如果出现佳粒子距在kt更新中连续为后t%，即淘汰。

民族武术社与通背拳研究会由于社团性质的根本区别，传承空间也截然不同.民族武术社的生源大多来自于牛街及附近地区，学校及社区等地合作范围有限，传承空间相对较小.而通背拳研究会是由通背拳各个派系传承人组成，教学范围遍布北京市多数地区，不断发展各个派系的通背拳.因此，与民族武术社相比,通背拳研究会的传承空间更加广泛.通过交谈，在询问张斌教学地点时，他无奈地说道：“怎么说呢，就在马路边，因为这个是事实，没有空间.你要想在商场开，一年都得上万，你弄一场地，我哪弄的起啊.”

步骤3：更新，剔除所有不达标的粒子，随机生成相同数目的新的粒子，继续运行，直到整体得到最优解。

优化过后的PSO算法为：

步骤1：初始化。设置代数t=0，设置所有群粒子即种群的初始位置X及其速度V，初始化每个粒子的个体历史最优值位置令pbest=x和全局最优值位置。

步骤2：在保证粒子在搜索空间内飞行的条件下，更新每个粒子的速度和位置，并且产生新的种群和个体历史最优值位置。

步骤3：根据新的非支配解和已有的外部种群维护外部种群，防止溢出，同时为每个粒子选取全局最优值位置。

步骤6：结束算法，输出最优的位置。

同时为了防止一些粒子由于本身环境的影响，使其一直保留在整个粒子群中的变化滞后位置，即防止这些粒子陷入到局部最优，因此进行了种群意义上的淘汰工作，并更新同样数目的新的粒子。从本质上来讲，这是一种结合了惯性权值和种群规模的改进方法。

3仿真实验

本文采用了与文献[11]中一样的测试函数，即DeJong和Rastrigin函数，其中DeJong函数是一个连续的、单峰分布的函数，Rastrigin是一个非线性、多峰值分布的函数。从设计思路上本算法应具有全局最优的特点，应在多峰值的效果上有一定优势。

本文采用的DeJong函数如下：

(6)

采用的Rastrigin函数[12-13]如下：

(7)

在对该2项函数在不同种群大小、不同维数、不同最大代数、不同优化算法的情况下，进行了10次计算后，对结果进行了平均，测试结果见表1～2。

表1　DeJong函数测试结果

表2　Rastrigin函数测试结果

分析表1～2可见，本算法在单峰值的DeJong函数上优势并不明显，而在多峰值的Rastrigin 函数上具有一定的优势，且当种群规模相对较小时，效果比较突出。因此，该算法比较适用于多峰的问题，具有不会陷入到局部最优的特点。

另外，根据以上分析，统计了Rastrigin函数10次最优值迭代的速度结果，虚线为经典算法的计算效果，实线为本文所提出的算法效果。由图1可见，本文提出的算法在速度上更快。

4结语

本文对经典的PSO算法提出了一种新的优化策略。采用了佳粒子的概念，每次更新时，对所有粒子进行排序，在此基础上，对所有的粒子进行评估， 衡量每个粒子是否可以保留， 删除那些不符合保留要求的粒子，同时生成相应数目的新的粒子，以保持种群的规模，从而提高种群的整体适应性能。这种方法使得本算法在多峰值问题上具有较好的优势。实验数据表明，新算法提高了算法的性能，具有更好的全局性能，不易陷入局部最优。

图1　 Rastrigin函数的对比结果

参考文献

[1] Kennedy J, Eberhart R. Particle swarm optimization[M]//Claude Sammut,Geoffrey I Webb.Encyclopedia of Machine Learning.New Yok: Springer US,2010:760-766.

[2] Pedersen M E H, Chipperfield A J. Simplifying particle swarm optimization[J]. Applied Soft Computing,2010,10(2): 618-628.

[3] 王姝,陈崚.基于正交试验设计的粒子群优化算法[J].扬州大学学报:自然科学版,2012,13(2):58-60.

[4] Sharma T,Srivastava L. Evolutionary computing techniques for optimal reactive power dispatch: an overview and key issues[C]// Communication Systems and Network Technologies (CSNT), 2014 Fourth International Conference on .Bhopal:IEEE,2014: 7-9.

[5] Khan S A,Nadeem A.Automated test data generation for coupling based integration testing of object oriented programs using particle swarm optimization [C]//Information Technology:New Generations (ITNG),2013 Tenth Internation Conference.Las Vegas,NV:IEEE,2013:369-374.

[6] Gaing Z L, Lin C H, Tsai M H,et al. Rigorous design and optimization of brushless pm motor using response surface methodology with quantum-behaved pso operator[J].IEEE Transactionss on Magnetics, 2014,50(1):1-4.

[7] 郭文忠,陈国龙.离散粒子群优化算法及其应用[M].北京:清华大学出版社,2012:5-17.

[8] 陶乾,阮锦新,常会友,等. PSO算法扰动优化策略及其收敛性研究[J].华南师范大学学报:自然科学版,2014,46(4):26-30.

[9] Kulkarni R V, Venayagamoorthy G K. Particle swarm optimization in wireless-sensor networks: A brief survey[J]. Systems, Ma, and Cybernetics, Part C: Applications and Reviews, 2011,41(2): 262-267.

[10] Moradi M H, Abedini M. A combination of genetic algorithm and particle swarm optimization for optimal DG location and sizing in distribution systems[J]. International Journal of Electrical Power & Energy Systems, 2012, 34(1): 66-74.

[11] Lovbjerg M, Rasmussen T K, Krink T. Hybrid particle swarm optimiser with breeding and subpopulations[C]//Proceedings of the Genetic and Evolutionary Computation Conference. USA :San Francisco, 2001: 469-476.

[12] Moslehi G, Mahnam M. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search[J]. International Journal of Production Economics,2011, 129(1): 14-22.

[13] Pandey S,Wu L, Guru S M, et al. A particle swarm optimization-based heuristic for scheduling workflow applications in cloud computing environments[C]//Advanced Information Networking and Applications (AINA),2010,24th IEEE International Conference on. Perth,WA:IEEE,2010: 400-407.

An improved particle swarm optimization algorithm

XU Xian-wei, et al.

(DepartmentofInformationTechnology,NanjingForestPoliceCollege,Nanjing210023,China)

Abstract：Standard Particle Swarm Optimization (PSO) algorithm can solve problems of all kinds of optimizations, has been widely used in many fields，and has been caused attention from a lot of researchers. To make Standard PSO have better ability of global search， avoid local optimum，this paper proposes a new optimal strategy. Firstly，the concept of Good Particle has been adopted. In each update，all particles have been sorted; then, on this basis all particles have been evaluated to identify the fitness; lastly，we those particles unsuitable to retain are eliminate. At the same time, the same number new particles are generated randomly to keep the scale of the population to improve the whole fit capability of the population. Experiments results show that this new algorithm has improved the property of the algorithm, and with better generalization performance.

Key words：particle swarm optimization; optimization algorithm; elimination

文献标志码：A

文章编号：1009-8984(2015)04-0100-04

中图分类号：TP301

作者简介：徐仙伟 (1977-)，女(汉)，江苏，讲师

基金项目：中央高校基本科研项目(LGYB201410)

收稿日期：2015-04-15

doi:10.3969/j.issn.1009-8984.2015.04.025