粒子群算法解最短路徑

1、摘要粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是由美國的Eberhart和Kennedy在1995年提出的一種高效的并行優(yōu)化算法。由于該算法具有深刻的智能背景，且簡單、易實現(xiàn)，因此，一經(jīng)提出便引起了許多學者的廣泛關注，并在短短的幾年里出現(xiàn)了大量的研究成果，現(xiàn)已成為研究的熱點。目前，已提出了多種PSO的改進算法，被廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模式分類、模糊系統(tǒng)控制等領域。但其應用大多是連續(xù)優(yōu)化問題，很少被用來解決離散問題，而現(xiàn)實生活中的許多工程實例只能抽象出離散模型，如典型的旅行商問題(Traveling Salesman Problem，TSP)、加

2、工調度(Job-slmp)問題、最短路徑問題等。最短路徑問題是圖論中的一個典范問題。從網(wǎng)絡模型的角度看最短路徑分析就是在指定網(wǎng)絡的兩節(jié)點間找一條阻礙強度最小的路徑。最短路徑問題的研究在汽車實時導航、應急救援等領域有廣泛的應用。經(jīng)典的Dijkstra算法是應用最短路徑解決實際問題的理論基礎。但是算法在具體的城市道路網(wǎng)絡中執(zhí)行的效率比較低，無法滿足實時高效的應用需求，因此國內外很多學者開始了最短路徑問題的粒子群優(yōu)化算法研究。本文主要是研究在最短路徑問題中的粒子群算法。文中給出了基于交換序的基本的粒子群算法，并在此基礎上提出了一種改進的粒子群算法?；镜牧Ｗ尤核惴ㄊ窃谟嬎阃炅Ｗ铀俣戎笤俑铝Ｗ拥奈?/p>

3、置，改進算法則是計算粒子速度的同時更新粒子的位置。文中還引入自適應慣性權重的改進策略，使粒子在開始時慣性速度大，能快速的向最優(yōu)值點運動，而在粒子迭代過程中慣性速度越來越小，從而使粒子能更好的接近最優(yōu)值點。引入罰函數(shù)，把約束優(yōu)化問題轉化為無約束優(yōu)化問題來解，從而減化求解過程。本文用實例對基本的粒子群算法和改進粒子群算法進行了對比分析，并得出了改進算法確實存在優(yōu)勢的結論。文中還對算法的主要參數(shù)如何取值進行了分析，并結合經(jīng)驗給出了總結。本文最后用實例驗證了算法確實在執(zhí)行了若干次迭代后收斂。程序的編程環(huán)境為Microsoft Visual Studio 2008,編程語言為C#。關鍵詞： 粒子群算法

4、最短路徑 約束優(yōu)化 慣性權重 粒子群優(yōu)化算法理論2.1粒子群優(yōu)化算法基本定義群居昆蟲以集體的力量覓食、御敵、筑巢，單個個體只能完成簡單的認務，而由單個個體組成的群體卻能完成復雜的認務，這種群體所表現(xiàn)出來的“智能”稱為群體智能(Swarm Intelligence,SI)1。如蜜蜂采蜜、筑巢，螞蟻覓食、筑巢等。從群居昆蟲互相合作進行工作中得到啟迪，研究其中的原理，以此設計新的算法被稱為群智能算法2。粒子群優(yōu)化算法是一種新興的群智能優(yōu)化算法，其思想來源于人工生命和演化計算理論，粒子在解空間根據(jù)所處的情況進行搜索，容易實現(xiàn)并且沒有許多參數(shù)需要調整，另外收斂速度快，相對于遺傳算法等更簡單有效。PSO已

5、經(jīng)得到眾多學者的重視和研究3-4，在許多實際應用中被證明是有效的。國際上已有專門從事相關科研內容的研究組織以及進行學術交流和會議發(fā)布的網(wǎng)站和論壇?；径x5定義1：（粒子） d-粒子p是維度為d的空間粒子，簡稱粒子；d稱做粒子的維度，p=(x1,x2,.,xj,.xd)為d-粒子空間。定義 2：（粒子群） n-種群是n個粒子組成的群落（粒子允許重復），簡稱粒子群。N稱為粒子群規(guī)模,Snp|pi=(xi,1,xi,2,xi,j,xi,d),in為n-種群空間。定義 3：（個性算子）粒子在d維解空間搜索的過程中，下一步的飛翔速度和到達的位置與粒子自身的飛翔速度有關，即V(t+1)=wV(t),該操

