基于适应值变化率的个体决策粒子群算法

焦国辉+陈鹏

摘 要： 传统的粒子群算法通过粒子的适应值大小来判断粒子好坏，作为智能体，粒子本身有决策能力，而这在粒子群算法中并没有体现出来。因此提出了一种新的粒子好坏的判断标准——适应值变化率。通过个体决策的方法和适应值变化率，利用粒子位置与对应的适应值信息对粒子群算法中的个体历史最优位置和认知系数进行决策。采用几个常用的测试函数进行仿真实验，与其他改进的粒子群算法相比，结果表明该算法具有更好的性能。

关键词： 粒子群算法； 适应值变化率； 个体决策； 认知系数

中图分类号： TN911?34 文献标识码： A 文章编号： 1004?373X（2014）14?0018?03

Individual decision particle swarm optimization based on change rate of adaptive value

JIAO Guo?hui1， CHEN Peng2

（1.Computer Centre of Taiyuan Normal University， Taiyuan 030619， China； 2.Military Department， Xian Institute of Politics， Xian 710068， China）

Abstract：Traditional particle swarm optimization can determine the quality of the particle by adaptive value. As an intelligent agent， each particle has the ability of decision?making， but it is not reflected in the PSO. Therefore， change rate of adaptive value， a new judgement standard for particle evaluation is proposed. The particles position and corresponding information of the adaptive value are adopted to decide individual optimal position in history and cognitive coefficient in the PSO with the help of individual decision?making method and change rate of adaptive value. Several commonly?used test functions were used in the simulation experiments. The results shows that the algorithm has a better performance than other improved PSOs.

Keywords： particle swarm algorithm； change rate of adaptive value； individual decision； cognitive coefficient

粒子群算法是一种基于群体智能的随机优化算法[1]，由于其结构简单，运算速度快，且不需要领域知识，一经提出便引起许多学者广泛的研究兴趣，现在已经广泛应用于神经网络训练[2]，模式识别[3]，多目标优化[4] ，图像处理[5]等领域。近几年，许多学者从多个方面对粒子群算法进行了深入研究，Liu 等人利用混沌特性设置参数[6]，Zhan 等人实时识别算法状态自动控制参数设置[7]，cai提出了个性化粒子群算法[8]，马慧民提出了文化进化的粒子群算法[9] 。曾传华提出了强社会认知能力的粒子群优化算法[10]。Tsai 等人则直接使用特定的全局最优来替代个体最优[11] 。这些改进的粒子群算法都是把适应值作为判断粒子优劣的标准，本文提出了新的判断粒子优劣的标准——适应值变化率，表现最好的不是那些适应值最好的的粒子，而是那些进步最快的粒子，即适应值变化率最快的。同时虽然作为智能体，粒子本身具有个体决策的能力，但是粒子群算法没有体现粒子在这方面的能力。所以借助适应值变化率，通过个体决策的思想，把个体历史最优位置和认知系数通过个体决策计算出来。这样既可以增加算法的智能特性又可以保持粒子的多样性，避免算法过陷入局部最优。

1 标准粒子群算法的进化方程

标准粒子群算法的进化方程可表示如下：

[vjk（t+1）=wvjk（t）+c1r1（pjk（t）-xjk（t））+c2r2（pgk（t）-xjk（t））xjk（t+1）=xjk（t）+vjk（t+1）] （1）

式中：[xjk]为粒子j的当前位置；[vjk]为粒子的当前速度；[pjk]为粒子j的最优位置，称为个体历史最优位置。[pgk]为全局历史最优位置；j=1，2，…，m，m为粒子的个数；k=1，2，…，n，n为解空间的维数；t为粒子的当前进化代数；w为惯性权重，具有平衡全局和局部搜索能力的作用，介于[0，1]之间；c1与c2为学习因子，通常在[0，2]之间取值，c1具有调节粒子向自身最优位置靠近的作用；c2具有调节粒子向群体历史最优位置靠近的作用。[r1]～[U（0，1）]，[r2]～[U（0，1）]为两个相互独立的随机数。

