黃毅 柳先輝 趙衛(wèi)東

摘要：近來，粒子群優(yōu)化算法在許多工程應(yīng)用領(lǐng)域取得關(guān)注和使用。這個(gè)算法受自然界鳥類活動(dòng)的啟發(fā)，形成了一個(gè)簡單有效的最優(yōu)化算法。有許多研究者通過組合其他heuristics算法和PSO算法的優(yōu)點(diǎn)，產(chǎn)生了許多混合算法，大大提高了PSO算法的表現(xiàn)。基于以上思想，提出了一種使用粒子所在周邊信息的改進(jìn)PSO算法。使用4個(gè)典型的非線性優(yōu)化問題來測(cè)試和標(biāo)準(zhǔn)PSO算法的性能差異。

關(guān)鍵詞：PSO；混合算法；最優(yōu)化；周邊信息

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1009-3044(2012)16-3973-04

Using Neighbor Information to Improve PSO Algorithm

HUANG Yi, LIU Xian-hui, ZHAO Wei-dong

(Department of Electronics and Information Engineering, Tongji University, Shanghai 201804, China)

Abstract: Recently, particle swarm optimization algorithm has got a lot of attention and been used in many engineering applications. This algorithm is inspired by nature bird activities and becomes a simple and effective optimization algorithm. Many researchers proposed many hybrid algorithms through a combination of the advantage of other heuristics algorithm and PSO algorithm, greatly improving the perfor? mance of the PSO algorithm. Based on above ideas, an improved PSO algorithm by using neighbor information surrounding the particle is proposed. The performance of the improved algorithm is tested by using four typical non-linear optimization and compared with that of basic PSO.

Key words: PSO; hybrid algorithm; optimization; neighbor information

群體智能算法是一門新興的優(yōu)化計(jì)算方法，自從20世紀(jì)80年代出現(xiàn)以來，引起了多個(gè)學(xué)科領(lǐng)域科研人員的關(guān)注，已經(jīng)成為了優(yōu)化技術(shù)領(lǐng)域的一個(gè)研究重點(diǎn)，是人工智能以及經(jīng)濟(jì)、社會(huì)、生物等交叉學(xué)科的熱點(diǎn)和前沿領(lǐng)域。

PSO算法最早是1995年由Kennedy和Eberhart提出的，來解決單目標(biāo)或多目標(biāo)連續(xù)優(yōu)化問題[1]?，F(xiàn)在PSO擴(kuò)展到處理組合優(yōu)化問題(combinatorial optimization problems)。算法實(shí)現(xiàn)的簡單；在各種問題中有良好的優(yōu)化能力；因此PSO算法，廣泛用于多對(duì)象優(yōu)化，參數(shù)尋優(yōu)[1]。PSO算法缺點(diǎn)在于，有計(jì)算復(fù)雜性高和容易陷入局部最優(yōu)點(diǎn)的問題。這些缺點(diǎn)限制了PSO的應(yīng)用。因此，大量的研究工作集中于各種參數(shù)的改進(jìn)[6]，以及混合算法的設(shè)計(jì)[3][4][5]。他們的方法在提高了PSO算法表現(xiàn)的同時(shí)，也額外地增加了計(jì)算的復(fù)雜度或開銷。

在整個(gè)PSO算法中，粒子局部最優(yōu)點(diǎn)的選擇起著很大的影響和作用。通過選擇某些符合條件的特定粒子，使用其周邊信息，來提高局部最優(yōu)點(diǎn)的準(zhǔn)確度，從而提高整個(gè)算法的性能。該文在借鑒CLS-PSO算法[3]的基礎(chǔ)上，在粒子局部最優(yōu)點(diǎn)的選擇準(zhǔn)確度上有所改進(jìn)，不僅保留了PSO的全局探索能力，而且提高了算法的準(zhǔn)確度。

通過模擬實(shí)驗(yàn)，我們得到了圖2，3，4，5的結(jié)果。我們可以清楚地發(fā)現(xiàn)，改進(jìn)的PSO算法的表現(xiàn)性能優(yōu)于標(biāo)準(zhǔn)PSO算法。仔細(xì)觀察各表，我們也可以發(fā)現(xiàn)2者在迭代次數(shù)為100到1000次之間時(shí)，性能有不小的提升（如圖2），而超過1000次以后，性能基本保持不變，在少數(shù)情況下，反而會(huì)有所下降（如圖5）。

改進(jìn)PSO算法為什么對(duì)Griewank函數(shù)的效果會(huì)隨著迭代次數(shù)的增加而下降的原因，我們現(xiàn)在還不得而知。一個(gè)可能的原因是函數(shù)的邊界以及實(shí)驗(yàn)的設(shè)定。我們?cè)谝院髸?huì)更加深入探討這個(gè)問題。然而，從上面得到的實(shí)驗(yàn)結(jié)果，可以看出改進(jìn)的PSO算法明顯優(yōu)于標(biāo)準(zhǔn)PSO算法。

該文提出了一種基于周邊信息的PSO改進(jìn)算法，通過與標(biāo)準(zhǔn)PSO算法進(jìn)行多次實(shí)驗(yàn)比較與性能分析。通過實(shí)驗(yàn)結(jié)果，我們可以得出改進(jìn)的PSO算法的表現(xiàn)優(yōu)于標(biāo)準(zhǔn)PSO算法的結(jié)論。為了對(duì)算法有更進(jìn)一步的研究，我們?cè)谝院筮€需要對(duì)更多地優(yōu)化函數(shù)進(jìn)行分析測(cè)試，另外改進(jìn)PSO算法的邊界選取策略和迭代次數(shù)還需要更進(jìn)一步的研究。在我們將來的研究中，我們會(huì)進(jìn)行更多的實(shí)驗(yàn)來理解PSO算法的行為與表現(xiàn)。

[1] Shi Y H,Eberhart R C.A modified particle swarm optimization[C].Proceedings of IEEE International Conference on Evolutionary Computa? tion,1998:69-73.

[2] RAHMATIZADEH S H,SHAH-HOSSEINI H,TORKAMAN H.The Ant-Bee routing algorithm: a new agent based Nature-Inspired rout? ing algorithm[J].Journal of Applied science,2009,9(5):983-987.

[3] LI XIANG,LIANG XIMING,YAN GANG,etc.Using co-line search technique to improve performance of PSO[J].Control Conference,CCC 2008,27th Chinese,2008:49-52.

[4] SOUDAN,SAAD.An evolutionary dynamic population size PSO implementation[C].Information and Communication Technologies:From Theory to Applications, 2008, 3rd International Conference,2008:1-5.

[5] JIE JING,ZENG JIANCHAO.Particle swarm optimization with diversity controlled acceleration coefficients[C]. Natural Computation, 2007, 3rd International Conference, 2007:150-154.

[6] PARSOPOULOS K E,VARAHATIS M N.Parameter selection and adaptation in unified particle swarm optimization[J].Journal on Mathe? matical and Computer Modeling,2007(46):198-213.

[7] Li T S.Applying wavelets transform and support vector machine for copper clad laminate defects classification[J].Computers & Industrial Engineering,2009,56:1154-1168.

[8] Vapnik V N.An overview of statistical learning theory[J].IEEE Transaction on Neural Networks,1999,10(5):988-999.