6、作稱為個性算子。定義 4：（自意識算子）粒子在d維解空間搜索過程中，下一步的飛翔速度和到達的位置與粒子自身到當前為止所到達的最好位置有關。也就是說，粒子在d維解空間搜索的過程中受到粒子自身的經(jīng)歷影響，在整個飛翔過程中一直下意識地根據(jù)自身的經(jīng)驗調整飛行速度和方向，即Vi,j(t+1)=c1U(0,1)(Xi,j#(t)-Xi,j(t) (2-1)該操作稱為自意識算子。C1是正常數(shù)，稱為自意識學習因子；U(0,1)是0,1區(qū)間正態(tài)分布的隨機數(shù)。定義 5：（群意識算子）粒子在d 維解空間搜索的過程中，下一步的飛翔速度和到達的位置與粒子群到當前為止所到達的最好位置有關。也就是說，粒子在d維解空間搜索過

7、程中受粒子群的經(jīng)歷影響，在整個飛翔過程中一直下意識得根據(jù)粒子群的經(jīng)驗調整飛行速度和方向，即 Vi,j(t+1)=c2U(0,1)(Xi,j*(t)-Xi,j(t) (2-2)該操作算子稱為群意識算子。C2是正常數(shù)，稱為群意識學習因子；U(0,1)是0,1區(qū)間正態(tài)分布的隨機數(shù)。定義 6：（粒子種群多樣性）粒子群中的粒子因在解空間飛行所到達的位置不同而搜索到不同的可行解，即因粒子的位置不同而表現(xiàn)出的多樣性稱為種群多樣性。它是評價粒子群搜索可行解能力的重要尺度，由以下式給出： D= (2-3)其中，為粒子群的中心位置，它的第j維為i。2.2粒子群優(yōu)化算法詳細描述假設在一個群體中有popsize個粒子

8、,每個粒子是n維空間中的一個個體,不同的個體具有不同的位置 (j=1,2,popsize),不同的位置對應于不同的與優(yōu)化目標函數(shù)值相關的個體適應度函數(shù)值fitness()。對于第j個粒子,以表示其位置,它在空間中以某個速度飛行,它所經(jīng)歷的最好位置為,也稱為。群體中所有粒子所經(jīng)歷的最好位置為,也稱為。若已知第k代第j個粒子的速度及位置,則第(k+1)代第j個粒子的速度及位置為: (2-4) (2-5)式中: 慣性權重系數(shù),為迭代次數(shù)的函數(shù),且隨迭代次數(shù)線性減少,即 (2-6)這里,初始、終止慣性權重; 最大迭代代數(shù);粒子自身加速度權重系數(shù),一般在02之間取值;全局加速度權重系數(shù),一般在02之間取

9、值;, 0,1范圍內兩個相互獨立的、均勻分布的隨機數(shù),即,U(0,1)。 為了減少在搜索過程中粒子離開搜索空間的可能性,V通常被限定于一定的范圍內,即-V。當然,亦可根據(jù)具體情況,將搜索空間限定于一定的范圍內,即X。解優(yōu)化問題的PSO流程圖如下： 是否開 始初始化粒子群計算每個粒子新位置的適應值根據(jù)粒子適應值更新個體極值與全局極值根據(jù)(2-4)和(2-5)式,更新自己的速度和位置達到最大迭代次數(shù)數(shù)結 束 圖 2-1 PSO流程圖PSO的計算流程如下:Step1 初始化一群粒子(種群規(guī)模為popsize),包括隨機位置和速 度,k=0;Step2 計算每個粒子的適應度值fitness();Ste

10、p3 對每個粒子,將其適應度值fitness()與其歷史最好位置 的適應度值fitness()比較,若較好,則將其作為當前的最 好位置;Step4 對每個粒子,將其適應度值fitness()與全局所經(jīng)歷的最好位置的適應度值fitness()比較,若較好,則重新設置;Step5 用式(1)和式(2)計算和其中:(j=1,2,popsize);Step6若達到終止條件(通常為足夠好的適應值或達到預設最大代數(shù)),則結束,返回當前全局最優(yōu)個體即為結果;否則,k=k+1,轉Step2。2.3粒子群優(yōu)化算法特點PSO具有以下一些特點:(1)基本PSO算法最初是處理連續(xù)優(yōu)化問題的。(2)類似于遺傳算法，PS

11、O也是多點搜索。(3) 計算準確、效率高。(4)(2-4)式的第一項對應于多樣化的特點，第二項、第三項對應于搜索過程中的集中化特點，因此這個方法在多樣化和集中化之間建立均衡6。 PSO有全局版和局部版兩種,全局版收斂快,但有時會陷入局部最優(yōu)。局部版PSO通過保持多個吸引子來避免早熟,假設每一個粒子在大小l的鄰域內定為一個集合: (2-7)從Ni中選出最好的,將其位置作為lbest代替公式中的gbest,其他與全局版PSO相同。實驗表明,局部版比全局版收斂慢,但不容易陷入局部最優(yōu)7。在實際應用中,可以先用全局PSO找到大致的結果,再用局部PSO進行搜索。2.4 粒子群優(yōu)化算法幾何特性PSO中每個

12、優(yōu)化問題的解都是搜索空間中的一個“粒子”狀態(tài)。所有粒子都有一個適應函數(shù)決定的適應值，每個粒子還有一個速度直接影響它們飛翔的距離。粒子根據(jù)當前的自身情況和粒子群的情況在解空間中搜索。PSO初始化時將一群粒子的狀態(tài)賦隨機值（隨機解），根據(jù)式2-4和式2-5來更新速度和新的位置。在式2-4中等式右邊共有三項。第一項是粒子上一次的速度與慣性權重W的乘積，慣性權重W對優(yōu)化性能的影響，發(fā)現(xiàn)較大的W值有利于跳出局部極小點，而較小的W值有利于算法收斂。第二項是粒子自身行為差異比較。第三項是粒子群體行為差異比較。后兩項合稱為粒子的“意識”部分。每次迭代后粒子運動狀態(tài)如下圖2-2所示，在整個解空間搜索中粒子呈正弦

13、曲線擺動2。X#(t)X(t)V(t)X(t+1)X*(t) 圖2-2 粒子飛翔狀況的幾何表示從粒子群優(yōu)化算法的幾何分析可知，如果一個粒子當前的位置與該粒子的當前最優(yōu)值一致，該粒子會因為它以前的速度和慣性權重不為零而遠離最佳位置導致算法不能收斂；如果以前的速度非常接近零，粒子一旦趕上了粒子群的當前最佳粒子，種群多樣性就會慢慢消失，所有的粒子將會停止移動，粒子群最優(yōu)化出現(xiàn)停滯狀態(tài)，不能搜索到滿意解，這種情況大多導致早熟。因此目前尚需設計新型操作算子或者解決方案。粒子群優(yōu)化算法是一類隨機全局優(yōu)化技術，PSO算法通過粒子間的相互作用發(fā)現(xiàn)復雜搜索空間中的最優(yōu)區(qū)域。PSO的優(yōu)勢在于簡單、容易實現(xiàn)且功能強

14、大。PSO已成為國際演化計算界研究的熱點。目前已經(jīng)發(fā)表不少該方面的研究論文，且有部分開源VB和C代碼可供參考。有興趣的讀者，可深入閱讀相關參考文獻。2.5粒子群優(yōu)化算法參數(shù)分析對PSO算法中參數(shù)分析如下: 在PSO算法中有3個權重因子:慣性權重w,加速常數(shù)C1和C2。慣性權重w使粒子保持運動慣性，使其有擴展搜索空間的趨勢，有能力探索新的區(qū)域。加速因子C1和C2代表將每個粒子推向pbest和gbest位置的統(tǒng)計加速項的權重。低的值允許粒子在被拉回之前可以在目標區(qū)域外徘徊，而高的值則導致粒子突然沖向或超過目標區(qū)域。如果沒有后兩部分，即C1=C2=0，粒子將一直以當前的速度飛行，直到到達邊界。由于它

15、只能搜索有限的區(qū)域，所以很難找到好解。如果沒有第一部分，即w=0，則速度只取決于粒子當前位置和其歷史最好位置pbest和gbest，速度本身沒有記憶性。假設一個粒子位于全局最好位置，它將保持靜止。而其他粒子則飛向它本身最好位置pbest和全局最好位置gbest的加權中心。在這種條件下，粒子群將收縮到當前的全局最好位置，更像一個局部算法。在加上第一部分后，粒子有擴展搜索空間的趨勢，即第一部分有全局搜索能力。這也使得w的作用為針對不同的搜索問題，調整算法全局和局部搜索能力的平衡。如果沒有第二部分，即C1=0,則粒子沒有認知能力，也就是“只有社會”的模型在粒子的相互作用下，有能力達到新的搜索空間。它

16、的收斂速度比標準版本更快，但對復雜問題，則比標準版本更容易陷入局部優(yōu)值點。如果沒有第三部分，即C2=0,則粒子之間沒有社會信息共享，也就是“只有認知”的模型。因為個體間沒有交互，一個規(guī)模為m的群體等價于運行了m個單個粒子的運行，因而得到解的機率非常小。早期的試驗將w固定為1，C1和C2固定為2，因此Vmax成為唯一需要調節(jié)的參數(shù)，通常設為每維變化范圍的1020。引入慣性權重w可消除對Vmax的需要，因為它們的作用都是維護全局和局部搜索能力的平衡。這樣，當Vmax增加時，可通過減小w來達到使得所需的迭代次數(shù)變小。從這個意義上看，可以將Vmax固定為每維變量的變化范圍，只對w進行調節(jié)。研究發(fā)現(xiàn)較大

17、慣性權重w值有利于跳出局部極小點，而較小的慣性權重w有利于算法收斂，因此提出自適應調整w的策略，即隨迭代的進行，線性減小w的值，對全局搜索，通常的好方法是在前期有較高的探索能力以得到合適的種子，而在后期有較高的開發(fā)能力以加快收斂速度。為此可將w設為隨時間線性減小，例如由1.4到1.0，或由0.9到0.4,或由0.95到0.2等。Suganthan的實驗表明，C1和C2為常數(shù)時可以得到較好的解，但不一定必須為2。Clere引入收縮因子K來保證收斂性: (2-8)式中，T=2/|2-s-sqrt(s*s-4s)|,s=w1+w2,w4。這對應于1-3式中一種特殊的參數(shù)組合，其中T即一種受w1和w2

18、限制的w，而C1Tw1和C2Tw2。這些參數(shù)也可以通過模糊系統(tǒng)進行調節(jié)。Shi和Eberhart提出一個模糊系統(tǒng)來調節(jié)w，該系數(shù)包括9條規(guī)則，有兩個輸入和一個輸出，每個輸入和輸出定義了3個模糊集。一個輸入為當前的全局最好適應值，另一個為當前的w,輸出為w的變化。結果顯示該方法能大幅度提高平均適應值。此外，群體的初始化也是影響算法性能的一個方法。Aageline對不對稱的初始化進行了實驗，發(fā)現(xiàn)PSO只是略微受影響。Ozcan和Mohan通過假設w1、C1和C2為常數(shù)、pbest和gbest為固定點進行理論分析，得到一個粒子隨時間變化可以描述為波的運行，并對不同的感興趣的區(qū)域進行軌跡分析。這個分析

19、被Kennedy的模擬結果支持。一個尋求優(yōu)值位置的粒子嘗試著操縱它的頻率和幅度，以捕獲不同的波。W可以看作是修改了感興趣的區(qū)域的邊界，而Vmax則幫助粒子跳到另外一個波。2.6粒子群優(yōu)化算法收斂性分析因為引入了隨機量的原因,PSO的收斂性分析一直是研究的難點。Clerc對式(1)和(2)中的參數(shù)進行了初步分析8,盡管有明顯缺陷,但仍具重要意義。 首先,定義: 式（2-9）簡化成： (2-10)其中, 。進一步簡化系統(tǒng),假設、c不變,且解空間僅一維,研究一個粒子,則式(2-3)、(2-4)式可變?yōu)闋顟B(tài)方程的形式: (2-11) P和r是常數(shù),通過對狀態(tài)轉移矩陣(4)的穩(wěn)定性分析,即可得出粒子運動

20、穩(wěn)定性的約束條件。其結論如下: 當式(2-4)和式(2-5)中參數(shù)滿足約束條件: (2-12),4 (2-13)時,在假設條件下粒子運動軌跡穩(wěn)定。在此基礎上,Bergh9做了進一步分析,研究隨機性對粒子軌跡的影響,在Lebesgue和Borel測度空間上對收斂性做了分析。 PSO算法求解最短路徑問題4.1 PSO算法的中數(shù)據(jù)的表達方式(1)所有邊的權值數(shù)據(jù)存儲為如下的矩陣：其中, n為頂點的數(shù)目。(2)源點-匯點的最短路徑存儲：其中，中存放了源點或匯點在數(shù)組中的位置，是頂點的編號，n為項點的數(shù)目。例4.1：頂點數(shù)為5，項點編號依次為0，1，2，3，4，一條路徑為03214,源點的0,匯點為1,

21、則存儲為如下所示：25032144.2初始化粒子本文在粒子初始化時，首先根據(jù)圖的信息生成一張表示頂點連接信息的NM表,然后由表的信息計算出一張NM的粒子隨機生成的概率表,最后由概率表來隨機生成粒子.4.2.1生成頂點信息表頂點信息表的樣式如表4-1.表4-1頂點信息表0Num_0A0,1A0,2A0,Num_01Num_1A1,1A1,2A1,Num_12Num_2.N-2Num_N-2AN-2,1AN-2,Num_N-2N-1Num_N-1AN-1,1AN-1,Num_N-1其中的第一列分別給出了此列信息是編號為i的頂點的連接信息.Num_i,表示編號為i的頂點共有Num_i個鄰接頂點.Ai

22、,j表示編號的i的頂點的第j 個相鄰的頂點的編號.4.2.2生成概率表概率表的樣式如表4-2所示.表4-2概率表0Num_0P0,1P0,2P0,Num_01Num_1P1,1P1,2P1,Num_12Num_2.N-2Num_N-2PN-2,1PN-2,Num_N-2N-1Num_N-1PN-1,1PN-1,Num_N-1前兩列的含義與表4-3相同,這里這不在介紹,Pi,j表示編號的i的頂點的第j個相鄰的頂點對應的概率和的值.假設Wi,j表示編號為i的頂點與它的第j 個相鄰頂點所形成的邊的權值,側Wi,j表示它的倒數(shù),在計算Pi,j時要先計算編號為i的頂點所有鄰邊的權值的倒數(shù)之和,記為sum

23、_i, 然后計算Wi,j/sum_i.Pi,j=4.2.3生成初始化的粒子在生成初始化的粒子是,選取源點作為起點,隨機生成一個01之間的數(shù)x,從上面得到的頂點的概率表的起點所在的行中的第三列開始比較x與Pi,j的值,直到x小于Pi,j時取得第j 個相鄰頂點的編號放入最短路徑存儲的數(shù)組中,然后把得到的新頂點作為起點重復上述過程,直到遍歷完所有的頂點.4.3 PSO算法求解最短路徑問題的模型定義4.1 ：設n個節(jié)點的最短路徑問題的解序列為S=（）,i=1,n。定義交換子15SO（）為交換解S中的點，則=S+SO（）為解S經(jīng)算子SO（）后的新解，這里的符號“+”賦予了新的含義。例4.1：有一個5個節(jié)

24、點的最短路徑問題，其解為S=（1 3 5 2 4），交換算子為SO（1，2），則 =S+SO（1，2）=（1 3 5 2 4）+SO（1，2）=（3 1 5 2 4）。交換算子在存儲形式如下： 其中 ，其中n為頂點數(shù)目。例：交換子為SS=（s1(5,2),s2(3,4)），則交換算子的存儲形式為：00402定義4.2：一個或多個交換子的有序隊列就是交換序，記作SS。 SS=S， （4-1）其中是交換子，它們之間的順序是有意義的。交換序作用于一個最短路徑解上意味著這個交換序中的所有交換子依次作用于該解上，即=S+SS=S+（）=（S+S （4-2）定義4.3：不同的交換序作用于同一解上可能產生相

25、同的新解，所有有相同效果的交換序列集合稱為交換序的等價集17。定義4.4：若干個交換序可以合并成一個新的交換序，定義為兩個交換序的合并算子。例行4.2：設兩個交換序，按先后順序作用于解S上，得到新解。假設另外有一個交換序作用于同一解S上，能夠得到相同的解，可定義 =， （4-3）和屬于同一個等價集，一般來說，不唯一。定義4.5：在交換序等價集中，擁有最少交換子的交換序稱為該等價集的基本交換序17?？砂慈缦碌姆椒嬙煲粋€基本交換序，設給定兩個解路徑A和B，需要構造一個基本交換序SS，使得B+SS=A。 A：（1 2 3 4 5）；B（2 3 1 5 4）可以看出，A（1）=B（3）=1，所以第一

26、個交換子是SO（1，3），=B+SO（1，3），得到：（1 3 2 5 4）；A（20）=（3）=1，所以第二個交換子是SO（2,3）,=+SO(2,3),得到：（1 2 3 5 4）。同理，第三個交換子是SO（4，5），=+SO（4，5）=A。這樣，就得到一個基本交換序：SS=A-B=（SO（1，3），SO（2，3），SO（4，5）。4.4求解最短路徑問題的PSO算法基本PSO算法中的速度算式（1.1）已不適合最短路徑問題，于是重新構造了速度算式： =(-)(-), (4-4)其中,(,0,1)為隨機數(shù)，(-)表示基本交換序（-）中的所有交換子以概率保留；同理，（-）表示基本交換序（-）中的

27、所有交換子以概率保留。由此可以看出，的值越大，（-）保留的交換子就越多， 的影響就越大；同理，的值越大，（-）保留的交換子就越多，的影響就越大。求解最短路徑問題的PSO算法步驟描述如下：（1）初始化粒子群，給每個粒子一個初始解和隨機的交換序。（2）如果滿足結束條件，轉步驟（5）。（3）根據(jù)粒子當前位置計算下一新解: 1）計算（-）交換序。 2）計算(-)。 3）計算式4.4，并將轉換為基本交換序。 4）計算搜索到的新解 5）如果找到一個更好得解，更新。（4）如果整個群體找到一個更好的解，更新，轉步驟（2）。（5）顯示結果。4.5粒子群優(yōu)化的幾種策略4.5.1改進策略一 由于離散量運算的特殊性，

28、對粒子的運動方程作了修改，因為速度的定義使位置的運動是一步到位的，公式4.4的第一項采用原有速度的意義已經(jīng)不大了，由于慣性的主要作用是產生擾動，維持粒子群的多樣性，沒有它的作用PSO算法就將陷入早熟，為了解決這一問題，改進策略一中采用了擾動速度，它的每一維的速度的值采用隨機方式產生，擾動的速度使算法在迭代的后期依然保持進化的能力，能有效的解決早熟收斂的影響；另外因為速度之間存在相互干擾的現(xiàn)象，為了使各個速度的作用不會相互干擾，采用分步計算速度和修改粒子位置的方式，修改后的運動方程如下： =+w （4-5）=+c1*rand()() (4-6)=+c2*rand()() (4-7)4.5.2近鄰

29、搜索算子 對最短路徑問題，傳統(tǒng)的鄰域產生函數(shù)包括互換、逆序、和插入等操作，他們大都隨機方式產生一個狀態(tài)，由于沒有充分使用鄰域知識，致使搜索的效率不高，由于最短路徑的中必然包括而且在很在程度上包括了相鄰頂點權重最短的邊，所以可以用一個NM的矩陣K來存儲各個頂點的近鄰頂點排序表，里面的每一個元素的值表示對頂點i而言，第j近的頂點是，第一近的城市是，次近的城市是,依次類推，K作用所有粒子公共的知識序，能被所有粒子所感知，并以此來指導粒了的近鄰搜索過程。在近鄰搜索算子中，對第一維i上的頂點，如果它接下來要訪問的頂點是第j 近的頂點，則依次以為下一維的速度，作用到此粒子上，看能不能減小路徑長度，如果能，

30、則粒子進入新的位置，對所有的維數(shù)重復這個過程，因為搜索本身是有代價的，除了使算法運算速度變慢外，還可能使算法易于陷入早熟悉、停滯，為此定義搜索深度（depth）這個參數(shù)來控制在搜索時所考慮的頂點數(shù)，即速度中的下標j 還應小于depth.。4.5.3自適應慣性系數(shù)的改進策略粒子在解內不斷地跟蹤個體極值和全局極值進行搜索，直到達到規(guī)定的誤差標準或搜索次數(shù)為止。粒子每一維飛行的最大速度不能超過算法設定的最大速度,設置較大的可以保證粒子種群的全局搜索能力，較小則粒子的局部搜索能力強。由于在搜索過程中有時會出現(xiàn)粒子在全局最優(yōu)解附近出現(xiàn)“振蕩”現(xiàn)象，為避免此問題，可以進行如下改進：隨迭代次數(shù)增加，速度更新

31、公式中的加權因子w由最大因子線性減小到最小加權因子，即 (4-8)其中gen為當前迭代次數(shù)，為總的迭代次數(shù)。4.5.4對約束條件的優(yōu)化 考慮目標函數(shù)如下： min Z= (4-9) s.t.Weight(i,j)0,i=0,.,n-1,j=0,n-1; (4-10) 罰函數(shù)19是在目標函數(shù)中加上一下懲罰項，以反映得到的解是否位于約束集中，通過廣義的目標函數(shù)，使得算法在懲罰項作用下找到原問題的最優(yōu)解。這樣將一個有約束的優(yōu)化問題，轉化成一個無約束的優(yōu)化問題，因此在改進的PSO算法中適應值函數(shù)修改為如下式： (4-11) 其中，M為自定義的一個大數(shù)，是最短路路徑問題中達不到的大數(shù)。再通過全局搜索的P

32、SO算法“跳出局部最小”，最終收斂于全局最小。PSO算法求解最短路徑問題的實現(xiàn)5.1繪圖部分的實現(xiàn)5.1.1總的繪圖界面 系統(tǒng)運行時的圖如圖5-1圖所示：圖5-1系統(tǒng)界面圖5.1.2畫點具體效果如圖5-2和圖5-3:圖5-2畫點工具欄圖圖5-3繪點5.1.3 畫線 系統(tǒng)中有三種畫線的方式，分別為畫一條線段、畫一條連續(xù)折線、畫一組同一起點的射線。具體效果如圖5-45-9所示：圖5-4畫線工具欄圖5-5畫線圖5-6畫連續(xù)折線圖5-7連續(xù)折線效果圖5-8畫同一起點的一組射線圖5-9畫一組射線的效果5.1.4選擇頂點 選取頂點的策略：當鼠標按下時，根據(jù)當前鼠標的坐標值（x,y）,用以（x,y）為中心的

33、長為20，寬為20的矩形區(qū)域來找點，如果在此區(qū)域中有點，則就標記這個點。選取點的目的主要是為連接兩頂點、刪除頂點、移動頂點服務的。具體效果圖5-10和圖5-11所示：圖5-10選擇頂點的工具欄圖5-11選擇頂點的效果5.1,5選擇邊 選擇邊的策略：當鼠標按下時記錄下鼠標位置（x,y）,然后依次從邊中找到編號為i的頂點的坐標（,）,編號為j 的頂點的坐標（,），計算頂點i與頂點j 之間的矩離記為C，頂點i與（x,y）和j 與（x,y）的矩離之和為A，設B=20，則如果，則就表示此邊就是要選的邊，然后標記此邊。上面描述的含義就是如果鼠標落在以B/2為b,以C/2為c的橢圓內部，就先邊。具體效果如圖

34、5-12和圖5-13所示：圖5-12選取邊的工具檔圖5-13選取邊的效果5.1.6連接兩頂點 連接兩個頂點前，要先選取兩個頂點，然后才能執(zhí)行連接操作。連接可分為三種情況。第一種：兩個沒有邊相連的點連接，此時要增加頂點的個數(shù)，并且增加連接的邊。第二種：只有一個頂點沒有邊相邊時，把沒有邊相連的頂點加入頂點序列，增加連接后的邊。第三種：兩個頂點全都有邊相連時，只需增加邊就可。具體效果如圖5-14圖5-17所示：圖5-14選取連接的兩頂點圖5-15連接兩頂點圖5-16連接兩頂點圖5-17連接兩頂點5.1.7頂點的移動 移動頂點的操作主要是為了對圖形形狀的修改，使用戶對圖形的整體結構有更直觀的了解。具體

35、效果如圖5-18和圖5-19：圖5-18移動頂點工具欄圖5-19移動頂點效果5.1.8刪除頂點和邊 刪除頂點和邊主要是用來修改繪制的圖形，可以使用戶更方便的繪圖。刪除操作執(zhí)行前必須要選擇需要執(zhí)行此操作的邊和頂點。具體效果如圖5-20圖5-22所示：圖5-20刪除操作工具欄圖5-21刪除頂點圖5-22刪除邊5.1.9取消所選 取消所選可以一次性取消所有已選擇的頂點和邊。具體效果如圖5-23圖5-25所示：圖5-23取消所選工具欄圖5-24取消頂點圖5-25取消邊5.1.10結束繪圖 此操作用來使繪圖工具欄無效，使分隔欄左側部分有效，從面轉入算法參數(shù)、圖形標記和權值的輸入狀態(tài)。具體效果如圖5-26

36、和圖5-27所示：圖5-26結束繪圖5-27結束繪圖效果5.1.11算法參數(shù)輸入w_max為慣性系數(shù)最大值,w_min為慣性系數(shù)最小值，C1為粒子自身加速度權重系數(shù)，C2為全局加速度權重系數(shù)，M為自己設定的一個罰函數(shù)值。Same_max為在不更新全局最優(yōu)值時最多迭代次數(shù)。圖5-28參數(shù)輸入欄5.1.12標記頂點和輸入權值標記頂點就是給每個頂點輸入具有一定含義的標記值，這樣可以更好的用圖來表達所代表的具體問題。輸入時格式為：”i,lable;”其中i為要標記的頂點的編號，lable為標記的字符串。；表示結束，只有輸入；后標記的內容才能生效。具體效果如圖5-29和圖5-30所示： 圖5-29權圖附

37、加信息輸入欄圖5-30標記頂點權值的輸入格式為：”i,j,value;”,其中i,j分別為邊的兩個端點，value為權值。注意第次輸入完value后必須以；結束。具體效果如圖5-31：圖5-31輸入邊的權重5.1.13起點和終點的設置起點和終點主要用來傳遞參數(shù)給算法。輸入框如圖5-32所示：圖5-32起終點輸入欄5.1.14按紐區(qū) 按下繪圖完成按紐時工具欄就被屏蔽掉了，按下算法參數(shù)完成按紐時算法的參數(shù)就傳遞給算法，起始點完成、權值完成、輸入完成的作用同上。按下輸入完成時表示算法所需的數(shù)據(jù)輸入完成，此時就可以生成粒子了，按下初始下按紐進行粒子的實始化操作，輸出1用來輸出基本粒子群算法的結果，輸出

38、2用來輸出改進方法的輸出結果。 圖5-33按紐區(qū) 圖5-34輸出區(qū)5.2自定義的輸入輸出方式（1）輸出：當一次操作完成生成了如下圖所示的結果，如果想保存此結果，可以在文件菜單中選擇保存，然后選擇保存位置和保存的文件名，最后點確定進行保存操作。假設操作完成后的圖如圖5-35所示：圖5-35輸入的完整圖 執(zhí)行完保存操作后的寫入文件中的內容如圖5-36所示：圖5-36寫入文件的格式(2)輸入可以直接從文件菜單頂中選打開，然后找到要找開的文件名，點確定完成打開操作。完成后主可在繪圖區(qū)看到上次保存的圖。假設要打開的文件的內容如圖5-37所示：圖5-37要讀取的文件格式 則執(zhí)行完打開操作后繪圖區(qū)顯示內容如

39、圖5-38：圖5-38讀取文件后生成的圖5.3算法的實現(xiàn)5.3.1 PSO求解最短路徑的數(shù)據(jù)流圖 系統(tǒng)的數(shù)據(jù)流圖如圖5-39所示：信息顯示調用相應的PSO算法進行計算帶權圖及參數(shù)優(yōu)化控制面板（用戶接口）帶權圖參數(shù)優(yōu)化模型參數(shù)最佳適應值全局最優(yōu)解顯示面板(用戶端)結果圖539 PSO求解最短路徑問題1層數(shù)據(jù)流程圖5.3.2數(shù)據(jù)字典用戶輸入的數(shù)據(jù)包括：帶權圖、迭代次數(shù)、種群規(guī)模、慣性系數(shù)、起點、終點、維數(shù)等。表5-1 輸入?yún)?shù)數(shù)據(jù)字典字段名標識類型取值范圍種群規(guī)模numint迭代次數(shù)timeint最大更新速度vmaxint最大慣性系數(shù)w_maxdouble01起點startint終點endint最

