一種基于支持向量數(shù)據(jù)域描述的改進(jìn)微粒群算法

1、2009年第4期文章編號:100622475(2009)0420055204計算機(jī)與現(xiàn)代化JISUANJIYUXIANDAIHUA總第164期一種基于支持向量數(shù)據(jù)域描述的改進(jìn)微粒群算法童子建(東南大學(xué)電氣工程學(xué)院,江蘇南京210096)摘要:分析標(biāo)準(zhǔn)微粒群算法的性能,通過引入支持向量數(shù)據(jù)域描述方法,提出一種改進(jìn)微粒群算法,性,增強(qiáng)了算法的全局尋優(yōu)能力。仿真結(jié)果表明,。關(guān)鍵詞:微粒群;多樣性;支持向量描述中圖分類號:TP301文獻(xiàn)標(biāo)識碼:AAModifiedParticleOtiithmBasedonSupportescriptionTONGZi2jian(ofElectricalEnginee

2、ring,SoutheastUniversity,Nanjing210096,China)Abstract:Behaviorofstandardparticleswarmoptimizationalgorithmisanalyzed.Byusingthesupportvectordomaindescrip2tion,amodifiedPSOalgorithmispresented.Diversityofparticlesisassured.Abilityofglobalsearchingisimproved.SimulationindicatesthatthemodifiedPSOalgori

3、thmcangetbetterperformance.Keywords:particleswarmoptimization;diversity;supportvectordomaindescription0引言近年來,一種新的群體智能算法微粒群算法(ParticleSwarmOptimization,PSO)已在優(yōu)化問題求解、交通、電力、機(jī)器人、電路設(shè)計、圖像處理、生物學(xué)等眾多領(lǐng)域得到了廣泛的應(yīng)用。該算法首先由Ken21nedy與Eberhart于1995年提出,用來解決優(yōu)化問題,由若干微粒構(gòu)成的群體在搜索空間內(nèi)進(jìn)行“飛行”,并計算其適應(yīng)值,群體內(nèi)部交換適應(yīng)值信息,促使個體向優(yōu)秀個體學(xué)習(xí),且保

4、持部分自身特征,從而達(dá)到“認(rèn)知”與“社會”的平衡,最終實現(xiàn)全局優(yōu)化的目的。微粒群算法與其它進(jìn)化算法的不同在于其不采取個體的變異方法,在搜索空間僅需要代數(shù)運(yùn)算,計算量小,并行搜索能力強(qiáng),從而在優(yōu)化領(lǐng)域取得了較大的成功。微粒群收斂速度較快,方法易于實現(xiàn),但也存在容易早熟收斂的問題。本文引入支持向量數(shù)據(jù)域描述,對標(biāo)準(zhǔn)微粒群算法進(jìn)行改進(jìn),仿真結(jié)果表明早熟收斂得到了抑制。1標(biāo)準(zhǔn)微粒群算法Shi等2在文獻(xiàn)1提出的基本微粒群算法基礎(chǔ)上引入慣性權(quán)重,提出了標(biāo)準(zhǔn)微粒群算法,其具體步驟如下:(1)記t=0,首先在D維空間內(nèi)隨機(jī)初始化n個微粒,其位置和速度分別為xi=xi1,xi2,xid,xiD,vi=vi1,v

5、i2,vid,viD,其中i為粒子的索00引號;(2)計算每個微粒的適應(yīng)值函數(shù)(fitnessfunc2tion,取決于優(yōu)化目標(biāo));(3)將每個微粒當(dāng)前位置xti的適應(yīng)值與其經(jīng)歷過的歷史最佳位置Pi=Pi1,Pi2,Pid,PiD的適應(yīng)值比較,若更好,則令Pi=xi;(4)在全部微粒的歷史最佳位置中選出全局最佳位置Pg;t收稿日期:2008205205作者簡介:童子建(19702),男,江蘇江都人,東南大學(xué)電氣工程學(xué)院講師,碩士,研究方向:電力電子與電力傳動,微機(jī)應(yīng)用。56計算機(jī)與現(xiàn)代化2009年第4期(5)令t=t+1,根據(jù)式(1)、式(2)對微粒的速4的基礎(chǔ)上提出了自適應(yīng)距離調(diào)整方法。度、

