【正文】 基本粒子群算法 （particle swarm optimization）%名稱： 基本粒子群算法%初始格式化clear all。 %學(xué)習(xí)因子1c21=2。 %隨機(jī)初始化位置 v(i,j)=randn。) tInfo=strcat(39。維39。初始速度39。維)。for i=1:N if(pbest1(i)gbest1) g1=p1(i,:)。 x1(j,:)=x1(j,:)+v1(j,:)。)。for i=1:N pbest2(i)=fitness(x2(i,:),D)。 end if(pbest2(j)gbest2) g2=p2(j,:)。title(TempStr)。for i=1:D sum=sum+x(i)^2。 %初始化群體維數(shù)T=100。v=zeros(N,D)。) ylabel(39。第39。粒子39。)。)。)。grid on xlabel(39。 %慣性權(quán)重eps=10^(6)。 %179。)。c1= %g ,c2=%g39。%浸入主循環(huán)，按照公式依次迭代直到滿足精度或者迭代次數(shù)for i=1:T for j=1:N if (fitness(x2(j,:),D)pbest2(j)) p2(j,:)=x2(j,:)。%初始化種群個(gè)體最有位置和 最優(yōu)解p2=x2。xlabel(39。 gbest1=pbest1(j)。end%初始化全局最優(yōu)位置和最優(yōu)值g1=1000*ones(1,D)。第39。粒子39。第39。) ylabel(39。v=zeros(N,D)。 %初始化群體維數(shù)T=100。for i=1:D sum=sum+x(i)^2。title(TempStr)。 end if(pbest2(j)gbest2) g2=p2(j,:)。for i=1:N pbest2(i)=fitness(x2(i,:),D)。)。 x1(j,:)=x1(j,:)+v1(j,:)。for i=1:N if(pbest1(i)gbest1) g1=p1(i,:)。維)。初始速度39。維39。) tInfo=strcat(39。 %隨機(jī)初始化位置 v(i,j)=randn。 %學(xué)習(xí)因子1c21=2。a)%主函數(shù)源程序（）%基本粒子群算法 （particle swarm optimization）%名稱： 基本粒子群算法%初始格式化clear all。此外，由于PSO本質(zhì)上是一種隨機(jī)搜索算法，現(xiàn)場(chǎng)工程技術(shù)人員對(duì)它的可靠性仍難免心存疑慮，將PSO(或與工業(yè)系統(tǒng)在役技術(shù)結(jié)合)進(jìn)行實(shí)用化推廣，仍是一項(xiàng)任重而道遠(yuǎn)的任務(wù)。由于PSO畢竟是一種新興的智能優(yōu)化算法，在以下方面仍然值得進(jìn)一步研究：(1) 理論研究：雖然目前對(duì) PSO 穩(wěn)定性和收斂性的證明已取得了一些初步成果[17]，但自誕生以來其數(shù)學(xué)基礎(chǔ)一直不完備，特別是收斂性一直沒有得到徹底解決。不全相等。平方和分解公式說明觀察值關(guān)于其總平均值之的差異是由組內(nèi)平方和組間平方和組成的。首先，假定因子有個(gè)水平，在每種水平下，做次試驗(yàn)，在每次試驗(yàn)后可得一試驗(yàn)值，記做它表示在第個(gè)水平下的第個(gè)試驗(yàn)值。慣性權(quán)值: 控制著速度前一變化量對(duì)當(dāng)前變化量的影響，如果較大，則影響較大，能夠搜索以前所未能達(dá)到的區(qū)域，整個(gè)算法的全局搜索能力加強(qiáng)，有利于跳出局部極小點(diǎn)；而值較小，則前一動(dòng)量項(xiàng)的影響較小，主要是在當(dāng)前解的附近搜索，局部搜索能力較強(qiáng)，有利于算法收斂。關(guān)鍵參數(shù)設(shè)置如下:粒子種群大小N:較小的群能充分探索解空間，避免了過多的適應(yīng)值評(píng)估和計(jì)算時(shí)間。程序（1）運(yùn)行結(jié)果為： 粒子群位置初始化 粒子群速度初始化 迭代結(jié)果對(duì)比最優(yōu)點(diǎn)坐標(biāo)（1）：[ ]最優(yōu)點(diǎn)坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（2）當(dāng)于對(duì)比（加速因子與正常情況對(duì)比）且運(yùn)行程序（2）得如下結(jié)果： 初始化速度 初始化速度 迭代結(jié)果對(duì)比最優(yōu)點(diǎn)坐標(biāo)（1）：[ ]最優(yōu)點(diǎn)坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（3）當(dāng)于對(duì)比（加速因子與正常情況對(duì)比）的結(jié)果為： 初始化位置 初速度位置 迭代結(jié)果對(duì)比最優(yōu)點(diǎn)坐標(biāo)（1）：[ ]最優(yōu)點(diǎn)坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（4）當(dāng)，分別對(duì)其取值。帶慣性常數(shù)PSO的速度更新公式如下： （）其中為慣性常數(shù)。的選擇通常憑經(jīng)驗(yàn)給定，并一般設(shè)定為問題空間的 [3]。 4）量子粒子群優(yōu)化：文獻(xiàn)[9]采用量子個(gè)體提出離散PSO；文獻(xiàn)[9]則基于量子行為更新粒子位置。此外，還有其它一些混合PSO： 1）高斯PSO：由于傳統(tǒng)PSO往往是在全局和局部最佳位置的中間進(jìn)行搜索，搜索能力和收斂性能嚴(yán)重依賴加速常數(shù)和慣性權(quán)值的設(shè)置，為了克服該不足，Secrest等人[10]將高斯函數(shù)引入PSO算法中，用于引導(dǎo)粒子的運(yùn)動(dòng)；GPSO不再需要慣性權(quán)值，而加速常數(shù)由服從高斯分布的隨機(jī)數(shù)產(chǎn)生。 此外，其它一些搜索技術(shù)與PSO結(jié)合以提高算法的局部搜索能力，如文獻(xiàn)[9]提出一種基于PSO和LevenbergMarquardt的混合方法。同時(shí)，為了確保粒子盡可能向好的對(duì)象學(xué)習(xí)而不把時(shí)間浪費(fèi)在較差的對(duì)象上，上述學(xué)習(xí)對(duì)象選擇過程設(shè)定一個(gè)更新間隔代數(shù)(refreshing gap)，在此期間的學(xué)習(xí)對(duì)象保持上次選擇的學(xué)習(xí)對(duì)象不變。 上述粒子間學(xué)習(xí)是在整個(gè)維空間中構(gòu)造鄰域進(jìn)行的，這樣當(dāng)搜索空間維數(shù)較高時(shí)往往容易遭受“維數(shù)災(zāi)(curse of dimensionality)”的困擾[14]。Kennedy[20]提出了社會(huì)趨同(Stereotyping)模型，使用簇分析將整個(gè)粒子群劃分為多個(gè)簇，然后用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置。空間鄰域直接在搜索空間按粒子間的距離(如歐式距離)進(jìn)行劃分，如Suganthan[23]引入一個(gè)時(shí)變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個(gè)粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴(kuò)展到整個(gè)種群。本文將這些改進(jìn)分為4類：粒子群初始化、鄰域拓?fù)?、參?shù)選擇和混合策略。當(dāng)時(shí)，式()與式()完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展。在粒子群優(yōu)化算法中，信息流動(dòng)是單向的，即只有將信息給其他的粒子，這使得整個(gè)搜索更新過程跟隨當(dāng)前解。輸出結(jié)果根據(jù)方程()對(duì)粒子的位置進(jìn)行進(jìn)化根據(jù)方程()對(duì)粒子的速度進(jìn)行進(jìn)化求出整個(gè)群體的全局最優(yōu)值求出每個(gè)粒子的個(gè)體最優(yōu)計(jì)算每個(gè)粒子的適應(yīng)值初始化每個(gè)粒子的速度和位置是否滿足結(jié)束條件是否開 始. PSO算法流程圖 特點(diǎn)式()中第1部分可理解為粒子先前的速度或慣性；第2部份可理解為粒子的“認(rèn)知”行為，表示粒子本身的思考能力；第3部分可理解為粒子的“社會(huì)”行為，表示粒子之間的信息共享與相互合作。假設(shè)在一個(gè)維的目標(biāo)搜索空間中，有個(gè)粒子組成一個(gè)群落，其中第個(gè)粒子表示為一個(gè)維的向量。思維背后的社會(huì)現(xiàn)象遠(yuǎn)比魚群和鳥群聚集過程中的優(yōu)美動(dòng)作復(fù)雜的多：首先，思維發(fā)生在信念空間，其維數(shù)遠(yuǎn)遠(yuǎn)高于3；其次，當(dāng)兩種思想在認(rèn)知空間會(huì)聚于同一點(diǎn)時(shí)，我們稱其一致，而不是發(fā)生沖突。1990年，生物學(xué)家Frank Heppner也提出了鳥類模型[8]，它的不同之處在于：鳥類被吸引飛到棲息地。并且通過公式計(jì)算準(zhǔn)確判斷參數(shù)對(duì)算法影響。 電子資源 身處信息和網(wǎng)絡(luò)時(shí)代的我們是幸運(yùn)的，豐富的電子資源能讓我們受益匪淺。本文通過對(duì)PSO算法的步驟的歸納、特點(diǎn)的分析，利用統(tǒng)計(jì)中的方差分析，通過抽樣實(shí)驗(yàn)方法，論證了該算法中關(guān)鍵參數(shù)因子:慣性權(quán)值、加速因子對(duì)算法整體性能的影響效果，并提出了參數(shù)設(shè)置的指導(dǎo)原則，給出了關(guān)鍵參數(shù)設(shè)置，為PSO算法的推廣與改進(jìn)提供了思路。這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測(cè)的群體行為。2010屆信息與計(jì)算科學(xué)專業(yè)畢業(yè)設(shè)計(jì)粒子群優(yōu)化算法及其參數(shù)設(shè)置畢業(yè)設(shè)計(jì)目 錄摘 要 IIAbstract III 1 研究背景和課題意義 1 參數(shù)的影響 1 應(yīng)用領(lǐng)域 2 電子資源 2 主要工作 2 3 粒子群算法思想的起源 3 算法原理 4 基本粒子群算法流程 5 特點(diǎn) 6 帶慣性權(quán)重的粒子群算法 7 粒子群算法的研究現(xiàn)狀 8 9 粒子群初始化 9 鄰域拓?fù)?9 混合策略 12 14 對(duì)參數(shù)的仿真研究 14 測(cè)試仿真函數(shù) 15 應(yīng)用單因子方差分析參數(shù)對(duì)結(jié)果影響 33 對(duì)參數(shù)的理論分析 345結(jié)論與展望 39致謝 43附錄 4479 研究背景和課題意義“人工生命”是來研究具有某些生命基本特征的人工系統(tǒng)。也可稱做“群智能”(swarm intelligence)。鑒于PSO的發(fā)展歷史尚短，它在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些缺陷，有待解決。實(shí)際工業(yè)應(yīng)用有：電力系統(tǒng)、濾波器設(shè)計(jì)、自動(dòng)控制、數(shù)據(jù)聚類、模式識(shí)別與圖像處理、化工、機(jī)械、通信、機(jī)器人、經(jīng)濟(jì)、生物信息、醫(yī)學(xué)、任務(wù)分配、TSP等等。分別對(duì)其利用單因子方差分析法，說明不同參數(shù)水平對(duì)算法速率性能的影響。仿真中僅利用上面三條簡(jiǎn)單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。人類的自然行為和魚群及鳥群并不類似，而人類在高維認(rèn)知空間中的思維軌跡卻與之非常類似。另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。 基本粒子群算法流程算法的流程如下：① 初始化粒子群，包括群體規(guī)模，每個(gè)粒子的位置和速度② 計(jì)算每個(gè)粒子的適應(yīng)度值；③ 對(duì)每個(gè)粒子，用它的適應(yīng)度值和個(gè)體極值比較，如果 ，則用替換掉；④ 對(duì)每個(gè)粒子，用它的適應(yīng)度值和全局極值比較，如果則用替；⑤ 根據(jù)公式（），（）更新粒子的速度和位置 ；⑥ 如果滿足結(jié)束條件(誤差足夠好或到達(dá)最大循環(huán)次數(shù))退出，否則返回②。與遺傳算法相比，粒子群優(yōu)化算法的信息共享機(jī)制是很不同的:在遺傳算法中，染色體互相共享信息，所以整個(gè)種群的移動(dòng)是比較均勻的向最優(yōu)區(qū)域移動(dòng)。較大，全局收斂能力強(qiáng)，局部收斂能力弱；較小，局部收斂能力強(qiáng)，全局收斂能力弱。為了克服上述不足，各國(guó)研究人員相繼提出了各種改進(jìn)措施。根據(jù)現(xiàn)有的研究成果，本文將鄰域分為空間鄰域(spatial neighborhood)、性能空間(performance space)鄰域和社會(huì)關(guān)系鄰域(sociometric neighborhood)。文獻(xiàn)[19]引入了子種群，子種群間通過繁殖(Breeding)實(shí)現(xiàn)信息交流。 在標(biāo)準(zhǔn)的PSO算法中，所有粒子僅僅向自身和鄰域的歷史最佳位置聚集，而沒有向鄰域內(nèi)其他個(gè)體(即使這些個(gè)體很優(yōu)秀)學(xué)習(xí)，造成信息資源的浪費(fèi)，甚至因此而陷入局部極值；考慮到此因素，Kennedy 等人[17]提出了全信息粒子群(fully informed particle swarm, FIPS)，在FIPS中，每個(gè)粒子除了自身和鄰域最佳歷史位置外，還學(xué)習(xí)鄰域內(nèi)其他粒子的成功經(jīng)驗(yàn)。CLPSO的速度更新公式為： （）其中為加速因子，為[0,1]內(nèi)的均勻隨機(jī)數(shù)，表示粒子在第維的學(xué)習(xí)對(duì)象，它通過下面的策略決定：產(chǎn)生[0,1]內(nèi)的均勻隨機(jī)數(shù)，如果該隨機(jī)數(shù)大于為粒子預(yù)先給定的學(xué)習(xí)概率，則學(xué)習(xí)對(duì)象為自身歷史最佳位置；否則，從種群內(nèi)隨機(jī)選取兩個(gè)個(gè)體，按錦標(biāo)賽選擇(tournament selection)策略選出兩者中最好的歷史最佳位置作為學(xué)習(xí)對(duì)象。文獻(xiàn)[16]將螞蟻算法與PSO結(jié)合用于求解離散優(yōu)化問題；Robinson 等人[17]和Juang[18]將GA與PSO結(jié)合分別用于天線優(yōu)化設(shè)計(jì)和遞歸神經(jīng)網(wǎng)絡(luò)設(shè)計(jì)；文獻(xiàn)[19]將種群動(dòng)態(tài)劃分成多個(gè)子種群，再對(duì)不同的子種群利用PSO或GA或爬山法進(jìn)行獨(dú)立進(jìn)化；Naka等人[10]將GA中的選擇操作引入到PSO中，按一定選擇率復(fù)制較優(yōu)個(gè)體；Angeline [11]則將錦標(biāo)賽選擇引入PSO 算法，根據(jù)個(gè)體當(dāng)前位置的適應(yīng)度，將每一個(gè)個(gè)體與其它若干個(gè)個(gè)體相比較，然后依據(jù)比較結(jié)果對(duì)整個(gè)群體進(jìn)行排序，用粒子群中最好一半的當(dāng)前位置和速度替換最差一半的位置和速度，同時(shí)保留每個(gè)個(gè)體所記憶的個(gè)體最好位置；ElDib 等人[12]對(duì)粒子位置和速度進(jìn)行交叉操作；Higashi [13]將高斯變異引入到PSO中；Miranda等人[14]則使用了變異、選擇和繁殖多種操作同時(shí)自適應(yīng)確定速度更新公式中的鄰域最佳位置以及慣性權(quán)值和加速常數(shù)；Zhang等人[8]利用差分進(jìn)化(DE)操作選擇速度更新公式中的粒子最佳位置；而Kannan 等人[18]則利用DE來優(yōu)化PSO的慣性權(quán)值和加速常數(shù)。文獻(xiàn)[9]將引力場(chǎng)模