【正文】 ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（2）當(dāng)于對比（加速因子與正常情況對比）且運(yùn)行程序（2）得如下結(jié)果： 初始化速度 初始化速度 迭代結(jié)果對比最優(yōu)點坐標(biāo)（1）：[ ]最優(yōu)點坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（3）當(dāng)于對比（加速因子與正常情況對比）的結(jié)果為： 初始化位置 初速度位置 迭代結(jié)果對比最優(yōu)點坐標(biāo)（1）：[ ]最優(yōu)點坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（4）當(dāng)，分別對其取值。（1）當(dāng)。 11122{()( 雖然慣性權(quán)值PSO和收縮因子PSO對典型測試函數(shù)表現(xiàn)出各自的優(yōu)勢[16]，但由于慣性常數(shù)方法通常采用慣性權(quán)值隨更新代數(shù)增加而遞減的策略，算法后期由于慣性權(quán)值過小，會失去探索新區(qū)域的能力，而收縮因子方法則不存在此不足[18]。近來，文獻(xiàn)[15]通過采用隨機(jī)近似理論(stochastic approximation theory)分析PSO的動態(tài)行為，提出了一種隨更新代數(shù)遞減至0的取值策略，以提高算法的搜索能力。帶慣性常數(shù)PSO的速度更新公式如下： （）其中為慣性常數(shù)。 c) 慣性權(quán)值或收縮因子的選擇：當(dāng)PSO的速度更新公式采用式(1)時，即使和兩個加速因子選擇合適，粒子仍然可能飛出問題空間，甚至趨于無窮大，發(fā)生群體“爆炸(explosion)”現(xiàn)象[12]。Ratnaweera 等人[13]則提出自適應(yīng)時變調(diào)整策略。b) 加速常數(shù)的選擇：式(1)中的加速常數(shù)和分別用于控制粒子指向自身或鄰域最佳位置的運(yùn)動。的選擇通常憑經(jīng)驗給定，并一般設(shè)定為問題空間的 [3]。增大，有利于全局探索(global exploration)；減小，則有利于局部開發(fā)(local exploitation)[3]。 a) 最大速度的選擇：如式()所示的粒子速度是一個隨機(jī)變量，由粒子位置更新公式()產(chǎn)生的運(yùn)動軌跡是不可控的，使得粒子在問題空間循環(huán)跳動[3, 6]。 主成分PSO：文獻(xiàn)[10]結(jié)合主成分分析技術(shù)，粒子不僅按照傳統(tǒng)算法在維的x空間飛行，而且還在維的z空間同步飛行。 4）量子粒子群優(yōu)化：文獻(xiàn)[9]采用量子個體提出離散PSO；文獻(xiàn)[9]則基于量子行為更新粒子位置。 3）免疫粒子群優(yōu)化：生物免疫系統(tǒng)是一個高度魯棒性、分布性、自適應(yīng)性并具有強(qiáng)大識別能力、學(xué)習(xí)和記憶能力的非線性系統(tǒng)。除此之外，文獻(xiàn)[4]利用慣性權(quán)值自適應(yīng)于目標(biāo)函數(shù)值的自適應(yīng)PSO進(jìn)行全局搜索、利用混沌局部搜索對最佳位置進(jìn)行局部搜索，提出一種PSO與混沌搜索相結(jié)合的混沌PSO；文獻(xiàn)[15]則利用混沌序列確定PSO的參數(shù)(慣性權(quán)值和加速常數(shù))。 混沌粒子群優(yōu)化：混沌是自然界一種看似雜亂、其實暗含內(nèi)在規(guī)律性的常見非線性現(xiàn)象，具有隨機(jī)性、遍歷性和規(guī)律性特點。此外，還有其它一些混合PSO： 1）高斯PSO：由于傳統(tǒng)PSO往往是在全局和局部最佳位置的中間進(jìn)行搜索，搜索能力和收斂性能嚴(yán)重依賴加速常數(shù)和慣性權(quán)值的設(shè)置，為了克服該不足，Secrest等人[10]將高斯函數(shù)引入PSO算法中，用于引導(dǎo)粒子的運(yùn)動；GPSO不再需要慣性權(quán)值，而加速常數(shù)由服從高斯分布的隨機(jī)數(shù)產(chǎn)生。文獻(xiàn)[8]通過模擬自然界的被動聚集(Passive Congregation)行為修改速度更新公式，實現(xiàn)種群內(nèi)信息充分共享，防止了微粒因缺乏足夠的信息而判斷失誤所導(dǎo)致陷入局部極小。該算法通過附加噪聲持續(xù)為粒子群引入負(fù)熵(negative entropy)，使得系統(tǒng)處于遠(yuǎn)離平衡態(tài)的狀態(tài)，又由于群體中存在內(nèi)在的非線性相互作用，從而形成自組織耗散結(jié)構(gòu)，使粒子群能夠“持續(xù)進(jìn)化”，抑制早熟停滯。 還有作者引入其它一些機(jī)制，以改進(jìn)PSO的性能。 此外，其它一些搜索技術(shù)與PSO結(jié)合以提高算法的局部搜索能力，如文獻(xiàn)[9]提出一種基于PSO和LevenbergMarquardt的混合方法。這種結(jié)合的途徑通常有兩種：一是利用其它優(yōu)化技術(shù)自適應(yīng)調(diào)整收縮因子/慣性權(quán)值、加速常數(shù)等；二是將PSO與其它進(jìn)化算法操作算子或其它技術(shù)結(jié)合。vbjerg 等人為每個粒子引入與相鄰粒子距離成反比的自組織危險度(selforganized criticality)指標(biāo)，距離越近則危險度越高，當(dāng)達(dá)到一定閾值后，對該粒子進(jìn)行重新初始化或推開一定距離降低危險度，達(dá)到提高群體多樣性的目的；文獻(xiàn)[15]提出一種帶空間粒子擴(kuò)展的PSO，為每個粒子賦一半徑，以檢測兩個粒子是否會碰撞，并采取隨機(jī)彈離、實際物理彈離、簡單的速度—直線彈離等措施將其分開。還有一類局部模型就是主動改變粒子鄰域空間，避免碰撞和擁擠，本文稱之為PSO的主動局部模型。同時，為了確保粒子盡可能向好的對象學(xué)習(xí)而不把時間浪費在較差的對象上，上述學(xué)習(xí)對象選擇過程設(shè)定一個更新間隔代數(shù)(refreshing gap)，在此期間的學(xué)習(xí)對象保持上次選擇的學(xué)習(xí)對象不變。與傳統(tǒng)PSO只向自身歷史最佳位置和鄰域歷史最佳位置學(xué)習(xí)不同，CLPSO的每個粒子都隨機(jī)地向自身或其它粒子學(xué)習(xí)，并且其每一維可以向不同的粒子學(xué)習(xí)；該學(xué)習(xí)策略使得每個粒子擁有更多的學(xué)習(xí)對象，可以在更大的潛在空間飛行，從而有利于全局搜索。 無論是粒子群在D維的搜索還是多個粒子群在不同維上的協(xié)作搜索，其目的都是為了每個粒子能夠找到有利于快速收斂到全局最優(yōu)解的學(xué)習(xí)對象。Baskar和Suganthan[19]提出一種類似的協(xié)作PSO，稱為并發(fā)PSO(concurrent PSO， CONPSO)，它采用兩個群體并發(fā)地優(yōu)化一個解矢量。 上述粒子間學(xué)習(xí)是在整個維空間中構(gòu)造鄰域進(jìn)行的，這樣當(dāng)搜索空間維數(shù)較高時往往容易遭受“維數(shù)災(zāi)(curse of dimensionality)”的困擾[14]。文獻(xiàn)[14]則每間隔一定代數(shù)將整個群體隨機(jī)地重新劃分，提出動態(tài)多群體PSO。文獻(xiàn)[14]將小生境(niche)技術(shù)引入到PSO中，提出了小生境PSO(Niching Particle Swarm Optimizer)。Stefan Janson等人[22]提出等級PSO(hierarchical particle swarm optimizer, HPSO)，采用動態(tài)等級樹作為鄰域結(jié)構(gòu)，歷史最佳位置更優(yōu)的粒子處于上層，每個粒子的速度由自身歷史最佳位置和等級樹中處于該粒子上一個節(jié)點的粒子的歷史最佳位置決定。Kennedy[20]提出了社會趨同(Stereotyping)模型，使用簇分析將整個粒子群劃分為多個簇，然后用簇中心代替帶收縮因子PSO中的粒子歷史最佳位置或群體歷史最佳位置。 此外，還有其它一些主要對群體進(jìn)行劃分的鄰域結(jié)構(gòu)(本文暫稱“宏觀鄰域”；則上述鄰域稱為“微觀鄰域”)。M. Clerc[25]對隨機(jī)拓?fù)溥M(jìn)行了進(jìn)一步分析，并在2006年版和2007年版的標(biāo)準(zhǔn)PSO[23]中采用了隨機(jī)拓?fù)?。社會關(guān)系鄰域通常按粒子存儲陣列的索引編號進(jìn)行劃分[25]，這也是研究最多的一種劃分手段，主要有[21]：環(huán)形拓?fù)?ring or circle topology)、輪形拓?fù)?wheel topology)或星形拓?fù)?star topology)、塔形拓?fù)?pyramid topology)、馮－諾以曼拓?fù)?Von Neumann topology)以及隨機(jī)拓?fù)?random topology)等。空間鄰域直接在搜索空間按粒子間的距離(如歐式距離)進(jìn)行劃分，如Suganthan[23]引入一個時變的歐式空間鄰域算子：在搜索初始階段，將鄰域定義為每個粒子自身；隨著迭代次數(shù)的增加，將鄰域范圍逐漸擴(kuò)展到整個種群。為了克服全局模型的缺點，研究人員采用每個粒子僅在一定的鄰域內(nèi)進(jìn)行信息交換，提出各種局部模型[21,]。對于模型，每個粒子與整個群體的其他粒子進(jìn)行信息交換，并有向所有粒子中的歷史最佳位置移動的趨勢。為了初始種群盡可能均勻覆蓋整個搜索空間，提高全局搜索能力，Richard 和Ventura[17]提出了基于centroidal voronoi tessellations (CVTs)的種群初始化方法；薛明志等人[18]采用正交設(shè)計方法對種群進(jìn)行初始化；Campana 等人[19]將標(biāo)準(zhǔn)PSO迭代公式改寫成線性動態(tài)系統(tǒng)，并基于此研究粒子群的初始位置，使它們具有正交的運(yùn)動軌跡；文獻(xiàn)[16]認(rèn)為均勻分布隨機(jī)數(shù)進(jìn)行初始化實現(xiàn)容易但尤其對高維空間效果差，并另外比較了3種初始化分布方法。本文將這些改進(jìn)分為4類：粒子群初始化、鄰域拓?fù)?、參?shù)選擇和混合策略。同時，PSO的性能也依賴于算法參數(shù)[15]。PSO由于有簡單、易于實現(xiàn)、設(shè)置參數(shù)少、無需梯度信息等特點，其在連續(xù)非線性優(yōu)化問題和組合優(yōu)化問題中都表現(xiàn)出良好的效果。 粒子群算法的研究現(xiàn)狀在算法的理論研究方面。當(dāng)時，式()與式()完全一樣，表明帶慣性權(quán)重的粒子群算法是基本粒子群算法的擴(kuò)展?？梢钥闯觯剑?中慣性權(quán)重表示在多大程度上保留原來的速度。1998年，Yuhui Shi[9]提出了帶有慣性權(quán)重的改進(jìn)粒子群算法。開發(fā)是利用一個好的解，繼續(xù)原來的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。在粒子群優(yōu)化算法中，信息流動是單向的，即只有將信息給其他的粒子，這使得整個搜索更新過程跟隨當(dāng)前解。粒子具有“記憶”的特性，它們通過“自我”學(xué)習(xí)和向“他人”學(xué)習(xí)，使其下一代解有針對性的從“先輩”那里繼承更多的信息，從而能在較短的時間內(nèi)找到最優(yōu)解。PSO 的一個優(yōu)勢就是采用實數(shù)編碼，不需要像遺傳算法一樣采用二進(jìn)制編碼(或者采用針對實數(shù)的遺傳操作) 。整個求解過程中，慣性權(quán)重、加速因子和和最大速度共同維護(hù)粒子對全局和局部搜索能力的平衡。輸出結(jié)果根據(jù)方程()對粒子的位置進(jìn)行進(jìn)化根據(jù)方程()對粒子的速度進(jìn)行進(jìn)化求出整個群體的全局最優(yōu)值求出每個粒子的個體最優(yōu)計算每個粒子的適應(yīng)值初始化每個粒子的速度和位置是否滿足結(jié)束條件是否開 始. PSO算法流程圖 特點式()中第1部分可理解為粒子先前的速度或慣性；第2部份可理解為粒子的“認(rèn)知”行為，表示粒子本身的思考能力；第3部分可理解為粒子的“社會”行為，表示粒子之間的信息共享與相互合作。和是介于之間的隨機(jī)數(shù)[2][5]。式()右邊由三部分組成，第一部分為“慣性(inertia)”或“動量(momentum)”部分，反映了粒子的運(yùn)動“習(xí)慣(habit)”，代表粒子有維持自己先前速度的趨勢；第二部分為“認(rèn)知(cognition)”部分，反映了粒子對自身歷史經(jīng)驗的記憶(memory)或回憶(remembrance)，代表粒子有向自身歷史最佳位置逼近的趨勢；第三部分為“社會(social)”部分，反映了粒子間協(xié)同合作與知識共享的群體歷史經(jīng)驗，代表粒子有向群體或鄰域歷史最佳位置逼近的趨勢，根據(jù)經(jīng)驗，通常。第個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為 。假設(shè)在一個維的目標(biāo)搜索空間中，有個粒子組成一個群落，其中第個粒子表示為一個維的向量。在每一次迭代中，粒子通過跟蹤兩個極值來更新自己；第一個就是粒子本身所找到的最優(yōu)解，這個解稱為個體極值；另一個極值是整個種群目前找到的最優(yōu)解，這個極值是全局極值。然后粒子們就追隨當(dāng)前的最優(yōu)粒子在解空間中搜索[1]。PSO 中，每個優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。思維背后的社會現(xiàn)象遠(yuǎn)比魚群和鳥群聚集過程中的優(yōu)美動作復(fù)雜的多：首先，思維發(fā)生在信念空間，其維數(shù)遠(yuǎn)遠(yuǎn)高于3；其次，當(dāng)兩種思想在認(rèn)知空間會聚于同一點時，我們稱其一致，而不是發(fā)生沖突。在人們的不斷交互過程中，由于相互的影響和模仿，他們總會變得更相似，結(jié)果就形成了規(guī)范和文明。Kennedy在他的書中描述了粒子群算法思想的起源。1995年，美國社會心理學(xué)家James Kennedy和電氣工程師Russell Eberhart共同提出了粒子群算法，其基本思想是受對鳥類群體行為進(jìn)行建模與仿真的研究結(jié)果的啟發(fā)。1990年，生物學(xué)家Frank Heppner也提出了鳥類模型[8]，它的不同之處在于：鳥類被吸引飛到棲息地。自然界中的鳥群和魚群的群體行為一直是科學(xué)家的研究興趣，生物學(xué)家Craig Reynolds在1987年提出了一個非常有影響的鳥群聚集模型[7]，在他的仿真中，每一個個體遵循：(1) 避免與鄰域個體相沖撞；(2) 匹配鄰域個體的速度；(3) 飛向鳥群中心，且整個群體飛向目標(biāo)。PSO算法具有很好的生物社會背景[2]而易理解、參數(shù)少而易實現(xiàn)，對非線性、多峰問題均具有較強(qiáng)的全局搜索能力，在科學(xué)研究與工程實踐中得到了廣泛關(guān)注[310]。 粒子群算法思想的起源粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法 [1]是Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機(jī)搜索算法，1995年IEEE國際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會議發(fā)表了題為“Particle Swarm Optimization”的論文，標(biāo)志著PSO算法誕生(注：國內(nèi)也有很多學(xué)者譯為“微粒群優(yōu)化”)。并且通過公式計算準(zhǔn)確判斷參數(shù)對算法影響。 主要工作論文內(nèi)容介紹了基本粒子群算法，用matlab實現(xiàn)標(biāo)準(zhǔn)粒子群算法算法，對兩個不同類型函數(shù)做具體分析，然后對其參數(shù)（慣性權(quán)值），（加速因子）測試。除了從中可以得到他們近幾年公開發(fā)表的相關(guān)文獻(xiàn)和源代碼，還可以下載一些未公開發(fā)表的文章。對一些初學(xué)者而言，哪里能下載得到PSO的源程序，是他們很關(guān)心的話題；即使對一些資深的讀者，為了驗證自己提出的新算法或改進(jìn)算法，如果能找到高級別國際期刊或會議上最近提出的算法源程序，那也是事半功倍的美事。 電子資源 身處信息和網(wǎng)絡(luò)時代的我們是幸運(yùn)的，豐富的電子資源能讓我們受益匪淺。典型理論問題包括：組合優(yōu)化、約束優(yōu)化、多目標(biāo)優(yōu)化、動態(tài)系統(tǒng)優(yōu)化等。 應(yīng)用