基于遺傳算法的多源多目路徑規(guī)劃問題研究.pdf

1、隨著人們消費(fèi)水平的不斷提高，汽車數(shù)量的快速增加與道路建設(shè)遲緩之間的矛盾日益凸顯，嚴(yán)重制約著社會(huì)與經(jīng)濟(jì)的可持續(xù)和諧發(fā)展，解決交通阻塞問題已經(jīng)迫在眉睫。合理高效的路徑規(guī)劃是解決交通堵塞問題的有效途徑之一。傳統(tǒng)的路徑規(guī)劃算法在搜索單源最短路徑等簡(jiǎn)單最優(yōu)路徑時(shí)是可行和高效的，但對(duì)于解決復(fù)雜交通網(wǎng)絡(luò)問題，進(jìn)行顧及全局優(yōu)化的多源多目最優(yōu)多路徑規(guī)劃時(shí)還不能直接應(yīng)用，存在遍歷搜索時(shí)間長(zhǎng)、效率較低等諸多問題。遺傳算法作為一種智能算法具有并行搜索和全局優(yōu)化

2、的優(yōu)勢(shì)，成為快速解決多源多目復(fù)雜路徑規(guī)劃問題的潛在有效手段。因此，論文開展了基于遺傳算法的復(fù)雜路徑規(guī)劃問題研究，研究分析了利用遺傳算法解決單源和多源多目標(biāo)路徑規(guī)劃的算法設(shè)計(jì)和基本流程，并運(yùn)用網(wǎng)絡(luò)拓?fù)鋱D進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證遺傳算法解決多源多目路徑規(guī)劃問題的可行性和收斂性。主要研究?jī)?nèi)容如下:
　　(1)基于遺傳算法的單源最短路徑問題:采用基于路徑的編碼方式，設(shè)計(jì)基于遺傳算法的單源最短路徑算法，對(duì)初始種群進(jìn)行基于路徑的選擇、交叉、變異等遺

3、傳操作，解決網(wǎng)絡(luò)拓?fù)鋱D中給定兩點(diǎn)的路徑（或權(quán)值）最短問題，并將輪盤賭選擇與最優(yōu)選擇策略模型結(jié)合與單純輪盤賭方式進(jìn)行分析，解決遺傳算法未成熟收斂問題。
　　(2)基于遺傳算法的多源多目標(biāo)路徑規(guī)劃問題:將遺傳算法解決單源最短路徑問題的基本思路擴(kuò)展到解決多源多目路徑規(guī)劃問題上，提出了一種雙層遺傳算法模式。第一層在忽略通路承載量M的基礎(chǔ)上，利用遺傳算法針對(duì)各個(gè)源點(diǎn)到終點(diǎn)找到n條最短路徑;第二層引入重選擇算子和刪除算子對(duì)超過通路承載量M的線