2 适应值变化率

根据多峰值测试函数的立体图形，函数峰值为全局或局部最优值。也就是说越接近峰值，同一个粒子相邻两位置之间的斜率的绝对值越大。斜率的绝对值越大，粒子越接近全局最优或者局部最优位置，斜率的绝对值小的情况出现最优值的概率较小。下面就是确定适应值变化率的方法步骤。

[Fj（t）=f（xj（t））-f（xj（t-1））xj（t）-xj（t-1）] （2）

[weightj（t）=1， if（Fbest（t）=Fworst（t））Fj（t）-Fworst（t）Fbest（t）-Fworst（t）， otherwise] （3）

式中：[xj（t）-xj（t-1）]为粒子[j]在相邻两代中的距离，如果[xj（t）-xj（t-1）=0]，则赋值[weightj（t）=1]，否则按照适应值变化率算出性能评价值[weightj（t）]；[f（xj（t））-f（xj（t-1）））]为适应值之差；[Fj（t）]为适应值变化率的绝对值；[Fbest（t）]与[Fworst（t）]为按照绝对值排序后的最大与最小值。

3 个体决策粒子群算法

3.1 个体决策个体历史最优位置

由于粒子本身的生长环境、能力、经验等方面的差异，所以他们在决策过程中的作用是不同的，这中差异可以用决策权重来表示：

[Qj=eweightjteweight1t+eweight2t，…，+eweightnt]

决策后的个体历史最优位置为[PID=QjPjt]，其中[Pjt]为上一代个体历史最优位置。

3.2 个体决策认知系数

从式（3）可以看出，适应值变化率越大的微子，它的评价值[weightj（t）]越高，而适应值变化率越小的粒子，它的评价值越低。评价值主要是由粒子自本身位置与对应的适应值来确定。等于把粒子在相邻两代的适应值变化率进行了排序，使得变化率越大的粒子评价值越好，反之亦然。设[Xj（t），Xj（t-1），Xj（t-2），…，Xj（t-m）]为微粒[j]在相邻[m]（[m]通过试验设置）代的位置。[fj（xj（t）），fj（xj（t-1）），][fj（xj（t-2），…，fj（xj（t-m）））]为相应的适应值。[c1j=clow（t）+][（chigh（t）-clow（t））·weightj（t）]。其中[clow（t）]与[chigh（t）]分别表示认知系数在[t]代的上下限。对照标准粒子群算法，个体决策后的粒子群算法进化方程为：

[vjk（t+1）=wvjk（t）+c1jr1（pID（t）-xjk（t））+c2r2（pgk（t）-xjk（t））xjk（t+1）=xjk（t）+vjk（t+1）]

4 仿真实验

为了验证本文提出的的基于适应值变化率个体决策认知系数粒子群算法（Individual Decision Cognitive Strategy with Rate change Fitness，IDCS?RF）对函数优化的性能，利用标准粒子群算法（Standard Particle Swarm Optimization，SPSO）及带时间加速常数的粒子群算法[17]Modified Time?varying accelerator coefficients Particle Swarm Optimization，MPSO?TVAC）进行比较。

为了测试PSO?IDHF在函数优化方面的性能，本文选取了两个经典的测试函数进行测试：

Schwefel函数：

[f2（x）=-i=1nxisin（xi）， -500≤xi≤500]

[min（f2）=f2（420.968 7，…，420.968 7）=-418.98×n]

Griewank函数：

[f.5（x）=14 000i=1nx2i-i=1ncosxii+1， -600≤xi≤600] [min（f5）=f5（0，…，0）=0]

两个测试函数的维数分别为50，200，既包含了低维，又包括了高维情形。种群所含微粒数为100，每个函数独立运行30 次，每次的最大进化代数为维数的50倍。如表1、表2所示。仿真结果见图1～图4所示。

