必經(jīng)點(diǎn)K短路徑蛙跳算法研究.pdf

1、最短路徑問題是圖論的經(jīng)典問題,其廣泛應(yīng)用于網(wǎng)絡(luò)科學(xué)、路徑規(guī)劃、計(jì)算機(jī)科學(xué)等領(lǐng)域,是科學(xué)領(lǐng)域多個(gè)學(xué)科的重要理論支撐,是工程領(lǐng)域解決方案的理論摹礎(chǔ),隨著現(xiàn)實(shí)需求的日益增加,對路徑問題的約束條件也隨之增加,因而必經(jīng)點(diǎn)K短路徑問題的解決日益重要。
　　必經(jīng)點(diǎn)K短路徑即在網(wǎng)絡(luò)中包含必經(jīng)點(diǎn)的多條最短路徑,日前在GPS導(dǎo)航,路線規(guī)劃,路由器應(yīng)剛等方面應(yīng)用逐漸廣泛,必經(jīng)點(diǎn)K短路徑問題是傳統(tǒng)最短路徑問題的泛化,因而對該問題的研究更具有實(shí)際意義與一般

2、性意義。
　　目前處理必經(jīng)點(diǎn)K短路徑問題的方法小多,并且已有方法耗時(shí)多、算法復(fù)雜、網(wǎng)絡(luò)依賴性強(qiáng)、求解最優(yōu)解的性能不夠好等問題。如何快速、準(zhǔn)確的求解必經(jīng)點(diǎn)K短路徑問題是當(dāng)前路徑問題的一個(gè)急需解決的問題。
　　混合蛙跳算法作為新興的群智能算法,其結(jié)合了粒子群算法的群體協(xié)作進(jìn)化機(jī)制的特點(diǎn)與遺傳算法的模因交換的特點(diǎn),保證了快速收斂性質(zhì)的同時(shí)提高了求解的多樣性,因而采用混合蛙跳算法求解必經(jīng)點(diǎn)K短路徑問題在改善傳統(tǒng)算法對于耗時(shí)和求解多樣

3、性方面會具有較好的效果。
　　本文旨在利用混合蛙跳算法針對必經(jīng)點(diǎn)K短路徑問題進(jìn)行建模,通過改變算法的編碼、種群初始化、蛙跳算予等各個(gè)環(huán)節(jié),在分析必經(jīng)點(diǎn)路徑存在性的前提條件卜_,針對必經(jīng)點(diǎn)保序條件的不同,使得算法針對該問題的求解具有良好的適配性。因而能在較短時(shí)間內(nèi)求解優(yōu)良的最優(yōu)解集,并同時(shí)提高了算法的穩(wěn)定性。
　　本文同時(shí)分析了當(dāng)前隨機(jī)路徑生成算法并對傳統(tǒng)的隨機(jī)路徑生成算法在生成含必經(jīng)點(diǎn)隨機(jī)路徑時(shí)的低成功率弊端給予了分析與總結(jié)