基于適應值變化率的個體決策粒子群算法

焦國輝+陳鵬

摘 要： 傳統(tǒng)的粒子群算法通過粒子的適應值大小來判斷粒子好壞，作為智能體，粒子本身有決策能力，而這在粒子群算法中并沒有體現(xiàn)出來。因此提出了一種新的粒子好壞的判斷標準——適應值變化率。通過個體決策的方法和適應值變化率，利用粒子位置與對應的適應值信息對粒子群算法中的個體歷史最優(yōu)位置和認知系數(shù)進行決策。采用幾個常用的測試函數(shù)進行仿真實驗，與其他改進的粒子群算法相比，結(jié)果表明該算法具有更好的性能。

關鍵詞： 粒子群算法； 適應值變化率； 個體決策； 認知系數(shù)

中圖分類號： 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

粒子群算法是一種基于群體智能的隨機優(yōu)化算法[1]，由于其結(jié)構(gòu)簡單，運算速度快，且不需要領域知識，一經(jīng)提出便引起許多學者廣泛的研究興趣，現(xiàn)在已經(jīng)廣泛應用于神經(jīng)網(wǎng)絡訓練[2]，模式識別[3]，多目標優(yōu)化[4] ，圖像處理[5]等領域。近幾年，許多學者從多個方面對粒子群算法進行了深入研究，Liu 等人利用混沌特性設置參數(shù)[6]，Zhan 等人實時識別算法狀態(tài)自動控制參數(shù)設置[7]，cai提出了個性化粒子群算法[8]，馬慧民提出了文化進化的粒子群算法[9] 。曾傳華提出了強社會認知能力的粒子群優(yōu)化算法[10]。Tsai 等人則直接使用特定的全局最優(yōu)來替代個體最優(yōu)[11] 。這些改進的粒子群算法都是把適應值作為判斷粒子優(yōu)劣的標準，本文提出了新的判斷粒子優(yōu)劣的標準——適應值變化率，表現(xiàn)最好的不是那些適應值最好的的粒子，而是那些進步最快的粒子，即適應值變化率最快的。同時雖然作為智能體，粒子本身具有個體決策的能力，但是粒子群算法沒有體現(xiàn)粒子在這方面的能力。所以借助適應值變化率，通過個體決策的思想，把個體歷史最優(yōu)位置和認知系數(shù)通過個體決策計算出來。這樣既可以增加算法的智能特性又可以保持粒子的多樣性，避免算法過陷入局部最優(yōu)。

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的最優(yōu)位置，稱為個體歷史最優(yōu)位置。[pgk]為全局歷史最優(yōu)位置；j=1，2，…，m，m為粒子的個數(shù)；k=1，2，…，n，n為解空間的維數(shù)；t為粒子的當前進化代數(shù)；w為慣性權(quán)重，具有平衡全局和局部搜索能力的作用，介于[0，1]之間；c1與c2為學習因子，通常在[0，2]之間取值，c1具有調(diào)節(jié)粒子向自身最優(yōu)位置靠近的作用；c2具有調(diào)節(jié)粒子向群體歷史最優(yōu)位置靠近的作用。[r1]～[U（0，1）]，[r2]～[U（0，1）]為兩個相互獨立的隨機數(shù)。

2 適應值變化率

根據(jù)多峰值測試函數(shù)的立體圖形，函數(shù)峰值為全局或局部最優(yōu)值。也就是說越接近峰值，同一個粒子相鄰兩位置之間的斜率的絕對值越大。斜率的絕對值越大，粒子越接近全局最優(yōu)或者局部最優(yōu)位置，斜率的絕對值小的情況出現(xiàn)最優(yōu)值的概率較小。下面就是確定適應值變化率的方法步驟。

[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 個體決策個體歷史最優(yōu)位置

由于粒子本身的生長環(huán)境、能力、經(jīng)驗等方面的差異，所以他們在決策過程中的作用是不同的，這中差異可以用決策權(quán)重來表示：

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

決策后的個體歷史最優(yōu)位置為[PID=QjPjt]，其中[Pjt]為上一代個體歷史最優(yōu)位置。

3.2 個體決策認知系數(shù)

從式（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）]分別表示認知系數(shù)在[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 仿真實驗

為了驗證本文提出的的基于適應值變化率個體決策認知系數(shù)粒子群算法（Individual Decision Cognitive Strategy with Rate change Fitness，IDCS?RF）對函數(shù)優(yōu)化的性能，利用標準粒子群算法（Standard Particle Swarm Optimization，SPSO）及帶時間加速常數(shù)的粒子群算法[17]Modified Time?varying accelerator coefficients Particle Swarm Optimization，MPSO?TVAC）進行比較。

為了測試PSO?IDHF在函數(shù)優(yōu)化方面的性能，本文選取了兩個經(jīng)典的測試函數(shù)進行測試：

Schwefel函數(shù)：

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

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

Griewank函數(shù)：

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

兩個測試函數(shù)的維數(shù)分別為50，200，既包含了低維，又包括了高維情形。種群所含微粒數(shù)為100，每個函數(shù)獨立運行30 次，每次的最大進化代數(shù)為維數(shù)的50倍。如表1、表2所示。仿真結(jié)果見圖1～圖4所示。

表1 Schwefel函數(shù)比較結(jié)果

表2 Griewank函數(shù)函數(shù)比較結(jié)果

圖1 Schwefel 50維的比較結(jié)果

圖2 Schwefel 200維的比較結(jié)果

圖3 Griewank 50維的比較結(jié)果

圖4 Griewank 200維的比較結(jié)果

對于Schwefel 函數(shù)，從表1，表2中數(shù)據(jù)可以看出，無論低維50還是高維200，均值還是方差，IDCS?RF都比SPSO與MPSO?TVAC結(jié)果要好，始終能夠保持較快的收斂速度，明顯優(yōu)于另外兩種算法。從圖可以看出，在進化初期PSO?IDRF取得了較好的效果，表明該算法具有較強的全局搜索能力。

Griewank函數(shù)在低維較難優(yōu)化，且極不穩(wěn)定。在低維50維維IDCS?RF與SPSO與MPSO?TVAC相比結(jié)果要好，但是差別不是很大，但是在高維200無論均值還是方差，IDCS?RF都取得了不錯的結(jié)果。從圖可以看出，在搜索早期IDCS?RF效果不是很明顯，但是在搜索后期達到了很好的效果，保持了較快的收斂速度。

5 結(jié) 語

本文引入了一種新的判斷粒子優(yōu)劣的標準——適應值變化率，作為智能體，粒子本身具有個體決策的能力，但是粒子群算法中沒有表現(xiàn)出粒子在個體決策方面的能力。本文通過引入個體決策的思想，借助適應值變化率來個體決策個體歷史最優(yōu)位置和認知系數(shù)。改變了傳統(tǒng)粒子群算法以適應值大小來判斷粒子優(yōu)劣的弊端，同時每個粒子具有個體決策能力，很好的擺脫了粒子群算法容易陷入局部最優(yōu)的劣勢。仿真結(jié)果表明該算法具有更好的性能。

參考文獻

[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] 曾傳華，申元霞.強社會認知能力的粒子群優(yōu)化算法[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] 曾傳華，申元霞.強社會認知能力的粒子群優(yōu)化算法[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] 曾傳華，申元霞.強社會認知能力的粒子群優(yōu)化算法[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.