基于边界变异的一种新的粒子群优化算法

刘依依+徐生兵

【 摘 要 】 针对传统粒子群优化算法易早熟，收敛精度低，特别是在解决大维数问题时，效果很不理想等缺点。针对这类问题，首先提出一个判别机制，判定算法什么时候达到早熟，若达到早熟则提出一种基于边界与随机变异的方法使部分粒子进行变异，从而使粒子重新分散后，再进行搜索。通过对四个经典测试函数的数值仿真实验证明，该方法能极大地提高算法的寻优能力，特别是在高维函数寻优时获得了较好的优化效果。

【 关键词 】 粒子群优化；早熟；边界；变异

【 中图分类号 】 TP18

【 文献标识码 】 A

New Particle Swarm Optimization Base On Boundary Mutation

Liu Yi-yi Xu Sheng-bing

（City College of Dongguan University of Technology GuangdongDongguan 523419）

【 Abstract 】 The traditional particle swarm optimization algorithm was premature convergence， low accuracy.Especially in solving large dimension problems， the effect is not ideal.In order to solve these problems，first it presents adecision mechanism when the algorithm reaches puberty.If the algorithm reaches puberty，present a method based on the boundary and random variation.It makes part of particle variation and then these particles are variationso that the particles bounce early regional and search again。Based on the 4 classical test functions of numerical simulation experiment， the method can greatly improve the searching capability especially in highdimensional function optimization it obtained better optimization effect.

【 Keywords 】 particle swarm optimization； premature； boundary； mutation

1 引言

粒子群優化（Particle Swarm Optimization，PSO）是由Kennedy 和Eberhart 于1995 年提出的一种优化算法。它是一种仿真算法，是模拟自然界一些生物的行为，如鸟群觅食、鱼群学习等。由于其容易理解、易于实现、不要求目标函数和约束条件是可微的， 并能以较大概率求得全局最优解， 目前已在许多优化问题中得到成功应用。与其它进化算法类似， 粒子群优化算法也存在早熟收敛现象， 尤其是在比较复杂的多峰搜索问题中。目前解决这一问题的主要方法是增加粒子群的规模， 虽然对算法性能有一定改善， 但同样存在缺陷：一是不能从根本上克服早熟收敛问题；二是会大大增加算法的运量。

基于这种情况提出一种改进的PSO算法。此算法首先设计出一种方法判定算法在什么情况达到了早熟；当粒子达到早熟时，设计让其中一个粒子呆在早熟区，而其它粒子的其中一维上加入一个[-1，1]中的随机数进行变异，使其能够跳出该区域。这样，使陷入该区域的粒子能够在跳出早熟状态的情况下，又能够在保持目前搜寻到的最优值，再次重新寻找最优值，从而保证了算法能够找到比现在更好的全局最优值。

这种思想在理论上也是行得通的，因为粒子在寻优过程中达陷入早熟时，其目前寻到的最好值离理论最优值虽然有一定的距离，但相对于算法迭代前的位子肯定有一个很大的提高，这时我们保持一个粒子在这个区域中就保留了这个值的优越性，使算法在以后的迭代中能达到的最优值一定不会比现在的值更差，而其它粒子进行变异是为了能够使粒子跳出该区域，从而让算法重新进行搜索去寻找更好的最优值。加入一个[-1，1]中的随机数进行变异是因为当粒子陷入早熟说明此时粒子在某种程度上已经比较接近最优值了，此时粒子进行变异不宜进行大的变动，只需小的变动使其跳出该区域重新寻找最优值即可。其通过数值模拟实验，发现改进的PSO算法对改进粒子群优化的性能方面特别是对大维数的寻优方面有极大的提高。

3 改进的粒子群算法

3.1 PSO的早熟现象和判定机制

从公式（1）中可看出，PSO 速度更新方程由三部分组成：式（1）中第一项表示粒子的当前速度，说明了粒子的目前状态；第二项为“认知（Cognition）”部分，考虑了粒子自身经验；第三项为“社会（Social）”部分，代表着粒子之间的“社会”作用。分析此式不难发现，当粒子的当前位置处在全局极值位置Gbest 时，该粒子只有在先前速度和惯性权系数不等于零情形下，粒子才有可能离开这一点；如果种群中粒子的先前速度都接近于零时，一旦它们落于全局极值位置Gbest，则种群中的粒子很难再重新移动，此时意味着算法将收敛到种群目前寻优到的最优解，即全局极值位置Gbest。此时搜索到的全局极值位置Gbest对应的解如果只是优化问题的一个局部最优解，那么算法就出现了早熟收敛现象。在实验中，我们采取了一些具体方法，来判定粒子什么情况达到早熟。

在粒子群算法中，我们用个Gbest的值来保存现寻到的最优值，若是下次迭代中寻到的最优值比现寻到的最优值更优越则更新Gbest的值。但当算法陷入早熟时，粒子只在一个很小的区域内变动，此时最优值几乎不改变，则我们设计出如下判别早熟方法， 我们定义两个变量Gbest与Gbest1，Gbest保存算法目前寻到的最优值，Gbest1保存前一次算法寻到的最优值，两者相比较，若不相等，则用Gbest值更新Gbest1的值；若相等，则我们用一个初始化h=0的值来记它们相等的次数，h的值加1，当h的值达到100时，若此时算法还没达到最优值，则判定出算法陷入局部最优。过程伪代码如下：

