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