粒子群算法解最短路徑

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

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

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

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

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

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

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