【文章內(nèi)容簡介】 素質(zhì)”的提高，比如解群體隨進化代數(shù)的變化過程中存在“掉隊”個體的“歸隊”現(xiàn)象，使得每代種群中的解具有“自我”學(xué)習(xí)和向“他人”學(xué)習(xí)提高的雙重優(yōu)點，因此其下代解具有針對性的從“先輩”那里繼承的更多的信息。在這種前提下，種群很快就達到了收斂狀態(tài)，從而能在較少的代數(shù)內(nèi)找到最優(yōu)解。 旅行商問題 最優(yōu)化問題自然而然的被分 為兩類：一類是連續(xù)變量的問題，另一類是離散變量的問題，對于后者，我們稱它為組合優(yōu)化。在組合優(yōu)化問題里，是從一個無限集或者可數(shù)無限集里尋找一個對象，典型的是一個整數(shù)，一個集合，一個排列或一個圖。這與連續(xù)變量問題求一組實數(shù)或一個函數(shù)有著很大不同，因而求解它們的方法也很大相同。從某種意義上講，組合優(yōu)化問題的研究是從它與連續(xù)優(yōu)化問題之間的分界線上入手的。 旅行商問題 (Traveling Salesman ProblemTSP)是運籌學(xué)、圖論和組合優(yōu)化中的 NP難題，旅行商問題描述如下：給定 n 個城市及兩兩城市之間的距 離，求一條經(jīng)過各城市一次且僅一次的最短路線。其圖論描述為：給定圖 G=(V,A)，其中 V 為頂點集， A為各頂點相互連接組成的弧集，已知各頂點間連接距離，要求確定一條長度最短的Hamilton 回路，即遍歷所有頂點一次且僅一次的最短回路。設(shè) ijd 為城市 i 與 j 之間的距離，即弧 (i,j)的長度。引入決策變量： 1 , i j0 ijij xx???? ???若 旅 行 商 訪 問 城 市 后 訪 問 城 市， 否 則 （ 13） 則 TSP 的目標(biāo)函數(shù)為 nij iji j 1M in Z dx?? ?。 （ 14） TSP 的描述非常簡單，但求解最優(yōu)化解是很困難的。對于 N 個城市的 TSP，存在著 ( 1)!/2n? 條可能的路徑。隨著城市數(shù)目 N 的增長，可能路徑的數(shù)目以 N 的指數(shù)倍增加，如果使用窮舉法搜索，需要考慮所有的可能情況，并兩兩比較，找出最優(yōu)解，那么可搜索的路徑及其距離之和的計算量將正比于 ( !)/2N ,算法的復(fù)雜度呈指數(shù)增長，產(chǎn)生所謂的“組合爆 炸”，這即使是當(dāng)今世界上運算最快的計算機也感到無能為力。由于對 TSP 及與之具有類似復(fù)雜性的一些其它最優(yōu)化問題現(xiàn)在還沒有有效的算法，人們把這類問題稱為“ NP 完全問題”。因為所有的 NP 完全問題在數(shù)學(xué)上都等價于 TSP，因此研究 TSP 具有很重要的意義。 粒子群 優(yōu)化 算法的國內(nèi)外研究現(xiàn)狀 粒子群優(yōu)化算法概念簡單，實現(xiàn)容易，同時又有深刻的智能背景，既適合科學(xué)研究，又特別適合工程應(yīng)用。算法一提出就吸引了廣泛的注意，不斷涌現(xiàn)了各種關(guān)于PSO 算法應(yīng)用研究的成果，有力推動了 PSO 研究。目前，其研究現(xiàn)狀大致分為兩個方向：算 法的改進，算法的應(yīng)用。 由于粒子群算法提出的時間不長，算法缺乏深刻的的理論分析，數(shù)學(xué)基礎(chǔ)相對薄弱，且存在許多不完善和未涉及到的問題。因此，迄今已經(jīng)出現(xiàn)了很多對粒子群優(yōu)化算法的改進方法。例如：混合 PSO(HPSO)算法、雜交 PSO 算法、協(xié)同 PSO 算法、基于模擬退火的 PSO 算法、自適應(yīng)變異的 PSO 算法、離散 PS0、自適應(yīng) PSO、耗散的PSO， GAPSO 等多種粒子群優(yōu)化算法。如何利用有效的數(shù)學(xué)工具對算法的收斂性，收斂速度的估計，計算的復(fù)雜性，以及預(yù)防陷入局部最優(yōu)和參數(shù)設(shè)置影響等進行分析將是今后的研究熱點之一。 由于 PSO 算法概念簡單，易于實現(xiàn)，因而在短期內(nèi)得到很大發(fā)展，迅速得到了國際演化計算研究領(lǐng)域的認(rèn)可，并在很多領(lǐng)域得到應(yīng)用： PSO 的第一個應(yīng)用是神經(jīng)網(wǎng)絡(luò)訓(xùn)練。 Kennedy 和 Eberhart 的報告說明 PSO 成功用于正確區(qū)分 XOR 問題，包括 13 維搜索空間的函數(shù)優(yōu)化問題。 Salerno 也應(yīng)用 PSO到訓(xùn)練神經(jīng)網(wǎng)絡(luò)學(xué)習(xí) XOR 問題，比梯度遞減算法更好。另一個神經(jīng)網(wǎng)絡(luò)訓(xùn)練的例子中 Eberhart 和 Hu 用 PSO 訓(xùn)練神經(jīng)網(wǎng)絡(luò)以正確區(qū)分病人的顫抖行為是普通顫動或是患有帕金森氏癥。他們在 PSO 算法中使慣性權(quán)值在 2020 代中從 到 線性遞減，獲得很好的效果。 PSO 算法也用來優(yōu)化帶權(quán)神經(jīng)網(wǎng)絡(luò)的連接結(jié)構(gòu)。 Zhang 和 Shao 的 PSONN 算法使用 PSO 算法優(yōu)化神經(jīng)網(wǎng)絡(luò)，成功地用來評估噴氣機燃料的質(zhì)量。乘法單元神經(jīng)網(wǎng)絡(luò)是帶誤差函數(shù)的神經(jīng)網(wǎng)絡(luò)，很難訓(xùn)練。多種基于梯度的優(yōu)化算法在搜索空間陷入多個局部最小值。 Engelbrecht 和 Ismail 研究了不同優(yōu)化算法訓(xùn)練乘法單元神經(jīng)網(wǎng)絡(luò)的能力，發(fā)現(xiàn)在乘法單元神經(jīng)網(wǎng)絡(luò)的訓(xùn)練問題上， PSO 比其它隨機搜索算法還要好，如GA 和 LeapFrog 算法。 Eberhart 等人在文獻 [7]描述了 PSO 的一些 其他應(yīng)用。例如用訓(xùn)練神經(jīng)網(wǎng)絡(luò)來評估電池充電的狀態(tài)； PSO 用來優(yōu)化用于促進微生物的生長的化學(xué)成分配方，找到的解比之前使用其它優(yōu)化算法發(fā)現(xiàn)的各種解有明顯的改進。 PSO 的優(yōu)勢之一是能更加有效地對搜索空間內(nèi)的大范圍區(qū)域進行搜索，這使得 PSO 能夠在搜索空間里發(fā)現(xiàn)更好的解，并且該解明顯區(qū)別于使用其它已知算法發(fā)現(xiàn)的解。 另一個與神經(jīng)網(wǎng)絡(luò)訓(xùn)練 有 關(guān)的應(yīng)用是 Fukuyama 和 Yoshida 發(fā)表的論文。他們表明 PSO 優(yōu)化連續(xù)和離散變量都非常有效。在速度更新前，通過簡單離散值來調(diào)整 PSO的更新公式，粒子的位置也是如此。只要適當(dāng)調(diào)整 ，這些離散變量與連續(xù)變量可以自由組合，應(yīng)用到更新公式。他們使用的是慣性權(quán)值線性遞減的 PSO，結(jié)果表明比原來使用的 RTS 算法效率更高。 Fukuyama 等人把 Angeline 的混合 PSO 運用到相同問題，似乎混合 PSO 算法更有效。進一步的研究還發(fā)現(xiàn)相同參數(shù)設(shè)置的 PSO 應(yīng)用在不同電力系統(tǒng)問題上獲得了高質(zhì)量的解。 標(biāo)準(zhǔn)粒子群算法主要適用于連續(xù)空間函數(shù)的優(yōu)化問題，如何將算法應(yīng)用于離散空 間的優(yōu)化問題，特別是非數(shù)值優(yōu)化問題，將是粒子群算法的一個重要研究方向。此外，充分利用其他進化算法以改善微粒群算法存在的不足，也是值得研究 的問題。 總之， PSO 算法的應(yīng)用十分廣泛，有著比較好的發(fā)展前景。目前 PSO 的研究尚處于初期，還有許多問題值得做進一步的研究。 PSO 算法的理論研究還很缺乏，目前還沒有粒子群理論的數(shù)學(xué)證明。 由于實際問題的多樣性和復(fù)雜性，盡管目前已經(jīng)有了多種不同版本的 PSO 改進算法但這些 PSO 算法不具有通用性，或者參數(shù)的設(shè)置要求使用者具備較高的經(jīng)驗，否則難以達到理想的效果。 開拓 PSO 算法的新的應(yīng)用領(lǐng)域是一項很有意義的工作。 如何將 PSO 應(yīng)用于組合優(yōu)化問題也是一個重要的研究方向。 粒子群 優(yōu)化 算法的研究 意義 粒子群算法自 1995 年被提出之后，得到了數(shù)值優(yōu)化領(lǐng)域的廣泛關(guān)注，吸引了大量的研究者。如何加快算法的收斂速度和避免早熟收斂問題，一直是大多數(shù)研究者關(guān)注的重點，也是所有隨機搜索算法共同面臨的兩個主要難題。這兩個問題之間本身就存在很復(fù)雜的關(guān)系，在很多情況下是互相沖突的兩個目標(biāo)。在避免早熟收斂方面，現(xiàn)有的大量研究涉及如何讓算法跳出局部最優(yōu)點。在加快收斂速度方面，主要的工作集中在如何選擇最優(yōu)的算法參數(shù)，以及從其他智能優(yōu)化算法中借鑒一些思想對 PSO 算法的主要框架加以修改。 粒子群優(yōu)化技術(shù)的應(yīng)用領(lǐng)域己擴展到組合優(yōu)化 、數(shù)據(jù)分類、數(shù)據(jù)聚類、模式識別、電信 Qos 管理、生物系統(tǒng)建模、流程規(guī)劃、信號處理、機器人控制、決策支持以及仿真和系統(tǒng)辯識等方面。 由此可見，作為一類現(xiàn)代啟發(fā)式優(yōu)化算法，粒子群優(yōu)化算法理論及其應(yīng)用研究都具有相當(dāng)重要的學(xué)術(shù)意義和現(xiàn)實價值。 第 2章 粒子群優(yōu)化算法 粒子群算法 (PSO)是 1995 由 Kennedy 和 Eberhart[12]首先提出的一類基于群智能的演化計算方法。 PSO 源于對鳥群覓食行為的研究，研究者發(fā)現(xiàn)鳥群在飛行過程中經(jīng)常會突然改變方向、散開、聚集，其行為不可預(yù)測，但其整體總保持一致性， 個體與個體間也保持著適宜的距離。通過對類似生物群體的行為的研究，發(fā)現(xiàn)在生物群體中存在著個體與個體、個體與群體間的相互作用、相互影響的行為，這種行為體現(xiàn)的是一種存在于生物群體中的信息共享的機制。它為群體的進化提供了一種優(yōu)勢，這也是PSO 形成的基礎(chǔ)。 PSO 就是對這種社會行為的模擬，即利用信息共享機制，使得個體間可以相互借鑒經(jīng)驗，從而促進整個群體的發(fā)展。 PSO 和遺傳算法 (Geic Algorithm,GA)類似，也是一種基于迭代的優(yōu)化工具，系統(tǒng)初始化為一組隨機解，通過某種方式迭代尋找最優(yōu)解。但 PSO 沒有 GA 的“選擇”、“交叉”、“變異”算子，編碼方式也較 GA 簡單。由于 PSO 算法容易理解、易于實現(xiàn)，所以 PSO 算法發(fā)展很快。在 函數(shù)優(yōu)化 [14]、神經(jīng)網(wǎng)絡(luò)訓(xùn)練 [15]、系統(tǒng)控制 [10]等領(lǐng)域得到廣泛應(yīng)用。目前粒子群算法研究已被“國際進化計算會議” (IEEE International Conferences on EvolutionaryComputation,CEC)列為一個討論的專題。 粒子群算法的原理 粒子群優(yōu)化算法的基本概念源于對鳥群覓食行為的研究。設(shè)想這樣一個場景：一群鳥在隨機搜尋食物。在 這個區(qū)域里只有一塊食物。所有的鳥都不知道食物在哪里。但是他們知道當(dāng)前的位置離食物還有多遠(yuǎn)。那么找到食物的最優(yōu)策略是什么呢？最簡單有效的就是搜尋目前離食物最近的鳥的周圍區(qū)域。 PSO 從這種模型中得到啟示并用于解決優(yōu)化問題。 作為一種演化算法，粒子群優(yōu)化算法兼有進化計算和群智能的特點。起初Kennedy 和 Eberhart 只是設(shè)想模擬鳥群覓食的過程，但后來的研究中發(fā)現(xiàn) PSO 是一種很好的優(yōu)化工具。與其他進化算法相似， PSO 算法也采取“群體”與“進化”的概念，依據(jù)個體間的協(xié)作與競爭通過對個體適應(yīng)度進行評價，實現(xiàn)復(fù)雜空間 中最優(yōu)解的搜索。所不同的是 PSO 是將每個個體看作是在 N 維搜索空間中的沒有重量和體積的微粒，并在搜索空間中以一定的速度飛行。該飛行速度由個體的飛行經(jīng)驗和群體的飛行經(jīng)驗進行動態(tài)的調(diào)整。 PSO 首先生成初始種群，即在可行解空間中隨機初始化一群粒子，每個粒子都為優(yōu)化問題的一個可行解，并由目標(biāo)函數(shù)為之確定一個適應(yīng)值。每個粒子將在解空間中 運動，并由一個速度決定其方向和距離。通常粒子將追隨當(dāng)前的最優(yōu)粒子而運動，并經(jīng)逐代搜索最后得到最優(yōu)解。在每一代中，粒子將跟蹤兩個極值，一個為粒子本身迄今找到的最優(yōu)解 bestP ，另一個為全種群迄今找到的最優(yōu)解 bestg 。每個粒子都通過上述兩個極值不斷更新自己，從而產(chǎn)生新一代群體。 假設(shè)在一個 D 維的目標(biāo)搜索空間中，有 m 個粒子組成一個群落，其中第 i 個粒子表示為一個 D 維的向量 12( , , ..., )i i i idX X X X? ， i=1， 2，?， m，即第 i 個粒子在 D 維的搜索空間中的位置。將 X 代入一個目標(biāo)函數(shù)就可以計算出其適應(yīng)值，根據(jù)其適應(yīng)度值的大小衡量優(yōu)劣。第 i 個粒子的“飛行”速度也是一個 D 維的向量，記為12( , ,..., )i i i idY Y Y Y? 。第 i 個粒子迄今為止搜索到的最優(yōu)位置稱為個體極值，記為 bestP ，整個粒子群迄今為止搜索到的最優(yōu)位置為全局極值，記為 bestg 。 因為 bestg 是整個粒子群的最優(yōu)位置，因此上述 PSO 算法也稱為全局版 PSO。也可以把第 i 個粒子的鄰居們搜索到的最優(yōu)位置作為 bestg ，則上述方法又稱為局部版PSO。全局版 PSO 收斂速度快，但有時會陷入局部最優(yōu)。局部版 PSO 收斂速度慢一點，但相對的不易陷入局部最優(yōu)。 在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式來更新自己的速度和新的位置： 39。 12( ) ( ) ( ) ( )id id id id g d idV V c ra n d P X c ra n d P X?? ? ? ? ? （ 21） 39。39。id id idX X V?? （ 22） 式中 idv 表示第 i 個粒子在第 d 維上的速度； ? 為慣性權(quán)重，控制粒子的每一代速度更新有多少以前的速度保留下來； 1c 和 2c 為調(diào)節(jié) idP 和 gdP 相對重要性的參數(shù)，根據(jù)經(jīng)驗通常取 122cc??； ()rand 為隨機數(shù)生成函數(shù)，生成介于 (0,1)之間的隨機數(shù)；。 圖 21 粒子位置的改進 圖 21 表示了 PSO 中粒子位置改進，其中： tX ： 目前搜索到的點 1tX? ：改進后的搜索點 tV ：當(dāng)前速度 1tV? ：改進后的速度 pbestV：基于個體 極值的速度 pbestV：基于全局極值的速度 以下是粒子群優(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 %計算適應(yīng)值 If the fitness