粒子群算法解最短路徑

1、1摘要粒子群優(yōu)化算法(ParticleSwarmOptimization，PSO)是由美國的Eberhart和Kennedy在1995年提出的一種高效的并行優(yōu)化算法。由于該算法具有深刻的智能背景，且簡單、易實現(xiàn)，因此，一經(jīng)提出便引起了許多學者的廣泛關(guān)注，并在短短的幾年里出現(xiàn)了大量的研究成果，現(xiàn)已成為研究的熱點。目前，已提出了多種PSO的改進算法，被廣泛應用于函數(shù)優(yōu)化、神經(jīng)網(wǎng)絡訓練、模式分類、模糊系統(tǒng)控制等領域。但其應用大多是連續(xù)優(yōu)化問題

2、，很少被用來解決離散問題，而現(xiàn)實生活中的許多工程實例只能抽象出離散模型，如典型的旅行商問題(TravelingSalesmanProblem，TSP)、加工調(diào)度(Jobslmp)問題、最短路徑問題等。最短路徑問題是圖論中的一個典范問題。從網(wǎng)絡模型的角度看最短路徑分析就是在指定網(wǎng)絡的兩節(jié)點間找一條阻礙強度最小的路徑。最短路徑問題的研究在汽車實時導航、應急救援等領域有廣泛的應用。經(jīng)典的Dijkstra算法是應用最短路徑解決實際問題的理論基礎

3、。但是算法在具體的城市道路網(wǎng)絡中執(zhí)行的效率比較低，無法滿足實時高效的應用需求，因此國內(nèi)外很多學者開始了最短路徑問題的粒子群優(yōu)化算法研究。本文主要是研究在最短路徑問題中的粒子群算法。文中給出了基于交換序的基本的粒子群算法，并在此基礎上提出了一種改進的粒子群算法?；镜牧Ｗ尤核惴ㄊ窃谟嬎阃炅Ｗ铀俣戎笤俑铝Ｗ拥奈恢茫倪M算法則是計算粒子速度的同時更新粒子的位置。文中還引入自適應慣性權(quán)重的改進策略，使粒子在開始時慣性速度大，能快速的向最優(yōu)值

4、點運動，而在粒子迭代過程中慣性速度越來越小，從而使粒子能更好的接近最優(yōu)值點。引入罰函數(shù)，把約束優(yōu)化問題轉(zhuǎn)化為無約束優(yōu)化問題來解，從而減化求解過程。本文用實例對基本的粒子群算法和改進粒子群算法進行了對比分析，并得出了改進算法確實存在優(yōu)勢的結(jié)論。文中還對算法的主要參數(shù)如何取值進行了分析，并結(jié)合經(jīng)驗給出了總結(jié)。本文最后用實例驗證了算法確實在執(zhí)行了若干次迭代后收斂。程序的編程環(huán)境為MicrosoftVisualStudio2008編程語言為C#

5、。關(guān)鍵詞：粒子群算法最短路徑約束優(yōu)化慣性權(quán)重3n種群是n個粒子組成的群落（粒子允許重復），簡稱粒子群。N稱為粒子群規(guī)模Sn＝p|pi=(xi1xi2……xij……xid)in為n種群空間。?定義定義3：（個性算子）：（個性算子）粒子在d維解空間搜索的過程中，下一步的飛翔速度和到達的位置與粒子自身的飛翔速度有關(guān)，即V(t1)=wV(t)該操作稱為個性算子。定義定義4：（自意識算子）：（自意識算子）粒子在d維解空間搜索過程中，下一步的飛翔速

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

7、達的位置與粒子群到當前為止所到達的最好位置有關(guān)。也就是說，粒子在d維解空間搜索過程中受粒子群的經(jīng)歷影響，在整個飛翔過程中一直下意識得根據(jù)粒子群的經(jīng)驗調(diào)整飛行速度和方向，即Vij(t1)=c2U(01)(Xij(t)Xij(t))(22)該操作算子稱為群意識算子。C2是正常數(shù)，稱為群意識學習因子；U(01)是[01]區(qū)間正態(tài)分布的隨機數(shù)。定義定義6：（粒子種群多樣性）：（粒子種群多樣性）粒子群中的粒子因在解空間飛行所到達的位置不同而搜索到