基于具有量子行为的粒子群优化算法惯性权重研究及应用

粒子群优化(PSO)算法是一种群智能优化算法，最早由Kennedy和Eberhart于1995年共同提出，其基本思想是对鸟群捕食行为的仿生模拟，通过鸟群之间的集体协作，快速搜寻并找到最优解。其基本的进化方程如下：

其中，r1，r2∈[0，1]为均匀分布的随机数；C1，C2均是正常数；t表示进化代数；Vt，Xt分别表示每个粒子的速度和位置；Pg，Pt分别是粒子群的全局最优和个体最优。

为了改善基本PSO算法的收敛性能，Y?Shi等人提出了惯性权重的方法和用模糊控制器来动态自适应地改变惯性权重的技术。之后Jun Sun等人提出的具有δ函数形式的粒子群算法(QDPSO)使粒子群算法的计算更加简单容易。最近一种新的QDPSO算法考虑了速度对位置的影响，通过速度的更新选择位置的更新方程。在经典粒子群算法的可调整参数中，惯性权重是非常重要的参数，较大的权重有利于提高算法的全局搜索能力，而较小的权重会增强算法的局部搜索能力。因此，对这种新的QDPSO算法的速度项引用惯性权重ω，通过研究4种方案，发现惯性权重ω的变化对具有量子行为的粒子群算法的收敛性具有很大改善。可以说惯性权重的适当设置对新的QDPSO算法性能也起着重要的作用。

1 量子行为的粒子群优化算法及其改进

1.1 QDPS0算法

文献[4]的作者认为，若是在PSO系统下的个体粒子具有量子行为，则该粒子将会以与基本PSO算法中的粒子不同的方式运动。在量子空间，粒子的速度和位置不能再依据“不确定原理”被同时确定，所以提出了QDPSO算法。该算法改变了基本PSO算法的粒子更新策略，只用了粒子的位置向量。QDPSO算法的粒子进化方程如下：

其中，a，b，u∈[0，1]为均匀分布的随机数；pid是第i个粒子在第d维空间找到的局部最优解，pgd是群体在第d维空间找到的全局最优解；xid表示第i个粒子在第d维空间找到的当前值；而g必须满足条件：，才能保证算法的收敛。

1.2 改进的粒子群算法

新的QDPSO算法利用个体粒子的速度产生一个介于[0，1]之间的数来代替原算法中的由计算机随机产生的数，用以选择该粒子的位置更新方程。更新方程和参数设定参考文献[5]。

本文考虑到惯性权重随粒子的迭代次数变化影响个体粒子的速度引导该粒子向最优解靠拢，所以采用4种方案对该改进算法进行研究。通过使惯性权重随粒子的迭代次数变化，从而影响速度的更新方程：

其中，采用4种惯性权重ω方案来影响速度的更新，然后与QDPSO算法进行性能比较：

方案1 ω为从(1，0.875)递减的函数ω=1-k?0.125／genmax。采用这种方案的QDPSO算法称为ω1-QDPSO；

方案2 ω为从(0.9，0.4)递减的函数甜ω=0.9-k?0.5／genmax。采用这种方案的QDPSO算法称为ω2-QDPSO；

方案3 ω为一定值0.729 8，采用这种方案的QDPSO算法称为ω3-QDPSO；

方案4 ω为一凹函数(ωstart-ωend)(t／tmax)2+(ω-ωend)(2t／tmax)+ωstart，其中ωstart=0.95，ωend=0.4，tmax为最大的迭代次数。采用这种方案的QDPSO算法称为ω4-QDPOS。

综上所述，选择测试函数F1(x)和F2(x)分别为Sphere和Rastrigin(参数设置见文献[4])，改进后的算法流程如下：

Step 1 初始化种群粒子的速度和位置；

Step 2 通过对两个测试函数进行初始化计算，得到每个粒子的当前位置为粒子最佳位置Pbest，初始群体粒子位置的最优值为群体最佳位置gbest；

Step 3 重新把粒子的位置代入测试函数进行计算，得到每个粒子新的适应值，将其与Pbest比较，若较好，则将Pbest设置为新位置；并将其与gbest比较，若较好，则将gbest设置为新位置；

Step 4 根据公式(6)更新粒子的速度；

Step 5 用个体粒子的速度产生用以选择该粒子位置的更新方程的数据；

Step 6 由Step 5产生的数据选择更新粒子位置的方程；

Step 7 若未达到终止条件(足够小的适应值或预设的最大迭代次数)，则返回Step 3。

更新粒子速度时需要注意：如果粒子的速度超出预设的范围，则采取使粒子反向运动的策略，从而保证算法有效进行。

1.3 算法的结果及数据分析

目标函数为F1(x)和F2(x)，基本参数是：c1=c2=2.05，g=0.968 5，每种算法都在同一台计算机，同一环境下用Matlab 7.1.0软件运行。结果如表1所示。

