【正文】 下的公式()和( )來更新自己的速度和位置[12]： () (2. 2)其中：和為學(xué)習(xí)因子，也稱加速常數(shù)(acceleration constant)，和為[0，1]范圍內(nèi)的均勻隨機(jī)數(shù)。另外也可以不用整個(gè)種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。所有的粒子都有一個(gè)由被優(yōu)化的函數(shù)決定的適值( fitness value) ，每個(gè)粒子還有一個(gè)速度決定它們飛翔的方向和距離。人類的自然行為和魚群及鳥群并不類似，而人類在高維認(rèn)知空間中的思維軌跡卻與之非常類似。他們的模型和仿真算法主要對(duì)Frank Heppner的模型進(jìn)行了修正，以使粒子飛向解空間并在最好解處降落。仿真中僅利用上面三條簡(jiǎn)單的規(guī)則，就可以非常接近的模擬出鳥群飛行的現(xiàn)象。它與其他進(jìn)化算法一樣，也是基于“種群”和“進(jìn)化”的概念，通過個(gè)體間的協(xié)作與競(jìng)爭(zhēng)，實(shí)現(xiàn)復(fù)雜空間最優(yōu)解的搜索；同時(shí)，PSO又不像其他進(jìn)化算法那樣對(duì)個(gè)體進(jìn)行交叉、變異、選擇等進(jìn)化算子操作，而是將群體(swarm)中的個(gè)體看作是在D維搜索空間中沒有質(zhì)量和體積的粒子(particle)，每個(gè)粒子以一定的速度在解空間運(yùn)動(dòng)，并向自身歷史最佳位置pbest和鄰域歷史最佳位置聚集，實(shí)現(xiàn)對(duì)候選解的進(jìn)化。分別對(duì)其利用單因子方差分析法，說明不同參數(shù)水平對(duì)算法速率性能的影響。這里介紹當(dāng)今PSO研究領(lǐng)域較有影響的一個(gè)網(wǎng)址： Maurice Clerc 博士()的PSO主頁(yè)：該主頁(yè)主要介紹Maurice Clerc博士帶領(lǐng)的PSO研究小組的研究成果。實(shí)際工業(yè)應(yīng)用有：電力系統(tǒng)、濾波器設(shè)計(jì)、自動(dòng)控制、數(shù)據(jù)聚類、模式識(shí)別與圖像處理、化工、機(jī)械、通信、機(jī)器人、經(jīng)濟(jì)、生物信息、醫(yī)學(xué)、任務(wù)分配、TSP等等。還有保持，不變對(duì)分別取不同值分析其對(duì)算法結(jié)果影響。鑒于PSO的發(fā)展歷史尚短，它在理論基礎(chǔ)與應(yīng)用推廣上都還存在一些缺陷，有待解決。但后來發(fā)現(xiàn)PSO是一種很好的優(yōu)化工具。也可稱做“群智能”(swarm intelligence)?，F(xiàn)在已經(jīng)有很多源于生物現(xiàn)象的計(jì)算技巧。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)。 例如，人工神經(jīng)網(wǎng)絡(luò)是簡(jiǎn)化的大腦模型。這些模擬系統(tǒng)利用局部信息從而可能產(chǎn)生不可預(yù)測(cè)的群體行為。優(yōu)化是科學(xué)研究、工程技術(shù)和經(jīng)濟(jì)管理等領(lǐng)域的重要研究課題。本文通過對(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)提供了思路。 應(yīng)用領(lǐng)域近年來，PSO快速發(fā)展，在眾多領(lǐng)域得到了廣泛應(yīng)用。 電子資源 身處信息和網(wǎng)絡(luò)時(shí)代的我們是幸運(yùn)的，豐富的電子資源能讓我們受益匪淺。除了從中可以得到他們近幾年公開發(fā)表的相關(guān)文獻(xiàn)和源代碼，還可以下載一些未公開發(fā)表的文章。并且通過公式計(jì)算準(zhǔn)確判斷參數(shù)對(duì)算法影響。PSO算法具有很好的生物社會(huì)背景[2]而易理解、參數(shù)少而易實(shí)現(xiàn)，對(duì)非線性、多峰問題均具有較強(qiáng)的全局搜索能力，在科學(xué)研究與工程實(shí)踐中得到了廣泛關(guān)注[310]。1990年，生物學(xué)家Frank Heppner也提出了鳥類模型[8]，它的不同之處在于：鳥類被吸引飛到棲息地。Kennedy在他的書中描述了粒子群算法思想的起源。思維背后的社會(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ā)生沖突。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索[1]。假設(shè)在一個(gè)維的目標(biāo)搜索空間中，有個(gè)粒子組成一個(gè)群落，其中第個(gè)粒子表示為一個(gè)維的向量。式()右邊由三部分組成，第一部分為“慣性(inertia)”或“動(dòng)量(momentum)”部分，反映了粒子的運(yùn)動(dòng)“習(xí)慣(habit)”，代表粒子有維持自己先前速度的趨勢(shì)；第二部分為“認(rèn)知(cognition)”部分，反映了粒子對(duì)自身歷史經(jīng)驗(yàn)的記憶(memory)或回憶(remembrance)，代表粒子有向自身歷史最佳位置逼近的趨勢(shì)；第三部分為“社會(huì)(social)”部分，反映了粒子間協(xié)同合作與知識(shí)共享的群體歷史經(jīng)驗(yàn)，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢(shì)，根據(jù)經(jīng)驗(yàn)，通常。輸出結(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ì)”行為，表示粒子之間的信息共享與相互合作。PSO 的一個(gè)優(yōu)勢(shì)就是采用實(shí)數(shù)編碼，不需要像遺傳算法一樣采用二進(jìn)制編碼(或者采用針對(duì)實(shí)數(shù)的遺傳操作) 。在粒子群優(yōu)化算法中，信息流動(dòng)是單向的，即只有將信息給其他的粒子，這使得整個(gè)搜索更新過程跟隨當(dāng)前解。1998年，Yuhui Shi[9]提出了帶有慣性權(quán)重的改進(jìn)粒子群算法。當(dāng)時(shí)，式()與式()完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展。PSO由于有簡(jiǎn)單、易于實(shí)現(xiàn)、設(shè)置參數(shù)少、無需梯度信息等特點(diǎn)，其在連續(xù)非線性優(yōu)化問題和組合優(yōu)化問題中都表現(xiàn)出良好的效果。本文將這些改進(jìn)分為4類：粒子群初始化、鄰域拓?fù)洹?shù)選擇和混合策略。對(duì)于模型，每個(gè)粒子與整個(gè)群體的其他粒子進(jìn)行信息交換，并有向所有粒子中的歷史最佳位置移動(dòng)的趨勢(shì)。空間鄰域直接在搜索空間按粒子間的距離(如歐式距離)進(jìn)行劃分，如Suganthan[23]引入一個(gè)時(shí)變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個(gè)粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴(kuò)展到整個(gè)種群。M. Clerc[25]對(duì)隨機(jī)拓?fù)溥M(jìn)行了進(jìn)一步分析，并在2006年版和2007年版的標(biāo)準(zhǔn)PSO[23]中采用了隨機(jī)拓?fù)洹ennedy[20]提出了社會(huì)趨同(Stereotyping)模型，使用簇分析將整個(gè)粒子群劃分為多個(gè)簇，然后用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置。文獻(xiàn)[14]將小生境(niche)技術(shù)引入到PSO中，提出了小生境PSO(Niching Particle Swarm Optimizer)。 上述粒子間學(xué)習(xí)是在整個(gè)維空間中構(gòu)造鄰域進(jìn)行的，這樣當(dāng)搜索空間維數(shù)較高時(shí)往往容易遭受“維數(shù)災(zāi)(curse of dimensionality)”的困擾[14]。 無論是粒子群在D維的搜索還是多個(gè)粒子群在不同維上的協(xié)作搜索，其目的都是為了每個(gè)粒子能夠找到有利于快速收斂到全局最優(yōu)解的學(xué)習(xí)對(duì)象。同時(shí)，為了確保粒子盡可能向好的對(duì)象學(xué)習(xí)而不把時(shí)間浪費(fèi)在較差的對(duì)象上，上述學(xué)習(xí)對(duì)象選擇過程設(shè)定一個(gè)更新間隔代數(shù)(refreshing gap)，在此期間的學(xué)習(xí)對(duì)象保持上次選擇的學(xué)習(xí)對(duì)象不變。vbjerg 等人為每個(gè)粒子引入與相鄰粒子距離成反比的自組織危險(xiǎn)度(selforganized criticality)指標(biāo)，距離越近則危險(xiǎn)度越高，當(dāng)達(dá)到一定閾值后，對(duì)該粒子進(jìn)行重新初始化或推開一定距離降低危險(xiǎn)度，達(dá)到提高群體多樣性的目的；文獻(xiàn)[15]提出一種帶空間粒子擴(kuò)展的PSO，為每個(gè)粒子賦一半徑，以檢測(cè)兩個(gè)粒子是否會(huì)碰撞，并采取隨機(jī)彈離、實(shí)際物理彈離、簡(jiǎn)單的速度—直線彈離等措施將其分開。 此外，其它一些搜索技術(shù)與PSO結(jié)合以提高算法的局部搜索能力，如文獻(xiàn)[9]提出一種基于PSO和LevenbergMarquardt的混合方法。該算法通過附加噪聲持續(xù)為粒子群引入負(fù)熵(negative entropy)，使得系統(tǒng)處于遠(yuǎn)離平衡態(tài)的狀態(tài)，又由于群體中存在內(nèi)在的非線性相互作用，從而形成自組織耗散結(jié)構(gòu)，使粒子群能夠“持續(xù)進(jìn)化”，抑制早熟停滯。此外，還有其它一些混合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)生。除此之外，文獻(xiàn)[4]利用慣性權(quán)值自適應(yīng)于目標(biāo)函數(shù)值的自適應(yīng)PSO進(jìn)行全局搜索、利用混沌局部搜索對(duì)最佳位置進(jìn)行局部搜索，提出一種PSO與混沌搜索相結(jié)合的混沌PSO；文獻(xiàn)[15]則利用混沌序列確定PSO的參數(shù)(慣性權(quán)值和加速常數(shù))。 4）量子粒子群優(yōu)化：文獻(xiàn)[9]采用量子個(gè)體提出離散PSO；文獻(xiàn)[9]則基于量子行為更新粒子位置。 a) 最大速度的選擇：如式()所示的粒子速度是一個(gè)隨機(jī)變量，由粒子位置更新公式()產(chǎn)生的運(yùn)動(dòng)軌跡是不可控的，使得粒子在問題空間循環(huán)跳動(dòng)[3, 6]。的選擇通常憑經(jīng)驗(yàn)給定，并一般設(shè)定為問題空間的 [3]。Ratnaweera 等人[13]則提出自適應(yīng)時(shí)變調(diào)整策略。帶慣性常數(shù)PSO的速度更新公式如下： （）其中為慣性常數(shù)。 11122{()( 雖然慣性權(quán)值PSO和收縮因子PSO對(duì)典型測(cè)試函數(shù)表現(xiàn)出各自的優(yōu)勢(shì)[16]，但由于慣性常數(shù)方法通常采用慣性權(quán)值隨更新代數(shù)增加而遞減的策略，算法后期由于慣性權(quán)值過小，會(huì)失去探索新區(qū)域的能力，而收縮因子方法則不存在此不足[18]。程序（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ì)其取值。其二，在迭代后期，則因全局搜索能力變?nèi)?，而易陷入局部極值。關(guān)鍵參數(shù)設(shè)置如下:粒子種群大小N:較小的群能充分探索解空間，避免了過多的適應(yīng)值評(píng)估和計(jì)算時(shí)間。決定粒子在一個(gè)循環(huán)中最大的移動(dòng)距離，通常設(shè)為粒子的范圍寬度。慣性權(quán)值: 控制著速度前一變化量對(duì)當(dāng)前變化量的影響，如果較大，則影響較大，能夠搜索以前所未能達(dá)到的區(qū)域，整個(gè)算法的全局搜索能力加強(qiáng)，有利于跳出局部極小點(diǎn)；而值較小，則前一動(dòng)量項(xiàng)的影響較小，主要是在當(dāng)前解的附近搜索，局部搜索能力較強(qiáng)，有利于算法收斂。單因子方差分析是通過觀察一個(gè)因子的量值變化，分析這個(gè)因子變化對(duì)整個(gè)試驗(yàn)的影響程度。首先，假定因子有個(gè)水平，在每種水平下，做次試驗(yàn)，在每次試驗(yàn)后可得一試驗(yàn)值，記做它表示在第個(gè)水平下的第個(gè)試驗(yàn)值。 ， （）其中，總離差平方和是所有觀察值與其總平均值之差的平方和，是描述全部數(shù)據(jù)離散程度的數(shù)量指標(biāo)。平方和分解公式說明觀察值關(guān)于其總平均值之的差異是由組內(nèi)平方和組間平方和組成的。在需要較高計(jì)算速率的應(yīng)用中，可適當(dāng)減小慣性權(quán)值。不全相等。本文對(duì)PSO的基本原理、改進(jìn)形式與應(yīng)用領(lǐng)域等方面進(jìn)行了全面綜述。由于PSO畢竟是一種新興的智能優(yōu)化算法，在以下方面仍然值得進(jìn)一步研究：(1) 理論研究：雖然目前對(duì) PSO 穩(wěn)定性和收斂性的證明已取得了一些初步成果[17]，但自誕生以來其數(shù)學(xué)基礎(chǔ)一直不完備，特別是收斂性一直沒有得到徹底解決。同時(shí)，由于全局模型具有較快的收斂速度、而局部模型具有較好的全局搜索能力，對(duì)信息共享機(jī)制做進(jìn)一步研究，保證算法既具有較快的收斂速度、又具有較好的全局搜索能力，也是一個(gè)很有意義的研究方向。此外，由于PSO本質(zhì)上是一種隨機(jī)搜索算法，現(xiàn)場(chǎng)工程技術(shù)人員對(duì)它的可靠性仍難免心存疑慮，將PSO(或與工業(yè)系統(tǒng)在役技術(shù)結(jié)合)進(jìn)行實(shí)用化推廣，仍是一項(xiàng)任重而道遠(yuǎn)的任務(wù)。我的設(shè)計(jì)較為復(fù)雜煩瑣，而且本身學(xué)習(xí)底子不是很好，但是徐小平老師仍然細(xì)心地糾程序和文章中的錯(cuò)誤。a)%主函數(shù)源程序（）%基本粒子群算法 （particle swarm optimization）%名稱： 基本粒子群算法%初始格式化clear all。 %179。 %學(xué)習(xí)因子1c21=2。 %慣性權(quán)重eps=10^(6)。 %隨機(jī)初始化位置 v(i,j)=randn。grid on xlabel(39。) tInfo=str