6、位置進(jìn)行優(yōu)化;(6)若tNmax或適應(yīng)值滿足要求則算法結(jié)束,否則返回步驟(2),其中Nmax為最大進(jìn)化代數(shù)?；疚⒘Ｈ核惴ㄖ懈魑⒘５乃俣?、位置相應(yīng)優(yōu)化公式如下:vidxidt+1t+1ttt=wvid+c1r1d(Pid-xid)+c2r2d(Pgd-xid)(1)(2)=xid+vidtt+1其中w為慣性權(quán)重,c1、c2為正的加速常數(shù),分別調(diào)節(jié)微粒飛向本微粒歷史最佳位置和飛向全局最佳微粒位置的速度,r1、r2為0,1范圍內(nèi)變化的隨機(jī)數(shù)。式(1)中右邊第一項意味著搜索方向的慣性;二項代表著微粒的“認(rèn)知(Cognition)”,全局搜索能力,若無此項,;項則指微粒的“社會(,信息共享,n個微粒的

7、各自單獨(dú)搜索,。由于PSO問題是通過若干微粒在D維空間內(nèi)大范圍搜索來實現(xiàn)全局尋優(yōu)的,其是否能達(dá)到全局最優(yōu)的關(guān)鍵在于微粒在此D維空間的分布的多樣性。因此僅僅依靠適應(yīng)值來判斷是否早熟收斂不夠充分。而單獨(dú)微粒群分布的方差也不足以表征分布的多樣7性,如一維空間的微粒分布1,2,3,4,5的方差較分布1,1,1,1,5的方差為小,能力。鑒于此,把握。2.2(SupportVectorDomaintion,SVDD)可表述如下:對n個D維數(shù)據(jù),尋找一個包含大多數(shù)數(shù)據(jù)的半徑最小的D維超球體,顯然當(dāng)超球體包含全部數(shù)據(jù)時半徑最大,而包含的數(shù)據(jù)數(shù)量較少時,半徑可以相對較小,為了能在盡量包含最多數(shù)據(jù)和使超球體半徑最

8、小二者之間取得平衡,引入松弛變量i,得到以下約束:(xi-a)(xi-a)TR2+ii0(3)82微粒群算法的改進(jìn)微粒群算法性能的關(guān)鍵在于能否在保證全局搜其中a為超球的球心,R為超球半徑,優(yōu)化問題為如下最小化問題:F(R,a,i)=R+C6ii=1n(4)其中C為懲罰系數(shù),用以調(diào)節(jié)超球半徑與超球外數(shù)據(jù)數(shù)量的平衡。利用拉格朗日乘子法,得如下對偶最大化問題:L(ai)=6ai(xixi)-6aiaj(xixj)i=1i,j=1nn對標(biāo)準(zhǔn)微粒群算法進(jìn)行分析,可發(fā)現(xiàn):全局最優(yōu)位置Pgd僅為當(dāng)前搜索到的最優(yōu)位置,該位置未必為全局極值點(diǎn)。易見由于微粒群數(shù)量有限,難以遍歷全部搜索空間。為了有較快的全局搜索能

9、力,通常慣性權(quán)重w設(shè)置不會過小,且在進(jìn)化初期,速度v值較大,在飛行過程中易錯過一些搜索位置,從而不能保證搜索到全局極值點(diǎn)。運(yùn)算在得到最優(yōu)解之前,所有的個體就停留在某處不再進(jìn)化,將形成早熟收斂。為了解決微粒群算法與其它優(yōu)化算法都面臨的早熟收斂的問題,首先需要對早熟收斂進(jìn)行判斷。對此已有一些研究成果,文獻(xiàn)3引入了種群多樣性函數(shù),類似于考察群體到其形心的平均距離,此時若有少數(shù)微粒處于遠(yuǎn)離中心的位置,容易給此判斷方法造成偏4差。Krink等提出一種基于微粒間歐氏距離的提高多樣性的方法,若兩個微粒距離較近,則改變微粒的飛行方向,以提高其多樣性,當(dāng)維數(shù)較高時,微粒在高維空間處于稀疏分布狀態(tài),基于歐氏距離的

10、判別會因所56謂的“維數(shù)災(zāi)難”而性能下降。Monson等在文獻(xiàn)(5)(6)s.t.0aiC,6ai=1i=1n其中,式(5)的()表示內(nèi)積,超球的球心和半徑可表示如下:a=6aixii=1n(7)R=(xixi)+(aa)-2(xia)ii|0aiC(8)ai=0的數(shù)據(jù)分布在超球內(nèi)部,0aiC的數(shù)據(jù)分布在超球球面上,稱為支持向量(SupportVector),利用以上支持向量數(shù)據(jù)域描述方法可以界定微粒在D維空間的分布情況,當(dāng)微粒分布多樣性較高時,超球半徑較大,反之則較小。因此考慮以超球內(nèi)(含球面)各點(diǎn)到球心的平均歐氏距離作為多樣性的度量,這樣可以在忽略少量離群點(diǎn)的同時把握微粒群的整體分布情況,

11、該度量為:d(t)6mi:aiC=1(xtij-tj)2(9)2009年第4期童子建:一種基于支持向量數(shù)據(jù)域描述的改進(jìn)微粒群算法57其中m為超球球面及內(nèi)部的微粒數(shù)量,j為超球的球心?？梢娢墨I(xiàn)3中所提的種群多樣性函數(shù)實際上可看作本式中C趨于無窮時的特例(此時超球包含所有微粒)。當(dāng)d值較高時,系統(tǒng)多樣性較好,否則較差,因此可設(shè)定一個隨迭代運(yùn)算次數(shù)而變化的多樣性度量閾值,以是否超過閾值作為早熟收斂的判據(jù)。Step5:若未到多樣性判斷最大代數(shù)且d(t)d(t),則對超球內(nèi)鄰近球心處微粒按式(10)進(jìn)行速度變異,促其向球外散開;Step7:判斷整個算法是否滿足收斂條件,如滿足,算法結(jié)束,如不滿足,轉(zhuǎn)至S

12、tep3。3性能驗證隨著進(jìn)化的進(jìn)行,微粒群分布的多樣性不可避免地變差。為了保證運(yùn)算最終的收斂性,在進(jìn)化早期應(yīng)當(dāng)具備較高的多樣性,而到了進(jìn)化后期,則對多樣性,本文選取。i)+10)-5.12xi5.1216(-(2222x=100(xi+1-xi)+(1-xi)i=1i=1Df3(x)=xD2D6xi-cos)+1-60xi600i=14000i=1if1被稱為Rastrigin函數(shù),是一個多峰函數(shù),f2被稱為Rosenbrock函數(shù),f3被稱為Griewank函數(shù),這幾若微粒群多樣性度量值的d(t)小于多樣性閾值d(t),則認(rèn)為微粒群過早聚集在一起,此時若不介入算法參數(shù)設(shè)定如下:c1、c2均為

13、2,慣性權(quán)重w由0.9線性遞減至0.4,遞減代數(shù)為2000代,最大運(yùn)行進(jìn)化過程,進(jìn)化將很快出現(xiàn)早熟收斂。因此需要增加其多樣性,讓微粒進(jìn)入其它空間進(jìn)行搜索。故考慮改變微粒飛行方向,使球內(nèi)較為接近球心的微粒向遠(yuǎn)離球心方向飛行,而距球心較遠(yuǎn)的微粒則維持其飛行方向不變,這樣可使微粒群“散開”,從而增加微粒群多樣性。為了避免過度調(diào)整造成微粒位置反復(fù)動蕩,本文僅對超球內(nèi)距球心距離小于d(t)/2的微粒的速度進(jìn)行變異,即采取如下方式:ttttvij=vij+(xij-j)ifrand()pandxij-j代數(shù)為12000代,若連續(xù)3000代最優(yōu)值不更新或優(yōu)225化結(jié)果小于1310,則算法結(jié)束。改進(jìn)PSO算法

14、中支持向量描述懲罰系數(shù)C為0.15,多樣性閾值由2.5線性遞減至0.5,遞減代數(shù)為10000代,速度變異系數(shù)為4,變異概率為0.5,混沌搜索數(shù)為50次。將改進(jìn)后的微粒群算法(稱為MPSO)與原標(biāo)準(zhǔn)PSO算法針對上述幾個測試函數(shù)進(jìn)行比較,對應(yīng)各不同函數(shù)、不同微粒群規(guī)模等各運(yùn)行50次,運(yùn)算結(jié)果平均值如表1所示。表1測試函數(shù)運(yùn)行結(jié)果平均適應(yīng)值測試函數(shù)RastriginRastriginRastriginRosenbrockRosenbrockRosenbrockGriewankGriewankGriewankd(t)/2(10)其中為變異系數(shù),p為變異概率,即超球中離初值(2.56,5.12)(2.

15、56,5.12)(2.56,5.12)(15,30)(15,30)(15,30)(300,600)(300,600)(300,600)微粒群規(guī)模PSO203040203040203040綜上所述,改進(jìn)后的微粒群優(yōu)化算法步驟如下:Step1:參數(shù)設(shè)定:確定標(biāo)準(zhǔn)微粒群算法中的w、c1、c2,最大進(jìn)化代數(shù),多樣性判斷最大代數(shù),SVDD懲罰系數(shù),多樣性閾值,變異系數(shù);Step2:t=0,隨機(jī)確定n個微粒的初始位置及速度;Step3:按式(1)、式(2)進(jìn)行進(jìn)化計算,t=t+1;Step4:按式(5)進(jìn)行SVDD運(yùn)算,并按式(9)計算多樣性度量值d(t);當(dāng)測試函數(shù)為Rastrigin,維數(shù)為30,微粒

16、群規(guī)模58計算機(jī)與現(xiàn)代化2009年第4期為40時,適應(yīng)值對應(yīng)變化曲線如圖1所示,為了方便數(shù)據(jù)的顯示,適應(yīng)值采取以10為底的對數(shù)值;多樣性度量值如圖2所示。初期,多樣性度量值d(t)大于多樣性閾值d(t),其性能等同于與標(biāo)準(zhǔn)PSO相同。但到了進(jìn)化中期,d(t)逐漸受到d(t)的限制,則球心附近微粒經(jīng)過速度變異后逐漸向外飛出,而其余微粒不受限制,因此微粒群始終保持足夠的多樣性,也就意味著微粒群有持續(xù)的搜索能力,因此隨著進(jìn)化的進(jìn)行,不斷找到更優(yōu)適應(yīng)值。4結(jié)束語,。同時由于微粒群規(guī)模通常較小,支持向量描述方法所引入的凸二次規(guī)劃計算復(fù)雜度較低,速度變異也僅為與微粒群算法的迭代運(yùn)算相類似的代數(shù)運(yùn)算,因此改

17、進(jìn)微粒群算法的整體計算代價較小。參考文獻(xiàn):1KennedyJ,EberhartR.ParticleswarmoptimizationC/ProceedingsoftheIEEEInternationalConferenceonNeuralNetworks,1995:194221948.C/ProceedingsoftheIEEEInternationalConferenceonEvolutionaryComputation,1998:69273.optimizer2theARPSOR.TechnicalReport2002202,De2partmentofComputerScience,Uni

18、versityofAarhus,2002.sationwithspatialparticleextensionC/Proceedingsofthe2002CongressonEvolutionaryComputation,2002:147421479.behaviorofdistancemetricsinhighdimensionalspaceC/LectureNotesinComputerScience,2001:4202434.6MonsonCK,SeppiKD.AdaptivediversityinPSOC/Proceedingsofthe8thAnnualConferenceonGeneticandEvolutionaryComputation,2006:59266.圖2多樣性對比曲線由表1可見,在不同維數(shù)、不同微粒群規(guī)模的初始條件下,針對各種測試函數(shù)的運(yùn)行都說明了改進(jìn)后的微粒群算法MPSO較原標(biāo)準(zhǔn)算法為優(yōu)。較為典型的是Rastrigin函數(shù)