表1的数值是对每个函数在粒子数为20个的条件下，测试50次，然后取平均得到的结果。从表中可以看出，对于函数F1(x)，比较结果可以明显得知：在随粒子群维数增加的情况下，ω1-QDPSO是比QDPSO得到更好的解，其他几种改进方案的解都比较差；函数F2(x)在随粒子群维数增加的情况下，4种改进方案和QDPSO都能得出比较好的解。

通过实验，可以看出：对于单峰函数F1(x)，ω的递减不能太小，从方案ω1-QDPSO和ω2-QDPSO的结果就可以比较出来，而方案ω3-QDPSO和ω4-QDPSO的结果不好，可能是因为它们搜索的区域太小，从而陷入局部最优解。

对于多峰函数F2(x)，ω的变化对测试函数的解的精确度没有太大影响，说明了改进方案在此方面没有明显提高。接下来，我们还对算法的收敛速度进行了比较。结果如表2所示。

表2是对函数测试50次后取得平均值的结果。可见对于函数F1(x)，ω1-QDPSO和QDPSO都在10维的情况下收敛，而20维时只有ω1-QDPSO收敛，其他函数都没有收敛，导致这种结果的原因有2种：

(1)各种方案随ω的变化，削弱或失去了调节能力，在达到最大迭代次数时也未收敛；

(2)即使在算法已搜索到最优解附近时，由于局部搜索能力太差，跳过了最优解。对于函数F2(x)，ω3-QDPSO，ω4-QDPSO，QDPSO收敛速度都比较快，ω1=QDPSO和ω2-QDPSO的收敛速度就相对较慢一些。这是由于对多峰函数测试时，各种方案的初始化范围附近可能存在最优解，所以减少了迭代次数，加快了算法速度。

通过对4种方案的研究，这里选取方案1应用于0-1背包问题，并得到理想的结果。

2 对改进算法应用到0-1背包问题

2.1 0-1背包问题的数学描述

0-1背包问题是一种典型的组合优化问题。0-1背包问题的描述如下：假设有n个物品，其大小和价值分别为wi和ci(其中wi>0，ci>0，i=1，2，…，n)，背包的容量假设为V(V>0)。要求在背包的容量限制内，使所装物品的总价值最大。该问题的数学模型可表示为：

其中，当将物品i装入背包时xi=1；否则xi=0。

2.2 0-1背包问题的改进粒子群算法

改进粒子群算法应用到0-1背包问题的思想：粒子群中粒子的个数与每个粒子的维数相等。先定义二进制数x，x只能取0和1。再把粒子的种群数看作背包的个数n，对于每个粒子xi(其中i=1，2，…，n表示粒子个数)有n个维数，即1个粒子有n个位置。然后初始化每个粒子的速度vij，(其中j=1，2，…，n表示每个粒子位置的维数)，每个粒子的每一维都对应一个初始化了的速度。对公式(8)进行变化：

解决背包问题的步骤：

(1)初始化粒子的速度和位置；

(2)将初始化的位置向量代人式(9)，在所得每个粒子的解中找到最优解pbest，并令pbest=gbest；

(3)通过式(6)更新粒子的速度，对所得最优解进行修正，然后再次代入函数方程中继续寻找新的最优解；

(4)若达到终止条件，则结束迭代，输出到存储向量，即为所求结果；否则，k=k+1，转步骤(3)。

2.3 实验仿真

为了验证ω1-QDPSO求解0／1背包问题的可行性及有效性，这里进行了2组实验，每组实验用ω1-QDPSO算法进行测试，每组算法运行50次。

实验一：取参数popsize=10，dimsize=10，c1=c2=2.05，genmax=1 000，g=0.968 5；N=10，V=269，W={95，4，60，32，23，72，80，62，65，46}，C={55，10，47，5，4，50，8，61，85，87)，得到实验结果是max f=295，收敛平均迭代次数11。

实验二：取参数popsize=20，dimsize=20，c1=c2=2.05，genmax=1 000，g=0.968 5；N=20，V=878，W={92，4，43，83，84，68，92，82，6，44，32，18，56，83，25，96，70，48，14，58}，C={44，46，90，72，91，40，75，35，8，54，78，40，77，15，61，17，75，29，75，63}，得到实验结果是max f=1024，收敛平均迭代次数23。

ω1-QDPSO算法求解0-1背包问题，与文献[9]中提出的用带有死亡罚函数的粒子群优化算法求解0-1背包问题相比，其运行速度明显提高。

3 结 语

本文通过采用4种方案对具有量子行为的粒子群优化算法的惯性权重研究分析表明，QDPSO改进算法中惯性权重的改变对性能的影响与经典PSO算法相比既具继承性又具发展性，在算法精度上ω1-QDPSO的结果比较优，而在计算速度上ω3-QDPSO和ω4-QDPSO的结果更优。选择其中算法性能相对较好的ω1-QDPSO算法应用于0-1背包问题，可以看出改进算法性能的改善在应用中得到更好的体现