【正文】 更簡單、參數(shù)更少、實現(xiàn)更容易。在 GA 中，染色體(Chromosomes)互相共享信息，所以整個種群的移動是比較均勻的向最優(yōu)區(qū)域移動。而 GA 中，以前的知識隨著種群的改變被破壞。如果將粒子經(jīng)歷的最好位置看作是粒子群的組成部分，則粒子群的每一步進化都呈現(xiàn)出弱化形式的“選擇”機制。粒子群算法隱含著一定“形式”的選擇機制。根據(jù)個體的適應度信息進行搜索，因此不受函數(shù)約束條件的限制，如連續(xù)性、可導性等。搜索過程是從問題解的一個集合開始的，而不是從單個個體開始，具有隱含并行搜索特性，從而減小了陷入局部極小的可能性。在解空間都隨機產(chǎn)生初始種群，因而算法在全局的解空間進行搜索，并且將搜索重點集中在性能高的部分；PSO 中認知項和社會項前都加有隨機數(shù)，GA 的遺傳操作均屬隨機操作。（4） 如果終止條件滿足的話，就停止，否則轉步驟（2）從 PSO 基本步驟可以看到 PSO 和 GA 有很多共同之處，結合我們的理解，可以歸納如下。idiidV2）式中 表示第 i 個粒子在第 d 維上的速度； 為慣性權重，控制粒子的每一代速度idv ?更新有多少以前的速度保留下來； 和 為調(diào)節(jié) 和 相對重要性的參數(shù)，根據(jù)1c2idPg經(jīng)驗通常取 ； 為隨機數(shù)生成函數(shù)，生成介于(0,1)之間的隨機數(shù)；。 12())())idi idi gdiVcranPXcranPX??????1） （239。局部版 PSO 收斂速度慢一點，但相對的不易陷入局部最優(yōu)。也bestg可以把第 i 個粒子的鄰居們搜索到的最優(yōu)位置作為 ，則上述方法又稱為局部版estPSO。第 i 個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為 ，12(,.)iiidY? bestP整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 。將 代入一個目標函數(shù)就可以計算出其適應值，根據(jù)其適應度值的大小衡量優(yōu)劣。每個粒子bestP bestg都通過上述兩個極值不斷更新自己，從而產(chǎn)生新一代群體。通常粒子將追隨當前的最優(yōu)粒子而運動，并經(jīng)逐代搜索最后得到最優(yōu)解。PSO 首先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都為優(yōu)化問題的一個可行解，并由目標函數(shù)為之確定一個適應值。所不同的是 PSO 是將每個個體看作是在 N 維搜索空間中的沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。起初Kennedy 和 Eberhart 只是設想模擬鳥群覓食的過程，但后來的研究中發(fā)現(xiàn) PSO 是一種很好的優(yōu)化工具。PSO 從這種模型中得到啟示并用于解決優(yōu)化問題。但是他們知道當前的位置離食物還有多遠。在這個區(qū)域里只有一塊食物。 粒子群算法的原理 粒子群優(yōu)化算法的基本概念源于對鳥群覓食行為的研究。在函數(shù)優(yōu)化 [14]、神經(jīng)網(wǎng)絡訓練 [15]、系統(tǒng)控制 [10]等領域得到廣泛應用。但 PSO 沒有 GA 的“選擇” 、 “交叉” 、 “變異”算子，編碼方式也較 GA 簡單。PSO 就是對這種社會行為的模擬，即利用信息共享機制，使得個體間可以相互借鑒經(jīng)驗，從而促進整個群體的發(fā)展。通過對類似生物群體的行為的研究，發(fā)現(xiàn)在生物群體中存在著個體與個體、個體與群體間的相互作用、相互影響的行為，這種行為體現(xiàn)的是一種存在于生物群體中的信息共享的機制。第 2 章 粒子群優(yōu)化算法 粒子群算法(PSO)是 1995 由 Kennedy 和 Eberhart[12]首先提出的一類基于群智能的演化計算方法。粒子群優(yōu)化技術的應用領域己擴展到組合優(yōu)化、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信 Qos 管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面。在避免早熟收斂方面，現(xiàn)有的大量研究涉及如何讓算法跳出局部最優(yōu)點。如何加快算法的收斂速度和避免早熟收斂問題，一直是大多數(shù)研究者關注的重點，也是所有隨機搜索算法共同面臨的兩個主要難題。如何將 PSO 應用于組合優(yōu)化問題也是一個重要的研究方向。由于實際問題的多樣性和復雜性，盡管目前已經(jīng)有了多種不同版本的 PSO改進算法但這些 PSO 算法不具有通用性，或者參數(shù)的設置要求使用者具備較高的經(jīng)驗，否則難以達到理想的效果。目前 PSO 的研究尚處于初期，還有許多問題值得做進一步的研究。此外，充分利用其他進化算法以改善微粒群算法存在的不足，也是值得研究的問題。進一步的研究還發(fā)現(xiàn)相同參數(shù)設置的 PSO應用在不同電力系統(tǒng)問題上獲得了高質(zhì)量的解。他們使用的是慣性權值線性遞減的 PSO，結果表明比原來使用的 RTS 算法效率更高。在速度更新前，通過簡單離散值來調(diào)整PSO 的更新公式，粒子的位置也是如此。另一個與神經(jīng)網(wǎng)絡訓練有關的應用是 Fukuyama 和 Yoshida 發(fā)表的論文。例如用訓練神經(jīng)網(wǎng)絡來評估電池充電的狀態(tài)；PSO 用來優(yōu)化用于促進微生物的生長的化學成分配方，找到的解比之前使用其它優(yōu)化算法發(fā)現(xiàn)的各種解有明顯的改進。Engelbrecht 和 Ismail 研究了不同優(yōu)化算法訓練乘法單元神經(jīng)網(wǎng)絡的能力，發(fā)現(xiàn)在乘法單元神經(jīng)網(wǎng)絡的訓練問題上，PSO 比其它隨機搜索算法還要好，如 GA 和 LeapFrog 算法。乘法單元神經(jīng)網(wǎng)絡是帶誤差函數(shù)的神經(jīng)網(wǎng)絡，很難訓練。PSO 算法也用來優(yōu)化帶權神經(jīng)網(wǎng)絡的連接結構。另一個神經(jīng)網(wǎng)絡訓練的例子中 Eberhart 和 Hu 用 PSO 訓練神經(jīng)網(wǎng)絡以正確區(qū)分病人的顫抖行為是普通顫動或是患有帕金森氏癥。Kennedy 和 Eberhart 的報告說明 PSO 成功用于正確區(qū)分 XOR 問題，包括 13 維搜索空間的函數(shù)優(yōu)化問題。如何利用有效的數(shù)學工具對算法的收斂性，收斂速度的估計，計算的復雜性，以及預防陷入局部最優(yōu)和參數(shù)設置影響等進行分析將是今后的研究熱點之一。因此，迄今已經(jīng)出現(xiàn)了很多對粒子群優(yōu)化算法的改進方法。目前，其研究現(xiàn)狀大致分為兩個方向：算法的改進，算法的應用。 粒子群優(yōu)化算法的國內(nèi)外研究現(xiàn)狀粒子群優(yōu)化算法概念簡單，實現(xiàn)容易，同時又有深刻的智能背景，既適合科學研究，又特別適合工程應用。由于對 TSP 及與之具有類似復雜性的一些其它最優(yōu)化問題現(xiàn)在還沒有有效的算法，人們把這類問題稱為“NP 完全問題” 。對于 N 個城市的 TSP，存在著 條可能的路徑。引入決策變量： （13）1, ij0ijijx?????若 旅 行 商 訪 問 城 市 后 訪 問 城 市， 否 則則 TSP 的目標函數(shù)為。其圖論描述為：給定圖 G=(V,A)，其中 V 為頂點集，A 為各頂點相互連接組成的弧集，已知各頂點間連接距離，要求確定一條長度最短的 Hamilton 回路，即遍歷所有頂點一次且僅一次的最短回路。從某種意義上講，組合優(yōu)化問題的研究是從它與連續(xù)優(yōu)化問題之間的分界線上入手的。在組合優(yōu)化問題里，是從一個無限集或者可數(shù)無限集里尋找一個對象，典型的是一個整數(shù)，一個集合，一個排列或一個圖。在這種前提下，種群很快就達到了收斂狀態(tài)，從而能在較少的代數(shù)內(nèi)找到最優(yōu)解。粒子群優(yōu)化算法并沒有能給出嚴格的數(shù)學證明，但在實際應用中被證明是有效的。由此可見idPgdPPSO 的基本思想就是每個個體充分利用群體與自身的智能,不斷地調(diào)整學習,最終得到滿意解。 39。 12())())idi idi gdiVcranPXcranPX??????1）式中 表示第 i 個粒子在第 d 維上的速度； 為慣性權重，控制粒子的每一代idv ?速度更新有多少以前的速度保留下來； 和 為調(diào)節(jié) 和 相對重要性的參數(shù)；1c2idg為隨機數(shù)生成函數(shù)。另外也可以不用整個種群而只是用其中一部分作為粒子的鄰居，那么在所有鄰居中的極值就是局部極值。第一個極值就是粒子本身所找到的最優(yōu)解，這個解被稱為個體極值。粒子群優(yōu)化算法初始化為一群隨機粒子(隨機解)，然后通過迭代找到最優(yōu)解。在粒子群優(yōu)化算法中，每個優(yōu)化問題的潛在解都是搜索空間中的一只“鳥” ，稱之為“粒子” 。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前距離食物最近的鳥的周圍區(qū)域。設想這樣一個場景：一群鳥在隨機搜尋食物。粒子群優(yōu)化算法(PSO)也是起源于對簡單社會系統(tǒng)的模擬，最初設想是模擬鳥群覓食的過程，但后來發(fā)現(xiàn) PSO 是一種很好的優(yōu)化工具。蟻群算法已經(jīng)成功運用在很多離散優(yōu)化問題上。在群智能領域主要有兩種基本群智能的算法，蟻群算法(Ant Colony Optimization)和粒子群優(yōu)化算法(Particle Swarm Optimization)。(3)個體可改變環(huán)境(個體間通過改變環(huán)境，感知環(huán)境變化來彼此間接通訊的方式被稱為“Stigmergy”)。群智能的特點是：(1)控制是分布的，不存在中心控制。雖然這些交互行為非常簡單，但是他們聚在一起卻能解決一些難題。顯然，在所有個體活動的完美集成過程中不需要任何的指導。昆蟲群體行為的奇妙之處在于：昆蟲的個體都很簡單，但當它們一起協(xié)同工作時卻能表現(xiàn)出很復雜的行為，如蜜蜂能夠建造完美的蜂窩，螞蟻覓食能夠找到最短的路徑，簡單的昆蟲可建造復雜形狀的巢穴等。這些模擬系統(tǒng)利用局部信息從而產(chǎn)生不可預測的群體行為。在這里，自治體是指在一個環(huán)境中具備自身活動能力的一個實體，其自身力求簡單，通常不必具有高級智能，但是，他們的集群的活動所表現(xiàn)出來的則是一種高級智能才能達到的活動，我們稱這種活動為群智能(Swarm Intelligence)。由于進化算法是對自然進化的一個粗糙簡化，其完整的數(shù)學基礎有待深入研究，假以時日，隨著不斷地完善，其應用會更加廣泛。如進化算法用來發(fā)現(xiàn)細胞自動機規(guī)則來完成一定的任務，基于遺傳信息處理模型的人工生命的合成等。進化算法只需利用目標的取值信息而不需要梯度、連續(xù)性、凸性等信息，因而適用于大規(guī)模、高度非線性的不連續(xù)、多峰函數(shù)的優(yōu)化以及無解析表達式的目標函數(shù)優(yōu)化，具有很強的通用性；算法的操作對象是一組個體，而且非單個個體，具有多條搜索軌跡，因而具有隱并行性。進化算法通過模擬“優(yōu)勝劣汰，適者生存”的規(guī)律，通過模擬孟德爾的遺傳變異理論在迭代過程中保持已有的結構，同時尋找更好的結構。該算法的核心思想是：生物進化過程(從簡單到復雜，從低級到高級)本身是一個自然的，并行發(fā)生的，穩(wěn)健的優(yōu)化過程，其目的就是要適應環(huán)境。進化算法是借鑒生物自然選擇和遺傳機制的隨機搜索算法。飛機、輪船、雷達、計算機的問世，都是人類模擬自然的極好例證。生命不斷地繁衍生息，產(chǎn)生出具有思維和智能的高級生命體。目前，PSO 已經(jīng)成為一個研究熱點，被廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模糊系統(tǒng)控制和決策支持等領域。由于 PSO 算法概念簡單，實現(xiàn)容易，同時又有深刻的智能背景，既適合科學研究，又特別適合工程應用。PSO 的概念起源于對鳥群覓食的行為研究，最先是一個用來圖形化仿真鳥群飛行(Flocking)的算法，可模擬出鳥群尋找谷場(Cornfield)的過程。目前共同進化算法己經(jīng)成為進化算法的一個研究熱點，相關的理論研究以及應用研究已經(jīng)全面展開。共同進化算法正是體現(xiàn)了以上思想，它不僅是對達爾文的“適者生存、優(yōu)勝劣汰”自然規(guī)律的模擬，同時也體現(xiàn)了自然界中多個物種通過相互合作而共同進化的自然規(guī)律。因此從實質(zhì)上來說，進化算法是一類具有自適應調(diào)節(jié)功能的搜索尋優(yōu)技術，目前己經(jīng)被廣泛地應用到組合優(yōu)化問題、機器學習、人工生命、自動控制以及動態(tài)系統(tǒng)的故障診斷等領域中。雖然這幾種方法在實現(xiàn)手段上各有特點、互不相同，但它們所遵循的進化原則是一致的。20 世紀 60 年代以來，生物學中的進化論被廣泛地應用于工程技術、人工智能等領域中，形成了一類新的搜索算法進化算法。許多工程優(yōu)化問題性質(zhì)十分復雜，常常需要在復雜而龐大的搜索空間中尋找最優(yōu)解或者準最優(yōu)解。隨著生產(chǎn)、經(jīng)濟、技術的發(fā)展，工程技術、管理人才在實際工作中常常會面臨工程設計中這樣的一類問題：怎樣選取參數(shù)使得設計既滿足要求又能降低成本；在資源分配中，怎樣的分配方案既能滿足各方面的基本要求，又能獲得好的經(jīng)濟效益；在生產(chǎn)計劃安排中，選擇怎樣的計劃方案才能提高產(chǎn)值和利潤；在原料配比問題中，怎樣確定各種成分的比例才能提高質(zhì)量、降低成本；在城建規(guī)劃中，怎樣安排工廠、機關、學校、商店、醫(yī)院、住宅和其他單位的合理布局，才能方便群眾，有利于城市各行各業(yè)的發(fā)展。自 20 世紀 40 年代以來，由于生產(chǎn)和科學研究突飛猛進地發(fā)展，最優(yōu)化理論和方法日益受到人們的重視，特別是計算機日益廣泛應用，使最優(yōu)化問題的研究不僅成為一種迫切的需要，而且有了求解的有力工具，因此最優(yōu)化理論和算法迅速發(fā)展起來，形成了一門新的應用數(shù)學分支學科，已經(jīng)滲透到生產(chǎn)、管理、商業(yè)、軍事、決策等各領域。早在 17 世紀，英國偉大科學家 Newton 開創(chuàng)了微積分時代，已經(jīng)提出極值問題；后來出現(xiàn) Lagrangian 乘數(shù)法，1847 年法國數(shù)學家 Cancky 研究了函數(shù)沿什么方向下降最快的問題；1949 年前蘇聯(lián)數(shù)學家 KaHTOPOBNq 提出解決下料問題和運輸問題這兩種線性規(guī)劃問題的求解方法。追求最優(yōu)目標一直是人類的理想，長期以來，人們對最優(yōu)化問題進行不斷的探討和研究。國內(nèi)外的應用實踐表明，在同樣條件下，優(yōu)化方法對系統(tǒng)效率的提高、能耗的降低、資源的合理利用及經(jīng)濟效益的提高等均有顯著的效果，而且隨著處理對象規(guī)模的增大，這種效果也更加顯著。在國民經(jīng)濟各部門和科學技術的各個領域中普遍存在著優(yōu)化問題，最優(yōu)化方法廣泛應用十工業(yè)、農(nóng)業(yè)、國防、工程、交通、金融、化工、能源、通信等許多領域，如在資源利用、結構設計、調(diào)度管理、后勤供應等許多領域中產(chǎn)生了巨大的經(jīng)濟效益和社會效益。最后，本文將改進的粒子群算法在 burma14 和 oliver30 這兩個 TSP 實例中進行了仿真，得到了較為滿意的結果。本文首先分析了粒子群優(yōu)化算法的原理，應用粒子群優(yōu)化算法的步驟，以及算法中經(jīng)驗參數(shù)的設置，總結了目前 PSO 算法研究的成果，對比分析了目前