混沌粒子群優(yōu)化算法

混沌粒子群優(yōu)化算法..計算機科學2004V01.31N-0.8高鷹h2謝勝利1(華南理工大學電子與信息學院廣州510641)1(廣州大學信息機電學院計算機科學與技術系廣州510405)2摘要粒子群優(yōu)化算法是一種新的隨機全局優(yōu)化進化算法。本文把混沌手優(yōu)思想引入到粒子群優(yōu)化算法中，這種方法利用混沌運動的隨機性、遍歷性和規(guī)律性等特性首先對當前粒子群體中的最優(yōu)粒子進行混池尋優(yōu)，然后把混沌尋優(yōu)的結果隨機替換粒子群體中的一個粒子。通過這種處理使得粒子群體的進化速度加快t從而改善了粒子群優(yōu)化算法擺脫局部極值點的能力，提高了算法的收斂速度和精度。仿真結果表明混沌粒子群優(yōu)化算法的收斂性能明顯優(yōu)于粒子群優(yōu)化算法。關鍵詞粒子群優(yōu)化算法?；煦缡謨?yōu)，優(yōu)化’ChaosParticleSwarmOptimizationAlgorithmGAOYin91”XIESheng—(CollegeofElectronic&InformationEngineeringtSouthChinaUniversityofTechnology，Guangzhou510641)1(Dept.ofComputerScienceandTechnology.GuangzhouUniversity?Guangzhou510405)2AbstractParticleswarmoptimizationisanewstochasticglobaloptimizationevolutionaryalgorithm.Inthispaper，thechaoticsearchisembeddedintooriginalparticleswarmoptimizers.Basedontheergodicity，stochasticpropertyandregularityofchaos,flnewsuperiorindividualisreproducedbychaoticsearchingonthecurrentglobalbestindivid—ualoandastochasticselectedindividualfromthecurrent"population"isreplacedbythenewsuperiorindividual.TheparticleswarmoptimizationembeddedchaoticsearchquicIcenstheevolutionprocess,andimprovestheabilitiesofseekingtheglobalexcellentresultandconvergencespeedandaccuracy.Theexperimentresultsdemonstratethattheproposedalgorithmsaresuperiortooriginalparticleswarmoptimizationalgorithms.KeywordsParticleswarmoptimization,Chaoticsearch,0ptimization1引言Kennedy和EberhartE“釘于1995年提出的粒子群優(yōu)化算法是一種基于群智能的隨機優(yōu)化進化算法。同遺傳算法類似，是一種基予群體的具有全局尋優(yōu)能力的優(yōu)化工具。但它沒有遺傳算法中用的交叉以及變異等復雜的遺傳操作，其優(yōu)勢在于簡單、易于實現(xiàn)同時又有深刻的智能背景，既適合科學研究。又特別適合工程應用。自從粒子群優(yōu)化算法提出以來，一直受到計算智能等領域的研究人員的廣泛關注，在短短的幾年時間里取得了豐碩的研究成果［2““。然而，Kennedy等人提出的粒子群優(yōu)化算法亦有其不足：易陷入局部極值點，進化后期收斂速度慢，精度較差等。為了克服粒子群優(yōu)化算法的這些不足，研究人員提出了許多改進的粒子群優(yōu)化算法，如：1998年ShiY提出的帶慣性因子的粒子群優(yōu)化算法［3］，隨后于2001年給出的模糊自適應粒子群優(yōu)化算法“1；為控制粒子的飛行速度，ClercM于1999年提出的帶約束因子的粒子群優(yōu)化算法［53；借鑒遺傳算法的思想，AngelineP.(1998)提出了雜交粒子群優(yōu)化算法口］，之后，LovbjergM(2001)給出了具有繁殖和子群的粒子群優(yōu)化算法［7］，2003年Natsuki又給出的具有高斯變異的粒子群優(yōu)化算法［83；為使粒子群優(yōu)化算法更易跳出局部極值點，Van(2001)給出了協(xié)同粒子群優(yōu)化算法“”］；文［11，123(1997，2000)對粒子群優(yōu)化算法進行了擴展而提出了離散粒子群優(yōu)化算法等。這些算法從不同方面對粒子群優(yōu)化算法進行了改進，不同程度地提高了算法的收斂速度和精度，但效果并不是非常理想。混沌(Chaos)是自然界中一種常見的非線性現(xiàn)象?；煦缱兞靠此齐s亂的變化過程其實含有內在的規(guī)律性，利用混沌變量的隨機性、遍歷性及規(guī)律性可以進行優(yōu)化搜索［15,16］。本文將混沌優(yōu)化思想引入到粒子群優(yōu)化算法中，給出了混沌粒子群優(yōu)化算法。其基本思想是首先對粒子群體中的最優(yōu)粒子進行混沌尋優(yōu)，然后把混沌尋優(yōu)的結果隨機替換粒子群體中的一個粒子。這種處理改善了粒子群優(yōu)化算法擺脫局部極值點的能力，提高了算法的收斂速度和精度。仿真結果表明混沌粒子群優(yōu)化算法的收斂性能明顯優(yōu)于粒子群優(yōu)化算法。2混沌粒子群優(yōu)化算法一般將由確定性方程得到的具有隨機性的運動狀態(tài)稱為混沌，呈現(xiàn)混沌狀態(tài)的變量稱為混沌變量。如下的Logistic方程D53是一個典型的混沌系統(tǒng)：計l=pz。(1一z.)n一0，1，2，…(1)*)國家自然科學基金(602"/4006)、廣東省優(yōu)秀人才基金(2000—6—15)、華南理工大學自然科學基金資助項目.離鷹博士后，尉教授，主要研究領域：盲信號處理、人工神經(jīng)網(wǎng)絡、小波分析和智能信息處理等.謝勝利教授，博士生導師，主要研究領域：智能信息處理、盲信號處理、非線性系統(tǒng)學習控制等.?13-萬方數(shù)據(jù)式中盧為控制參量，方程（1）可以看作是一個動力學系統(tǒng)。p值確定后，由任意初值Z°￡［o,1］.可迭代出一個確定的時間序列Z。，砘橢，…。一個混沌變量在一定范圍內有如下特點：隨機性，即它的表現(xiàn)同隨機變量一樣雜亂；遍歷性，即它可以不重復地歷經(jīng)空間內的所有狀態(tài)；規(guī)律性，該變量是由確定的迭代方程導出的?；煦鐑?yōu)化方法是一種新穎的優(yōu)化方法，它利用混沌系統(tǒng)特有的遍歷性來實現(xiàn)全局最優(yōu)，而且它不要求目標函數(shù)具有連續(xù)性和可微性的性質。粒子群優(yōu)化算法最初是Kennedy和Eberhart［1’21從模擬社會行為而發(fā)展起來的具有全局尋優(yōu)能力的優(yōu)化工具。它通過迭代搜尋最優(yōu)值，系統(tǒng)初始化為一組隨機解，而粒子（潛在的解）在解空間追隨最優(yōu)的粒子進行搜索。假設在一個n維的目標搜索空間中，有W個粒子組成一個群體，其中第i個粒子表示一個n維的向量麓一（巍l，軋2，?，囂..），i一1，2，?，N，分基乩，在［口，，幻］范圍內取制值，即n，W札，W幻，i一1，2，…，W，j—1，2，?，以，每個粒子的位置就是一個潛在的解。將Xi帶入一個目標函數(shù)就可以計算出其適應值.根據(jù)適應值的大小衡量Xi的優(yōu)劣。第i個粒子的“飛行”速度也是一個n維的向量，記為8=（研.1'研.2’…，口。），i一1，2，?，W。記第i個粒子迄今為止搜索到的最優(yōu)位置為A一（丸t，pm，…，p。），i一1，2，?，W，整個粒子群迄今為止搜索到的最優(yōu)位置為m一（A。P川，…，P。），粒子群優(yōu)化算法采用下列公式對粒子操作：塒一q+clrl（肼?8）+c2r2（辦一麓）（2）ao一8+砌⑶其中，i=1，2.…，N；學習因子c，和C。是非負常數(shù)m和r。是介于［o,1］之間的隨機數(shù)。迭代中止條件根據(jù)具體問題一般選為最大迭代次數(shù)或（和）粒子群迄今為止搜索到的最優(yōu)位置滿足預定最小適應閾值。粒子群優(yōu)化算法雖然簡單，但其有易陷入局部極值點，進化后期收斂速度慢，精度較差等的缺點。如能采取某種優(yōu)化手段使每一代群體的質量進一步提高，則無疑會有助于后面的搜索過程。為此，我們把混沌優(yōu)化思想引入到粒子群優(yōu)化算法中，提出了混沌粒子群優(yōu)化算法。主要措施是利用混沌運動的遍歷性以當前整個粒子群迄今為止搜索到的最優(yōu)位置為基礎產(chǎn)生混沌序列，把產(chǎn)生的混沌序列中的最優(yōu)位置粒子隨機替代當前粒子群中的一個粒子的位置。提出的混沌粒子群優(yōu)化算法的具體步驟如下：確定參數(shù)：學習因子c。，c2,和群體規(guī)模W，進化次數(shù)，混沌尋優(yōu)次數(shù)。隨機產(chǎn)生N個粒子的種群。按⑵和(3)式對粒子進行操作。對最優(yōu)位置辦一(A—P川，…，A.。)進行混沌優(yōu)化。將P。(i一1,2,…，九)映射到Logistic方程(1)的定義域［o,…7,1］淄=筆蘭亭，(i=1,2,…，n),然后，用Logistic方程(1)進行迭代產(chǎn)生混沌變量序列2j“(m—1,2,…)，再把產(chǎn)生的混沌變量序列zf神(m—1,2,…)通過逆映射聲囂=m+(6J一m)zf神(m一1,2,…)返回到原解空間，得p：搠'=(戶料，戶躞，…，戶冊)，(m—1,2,…)在原解空間對混沌變量經(jīng)歷的每一個可行解p才'(m一1,2,?)計算其適應值，保留性能最好的可行解p。。隨機從當前群體中選出的一個粒子用p。取代。@若達到最大代數(shù)或得到滿意解，則優(yōu)化過程結束，否?14-則返回步驟③。5算法仿真比較下面以求一個基準測試函數(shù)的最小值為例，通過計算機仿真來評價比較混沌粒子群優(yōu)化算法和粒子群優(yōu)化算法的性能，并和帶慣性因子的粒子群優(yōu)化算法(IWPSO)、雜交粒子群優(yōu)化算法(CrossoverPSO,CRPSO)和帶高斯變異的粒子群優(yōu)化算法(MPSO)進行比較，基準測試函數(shù)如下：f(x,y)=z2--0.4cos(3,rx)+2y2—0.6cos(4,ry)—1其中一10Wz,yW10，在［一10,103區(qū)間肉有1個全局最小值點(。，o),全局最小值為0。算法的初始化參數(shù)如下：粒子群規(guī)模20,學習因子ct一1,c2—1。帶慣性因子的粒子群優(yōu)化算法中的慣性因子W--=.0.9,雜交粒子群優(yōu)化算法中的交叉概率只一0.5，帶高斯變異的粒子群優(yōu)化算法中的變異概率P。一0.05,為評價算法的收斂性能，進化次數(shù)設為1000，混沌尋優(yōu)次數(shù)為500,連續(xù)運行50次所得函數(shù)全局最小值點的平均值和全局最小值的平均值作為算法的衡量指標。為便于圖示說明，下面的仿真圖中橫軸表示進化次數(shù)，縱軸表示最優(yōu)適應度值的對數(shù)(即每次進化所得全局最小值的對數(shù))。圖1是函數(shù)，最優(yōu)適應度值的對數(shù)(即每次進化所得全局最小值的對數(shù))隨進化次數(shù)變化的曲線圖(50次獨立運行的平均)，圖中，上面一條曲線對應于粒子群優(yōu)化算法，而下面一條曲線對應混沌粒子群優(yōu)化算法。從圖中可以看出，混沌粒子群優(yōu)化算法的收斂性能明顯優(yōu)于粒子群優(yōu)化算法的收斂性能。表1是粒子群優(yōu)化算法和混沌粒子群優(yōu)化算法數(shù)值仿真結果，由表1可以看出，混沌粒子群優(yōu)化算法對函數(shù)的求解結果優(yōu)于粒子群優(yōu)化算法的求解結果(50次獨立運行的平均)。對其它函數(shù)所做的大量的計算機仿真結果亦說明了這一點，限于篇幅，這里就不再給出結果。表1PSO和CPSo算法數(shù)值仿真結果全局最小值點平均值全局最小值平均值IPSO(0.01234485,0.00233262)0.01575119ICPSO(1.464e一007,0.623e一007)4.3978e一011l進化次數(shù)圖1PSO和CPSO算法進化曲線比較文［3］對⑵式作了如下的改動：q。一州+。1rl(所一的)+c2r2(兒一麓)(4)其中叫是非負數(shù)，稱為慣性因子(inertiaweight)0由此得到的算法稱為帶慣性因子的粒子群優(yōu)化算法。借鑒遺傳算法的思想，文［6］最早提出了雜交粒子群優(yōu)化算法。粒子群中的粒子被賦予一個雜交概率，這個雜交概率由用戶確定，與粒子的適應值無關。在每次迭代中，依據(jù)雜交概率選取指數(shù)量的粒子放入一個池中.池中的粒子隨機地兩兩一箔暑IIInH)0_囂crl萬方數(shù)據(jù)雜交，產(chǎn)同樣數(shù)目的孩子粒子，并用孩子粒子代替父母粒子，以保持群的粒子數(shù)目不變。孩子粒子的位置由父母粒子的位置的加權和計算，即：childl(x)一pXparentl(x)+(1—p)Xparentz(x)(5)childz(x)一PXparent2(x)+(1--p)Xparenta(x)(6)其中x是D維的位置向量，而child,(x)和parent?(x)，人一1，2分別指明是孩子粒子還是父母粒子的位置；P是D維均勻分布的隨機數(shù)向量，p的每個分量都在［。，1］取值，‘X’表示向量分量對應相乘。孩子粒子的速度分別由下面的公式得到：cE留，c曲^篡筆差襄害｛毒淼l戶d心nr?c曲lcz，曲iz以c曲一t差筆篆要害｛善端I戶口心n屯c曲Ics，其中口是D維的速度向量，而child?(8)和parent,(曲，k=1，2分別指明是孩子粒子還是父母粒子的速度。雜交粒子群優(yōu)化算法引入了較多的待調整參數(shù)，對使用者的經(jīng)驗有一定要求。表2CPSO、IWPSO、CRPSO和MPSO算法數(shù)值仿真結果全局最小值點平均值全局最小值平均值CPSo(O?723e一006，0?418e一006)5.018e一010IWPSO(0.239e一005.0.393e一006)8.175e一009CRPSO(0.00130518。0.00086676)0.00346642MPS0(0.00022500.0.00036320)0.00622002文［8］進一步把變異運算引入粒子群優(yōu)化算法中，提出了帶高斯變異的粒子群優(yōu)化算法，變異運算依據(jù)變異概率選取指定數(shù)量的粒子按高斯變異算子進行變異，用變異后的粒子代替原粒子，即：mutation(x)一x*(1+Gaussian(盯))⑼圖2CPSO、IWPSO、CRPSO和MPSO算法進化曲線比較圖2是CPSO、IWPSO、CRPSO和MPSO算法收斂曲線比較，從上往下的四條曲線依次對應的是MPSO算法、CRP—SO算法、IWPSO算法和CPSO算法。表2是這四種算法數(shù)值仿真結果。從圖2和表2可知混沌粒子群優(yōu)化算法優(yōu)于雜交粒子群優(yōu)化算法和帶高斯變異的粒子群優(yōu)化算法，而略好于帶慣性因子的粒子群優(yōu)化算法。結論本文把混沌優(yōu)化思想引入到粒子群優(yōu)化算法中，給出了混沌粒子群優(yōu)化算法。其基本思想是在粒子群的每次進化過程中，首先對粒子群體中的最優(yōu)粒子進行混沌尋優(yōu)，然后隨機地從粒子群體中選擇一個粒子用混沌尋優(yōu)的結果來替換。通過這種處理使得粒子群優(yōu)化算法擺脫局部極值點的能力得到改善，提高了算法的收斂速度和精度。計算機仿真結果表明混沌粒子群優(yōu)化算法的收斂性能明顯優(yōu)于粒子群優(yōu)化算法，亦優(yōu)于雜交粒子群優(yōu)化算法和帶高斯變異的粒子群優(yōu)化算法，而略好于帶慣性因子的粒子群優(yōu)化算法。參考文獻KennedyJ，eta1.Particleswarmoptimization.In：IEEEInt’1Conf.onNeuraINetworks.Perth.Australia.1995.1942?1948EberhartR，KennedyJ.Anewoptimizerusingparticleswarmtheory.In：Proc.ofthesixthintl.symposiumonMicroMachineandHumanScfence，Nagoya，Japan.1995.39?43ShiY，eta1.Amodifiedparticleswarmoptimizer[C].In：IEEEWorldCongressonComputationalIntelligence,1998.69?73ShiY.EberhartRC.FuzzyAdaptiveparticleswarmoptimization[C].In：Proc.oftheCongressonEvolutionaryComputation.SeoulKorea.2001ClercM.TheswarmandtheQueen：Towardsadeterministicandadaptiveparticleswarmoptimization[c].In：Proc.oftheCongressofEvolutionaryComputation,1999.1951?19576AngelinePJ.Evolutionaryoptimizationversusparticleswarmoptimization：Philosophyandperformancedifferences[c].In：EvolutionaryprogrammingVII.1998.601?6107LovbjergM.RasmussenTK.KrinkT.Hybridparticleswarmoptimizationwithbreedingandsubpopulations[C].In：Proc,ofthethirdGreneticandEvolutionarycomputationconf.SanFrancisco.USA,20018HigasshiN.IbaH.ParticleswarmoptimizationwithGraussianmutation[c].In：Proc.oftheCongressonEvolutionaryComputation.2003.72?79VandenBerghF-EngelbrechtAP.Trainingproductunitnetworksusingcooperativeparticleswarmoptimizers[C].In：Proc.ofthethirdGeneticandEvolutionarycomputationcon[.SanFrancisco。USA.2001VandenBerghF,EngelbrechtAP.Effectsofswarmsizecooper—ativeparticleswarmoptimizers[C].In：Proc.ofthethirdGe-neticandEvolutionarycomputationcon[.SanFrancisco,USA。200111KennedyJ.EberhartR.DiscretebinaryversionoftheparticleswarmalgorithmiC].IEEEInt’1Conf.oncomputationalCyberneticsandSimulation。1997.4104?410812ClercM.Discreteparticleswarmoptimizationillustratedbythetravelingsalesmanproblem.http：//www.mauriceclerc.net,200013CiuprinaG,IoanD,MunteanuI.Useofintelligent-particleswarmoptimizationinelectromagnetics.IEEETrans.onMag一netics,2002,38(2)：1037?104014ClercM.KennedyJ.Theparticleswarm一explosion.stability,andconvergenceinamuhidimensionalcomplexspace.IEEETrans.onEvolutionaryComputation,2002,6(1)：58?7315王東升.曹磊.混沌、分形及其應用[M].合肥：中國科學技術大學出版社，199516李兵，蔣慰孫.混沌優(yōu)化方法及其應用[J].控制理論與應用，1997(4)：613?615(上接第12頁)16e—governmentmetadataFramework.http：//www..uk/documents/ukmetadataframeworkv01202001—05.pdfI7GCL(GovernmentCategoryList)http：//www..uk/schemasstandards/gcl.asp18MullenA.GILSmetadatainitiativesatthestate1ev—e1.Govern-mentInformationQuarterly,2001,18：167?18019Jordan：readinessfore—government.http：//www.surf—/papers/e一gOv一english.pdfLinthcumDS. Mercator：NextgenerationApplicationintegrationFtomInfromation。orProcess.toSetviceMcreatorsoftware。Inc。2002KoellerA.IntegrationofHeterogeneousDatabaseDiscoverryofMeta—InformationandMaintenanceofSchema-restructuringviews：['PHDthesis].WorcesterpolytechnicInstitute，2001IBMCorporation.Optimizationofinformationtoimprovedecisionmakingingovernment：一theinformationvaluechainway.http：//www.ibm.com/services/files/ibv—infovaluech—ain.pdfE—GovernmentStrategy.http：//www.cio.gov/documents/ego一vreport.pdfReeseWD.AnInvestigationofTechniquesforIntegratingWeb-accessibleData：[PHI）thesis].UniversityofColorado,2001?15-萬方數(shù)據(jù)混沌粒子群優(yōu)化算法作者：高鷹，謝勝利作者單位：高鷹（華南理工大學電子與信息學院，廣州,510641;廣州大學信息機電學院計算機科學與技術系，廣州,510405）,謝勝利（華南理工大學電子與信息學院，廣州,510641）刊名：計算機科學英文刊名：COMPUTERSCIENCE年，卷（期）：2004,31（8）被引用次數(shù)：44次參考文獻（16條）李兵;蔣慰孫混沌優(yōu)化方法及其應用1997（04）王東升;曹磊混沌、分形及其應用1995ClercM;KennedyJTheparticleswarm-explosion,stability,andconvergenceinamultidimensionalcomplexspace2002（01）VandenBerghF;EngelbrechtAPTrainingproductunitnetworksusingcooperativeparticleswarmoptimizers2001HigasshiN;IbaHParticleswarmoptimizationwithGaussianmutation2003LovbjergM;RasmussenTK;KrinkTHybridparticleswarmoptimizationwithbreedingandsubpopulations［外文會議］2001AngelinePJEvolutionaryoptimizationversusparticleswarmoptimization:Philosophyandperformancedifferences1998ClercMTheswarmandtheQueen:Towardsadeterministicandadaptiveparticleswarmoptimization［外文會議］19999.ShiY;EberhartRCFuzzyAdaptiveparticleswarmoptimization外文會議］200110.ShiYAmodifiedparticleswarmoptimizer［外卜文會議］1998EberhartR;KennedyJAnewoptimizerusingparticleswarmtheory.In1995CiuprinaG;IoanD;MunteanuIUseofintelligent-particleswarmoptimizationinelectromagnetics［外文期刊］2002(02)ClercMDiscreteparticleswarmoptimizationillustratedbythetravelingsalesmanproblem2000KennedyJ;EberhartRDiscretebinaryversionoftheparticleswarmalgorithm1997VandenBerghF;EngelbrechtAPEffectsofswarmsizecooperativeparticleswarmoptimizers2001KennedyJParticleswarmoptimization.In1995引證文獻(44條)錢偉懿.寧必鋒基于混沌的聚類粒子群優(yōu)化算法［期刊論文］-計算機工程與設計2011(2)田雨波.潘朋朋粒子群算法優(yōu)化神經(jīng)網(wǎng)絡結構的研究［期刊論文］-現(xiàn)代電子技術2011(4)李婭.張德豐.王東全局混沌雜交的粒子群優(yōu)化算法及應用［期刊論文］-湖南師范大學自然科學學報2010(4)吳瑞海.賀軍銜.段琪慶.董吉文模擬退火粒子群與小波的地基沉降預測應用［期刊論文］-測繪科學2010(6)寧必鋒.褚國娟.馬春麗.錢偉懿一種改進的混合粒子群優(yōu)化算法［期刊論文］-渤海大學學報(自然科學版)2010(1)馬天才.陳淑靜基于修補粒子群算法的紅外目標跟蹤［期刊論文］-應用光學2010(5)劉麗軍.李捷.蔡金錠基于強引導粒子群與混沌優(yōu)化的電力系統(tǒng)無功優(yōu)化［期刊論文］-電力自動化設備2010(4)盛煜翔.潘海天.夏陸岳.蔡亦軍.孫小方混合混沌粒子群算法在苯與甲苯閃蒸過程優(yōu)化中的應用［期刊論文］-浙江工業(yè)大學學報2010(3)鄧顯羽.彭勇.葉碎高.溫進化.何斌粒子群算法在水庫(群)優(yōu)化調度研究中的應用綜述［期刊論文］-水利水電科技進展2010(5)連志剛.焦斌一種混合搜索的粒子群算法［期刊論文］-控制理論與應用2010(10)沈小衛(wèi).何明——種基于混合優(yōu)化算法的醫(yī)學圖像配準方法［期刊論文］-計算機應用研究2010(8)孟祥印.黃勝.李焱混沌PSO分析及其在船舶設計中的應用［期刊論文］-計算機工程與應用2010(17)唐新來.李春貴.王萌.張增芳基于混沌粒子群算法的神經(jīng)網(wǎng)絡短時交通流預測［期刊論文］-計算機測量與控制2010(8)呂丹.童創(chuàng)明手征媒質反射特性仿真計算［期刊論文