40、小慣性系數(shù)w_mindouble01頂點標記point_stringstring0500權值ptopWeightdouble0500罰函數(shù)值Mint學習因子1C1double04學習因子2C2double045.3.3 PSO算法求解最短路徑流程圖設置參數(shù)值如下：w,c1,c2,dim, interaterDegree, edgtWeight，M，start,end等由edgtWeight生成鄰接點的順序表Graph，調用Initilize（），初始化粒了的位置和速度。計算,并分別與c1和c2執(zhí)行依概率相乘，原位置與執(zhí)行自定義的加操作，再與c1(,)執(zhí)行同上操作，再與c2()執(zhí)行同上操作。當前

41、值小于個體最優(yōu)更新個體最優(yōu)值計算完此次迭代中的所有粒子的適應值當前最優(yōu)小于全局最優(yōu)更新全局最優(yōu)大于最大迭代次數(shù)END圖540 PSO求解最短路徑問題流程圖5.3.4 PSO算法的實現(xiàn)主要數(shù)據(jù)結構：種群大小(particleAmount) 空間維數(shù)(dim)最大迭代次數(shù)(interaterDegree) 邊的權重(edgtWeight)各粒子當前適應度值(particleFit)各粒最優(yōu)適應度值(particleBestFit)各粒子位置(particleCurrentSolution) 各粒子速度(p_V) 各粒子的最佳位置(particleBestSolution) 全局最佳粒子位置(Bes

42、tArray)全局最佳粒子序號(allParticleBestIndex) 得到相近適應度值的迭代次數(shù)(getBestValue_time)主要函數(shù)： CreateGragph：生成NM的矩陣Graph來存儲各個頂點的近鄰頂點排序表。 GetFit：計算粒子當前的適應度值。 GetBestFit：計算機全局最優(yōu)適應度值。 BeginWithStart：使每條路徑都從起始點開始排起。OperatorDelete：計算（Pid-Xid）等交換序。OperatorPlus：進行交換操作。OperatorCheng：計算以概率保留交換序。核心代碼如下：public void ParticleFly()

43、 int Array1 = new intdim + 2; int g_bestIndex = 0; for (int j = 0; j interaterDegree; j+) for (int i = 0; i particlei.particleFit)/如果當前的優(yōu)/于個體歷史最優(yōu)，則更新歷史最優(yōu). particlei.particleBestFit = particlei.particleFit; particlei.particleBestSolution = particlei.particleCurrentSolution; g_bestIndex = GetBestFit(particle); if (particle