【正文】 gy)或星形拓?fù)?star topology)、塔形拓?fù)?pyramid topology)、馮－諾以曼拓?fù)?Von Neumann topology)以及隨機(jī)拓?fù)?random topology)等。為了克服全局模型的缺點(diǎn)，研究人員采用每個(gè)粒子僅在一定的鄰域內(nèi)進(jìn)行信息交換，提出各種局部模型[21,]。為了初始種群盡可能均勻覆蓋整個(gè)搜索空間，提高全局搜索能力，Richard 和Ventura[17]提出了基于centroidal voronoi tessellations (CVTs)的種群初始化方法；薛明志等人[18]采用正交設(shè)計(jì)方法對(duì)種群進(jìn)行初始化；Campana 等人[19]將標(biāo)準(zhǔn)PSO迭代公式改寫成線性動(dòng)態(tài)系統(tǒng)，并基于此研究粒子群的初始位置，使它們具有正交的運(yùn)動(dòng)軌跡；文獻(xiàn)[16]認(rèn)為均勻分布隨機(jī)數(shù)進(jìn)行初始化實(shí)現(xiàn)容易但尤其對(duì)高維空間效果差，并另外比較了3種初始化分布方法。同時(shí)，PSO的性能也依賴于算法參數(shù)[15]。 粒子群算法的研究現(xiàn)狀在算法的理論研究方面?？梢钥闯觯剑?中慣性權(quán)重表示在多大程度上保留原來的速度。開發(fā)是利用一個(gè)好的解，繼續(xù)原來的尋優(yōu)軌跡去搜索更好的解，它是算法的局部搜索能力。粒子具有“記憶”的特性，它們通過“自我”學(xué)習(xí)和向“他人”學(xué)習(xí)，使其下一代解有針對(duì)性的從“先輩”那里繼承更多的信息，從而能在較短的時(shí)間內(nèi)找到最優(yōu)解。整個(gè)求解過程中，慣性權(quán)重、加速因子和和最大速度共同維護(hù)粒子對(duì)全局和局部搜索能力的平衡。和是介于之間的隨機(jī)數(shù)[2][5]。第個(gè)粒子迄今為止搜索到的最優(yōu)位置稱為個(gè)體極值，記為 。在每一次迭代中，粒子通過跟蹤兩個(gè)極值來更新自己；第一個(gè)就是粒子本身所找到的最優(yōu)解，這個(gè)解稱為個(gè)體極值；另一個(gè)極值是整個(gè)種群目前找到的最優(yōu)解，這個(gè)極值是全局極值。PSO 中，每個(gè)優(yōu)化問題的潛在解都是搜索空間中的一只鳥，稱之為粒子。在人們的不斷交互過程中，由于相互的影響和模仿，他們總會(huì)變得更相似，結(jié)果就形成了規(guī)范和文明。1995年，美國(guó)社會(huì)心理學(xué)家James Kennedy和電氣工程師Russell Eberhart共同提出了粒子群算法，其基本思想是受對(duì)鳥類群體行為進(jìn)行建模與仿真的研究結(jié)果的啟發(fā)。自然界中的鳥群和魚群的群體行為一直是科學(xué)家的研究興趣，生物學(xué)家Craig Reynolds在1987年提出了一個(gè)非常有影響的鳥群聚集模型[7]，在他的仿真中，每一個(gè)個(gè)體遵循：(1) 避免與鄰域個(gè)體相沖撞；(2) 匹配鄰域個(gè)體的速度；(3) 飛向鳥群中心，且整個(gè)群體飛向目標(biāo)。 粒子群算法思想的起源粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法 [1]是Kennedy和Eberhart受人工生命研究結(jié)果的啟發(fā)、通過模擬鳥群覓食過程中的遷徙和群聚行為而提出的一種基于群體智能的全局隨機(jī)搜索算法，1995年IEEE國(guó)際神經(jīng)網(wǎng)絡(luò)學(xué)術(shù)會(huì)議發(fā)表了題為“Particle Swarm Optimization”的論文，標(biāo)志著PSO算法誕生(注：國(guó)內(nèi)也有很多學(xué)者譯為“微粒群優(yōu)化”)。 主要工作論文內(nèi)容介紹了基本粒子群算法，用matlab實(shí)現(xiàn)標(biāo)準(zhǔn)粒子群算法算法，對(duì)兩個(gè)不同類型函數(shù)做具體分析，然后對(duì)其參數(shù)（慣性權(quán)值），（加速因子）測(cè)試。對(duì)一些初學(xué)者而言，哪里能下載得到PSO的源程序，是他們很關(guān)心的話題；即使對(duì)一些資深的讀者，為了驗(yàn)證自己提出的新算法或改進(jìn)算法，如果能找到高級(jí)別國(guó)際期刊或會(huì)議上最近提出的算法源程序，那也是事半功倍的美事。典型理論問題包括：組合優(yōu)化、約束優(yōu)化、多目標(biāo)優(yōu)化、動(dòng)態(tài)系統(tǒng)優(yōu)化等。包括不變的情況下通過，變化找出加速因子對(duì)算法的影響。雖然PSO算法發(fā)展迅速并取得了可觀的研究成果,但其理論基礎(chǔ)仍相對(duì)薄弱，尤其是算法基本模型中的參數(shù)設(shè)置和優(yōu)化問題還缺乏成熟的理論論證和研究。最初設(shè)想是模擬鳥群覓食的過程?，F(xiàn)在我們討論另一種生物系統(tǒng) 社會(huì)系統(tǒng)。研究如何利用生物技術(shù)研究計(jì)算問題。人工生命包括兩方面的內(nèi)容：研究如何利用計(jì)算技術(shù)研究生物現(xiàn)象。遺傳算法是模擬基因進(jìn)化過程的。粒子群優(yōu)化算法(PSO) 也是起源對(duì)簡(jiǎn)單社會(huì)系統(tǒng)的模擬。粒子群優(yōu)化算法[1] (簡(jiǎn)稱PSO)是由Kennedy和Eberhart通過對(duì)鳥群、魚群和人類社會(huì)某些行為的觀察研究，于1995年提出的一種新穎的進(jìn)化算法。 參數(shù)的影響標(biāo)準(zhǔn)粒子群算法中主要的參數(shù)變量為（慣性權(quán)值）， ，（加速因子），本文重點(diǎn)對(duì)參數(shù)， ，做數(shù)據(jù)統(tǒng)計(jì)實(shí)驗(yàn)。本文將應(yīng)用研究分典型理論問題研究和實(shí)際工業(yè)應(yīng)用兩大類。如果想較快地對(duì)PSO有一個(gè)比較全面的了解，借助網(wǎng)絡(luò)空間的電子資源無疑是不二之選。這些未公開發(fā)表的文章往往是Maurice Clerc博士的一些設(shè)想，而且在不斷更新，如“Back to random topology”、“Initialisations for particle swarm optimization”、“Some ideas about PSO”等等，對(duì)PSO研究人員很有啟發(fā)。最后說明粒子群優(yōu)化算法在實(shí)際中的應(yīng)用以及對(duì)未來展望，最后總結(jié)了算法的優(yōu)缺點(diǎn)，附錄里面附有測(cè)試程序和測(cè)試函數(shù)。自然界中各種生物體均具有一定的群體行為，而人工生命的主要研究領(lǐng)域之一是探索自然界生物的群體行為，從而在計(jì)算機(jī)上構(gòu)建其群體模型。在仿真中，一開始每一只鳥都沒有特定的飛行目標(biāo)，只是使用簡(jiǎn)單的規(guī)則確定自己的飛行方向和飛行速度（每一只鳥都試圖留在鳥群中而又不相互碰撞），當(dāng)有一只鳥飛到棲息地時(shí)，它周圍的鳥也會(huì)跟著飛向棲息地，這樣，整個(gè)鳥群都會(huì)落在棲息地。自20世紀(jì)30年代以來，社會(huì)心理學(xué)的發(fā)展揭示：我們都是魚群或鳥群聚集行為的遵循者。 算法原理PSO從這種模型中得到啟示并用于解決優(yōu)化問題。PSO初始化為一群隨機(jī)粒子(隨機(jī)解)，然后通過迭代找到最優(yōu)解。第個(gè)粒子的“飛行 ”速度也是一個(gè)維的向量，記為 。是粒子的速度，是常數(shù)，由用戶設(shè)定用來限制粒子的速度。公式() 表示了粒子在求解空間中，由于相互影響導(dǎo)致的運(yùn)動(dòng)位置調(diào)整。例如對(duì)于問題求解， 粒子可以直接編碼為 ，而適應(yīng)度函數(shù)就是 。 帶慣性權(quán)重的粒子群算法探索是偏離原來的尋優(yōu)軌跡去尋找一個(gè)更好的解，探索能力是一個(gè)算法的全局搜索能力。其進(jìn)化過程為： （） （）在式()中，第一部分表示粒子先前的速度，用于保證算法的全局收斂性能；第二部分、第三部分則是使算法具有局部收斂能力。實(shí)驗(yàn)結(jié)果表明，在之間時(shí)，PSO算法有更快的收斂速度，而當(dāng)時(shí)，算法則易陷入局部極值。由于PSO中粒子向自身歷史最佳位置和鄰域或群體歷史最佳位置聚集，形成粒子種群的快速趨同效應(yīng)，容易出現(xiàn)陷入局部極值、早熟收斂或停滯現(xiàn)象[1214]。 粒子群初始化 研究表明，粒子群初始化對(duì)算法性能產(chǎn)生一定影響[16]。Kennedy[21]指出，模型雖然具有較快的收斂速度，但更容易陷入局部極值。性能空間指根據(jù)性能指標(biāo)(如適應(yīng)度、目標(biāo)函數(shù)值)劃分的鄰域，如文獻(xiàn)[24]采用適應(yīng)度距離比值(fitnessdistanceratio)來選擇粒子的相鄰粒子。此外，文獻(xiàn)[21]提出動(dòng)態(tài)社會(huì)關(guān)系拓?fù)?Dynamic sociometry)，初始階段粒子采用環(huán)形拓?fù)?ringtype topology)，隨著迭代次數(shù)的增加，逐漸增加粒子間連接，最后形成星形拓?fù)?startype topology)。X. Li[21]根據(jù)粒子相似性動(dòng)態(tài)地將粒子群體按種類劃分為多個(gè)子種群，再以每個(gè)子種群的最佳個(gè)體作為每個(gè)粒子的鄰域最佳位置。文獻(xiàn)[15]采用多群體進(jìn)行解的搜索?；谶@方面的考慮，Van den Bergh等人[18]提出了協(xié)作PSO(Cooperative PSO)算法，其基本思路就是采用協(xié)作行為，利用多個(gè)群體分別在目標(biāo)搜索空間中的不同維度上進(jìn)行搜索，也就是一個(gè)優(yōu)化解由多個(gè)獨(dú)立群體協(xié)作完成，每個(gè)群體只負(fù)責(zé)優(yōu)化這個(gè)解矢量部分維上的分量。J. Liang 等人[4]提出了一種既可以進(jìn)行D維空間搜索、又能在不同維上選擇不同學(xué)習(xí)對(duì)象的新的學(xué)習(xí)策略，稱為全面學(xué)習(xí)PSO (Comprehensive Learning Particle Swarm Optimizer，CLPSO)。以上的各種鄰域結(jié)構(gòu)，無論是微觀拓?fù)溥€是宏觀鄰域，也無論是在整個(gè)搜索空間進(jìn)行信息交流還是以空間的不同維分量為單位協(xié)作搜索，都不主動(dòng)改變鄰域狀態(tài)，而只是在給定的鄰域內(nèi)進(jìn)行學(xué)習(xí)交流，本文稱之為PSO的被動(dòng)局部模型。 混合策略 混合策略混合PSO就是將其它進(jìn)化算法或傳統(tǒng)優(yōu)化算法或其它技術(shù)應(yīng)用到PSO中，用于提高粒子多樣性、增強(qiáng)粒子的全局探索能力，或者提高局部開發(fā)能力、增強(qiáng)收斂速度與精度。文獻(xiàn)[10]將PSO與單純形法相結(jié)合；文獻(xiàn)將PSO與序貫二次規(guī)劃相結(jié)合；文獻(xiàn)[12]將模擬退火與PSO結(jié)合；文獻(xiàn)[13]將禁忌技術(shù)與PSO結(jié)合；文獻(xiàn)[8]將爬山法與PSO結(jié)合；文獻(xiàn)[15]將PSO與擬牛頓法結(jié)合。文獻(xiàn)[7]將自然進(jìn)化過程中的群體滅絕現(xiàn)象引入PSO，在微粒的位置和速度更新之后，按照一個(gè)預(yù)先定義的滅絕間隔重新初始化所有微粒的速度。 2）拉伸PSO(Stretching PSO, SPSO)：SPSO將所謂的拉伸技術(shù)(stretching technique)[11]以及偏轉(zhuǎn)和排斥技術(shù)應(yīng)用到PSO中，對(duì)目標(biāo)函數(shù)進(jìn)行變換，限制粒子向已經(jīng)發(fā)現(xiàn)的局部最小解運(yùn)動(dòng)，從而利于粒子有更多的機(jī)會(huì)找到全局最優(yōu)解[4, 6]。文獻(xiàn)[9]提出一種不含隨機(jī)參數(shù)、基于確定性混沌Hopfield神經(jīng)網(wǎng)絡(luò)群的粒子群模型。 5）卡爾曼PSO：文獻(xiàn)[9]利用Kalman濾波更新粒子位置。為了抑制這種無規(guī)律的跳動(dòng)，速度往往被限制在內(nèi)。此外，文獻(xiàn)[17]提出了的動(dòng)態(tài)調(diào)節(jié)方法以改善算法性能；而文獻(xiàn)[48]提出了自適應(yīng)于群體最佳和最差適應(yīng)度值的選擇方法。與傳統(tǒng)PSO取正數(shù)加速常數(shù)不同，Riget和Vesterstrom[11]提出一種增加種群多樣性的粒子群算法，根據(jù)群體多樣性指標(biāo)調(diào)整加速常數(shù)的正負(fù)號(hào)，動(dòng)態(tài)地改變“吸引”(Attractive)和“擴(kuò)散”(Repulsive)狀態(tài)，以改善算法過早收斂問題。文獻(xiàn)[8]。 測(cè)試仿真函數(shù)例1. 函數(shù)對(duì)于適應(yīng)度函數(shù)fitness對(duì)其參數(shù)，做出不同方式的比較已測(cè)試其對(duì)函數(shù)結(jié)果影響。分析結(jié)果如下： 初始化位置 初始化速度 迭代結(jié)果對(duì)比最優(yōu)點(diǎn)坐標(biāo)（1）：[ ]最優(yōu)坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：（5）對(duì)，對(duì)分別取，對(duì)比其迭代影響 初始化位置 初速度位置 迭代結(jié)果最優(yōu)點(diǎn)坐標(biāo)（1）：[ 最優(yōu)坐標(biāo)（2）：[ ]適應(yīng)度值（1）為：適應(yīng)度值（2）為：108141522528168（6）標(biāo)準(zhǔn)粒子群算法無參數(shù)對(duì)比， 粒子群位置初始化 粒子群初始化速度 迭代結(jié)果在以上仿真中，我們5個(gè)實(shí)驗(yàn)實(shí)數(shù)的選擇分別對(duì)，不同情況做出對(duì)比得出結(jié)論：慣性權(quán)重的不同取值對(duì)PSO的影響試驗(yàn)表明權(quán)值將影響PSO 的全局與局部搜優(yōu)能力，值較大，全局搜優(yōu)能力強(qiáng)，局部搜優(yōu)能力弱。時(shí)，粒子群優(yōu)化算法的搜索效率和搜索精度高。一般取[20 40]，對(duì)于大部分的問題， 10個(gè)粒子已經(jīng)足夠取得好的結(jié)果，對(duì)于比較難的問題或者特定類別的問題，粒子數(shù)可以取到100，200。學(xué)習(xí)因子： 和通常等于2，不過文獻(xiàn)中也有其它的取值，一般，且范圍在0和4之間。研究表明，讓慣性權(quán)值隨著疊代次數(shù)的增加在1. 4到0之間逐步減少可以取得較好的效果。利用這種方法可考查PSO中和這兩個(gè)關(guān)鍵的參數(shù)因子各自對(duì)算法性能的影響。 如表1 所示，在考察因子對(duì)試驗(yàn)結(jié)果的影響程度時(shí)，把因子的個(gè)水平看成是個(gè)正態(tài)總體，因此可設(shè)， ， 。由于是服從正態(tài)分布的隨機(jī)量，當(dāng)公式() 成立時(shí)是獨(dú)立同分布。因此，公式() 表示的和之間的比值F就是反映了兩種差異所占的比重。針對(duì)本程序（適應(yīng)函數(shù)）令，做單因子方差分析，判斷因子對(duì)程序的影響。解：現(xiàn)在。在科學(xué)與工程實(shí)踐領(lǐng)域，關(guān)心PSO的讀者的共同興趣所在是PSO本身，即“PSO是什么”和“有些什么樣的改進(jìn)形式”，而“用PSO怎樣解決某個(gè)具體問題”則依賴于相應(yīng)領(lǐng)域的專業(yè)知識(shí)；為了讓盡可能多的國(guó)內(nèi)讀者從中受益而不局限于具體的工業(yè)背景，綜述內(nèi)容側(cè)重于對(duì)基本PSO原理、算法改進(jìn)，特別是相關(guān)國(guó)際發(fā)展現(xiàn)狀進(jìn)行分析，而PSO應(yīng)用綜述僅僅列出了典型理論問題和實(shí)際工業(yè)問題兩個(gè)方面的一些主要應(yīng)用對(duì)象。因此，仍需要對(duì) PSO 的收斂性等方面進(jìn)行進(jìn)一步的理論研究。(4) 混合 PSO：混合進(jìn)化算法是進(jìn)化算法領(lǐng)域的趨勢(shì)之一[12]，與其它進(jìn)化算法或傳統(tǒng)優(yōu)化技術(shù)相結(jié)合，提出新的混合PSO算法，甚至提出基于PSO的超啟發(fā)式搜索算法(hyperheuristics)，使算法對(duì)不同種類的問題具有盡可能好的普適性，并能“更好、更快、更廉(good enough – soon enough – cheap enough)”地得到問題的解[13]，也是一個(gè)很有價(jià)值的研究方向。參考文獻(xiàn):[1] Kennedy J, Eberhart R. Particle swarm optimization [A]. in: Proceedings of the 4th IEEE International Conference on Neural Networks [C]，Piscataway: IEEE Service Center, 1995, 1948. [2] Garnier S, Gautrais J, Theraulaz G. T