《具有量子行为的粒子群优化算法惯性权重研究及应用》由会员分享，可在线阅读，更多相关《具有量子行为的粒子群优化算法惯性权重研究及应用（7页珍藏版）》请在金锄头文库上搜索。
1、具有量子行为的粒子群优化算法惯性权重研究及应用粒子群优化(PSO)算法是一种群智能优化算法，最早由 Kennedy 和 Eberhart 于 1995 年共同提出，其基本思想是对鸟群捕食行为的仿生模拟，通过鸟群之间的集体协作，快速搜寻并找到最优解。其基本的进化方程如下： 其中，r1，r2 0，1为均匀分布的随机数； C1，C2 均是正常数；t 表示进化代数；Vt，Xt 分别表示每个粒子的速度和位置；Pg，Pt 分别是粒子群的全局最优和个体最优。为了改善基本 PSO 算法的收敛性能，Y?Shi 等人提出了惯性权重的方法和用模糊控制器来动态自适应地改变惯性权重的技术。之后 Jun Sun 等人提出
2、的具有 函数形式的粒子群算法(QDPSO)使粒子群算法的计算更加简单容易。最近一种新的 QDPSO 算法考虑了速度对位置的影响，通过速度的更新选择位置的更新方程。在经典粒子群算法的可调整参数中，惯性权重是非常重要的参数，较大的权重有利于提高算法的全局搜索能力，而较小的权重会增强算法的局部搜索能力。因此，对这种新的 QDPSO 算法的速度项引用惯性权重 ，通过研究 4 种方案，发现惯性权重 的变化对具有量子行为的粒子群算法的收敛性具有很大改善。可以说惯性权重的适当设置对新的 QDPSO 算法性能也起着重要的作用。1 量子行为的粒子群优化算法及其改进1.1 QDPS0 算法文献4的作者认为，若是在
3、 PSO 系统下的个体粒子具有量子行为，则该粒子将会以与基本 PSO 算法中的粒子不同的方式运动。在量子空间，粒子的速度和位置不能再依据“不确定原理” 被同时确定，所以提出了 QDPSO 算法。该算法改变了基本 PSO 算法的粒子更新策略，只用了粒子的位置向量。QDPSO 算法的粒子进化方程如下：其中，a，b ，u0 ，1为均匀分布的随机数； pid 是第 i 个粒子在第 d 维空间找到的局部最优解，pgd 是群体在第 d 维空间找到的全局最优解；xid 表示第 i 个粒子在第 d 维空间找到的当前值；而 g 必须满足条件： ，才能保证算法的收敛。1.2 改进的粒子群算法新的 QDPSO 算法
4、利用个体粒子的速度产生一个介于0，1 之间的数来代替原算法中的由计算机随机产生的数，用以选择该粒子的位置更新方程。更新方程和参数设定参考文献5。本文考虑到惯性权重随粒子的迭代次数变化影响个体粒子的速度引导该粒子向最优解靠拢，所以采用 4 种方案对该改进算法进行研究。通过使惯性权重随粒子的迭代次数变化，从而影响速度的更新方程：其中，采用 4 种惯性权重 方案来影响速度的更新，然后与 QDPSO 算法进行性能比较：方案 1 为从(1，0.875) 递减的函数 =1-k?0.125genmax。采用这种方案的 QDPSO 算法称为 1-QDPSO；方案 2 为从(0.9，0.4) 递减的函数甜 =0
5、.9-k?0.5genmax。采用这种方案的 QDPSO 算法称为 2-QDPSO；方案 3 为一定值 0.729 8，采用这种方案的 QDPSO 算法称为 3-QDPSO；方案 4 为一凹函数(start-end)(ttmax)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
6、通过对两个测试函数进行初始化计算，得到每个粒子的当前位置为粒子最佳位置 Pbest，初始群体粒子位置的最优值为群体最佳位置 gbest；Step 3 重新把粒子的位置代入测试函数进行计算，得到每个粒子新的适应值，将其与 Pbest 比较，若较好，则将 Pbest 设置为新位置；并将其与 gbest 比较，若较好，则将 gbest 设置为新位置；Step 4 根据公式(6)更新粒子的速度；Step 5 用个体粒子的速度产生用以选择该粒子位置的更新方程的数据；Step 6 由 Step 5 产生的数据选择更新粒子位置的方程； Step 7 若未达到终止条件(足够小的适应值或预设的最大迭代次数)，则
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 得到更好的解，其他几种改进方案的解都比较差；函
8、数 F2(x)在随粒子群维数增加的情况下，4种改进方案和 QDPSO 都能得出比较好的解。通过实验，可以看出：对于单峰函数 F1(x)， 的递减不能太小，从方案 1-QDPSO 和 2-QDPSO 的结果就可以比较出来，而方案 3-QDPSO 和 4-QDPSO 的结果不好，可能是因为它们搜索的区域太小，从而陷入局部最优解。 对于多峰函数 F2(x)， 的变化对测试函数的解的精确度没有太大影响，说明了改进方案在此方面没有明显提高。接下来，我们还对算法的收敛速度进行了比较。结果如表 2 所示。表 2 是对函数测试 50 次后取得平均值的结果。可见对于函数 F1(x)，1-QDPSO 和 QDPS
9、O 都在 10 维的情况下收敛，而 20 维时只有 1-QDPSO 收敛，其他函数都没有收敛，导致这种结果的原因有 2 种：(1)各种方案随 的变化，削弱或失去了调节能力，在达到最大迭代次数时也未收敛；(2)即使在算法已搜索到最优解附近时，由于局部搜索能力太差，跳过了最优解。对于函数 F2(x)，3-QDPSO，4-QDPSO，QDPSO 收敛速度都比较快，1=QDPSO 和 2-QDPSO 的收敛速度就相对较慢一些。这是由于对多峰函数测试时，各种方案的初始化范围附近可能存在最优解，所以减少了迭代次数，加快了算法速度。通过对 4 种方案的研究，这里选取方案 1 应用于 0-1 背包问题，并得到
10、理想的结果。2 对改进算法应用到 0-1 背包问题2.1 0-1 背包问题的数学描述0-1 背包问题是一种典型的组合优化问题。0-1 背包问题的描述如下：假设有 n 个物品，其大小和价值分别为 wi 和 ci(其中 wi0，ci0，i=1，2，n)，背包的容量假设为 V(V0)。要求在背包的容量限制内，使所装物品的总价值最大。该问题的数学模型可表示为：其中，当将物品 i 装入背包时 xi=1；否则 xi=0。2.2 0-1 背包问题的改进粒子群算法改进粒子群算法应用到 0-1 背包问题的思想：粒子群中粒子的个数与每个粒子的维数相等。先定义二进制数 x，x 只能取 0 和 1。再把粒子的种群数看
11、作背包的个数 n，对于每个粒子 xi(其中 i=1，2，n 表示粒子个数)有 n 个维数，即 1 个粒子有 n 个位置。然后初始化每个粒子的速度 vij，(其中 j=1，2 ，n 表示每个粒子位置的维数)，每个粒子的每一维都对应一个初始化了的速度。对公式(8)进行变化：解决背包问题的步骤：(1)初始化粒子的速度和位置；(2)将初始化的位置向量代人式(9)，在所得每个粒子的解中找到最优解 pbest，并令 pbest=gbest；(3)通过式(6)更新粒子的速度，对所得最优解进行修正，然后再次代入函数方程中继续寻找新的最优解；(4)若达到终止条件，则结束迭代，输出到存储向量，即为所求结果；否则，
12、k=k+1，转步骤(3)。2.3 实验仿真为了验证 1-QDPSO 求解 01 背包问题的可行性及有效性，这里进行了 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，
13、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 背包问题，可以看出改进算法性能的改善在应用中得到更好的体现