If（gbest！=gbest1）

gbest1=gbest；

else

h=h+1；

3.2 基于边界与随机变异的PSO算法

在粒子群优化算法中，在k+1代的粒子群位置由（2）式计算得出。当粒子超过边界时，我们一般取其边界值，然而在数值模拟实验中，我们发现当例子超出边界时，我们取其值小于边界时，对算法的提高有很大帮助，似乎边界对它们的寻优有一定的障碍。

当粒子陷入早熟时，算法再进行迭代时，粒子的位置几乎不发生改变，此时，在进行算法迭代已经没有太大意义了。本文提出一个加随机数的方法，对陷入早熟的粒子保留一个在其区域，而对剩下的粒子，每一个粒子的其中一维加上一个[-1，1]之间的一个随机数使粒子进行变异跳出早熟区域，重新搜索。进行变异伪代码如下：

For（i=0； i

x[i][i]+=2*rand（）-1；

其中x[i][i]表示第i个粒子第i维分量。

根据以上分析，提出一种新的基于边界变异的PSO算法，本文记为BVPSO算法，算法步骤如下所示：

Step1 在初始化范围内， 对粒子群 （种群规模N，维度M ）中各粒子进行随机初始化，包括随机位置和随机速度，算法开始迭代。

Step2 判断粒子是否达到最优值，达到算法结束，输出最优值；若没达到，则判断粒子是否陷入局部最优，若是，粒子进行变异；若否，则算法再行迭代

Step3 判断粒子是否达到最优值，达到算法结束，输出最优值；若否，判断算法是否达到最大迭代次数，若是结束程序，不是返回第二步。

4 数值仿真实验

4.1 标准测试函数

在数值仿真实验中，选取了如表1所示的4个标准测试函数进行数值实验。

4.2 实验参数设置

各个测试函数的初始搜索范围见表1，粒子的最大速度均为初始搜索范围的10%；SPSO 和BVPSO中的最大最小权重分别取0.9 和0.1，CPSO中压缩因子取值为0.729。

4.3 实验方案

为了充分比较BVPSO、SPSO、CPSO算法的优化性能，设置了两种不同检验性能的实验方案。

方案1 固定迭代次数和种群数，比较三种算法能达到的最优值。该方案中，测试函数种群数为40，维数分别去80，100，每个函数运行50 次。若算法在10000次迭代中，取其能达到的最优值。实验结果如表2、表3所示。

方案2 预设精度，看算法收敛到预设精度的迭代次数。该方案取种群数40时，维数分别为30，40，预设精度看下表，若算法在超过100000次迭代后，还没有达到预设的精度，则认为该算法收敛性达不到要求，次数就为100000。

5 结束语

针对粒子群算法易陷于早熟的问题和什么时候粒子陷入了早熟问题，提出了一种先判定粒子何时达到了早熟，当粒子达到早熟时，提出一种某些维加随机数的方法，使陷入早熟的粒子进行变异的BVPSO算法，通过实验结果分析得出BVPSO算法在解决复杂函数的大维寻优面相对与传统的SPSO，改进的CPSO算法的性能方面有极大的提高，且在维数相对来说较小的情况下相对与传统的两种算法无论是在收敛精度上还是速度上都有相当的进步。 从模拟的实验结果来看，相对于标准的粒子群优化算法SPSO与改进的CPSO算法，新的BVPSO算法从收敛的速度与精度上都有很大的提多，是一种有效的改进算法。

参考文献

[1] T L Seng， M B Khalid， R Yusof. Tuning of a neuro-fuzzy controller by genetic algorithm[J]. IEEE Trans.Syst.，Man， Cybern.B（S1083-4419），1999，29（2）：226-236.

[2] A Visioli. Tuning of PID controllers with fuzzy logic， Proc[C]//Inst. Elect. Eng. Contr. Theory Applicat， 2001， 148（1）： 1-8.

[3] R A Krohling， J P Rey. Design of optimal disturbance rejection PID controllers using genetic algorithm [J]. IEEE Trans. Evol. Comput. （S1089-778X）， 2001， 5（1）： 78-82.

[4] D B Fogel. Evolutionary Computation： Toward a New Philosophy of Machine Intelligence [M]. New York： IEEE Press， 2000.

[5] Z L Gaing. A Particle Swarm Optimization Approach for Optimum Design of PID Controller in AVR System [J]. IEEE Trans. on Energy Conversion （S0885-8969）， 2004， 19（2）： 384-391.

[6] J Kennedy，R Eberhart. Particle Swarm Optimization [C]//Proc. IEEE Int. Conf. Neural Networks， 1995， 1942-1948.

[7] Y Shi， R C Eberhart. A modified particle swarm optimizer [C]//Proc. IEEE Int. Conf. Evol. Comput.， Anchorage， Alaska， May 1998， 69-73.

基金項目：

东莞理工学院城市学院青年发展基金（2016QJY007Z）。

作者简介：

刘依依（1986-），女，汉族，江西九江人，毕业于广州大学，硕士，东莞理工学院城市学院，讲师；主要研究方向和关注领域：应用数学、密码安全。

徐生兵（1980-），男，汉族，湖北荆门人，毕业于深圳大学，硕士，东莞理工学院城市学院，讲师；主要研究方向和关注领域：智能计算。