一种新的改进粒子群算法研究马金玲，唐普英电子科技大学光电信息学院，成都 (610054）E-mail：majinling2006@摘 要：研究粒子群优化算法（PSO）的收敛速度，以提高该算法性能是PSO的一个重要而且有意义的研究。

Jun Sun 等人通过对PSO系统下的单个个体在量子多维空间的运动及其收敛性的分析，提出了具有δ函数形式的粒子群算法（Quantum Delta-Potential-Well-based PSO）。

论文在此基础上提出了改进型算法（IQDPSO），用粒子的速度来产生一个随机数引导粒子向最优解快速靠拢，并对速度的处理采取了新的策略。

仿真结果表明：该改进算法较原算法在收敛速度上有很好的改善，而且稳定性也较好。

关键词：粒子群优化算法，量子行为，量子机理中图分类号: TP301.61. 引言粒子群优化算法（PSO）是近年来被广泛关注和研究的一种智能优化算法，最初由Kennedy和Eberhart于1995年提出并成功地应用于函数优化，后来又进行了有效的拓展。

它是对鸟群觅食过程和集聚的模拟[1]，是一种全局优化算法。

其基本的表达式为v t+1= v t +c1·r1(P t - x t) + c2·r2(P g - x t) （1）x t+1 = x t + v t+1（2）其中，r1 ,r2是介于（0,1）之间的随机数；c1、c2均是正常数；P g是全局最优解；P t是当前代的个体粒子最优解；x t是当前代粒子的位置；v t是当前代粒子的速度。

经典PSO算法的粒子就是根据以上两式来更新自己的位置和速度，寻求最优解。

后来Shi 等人又提出了惯性权重的方法[2]和用模糊控制器来动态自适应地改变惯性权重的技术[3]，以提高算法的收敛速度。

Clerc 等人提出了压缩因子法[4]，以控制系统行为最终收敛。

随后又有很多学者从各个角度提出了改进型算法，这些改进的算法虽然解决了一些实际应用问题，但大部分却牺牲了粒子群算法简单、易实现的特性，并且大大增加了计算量。

这对要求快速找到最优解的问题显然是不适用的。

所以探索在不增加计算量的情况下，能够更好的解决实际问题的粒子群算法，是一个值得研究的课题。

Jun Sun等人提出的具有δ函数形式的粒子群算法就很好的保持了粒子群算法的特性[5]。

文中的算法就是该算法的改进(IQDPSO)：用个体粒子的速度产生一个引导该粒子向最优解靠拢的随机数,但是只有当前代个体粒子的适应值不如前一代时，才更新粒子的速度。

仿真结果显示：该改进算法在收敛率上有很大的提升，并且稳定性也近乎完美。

2. QDPSO算法该算法改变了经典PSO的粒子更新策略。

文献[5]认为，在PSO系统下的个体粒子如果具有量子行为，那么此粒子将会与经典PSO算法中的粒子以截然不同的方式运行。

根据传统的牛顿力学机制，经典PSO算法中的每一个粒子的状态都是由它的速度向量和位置向量来描述的，粒子移动的过程形成了一个确定的运动“轨迹”。

文献[5]的作者认为，这个所谓的“轨迹”对具有量子机理的粒子已经没有意义了。

因为粒子的速度向量和位置向量不能再依据“不确定原理”被同时确定了。

所以文献[5]在保持了PSO算法原理下，提出了QDPSO （Quantum Delta-Potential-Well-based PSO）算法。

该算法只用了粒子的位置向量，并且是用计算机随机产生的一个数据来选择更新粒子位置的方程。

QDPSO 算法是在量子时域空间的框架下讨论的，并且粒子的状态由一个波函数(,)x t Ψv 来描述的。

在三维空间中，粒子的波函数可以表述为2d x d y d z Q d x d y d z Ψ= （3） 其中， 2Ψ是波函数的概率密度，并且满足21d x d y d z Q d x d y d z +∞+∞−∞−∞Ψ==∫∫。

QDPSO 算法的粒子进化公式为：p = (a· p id + b·p gd )/(a +b ) （4）L = (1/g )·ab s( x id -p ) （5）x id = p ± L·(㏑(1/u )) （6）其中， p id 是第i 个粒子在解空间的第d 维所找到的最优解， x id 是第i 个粒子在解空间第d 维的当前值，p gd 是所有粒子在解空间中第d 维找到的最优解； a ，b ，u 都是(0,1)之间的随机数。

由上式可知，参数g 的选取将直接影响到算法的性能，根据文献[5]给出的参数控制与选取的方法，要求g 满足条件：ln g >3. 改进的QDPSO 算法（IQDPSO ）在量子框架下，虽然粒子的位置和速度不能再根据“不确定原理”被同时确定，但是，粒子的速度大小及状态仍然对粒子向最优解的靠拢有一定的影响。

那么利用粒子的速度来引导该粒子向最优解的方向飞去，自然也就能提高算法的性能，特别是在算法的收敛速度和稳定性方面。

试验结果也证明了这一点。

该改进算法与原算法相比，主要有两方面的改进：a.利用个体粒子的速度产生一个介于（0,1）之间的数来代替原算法中的由计算机随机产生的数，用以选择该粒子的位置更新公式。

b. 如果个体粒子的位置向量的大小超出了预设的范围，采取让该粒子向相反的方向飞行的策略。

为了尽可能的减少计算量和更好的引导粒子向最优解靠拢以增强粒子的收敛性[6]，此改进型算法还采用：只要当前代粒子的适应值优于上一代，就不再更新粒子的速度，即不计算公式（1）。

综上所述，IQDPSO 算法的流程如下所示（以寻求函数的极小值为例）：Step 1. 在给定的范围内初始化种群粒子的位置和速度；Step 2. 评价粒子当前适应值，并保存全局最优解和局部最优解及它们对应的状态；Step 3. 根据Step2的结果产生上面的（4）、（5）两式；Step 4. 用个体粒子的速度产生选择该粒子更新位置方程的数据m ax m in 11()/()id id ra n d q v v v v −=+−− （7）Step 5. 由Step4 产生的数据选择更新粒子位置的方程If rand-q > 0.5x id = p + L·(㏑(1/u ))Else x id = p –L ·(㏑(1/u ))Step 6. 判断Step5 中x id 的大小，并判断是否更新粒子的速度If x id > X maxx id = X max , v id = -v idElseif x id < X minx id =X min , v id = -v idOnly-if Fitness(x i t) > Fitness(x i t-1)更新公式（1）；直到达到终止的准则或预设的最大迭代次数。

在这一步中值得注意的是：在更新粒子速度时，即使粒子的速度超出了预设的范围，也不再采取v id = v min、v id = v max这种策略。

这样就避免了分母中的（v id - v min）和（v max- v id）这两项为零。

该算法采取对式（7）分母中的后一项取绝对值，保证式（7）的结果处于0和1之间，以保证算法的有效运行。

4. 仿真实验和数据分析4.1 仿真实验设计基准函数的选择和参数设置见文献[5]。

为了和原QDPSO算法公平比较。

两种算法都在同一台计算机、同一环境下运行。

运行环境为：MATLAB7.0.4。

并且评价粒子的适应值（Fitness）都采用的测试函数的函数值。

下面采用三种测试方式：TEST 1:检验算法在达到预设的最大迭代次数时所达到的最优值。

目的是比较原算法与文中改进的算法的寻优结果的比较。

每个基准函数都测试50次，然后取最优解的平均。

TEST 2:检验改进的QDPSO算法在达到原算法达到最大迭代次数寻到的最优解时的迭代次数。

目的是比较两个算法的收敛速度。

算法的时间上限是QDPSO算法的最大迭代次数。

如果迭代次数已经达到最大迭代次数而仍未达到QDPSO所寻到的最优值时，就把此时的迭代次数记为无穷大（inf），则总的结果为无穷大。

每个函数每次测试50次，然后取平均。

TEST 3:对每个基准函数测试50次，统计达到全局最优的比率，以检验算法的稳定性。

先对每个函数在不同的条件组合下的测试取平均，再对七个基准函数的结果取平均（mean）。

4.2 仿真结果及其分析仿真结果如表1~3所示。

由于篇幅原因只列出基准函数f3 的上述测试方式TEST1的结果（其它函数测试结果得出的结论与表1的一致）。

表中的M代表的是粒子总数，D是解空间维数，Gmax是最大迭代次数，QDPSO代表QDPSO算法运行的结果，IQDPSO是代表IQDPSO算法运行的结果。

表2中的best-ratio(%)记录的是七个基准函数在不同的测试条件组合下七个基准函数比原算法在收敛速度上平均提高的百分点。

其中表2中的30/2*表示f1-f5是在30维的解空间测试，而f6、f7是在2维的解空间测试，/ 表示没对此项测试。

TEST1的结果见表1：改进的QDPSO算法的寻优结果远比原算法（QDPSO）好。

而且随着粒子个数的增加，改进的QDPSO算法的优势就更明显。

TEST2的结果见表2：对于测试的七个基准函数，改进的QDPSO的收敛速度平均比原算法收敛速度都有不同程度的提高。

并且随着粒子个数的增加，这种优势更为明显。

表中的I-f1~I-f7所在的列表示七个基准函数f1~f7在IQDPSO算法寻到QDPSO在最大迭代次数找到的最优解时的迭代次数。

TEST3 测试的结果见表3：该算法的平均结果达到了0.9858，表明该的算法性能是非常稳定的。

表1 测试函数f3的平均最好适应值表3 IDQPSO收敛到最优解的比率Tab.1 Best fitness of test function f3 Tab.3 Ratio of IDQPSO converging to optimizationM D Gmax QDPSO IQDPSO M D I-f1 I-f2 I-f3 I-f4 I-f5 I-f6 I-f7 10 1000 0.1698 1.0658e-16 10 0.98 0.98 0.98 0.98 1.0 / / 20 20 1500 2.1620 4.9738e-16 20 20 0.96 0.94 0.98 0.94 1.0 / /30 2000 4.1729 2.8422e-16 30/2 0.94 0.92 0.96 0.92 1.0 1.0 1.010 1000 0.2061 7.1054e-17 10 0.98 0.98 0.98 1.0 1.0 / / 40 20 1500 1.0324 0.0000 40 20 0.98 0.96 1.0 1.0 1.0 / /30 2000 2.0826 7.1054e-17 30/2 0.96 0.94 0.98 0.98 1.0 1.0 1.010 1000 0.1325 0.0000 10 1.0 0.98 1.0 1.0 1.0 / /80 20 1500 0.0177 0.0000 80 20 0.98 0.96 1.0 1.0 1.0 / /30 2000 0.0030 0.0000 30/2 0.98 0.96 1.0 1.0 1.0 1.0 1.0mean=0.98580.9733 0.9600 0.9866 0.9800 1.0 1.0 1.0表2 7个测试函数在达到QDPSO算法寻到的最优解时的平均迭代次数Tab.2 Mean iteration of seven test functions getting the QDPSO optimization M D QDPSO I-f1 I-f2 I-f3 I-f4 I-f5 I-f6 I-f7 best-ratio(%)10 1000 985.2 901 789.8 898.4 910 / / 10.3120 20 1500 1322.6 1195.4 1202.2 1126. 6 1362 / / 17.2230/2* 2000 1881.2 1514.8 1207.8 1348.4 1769.2 957 915.6 31.4710 1000 924.4 894.2 869 889.2 907.4 / / 10.3240 20 1500 1282 1214.6 1114.4 1124 1243.6 / / 20.2830/2* 2000 1644 1374.4 1200 1307.8 1694.2 847.8 886.4 36.0410 1000 915 777.8 823.4 807 803.8 / / 17.4680 20 1500 1147.2 942.6 977.8 1091.4 1311.4 / / 27.630/2* 2000 1034 847.4 881.6 897 1079 842 827.4 54.235. 结论本文提出的改进型QDPSO算法(IQDPSO)，不再单纯地依靠粒子的速度和位置进化方程去寻求最优解，而是用粒子的速度产生一个随机数引导粒子的进化，并对速度采取了新的处理策略。