表1 Schwefel函数比较结果

表2 Griewank函数函数比较结果

图1 Schwefel 50维的比较结果

图2 Schwefel 200维的比较结果

图3 Griewank 50维的比较结果

图4 Griewank 200维的比较结果

对于Schwefel 函数，从表1，表2中数据可以看出，无论低维50还是高维200，均值还是方差，IDCS?RF都比SPSO与MPSO?TVAC结果要好，始终能够保持较快的收敛速度，明显优于另外两种算法。从图可以看出，在进化初期PSO?IDRF取得了较好的效果，表明该算法具有较强的全局搜索能力。

Griewank函数在低维较难优化，且极不稳定。在低维50维维IDCS?RF与SPSO与MPSO?TVAC相比结果要好，但是差别不是很大，但是在高维200无论均值还是方差，IDCS?RF都取得了不错的结果。从图可以看出，在搜索早期IDCS?RF效果不是很明显，但是在搜索后期达到了很好的效果，保持了较快的收敛速度。

5 结 语

本文引入了一种新的判断粒子优劣的标准——适应值变化率，作为智能体，粒子本身具有个体决策的能力，但是粒子群算法中没有表现出粒子在个体决策方面的能力。本文通过引入个体决策的思想，借助适应值变化率来个体决策个体历史最优位置和认知系数。改变了传统粒子群算法以适应值大小来判断粒子优劣的弊端，同时每个粒子具有个体决策能力，很好的摆脱了粒子群算法容易陷入局部最优的劣势。仿真结果表明该算法具有更好的性能。

参考文献

[1] EBERHART R C. Particle swarm optimization [C]. IEEE International Conference on Neural Networks. Australia： IEEE， 1995： 1942?1948.

[2] MEISSNER M， SCHMUKER M， SCHNEIDER G. Optimized particle swarm optimization and its application to artificial neural network training [J]. Bmc Bioinformatics， 2013， 7 （1）： 125?129.

[3] ZHANG Yong， GONG Dun?wei， QI C L. Vector evolved multiobjective particle swarm optimization algorithm [C]// Proceedings of 2011 International Conference in Electrics， Communication and Automatic Control. [S.l.]： Springer， 2012： 295?301.

[4] MACIEL R S， ROSA M， MIRANDA V， et al. Multi?objective evolutionary particle swarm optimization in the assessment of the impact of distributed generation [J]. Electric Power Systems Research， 2012， 89： 100?108.

[5] Anon. Algorithm for optimal camera network placement [J]. IEEE Sensors Journal， 2012，12（5）： 1402?1412.

[6] LIU B， WANG L， JIN Y H， et al. Improved particle swarm optimization ombined with chaos [J]. Chaos， Solitons & Fractals， 2011 5 （5）： 1261?1271.

