【文章內(nèi)容簡介】 Ni ,2,1 ?? 。 第 i 個粒子的“飛行”速度也是一個 D 維的向量，為 ), 21i iDii vvvV ?，（? ， 3,2,1 ??i 。 第 i 個粒子 目前 為止搜索到的最優(yōu)位置稱為個體極值，為 ),( 21 iDiibest pppp ?? ， Ni ,2,1 ?? 。 整個粒子群 目前 為止搜索到的最優(yōu)位置為全局極值，為 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 5 ),( 21 gDggb est pppg ?? 在找到這兩個最優(yōu)值時，粒子根據(jù)如下的公式 (1)和 (2)來更新自己的速度和位置 [12]： ? ? )(2211 idgdidididid xprcxprcvwv ?????? () ididid vxx ?? () 其中 ? 為慣性權(quán)重， 21,cc 為學(xué)習(xí)因子， 21,rr 為 0到 1之間均勻分布的隨機數(shù)。 粒子群算法的性能很大程度上取決于算法參數(shù)的選擇，選取較好的參數(shù)，不僅能縮短算法執(zhí)行的時間，而且可以提高解決問題的準確性。這其中決定算法性能的參數(shù)有：粒子數(shù)、慣性權(quán)重、學(xué)習(xí)因子、等，各個參數(shù)的選擇一般情況下可以參考如下： ? 粒子數(shù) ：粒子數(shù)的多少選擇一般是根據(jù)問題的復(fù)雜性決定的。對于一般優(yōu)化問題取 20到 40個粒子完全可以得到很好的結(jié)果。 ? 粒子的維度 ：這是由優(yōu)化問題決定，就是問題解的維度。 ? 學(xué)習(xí)因子 ：學(xué)習(xí)因子使粒子具有自我總結(jié)和向群體中優(yōu)秀個體的學(xué)習(xí)能力，一般取值范圍為 0到 4。 ? 慣性權(quán)重 ：決定了粒子對當前速度繼承多少，合適的選擇可以使粒子具有均衡的探索能力和開發(fā)能力。慣性權(quán)重越大粒子的全局搜索能力越強，反之慣性權(quán)重越小粒子的局部搜索能力越強。 算法的流程和流程圖 算法的流程如下： 步驟 1： 初始化粒子群，包括群體規(guī)模 N ，每個粒子的位置 ix 和速度 iV ； 步驟 2： 計算每個粒子的適應(yīng)度值 ，并將當前微粒的位置和適應(yīng)值存儲在 pbest中，將所有粒子的 pbest中適應(yīng)值最好的個體存儲在 gbest中； 步驟 3： 根據(jù)公式 (),()更新粒子的速度 iv 和位置 ix ； 步驟 4： 每個粒子，用它的適應(yīng)度值 ][iFit 和個體極值 ）（ ipbest 比較 出較優(yōu)為新）（ ibestp ； 步驟 5： 所有粒子的新的 pbest選出最優(yōu)的，為新的 gbest； 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 6 步驟 6： 如果滿足結(jié)束條件 (通常為預(yù)設(shè)的計算精度 或到達最大循環(huán)次數(shù) )退出，否則返回 步驟 3。 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 7 算法的流程 圖 如下： 否 是 開始 初始化每個粒子的速度和位置 根據(jù)方程 ()對粒子的位置進行進化 計算每個粒子的適應(yīng)值 求出每個粒子的個體最優(yōu) 求出整個群體的全局最優(yōu)值 根據(jù)方程 ()對粒子的速度進行進化 是否滿足條件 輸出結(jié)果 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 8 總結(jié)：對于這種連續(xù)性的問題 ,用粒子群算法求解 ,只要隨著粒子數(shù)和迭代步數(shù)的增加 ,求解的結(jié)果會不斷趨近最優(yōu)解。 算法的優(yōu)缺點分析 粒子群算法的優(yōu)點： 粒子群優(yōu)化算法 (PSO)是模擬鳥群覓食過程中的行為提出的一種基于群體智能的演化計算方法。該算法易于描述，在求解過程中只有非常少的參數(shù)需要調(diào)整并且無集中控制約束，不會因個體的故障影響整個問題的求解，確保了系統(tǒng)具備很強的魯棒性，相比其它演化算法，只需要較少的函數(shù)計算次數(shù)就可達到收斂，因此能以較大概率找到問題的全局最優(yōu)解。最后該算法最大 的優(yōu)勢也 在于編程簡單，易實現(xiàn)。 粒子群算法的缺點：在求解全局最優(yōu)解的過程中對于有多個局部極值點的函數(shù)，容易陷入到局部極值點中，得不到正確的結(jié)果。此外，由于粒子群算法問世時間不長在搜索糾結(jié)過程中缺乏精密搜索方法的配合，導(dǎo)致使用粒子群算法這種方法往往不能得到精確的結(jié)果。再則， PSO方法提供了全局搜索的可能，但并不能嚴格證明它在全局最優(yōu)點上的收斂性。因此， PSO一般適用于存在多個局部極值點而并不需要得到很高精度的優(yōu)化問題。對于本文而言，基本粒子群算法有一個致命的的缺點，它速度更新和位置更新都是由特定的連續(xù)函數(shù)決定 的，所以它只能解決連續(xù)性優(yōu)化問題，對于求解離散問題存在困難。 3 旅行商問題 9 3 旅行商問題 TSP 問題介紹 旅行商問題 (Traveling Salesman Problem,簡稱 TSP)是一個典型的 NP問題也是一個典型的組合優(yōu)化問題。旅行商問題描述如下：給定 n個城市及兩兩城市之間的距離，求一條經(jīng)過各城市一次且僅一次的最短路線。對于 n個城市的 TSP 問題，存在著（ n1） ! /2 條可能的路徑，隨著城市數(shù)目 n 的增長，可能路徑的數(shù)目以 n的指數(shù)倍增加。如果使用窮舉法搜索，需要考慮所有可能的情況，并兩兩比較，找出最優(yōu)解，那么可搜索的路徑及距離之和的計算量將正比于 n! /2，算法的復(fù)雜度呈指數(shù)增長，要求出旅行商問題的最優(yōu)化解是很困難的，這也是該問題被認為是 NP 問題的原因。同樣不幸的是，旅行商問題為離散問題，使得可以解決該問題的方法更少。因此，任何可以求解旅行商問題的方法都應(yīng)被高度關(guān)注。 在生產(chǎn)生活中許多問題都可以轉(zhuǎn)化為旅行商這類問題的模型，因此旅行商問題具有很高的實際應(yīng)用價值，例如：城市管道鋪設(shè)優(yōu)化、物流行業(yè)中的車輛調(diào)度優(yōu)化、制造業(yè)中的切割路徑優(yōu)化以及電力系統(tǒng)配電網(wǎng)絡(luò)重構(gòu)等現(xiàn)實生活中的很多優(yōu)化問題都可以歸結(jié)為旅行商模型來求解 ，目前旅行商問題應(yīng)用的一個非常重要方面就是無人飛機的航路設(shè)計問題，即事先針對敵方防御區(qū)內(nèi)的威脅部署和目標的分布情況，對無人作戰(zhàn)飛機的飛行航路進行整體規(guī)劃設(shè)計，可以綜合減小被敵方發(fā)現(xiàn)和反擊的可能性降低耗油量，從而顯著提高 UCAV（無人戰(zhàn)斗機）執(zhí)行對地攻擊（或偵察）任務(wù)的成功率。 TSP 問題定義 設(shè) n為城市數(shù)目 ][ jidD? 為 n*n 階距離矩陣， jid 代表從城市 i 到城市 j的距離，ni ,...,2,1? ， nj ,...,2,1? 。問題是要找出訪問每個城市且每個城市恰好只訪問一次的一條 Hamilton 回路，且其路徑的總長度是最短的。 這條 Hamilton 回路可以表示為 (1,2,...,n)的所有循環(huán)排列的集合，即 ][ ijSS? 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 10 為 (1,2,...,n)的排列， ijS 表示訪問第 i個城市后訪問第 j個城市。 目標函數(shù)（在粒子群算法中也可以叫做適應(yīng)值函數(shù)）：城市 Hamilton 回路總長度為： ??? ?? 11 )]1(),([m in kn ksksDd () 引入決策變量： 否則 后訪問城市若旅行商訪問城市 ji01????ijx () 旅行商問題定義雖然非常簡單，使用窮舉法可以讓旅行商得到確定的最優(yōu)解，但隨著需要訪問城市數(shù)目的增加，會出現(xiàn)所謂的組合爆炸現(xiàn)象。所以，城市數(shù)目比較多的時候使用窮舉搜索策略幾乎是不可能做到的。 4 改進的粒子群算法去解決 TSP問題 11 4 改進的粒子群算法求解 TSP 問題 改進的粒子群算法簡介 由第二章的基本粒子群算法介紹，我們可以看出基本的粒子群算法對適應(yīng)度函數(shù)是有連續(xù)的要求。因此，基本粒子群算法在很多連續(xù)優(yōu)化 問題中得到成功應(yīng)用，但粒子群算法不能直接應(yīng)用到離散問題中，那么，如果非要用它解決離散問題，就必須對算法進行改進。我們需要對方程 ()和方程 ()進行改寫并且重新定義方程中加法和乘法的含義。下面我將介紹幾種改進的粒子群算法，這些算法可以比較好的解決旅行商這種離散型問題。 王翠茹，張江維，王 等 [13][14]對粒子群優(yōu)化算法進行了改進后，粒子不僅根據(jù)自身和同伴中最好的個體調(diào)整自己的飛行速度，而且按照一定的概率向其他個體學(xué)習(xí)，這種強化后的學(xué)習(xí)行為更符合自然界生物的學(xué)習(xí)規(guī)律，更有利于粒子發(fā)現(xiàn)問題的 全局最優(yōu)解。同時借鑒單點調(diào)整算法思想，提出了調(diào)整因子和調(diào)整序概念用以重構(gòu)粒子群算法。傅 剛 [15]認為，用粒子群算法解決旅行商問題時，調(diào)整因子的先后順序決定下一代種子的優(yōu)劣，以及能否很快地收斂到最優(yōu)值，如何恰當?shù)亟鉀Q慣性權(quán)重個體間的協(xié)作和個體歷史最優(yōu)以及群體最優(yōu)對個體的影響是快速高效解決這一問題的關(guān)鍵。 旁巍，王康平，周春光等 [16]通過引入模糊矩陣提出了一種改進的粒子群優(yōu)化算法，采用模糊矩陣來表示粒子的位置和速度，并重新定義速度和位置更新公式中的各種運算符號，這種改進的粒子群算法給求解旅行商問題提供了一種 新思路?；谶@種思路下文將會介紹詳細的實現(xiàn)過程。 郭文忠等 [17]在介紹目前已經(jīng)有多種針對慣性權(quán)值的研究的基礎(chǔ)上，提出引入模 糊技術(shù)，并提出了佳粒子距的概念，并給出了一種慣性權(quán)值的模糊自適應(yīng)調(diào)整模型及其相應(yīng)的粒子群優(yōu)化算法，使用不同的慣性權(quán)值更新同一代種群，用于 TSP 問題的求解。實驗結(jié)果表明改進后的算法不僅在求解組合優(yōu)化問題中的有效性，而且同時提高了算法的性能，加快了收斂速度。 2021 年中國學(xué)者 易云飛 ， 陳國鴻 [18]提出了基于 kmeans 的改進粒子群算法求解旅行商問題。也是一種 基本粒子群算法進行了改進 ， 每一步都借鑒貪心算法的思想取局 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 12 部最優(yōu) ， 這樣產(chǎn)生的初始種群全局最優(yōu)值已經(jīng)比較接近問題的解 ， 可以節(jié)省搜索時間 ,提高算法收斂速度 。 針對粒子群算法易陷入局部最優(yōu)的缺陷 ， 采取了適合于求解 旅行商 問題的基于 kmeans 的改進策略 ,對粒子群進行聚類分析 ， 實現(xiàn)了粒子之間的信息交換 ,擴大了粒子的搜索空間 。兩個種群同時尋優(yōu) ,種群內(nèi)部獨立進行粒子群算法進化，種群個體最優(yōu)之間以一定概率進行交叉，兩個種群同時尋優(yōu)可以減小算法陷入局部最優(yōu)的概率，種群間個體最優(yōu)的交叉能夠增強兩種群間以及粒子間的信息共享，及時傳遞最優(yōu)值信息，提高粒子向更 好解進化的速度。實驗結(jié)果表明這種改進粒子群算法是有效的。 西南大學(xué)計算機與信息科學(xué)學(xué)院的教授王文峰，劉光遠，溫萬惠 [19]共同進行了求解旅行商問題的自逃逸混合離散粒子群算法研究。這種算法是 結(jié)合自然界中種群密度過大時，個體自動尋找棲息地的習(xí)性，提出了一種自逃逸思想：從候選邊集合中吸收新邊，給陷入局部區(qū)域的粒子一個變異，使其跳出局部區(qū)域。自逃逸思想提高了粒子群算法的全局搜索能力，成功地克服了早熟的缺陷。實驗結(jié)果表明，自逃逸的粒子群算法比混合蟻群算法具有更好的效率和收斂速度 , 尤其在較大規(guī)模的實例上更具優(yōu)勢。 引入模糊矩陣的粒子群算法求解 TSP 問題 旅行商問題的解用模糊矩陣表示 在用模糊矩陣 [16]表示旅行問題的解前，我們首先引入以下幾個定義： 定義 1： 一個城市為 n 的旅行商問題，設(shè)集合 s 為旅行商問題的一個解序列， s可以表示為 },...,{ 321 nssssS ? ，其中 ),...2,1( nisi ? 表示旅行商問題的解即 Hamilton 回路中第 i個結(jié)點。 定義 2：一個城市為 n的旅行商問題，設(shè)集合 M是旅 行商問題的結(jié)點集合， M 可以表示為： },...,{ 321 nmmmmM ? ，那么 )...3,2,1( nimi ? 表示旅行商問題中編號為 i 的具體結(jié)點。 對上述的定義 1 和定義 2，進行解釋：集合 S 中的每個元素， is 表示旅行商問題可行解中按照訪問的先后次序的第 i個結(jié)點，即已訪問了 i1個結(jié)點，即將訪問第 i 西安工業(yè)大學(xué)畢業(yè)設(shè)計 (論文 ) 13 個結(jié)點，還有 ni個結(jié)點需要訪問；對于 集合 M中的元素 ),