双评价粒子群优化算法
2012-02-19张媛媛高兴宝
张媛媛， 高兴宝
(陕西师范大学数学与信息科学学院， 陕西 西安 710062)
0 引 言
作为进化算法之一的粒子群优化算法(Particle Swarm Optimization，PSO)是一种模拟自然界的生物活动以及群体智能的全局随机搜索算法. 由于粒子群优化算法的模型和计算比较简单，全局优化能力强， 且能够解决高维多目标优化问题，因此已成功应用于函数优化、模糊系统控制、神经网络训练等.
自从1995年PSO被提出后，国内外专家在其理论、算法改进及应用方面的研究都取得了很大的进展.关于PSO的数学基础、收敛性和稳定性的研究，2002年法国数学家Clerc与Kennedy[1]在基本粒子群的基础上设计了压缩因子的参数，大大提高了收敛速度；Kadirkamanathan对PSO的研究和数学分析由静态分析深入到了动态分析[2].关于PSO拓扑结构的研究，Kennedy提出了如星型结构、环型结构、齿形结构、金字塔结构、冯．诺曼结构等，并比较了它们在PSO中的性能[3]，2006年Kennedy和Mendes将这些拓扑结构在Fully Informed的PSO上进行了测试[4].在这些静态的拓扑结构的基础上，研究者们在不同的迭代阶段用不同的拓扑结构动态地改变算法的探索和开发能力，在保持种群多样性和算法收敛性上取得了动态的变化和平衡，提高了算法的整体性能[5].另外，研究者还通过将其他搜索算法与PSO算法相结合，得到了许多不同性能的PSO混合算法，如Chen等人将遗传算法中的变异算子和交叉算子引入到PSO算法中[6，7]，增加种群的多样性以提高种群的搜索能力；Zhang和Xie将PSO算法与差分进化算法进行了混合[8].以上对PSO的改进仅限于结构和与其他算法的混合，本文从粒子群的个体出发，不但对迭代后粒子与上一代粒子的适应值进行评价，还评价了它们的位置，根据评价结果对每个粒子进行不同的操作，从而提高了整个粒子群的搜索速度和求解最优解的精度.
1 粒子群优化算法
在粒子群优化算法中，通过随机产生一定数目的粒子作为问题搜索空间的可行解，然后进行迭代搜索， 直到找到最优粒子.每个粒子都有自己的位置和速度，其优劣依据适应值来评价，即根据问题定义的适应度函数的值来评价；粒子根据自己的历史最优和群体的全局最优解决定下一次的位置和速度，进行不断的更新，使其在问题搜索空间进行探索和开发， 最终找到全局最优解.
设在一个D维目标搜索空间中，有N个粒子组成一个群体，第i个粒子的位置、速度和个体最优可用向量分别表示为：
群体探索到的最优位置为：gbest=(gbest1,gbest2,…,gbestD)，则其速度和位置的更新公式如下：
(1)
(2)
其中w是惯性权值，c1和c2是加速系数，r1和r2是两个[0.1]区间的随机数，t是迭代次数.
根据文献[9]，公式(1)中除第1项为粒子前一次迭代的速度外，其余两项为“认知项(cognition)”和“社会项(social)”，分别表示粒子自身的思考和对社会的认识.前一次迭代速度起到平衡全局和局部搜索的能力，“认知项(cognition)”使粒子有足够强的全局搜索能力，避免陷入局部极小，而“社会项(social)”体现了粒子间的信息共享.三项的共同作用使粒子在搜索空间有较好的飞行速度. 此外当w=1时， 算法称为基本粒子群算法.基本粒子群算法中，由于速度更新后的值变得很大，从而使粒子的位置变化也很大而偏离搜索空间. 针对此缺点，Shi等引入了如下线性递减权值w来平衡探索和开发能力：
w=wmax-i·(wmax-wmin)/Gmax
(3)
其中wmax、wmin分别为最大和最小惯性权值，Gmax是最大迭代次数.称此算法为标准粒子群算法.
2 双评价粒子群算法
2.1 双评价粒子群优化算法的思想
基于标准粒子群优化算法， 对迭代后的每个粒子的位置和适应值与上一代粒子的位置和适应值进行比较， 然后根据比较结果对粒子进行变异.
2.2 具体操作
在分析标准粒子群的迭代轨迹后，将迭代过程首先分为探索阶段和开发阶段， 即根据经验0～0.2 为探索阶段，0.2 ～1为开发阶段；其次在不同阶段根据评价结果对性质劣的粒子进行不同的变异.
在此，分如下3种情形对粒子进行相应的处理.
在探索阶段, 首先计算当前每个粒子的适应值(f(xi(t)))和到个体最优粒子的距离d1以及上一代粒子的适应值(f(xi(t-1)))和到个体最优粒子的距离d2.
(1) 若f(xi(t))
(2) 若f(xi(t))>f(xi(t-1))且d1 (3)若f(xi(t)) 类似于探索阶段，在开发阶段，首先迭代后计算当前每个粒子的适应值(f(xi(t)))和到全局最优粒子的距离d3以及与上一代粒子的适应值(f(xi(t-1)))和到全局最优粒子的距离d4. (1) 若f(xi(t)) (3) 若f(xi(t)) 为比较两个优化算法进化的效果.本文对6个函数进行了测试，其中函数f1、f2、f3为单峰函数，函数f4、f5、f6为多峰函数，且都有一个极值点. 测试函数如下： 根据实验，算法参数设置如下：种群规模为N=30， 粒子的维数为D=30， 最大迭代步数相应为Gmax=1 000，加速因子c1=2，c2=2.6，线性下降的惯性权重w的变化范围为[0. 2, 0. 4]. 两种算法对测试函数的进化轨迹如图1至图6所示. 图1 Sphere model function 图2 Quadric function 图3 Rosenbrock function 图4 Schwefel function 图5 Rastrigin function 图6 Griewank function 表1测试结果中SPSO代表标准粒子群优化算法， IPSO代表双评价粒子群优化算法.表中数据显示了SPSO和IPSO两种算法对函数f1(x)、f2(x)、f3(x)、f4(x)、f5(x)、f6(x)数值仿真的测试结果与精确解的比较.从实验结果看到，对函数f1(x)、f2(x)、f3(x)、f4(x)、f5(x)、f6(x)，双评价粒子群优化算法在标准粒子群优化算法的基础上，它的探索速度和开发精度都有一定的提高. 表1 测试结果 针对标准粒子群算法对迭代后粒子的优劣并不进行评价的缺陷，本文提出了双评价粒子群优化算法. 从实验结果可以看出双评价粒子群优化算法不仅加快了粒子群的探索速度， 还提高了开发精度.然而如何依据问题的特点来划分探索和开发阶段，以提高算法的性能仍是有待实验及研究的问题. 参考文献 [1] M Clerc, J Kennedy. The particle swarm-explosion, stability and convergence in a multidimensional complex space[J]. IEEE Trans. Evol. Comput.,2002,6(2):58-73. [2] V Kadirkamanathan, K Selvarajah, P J Fleming. Stability analysis of the particle dynamics in particle swarm optimizer[J].IEEE Trans. Evol. Comput., 2006, 10(3):245-255. [3] J Kennedy, R Mendes. Population structure and particle swarm performance[J]. Proc. IEEE Congr. Evol. Comput., 2002，(1):1 671-1 676. [4] J Kennedy, R Mendes. Neighborhood topologies in fully informed and best-of-neighborhood particle swarms[J]. IEEE Trans. on Syst. Man, Cybern., C, 2006,36(4):515-519. [5] J J Liang, P N Suganthan. Dynamic multi-swarm particle swarm optimizer[J]. Swarm Intelligence Symp., 2005,(6):124-129. [6] Y P Chen, W C Peng, M C Jian. Particle swarm optimization with recombination and dynamic linkage discovery[J]. IEEE Trans. on Syst., Man,Cybern., B, 2007,37(6):1 460-1 470. [7] P S Andrews. An investigation into mutation operators for particle swarm optimization[J]. Proc. IEEE Congr. Evol. Comput., 2006，(5):1 044-1 051. [8] W J Zhang, X F Xie. DEPSO: hybrid particle swarm with differential evolution operator[J]. Proc. IEEE Congr.Sys., Man,Cybern., 2003, (10): 3 816-3 821. [9] Shi Y, Eberhart R C. A Modified Particle Swarm Optimizer[C]. Proceedings of the IEEE . Congress on Evolutionary Computation, 1998:69-73.
3 算法的测试
4 结束语