[7] ZHAN Z H， ZHANG J， LI Y， et al. Adaptive particle swarm optimization [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（6）： 1362?1381.

[8] CAI Xing?juan， CUI Zhi?hua， ZENG Jian?chao， et al. Dispersed particle swarm optimization [J]. Information Processing Letters， 2012， 105 （6）：231?235.

[9] 马慧民，叶春明.基于文化进化的并行粒子群算法[J].计算机工程，2011，34（2）：194?196.

[10] 曾传华，申元霞.强社会认知能力的粒子群优化算法[J].计算机工程与应用，2009，45（28）：70?71.

[11] TSAI S J， SUN T Y， LIU C C， et al. An improved multi?objective particle swarm optimizer for multi?objective problems [J]. Expert Systems with Applications， 2010， 37 （8）： 5872?5886.

参考文献

[1] EBERHART R C. Particle swarm optimization [C]. IEEE International Conference on Neural Networks. Australia： IEEE， 1995： 1942?1948.

[2] MEISSNER M， SCHMUKER M， SCHNEIDER G. Optimized particle swarm optimization and its application to artificial neural network training [J]. Bmc Bioinformatics， 2013， 7 （1）： 125?129.

[3] ZHANG Yong， GONG Dun?wei， QI C L. Vector evolved multiobjective particle swarm optimization algorithm [C]// Proceedings of 2011 International Conference in Electrics， Communication and Automatic Control. [S.l.]： Springer， 2012： 295?301.

[4] MACIEL R S， ROSA M， MIRANDA V， et al. Multi?objective evolutionary particle swarm optimization in the assessment of the impact of distributed generation [J]. Electric Power Systems Research， 2012， 89： 100?108.

[5] Anon. Algorithm for optimal camera network placement [J]. IEEE Sensors Journal， 2012，12（5）： 1402?1412.

[6] LIU B， WANG L， JIN Y H， et al. Improved particle swarm optimization ombined with chaos [J]. Chaos， Solitons & Fractals， 2011 5 （5）： 1261?1271.

[7] ZHAN Z H， ZHANG J， LI Y， et al. Adaptive particle swarm optimization [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（6）： 1362?1381.

[8] CAI Xing?juan， CUI Zhi?hua， ZENG Jian?chao， et al. Dispersed particle swarm optimization [J]. Information Processing Letters， 2012， 105 （6）：231?235.

[9] 马慧民，叶春明.基于文化进化的并行粒子群算法[J].计算机工程，2011，34（2）：194?196.

[10] 曾传华，申元霞.强社会认知能力的粒子群优化算法[J].计算机工程与应用，2009，45（28）：70?71.

[11] TSAI S J， SUN T Y， LIU C C， et al. An improved multi?objective particle swarm optimizer for multi?objective problems [J]. Expert Systems with Applications， 2010， 37 （8）： 5872?5886.

参考文献

[1] EBERHART R C. Particle swarm optimization [C]. IEEE International Conference on Neural Networks. Australia： IEEE， 1995： 1942?1948.

[2] MEISSNER M， SCHMUKER M， SCHNEIDER G. Optimized particle swarm optimization and its application to artificial neural network training [J]. Bmc Bioinformatics， 2013， 7 （1）： 125?129.

[3] ZHANG Yong， GONG Dun?wei， QI C L. Vector evolved multiobjective particle swarm optimization algorithm [C]// Proceedings of 2011 International Conference in Electrics， Communication and Automatic Control. [S.l.]： Springer， 2012： 295?301.

[4] MACIEL R S， ROSA M， MIRANDA V， et al. Multi?objective evolutionary particle swarm optimization in the assessment of the impact of distributed generation [J]. Electric Power Systems Research， 2012， 89： 100?108.

[5] Anon. Algorithm for optimal camera network placement [J]. IEEE Sensors Journal， 2012，12（5）： 1402?1412.

[6] LIU B， WANG L， JIN Y H， et al. Improved particle swarm optimization ombined with chaos [J]. Chaos， Solitons & Fractals， 2011 5 （5）： 1261?1271.

[7] ZHAN Z H， ZHANG J， LI Y， et al. Adaptive particle swarm optimization [J]. IEEE Transactions on Systems， Man， and Cybernetics， Part B： Cybernetics， 2009， 39（6）： 1362?1381.

[8] CAI Xing?juan， CUI Zhi?hua， ZENG Jian?chao， et al. Dispersed particle swarm optimization [J]. Information Processing Letters， 2012， 105 （6）：231?235.

[9] 马慧民，叶春明.基于文化进化的并行粒子群算法[J].计算机工程，2011，34（2）：194?196.

[10] 曾传华，申元霞.强社会认知能力的粒子群优化算法[J].计算机工程与应用，2009，45（28）：70?71.

[11] TSAI S J， SUN T Y， LIU C C， et al. An improved multi?objective particle swarm optimizer for multi?objective problems [J]. Expert Systems with Applications， 2010， 37 （8）： 5872?5886.