【文章內容簡介】 最短回路。設 為城市 i 與ijdj 之間的距離，即弧(i,j)的長度。引入決策變量： （13）1, ij0ijijx?????若 旅 行 商 訪 問 城 市 后 訪 問 城 市， 否 則則 TSP 的目標函數為。 （14）nijij1MiZd??，TSP 的描述非常簡單，但求解最優(yōu)化解是很困難的。對于 N 個城市的 TSP，存在著 條可能的路徑。隨著城市數目 N 的增長，可能路徑的數目以 N 的指數(1)!/2n?倍增加，如果使用窮舉法搜索，需要考慮所有的可能情況，并兩兩比較，找出最優(yōu)解，那么可搜索的路徑及其距離之和的計算量將正比于 ,算法的復雜度呈指數(!)/2增長，產生所謂的“組合爆炸” ，這即使是當今世界上運算最快的計算機也感到無能為力。由于對 TSP 及與之具有類似復雜性的一些其它最優(yōu)化問題現在還沒有有效的算法，人們把這類問題稱為“NP 完全問題” 。因為所有的 NP 完全問題在數學上都等價于 TSP，因此研究 TSP 具有很重要的意義。 粒子群優(yōu)化算法的國內外研究現狀粒子群優(yōu)化算法概念簡單，實現容易，同時又有深刻的智能背景，既適合科學研究，又特別適合工程應用。算法一提出就吸引了廣泛的注意，不斷涌現了各種關于 PSO 算法應用研究的成果，有力推動了 PSO 研究。目前，其研究現狀大致分為兩個方向：算法的改進，算法的應用。由于粒子群算法提出的時間不長，算法缺乏深刻的的理論分析，數學基礎相對薄弱，且存在許多不完善和未涉及到的問題。因此，迄今已經出現了很多對粒子群優(yōu)化算法的改進方法。例如：混合 PSO(HPSO)算法、雜交 PSO 算法、協同 PSO 算法、基于模擬退火的 PSO 算法、自適應變異的 PSO 算法、離散 PS0、自適應PSO、耗散的 PSO，GAPSO 等多種粒子群優(yōu)化算法。如何利用有效的數學工具對算法的收斂性，收斂速度的估計，計算的復雜性，以及預防陷入局部最優(yōu)和參數設置影響等進行分析將是今后的研究熱點之一。由于 PSO 算法概念簡單，易于實現，因而在短期內得到很大發(fā)展，迅速得到了國際演化計算研究領域的認可，并在很多領域得到應用：PSO 的第一個應用是神經網絡訓練。Kennedy 和 Eberhart 的報告說明 PSO 成功用于正確區(qū)分 XOR 問題，包括 13 維搜索空間的函數優(yōu)化問題。Salerno 也應用 PSO到訓練神經網絡學習 XOR 問題，比梯度遞減算法更好。另一個神經網絡訓練的例子中 Eberhart 和 Hu 用 PSO 訓練神經網絡以正確區(qū)分病人的顫抖行為是普通顫動或是患有帕金森氏癥。他們在 PSO 算法中使慣性權值在 2022 代中從 到 線性遞減，獲得很好的效果。PSO 算法也用來優(yōu)化帶權神經網絡的連接結構。Zhang 和 Shao 的 PSONN 算法使用 PSO 算法優(yōu)化神經網絡，成功地用來評估噴氣機燃料的質量。乘法單元神經網絡是帶誤差函數的神經網絡，很難訓練。多種基于梯度的優(yōu)化算法在搜索空間陷入多個局部最小值。Engelbrecht 和 Ismail 研究了不同優(yōu)化算法訓練乘法單元神經網絡的能力，發(fā)現在乘法單元神經網絡的訓練問題上，PSO 比其它隨機搜索算法還要好，如 GA 和 LeapFrog 算法。Eberhart 等人在文獻 [7]描述了 PSO 的一些其他應用。例如用訓練神經網絡來評估電池充電的狀態(tài)；PSO 用來優(yōu)化用于促進微生物的生長的化學成分配方，找到的解比之前使用其它優(yōu)化算法發(fā)現的各種解有明顯的改進。PSO 的優(yōu)勢之一是能更加有效地對搜索空間內的大范圍區(qū)域進行搜索，這使得 PSO 能夠在搜索空間里發(fā)現更好的解，并且該解明顯區(qū)別于使用其它已知算法發(fā)現的解。另一個與神經網絡訓練有關的應用是 Fukuyama 和 Yoshida 發(fā)表的論文。他們表明 PSO 優(yōu)化連續(xù)和離散變量都非常有效。在速度更新前，通過簡單離散值來調整PSO 的更新公式，粒子的位置也是如此。只要適當調整，這些離散變量與連續(xù)變量可以自由組合，應用到更新公式。他們使用的是慣性權值線性遞減的 PSO，結果表明比原來使用的 RTS 算法效率更高。Fukuyama 等人把 Angeline 的混合 PSO 運用到相同問題，似乎混合 PSO 算法更有效。進一步的研究還發(fā)現相同參數設置的 PSO應用在不同電力系統問題上獲得了高質量的解。標準粒子群算法主要適用于連續(xù)空間函數的優(yōu)化問題，如何將算法應用于離散空間的優(yōu)化問題，特別是非數值優(yōu)化問題，將是粒子群算法的一個重要研究方向。此外，充分利用其他進化算法以改善微粒群算法存在的不足，也是值得研究的問題?？傊琍SO 算法的應用十分廣泛，有著比較好的發(fā)展前景。目前 PSO 的研究尚處于初期，還有許多問題值得做進一步的研究。PSO 算法的理論研究還很缺乏，目前還沒有粒子群理論的數學證明。由于實際問題的多樣性和復雜性，盡管目前已經有了多種不同版本的 PSO改進算法但這些 PSO 算法不具有通用性，或者參數的設置要求使用者具備較高的經驗，否則難以達到理想的效果。開拓 PSO 算法的新的應用領域是一項很有意義的工作。如何將 PSO 應用于組合優(yōu)化問題也是一個重要的研究方向。 粒子群優(yōu)化算法的研究意義粒子群算法自 1995 年被提出之后，得到了數值優(yōu)化領域的廣泛關注，吸引了大量的研究者。如何加快算法的收斂速度和避免早熟收斂問題，一直是大多數研究者關注的重點，也是所有隨機搜索算法共同面臨的兩個主要難題。這兩個問題之間本身就存在很復雜的關系，在很多情況下是互相沖突的兩個目標。在避免早熟收斂方面，現有的大量研究涉及如何讓算法跳出局部最優(yōu)點。在加快收斂速度方面，主要的工作集中在如何選擇最優(yōu)的算法參數，以及從其他智能優(yōu)化算法中借鑒一些思想對 PSO 算法的主要框架加以修改。粒子群優(yōu)化技術的應用領域己擴展到組合優(yōu)化、數據分類、數據聚類、模式識別、電信 Qos 管理、生物系統建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統辯識等方面。由此可見，作為一類現代啟發(fā)式優(yōu)化算法，粒子群優(yōu)化算法理論及其應用研究都具有相當重要的學術意義和現實價值。第 2 章 粒子群優(yōu)化算法 粒子群算法(PSO)是 1995 由 Kennedy 和 Eberhart[12]首先提出的一類基于群智能的演化計算方法。PSO 源于對鳥群覓食行為的研究，研究者發(fā)現鳥群在飛行過程中經常會突然改變方向、散開、聚集，其行為不可預測，但其整體總保持一致性，個體與個體間也保持著適宜的距離。通過對類似生物群體的行為的研究，發(fā)現在生物群體中存在著個體與個體、個體與群體間的相互作用、相互影響的行為，這種行為體現的是一種存在于生物群體中的信息共享的機制。它為群體的進化提供了一種優(yōu)勢，這也是 PSO 形成的基礎。PSO 就是對這種社會行為的模擬，即利用信息共享機制，使得個體間可以相互借鑒經驗，從而促進整個群體的發(fā)展。PSO 和遺傳算法(Geic Algorithm,GA)類似，也是一種基于迭代的優(yōu)化工具，系統初始化為一組隨機解，通過某種方式迭代尋找最優(yōu)解。但 PSO 沒有 GA 的“選擇” 、 “交叉” 、 “變異”算子，編碼方式也較 GA 簡單。由于 PSO 算法容易理解、易于實現，所以 PSO 算法發(fā)展很快。在函數優(yōu)化 [14]、神經網絡訓練 [15]、系統控制 [10]等領域得到廣泛應用。目前粒子群算法研究已被“國際進化計算會議”(IEEE International Conferences on EvolutionaryComputation,CEC)列為一個討論的專題。 粒子群算法的原理 粒子群優(yōu)化算法的基本概念源于對鳥群覓食行為的研究。設想這樣一個場景：一群鳥在隨機搜尋食物。在這個區(qū)域里只有一塊食物。所有的鳥都不知道食物在哪里。但是他們知道當前的位置離食物還有多遠。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。PSO 從這種模型中得到啟示并用于解決優(yōu)化問題。作為一種演化算法，粒子群優(yōu)化算法兼有進化計算和群智能的特點。起初Kennedy 和 Eberhart 只是設想模擬鳥群覓食的過程，但后來的研究中發(fā)現 PSO 是一種很好的優(yōu)化工具。與其他進化算法相似，PSO 算法也采取“群體”與“進化”的概念，依據個體間的協作與競爭通過對個體適應度進行評價，實現復雜空間中最優(yōu)解的搜索。所不同的是 PSO 是將每個個體看作是在 N 維搜索空間中的沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經驗和群體的飛行經驗進行動態(tài)的調整。PSO 首先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都為優(yōu)化問題的一個可行解，并由目標函數為之確定一個適應值。每個粒子將在解空間中運動，并由一個速度決定其方向和距離。通常粒子將追隨當前的最優(yōu)粒子而運動，并經逐代搜索最后得到最優(yōu)解。在每一代中，粒子將跟蹤兩個極值，一個為粒子本身迄今找到的最優(yōu)解 ，另一個為全種群迄今找到的最優(yōu)解 。每個粒子bestP bestg都通過上述兩個極值不斷更新自己，從而產生新一代群體。假設在一個 D 維的目標搜索空間中，有 m 個粒子組成一個群落，其中第 i 個粒子表示為一個 D 維的向量 ，i=1，2，…，m，即第 i 個粒子在 D12(,.,)iiidX?維的搜索空間中的位置。將 代入一個目標函數就可以計算出其適應值，根據其適應度值的大小衡量優(yōu)劣。第 i 個粒子的“飛行”速度也是一個 D 維的向量，記為。第 i 個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為 ，12(,.)iiidY? bestP整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 。bestg因為 是整個粒子群的最優(yōu)位置，因此上述 PSO 算法也稱為全局版 PSO。也bestg可以把第 i 個粒子的鄰居們搜索到的最優(yōu)位置作為 ，則上述方法又稱為局部版estPSO。全局版 PSO 收斂速度快，但有時會陷入局部最優(yōu)。局部版 PSO 收斂速度慢一點，但相對的不易陷入局部最優(yōu)。在找到這兩個最優(yōu)值時，粒子根據如下的公式來更新自己的速度和新的位置： （239。 12())())idi idi gdiVcranPXcranPX??????1） （239。 39。idiidV2）式中 表示第 i 個粒子在第 d 維上的速度； 為慣性權重，控制粒子的每一代速度idv ?更新有多少以前的速度保留下來； 和 為調節(jié) 和 相對重要性的參數，根據1c2idPg經驗通常取 ； 為隨機數生成函數，生成介于(0,1)之間的隨機數；。12c?()ran圖 21 粒子位置的改進圖 21 表示了 PSO 中粒子位置改進，其中：：目前搜索到的點tX：改進后的搜索點1tX?：當前速度V：改進后的速度1t：基于個體極值的速度pbes：基于全局極值的速度t以下是粒子群優(yōu)化算法程序的偽代碼：For each particle Do{Initialize particle} %初始化粒子群 While maximum iterations or minimum criteria is not attained %滿足循環(huán)條件Do{For each particle{Calculate fitness value %計算適應值If the fitness value is better than the best fitness value(pBest)in history Set current value as the new pBest %若當前值好于 pBest，當前值賦給 pBest}Choose the particle with the best fitness value of all the particles as the gBest%選擇最好的 pBest 做為群體最優(yōu) gBestFor each particle{Calculate particle velocity according equation(21)Update particle position according equation(22) }%根據公式 21，22 更新每個粒子位置和速度} 粒子群優(yōu)化算法和遺傳算法(GA)的比較大多數群智能算法都使用同樣的過程：（1） 種群隨機初始化；（2） 對種群內的每一個個體，計算其適應度值；（3） 種群根據適應度值進行復制。（4） 如果終止條件滿足的話，就停止，否則轉步驟（2）從 PSO 基本步驟可以看到 PSO 和 GA 有很多共同之處，結合我們的理解，可以歸納如下。兩者相同點：它們都屬全局優(yōu)化方法。在解空間都隨機產生初始種群，因而算法在全局的解空間進行搜索，并且將搜索重點集中在性能高的部分；PSO 中認知項和社會項前都加有隨機數，GA 的遺傳操作均屬隨機操作。隱含并行性。搜索過程是從問題解的一個集合開始的，而不是從單個個體開始，具有隱含并行搜索特性，從而減小了陷入局部極小的可能性。并且由于這種并行性，易在并行計算機上實現，以提高算法性能和效率。根據個體的適應度信息進行搜索，因此不受函數約束條件的限制，如連續(xù)性、可導性等。對高維、復雜問題，往往會遇到早熟收斂和收斂性能差的缺點，都無法保證收斂到最優(yōu)點。粒子群算法隱含著一定“形式”的選擇機制。粒子群算法和其它群智能算法一樣均使用“群體”概念，用于表示一組解空間中的個體的集合。如果將粒子經歷的最好位置看作是粒子群的組成部分，則粒子群的每一步進化都呈現出弱化形式的“選擇”機制。兩者不同點：PSO