交通路徑搜索系統及方法
2023-06-05 21:33:46
專利名稱：交通路徑搜索系統及方法
技術領域：
本發明涉及一種交通路徑搜索系統及方法，特別是涉及一種基於蟻群算法的不確定環境的交通路徑搜索系統及方法。
背景技術：
傳統的交通最短路徑的選擇往往是城市任意兩個地點的最短路徑，而駕駛員需要搜尋的是行駛時間最短的路徑。現實生活中行駛長度最短的路徑不一定就是行駛時間最短的路徑，因為隨時都有可能出現交通阻塞等意外情況，路網交通狀態具有實時可變的特點， 具有不確定性的因素。根據這種情況，當前最常見的做法是把交通路網節點和節點之間的距離描述成模糊變量的形式，該模糊變量符合某種隸屬函數的分布，建立模糊期望值模型求解模糊最短路徑問題。由於一般模糊變量其隸屬函數的形式是多種多樣的，對於有些模糊變量來說，很難求出其具體的期望值，因此只能採用一些智能算法來進行求解，當前最常使用的則為遺傳算法。遺傳算法來源於達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說，其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優解的算法。它模擬了自然選擇和自然遺傳過程中發生的繁殖、交配和變異現象，根據適者生存、優勝劣汰的自然法則，通過選擇、交叉和變異等遺傳算子，使群體一代一代地進行到搜索空間中越來越好的區域，直至獲得最優解。遺傳算法有三個基本算子選擇、交叉和變異。遺傳算法的編程實現比較複雜，首先需要對問題進行編碼，找到最優解之後還需要對問題進行解碼，另外三個算子的實現也有許多參數，如交叉概率和變異概率，並且這些參數的選擇嚴重影響解的品質，而目前這些參數的選擇大部分是依靠經驗。由於遺傳算法的主要特點是群體搜索策略和群體中個體間的隨機信息交換，搜索不依賴於梯度信息。使用遺傳算法求解問題，需要考慮下面5個基本要素(1)對參數進行編碼；(2)設定初始種群大小；( 適應度函數的設計；(4)遺傳操作設計；( 控制參數設定包括種群大小、最大進化代數、交叉概率、變異概率等。用遺傳算法求解問題容易出現 「早熟」現象。綜上所述，可知先前技術交通路徑搜索方法中採用遺傳算法存在編成複雜、求解問題容易出現早熟現象的問題，因此實有必要提出改進的技術手段，來解決此一問題
發明內容
為克服上述現有技術存在的不足，本發明的主要目的在於提供一種交通路徑搜索系統及方法，其通過採用蟻群算法解決交通路徑搜索的優化問題，具有實現簡單，收斂速度快，魯棒性好的優點，能更快地搜索到交通網絡的最短路徑。為達上述及其它目的，本發明提供一種交通路徑搜索系統，至少包括模糊期望值模型建立模組，通過將交通路網節點與節點之間的距離描述成模糊變量的形式，建立模糊期望值模型；以及最短路徑計算模組，根據獲得的模糊期望值模型利用蟻群算法計算獲得交通路網 節點和節點之間的最短路徑和長度。進ー步地，該模糊期望值模型為，
權利要求
1.一種交通路徑搜索系統，至少包括模糊期望值模型建立模組，通過將交通路網節點與節點之間的距離描述成模糊變量的形式，建立模糊期望值模型；以及最短路徑計算模組，根據獲得的模糊期望值模型利用蟻群算法計算獲得交通路網節點和節點之間的最短路徑和長度。
2.如權利要求1所述的交通路徑搜索系統，其特徵在於，該模糊期望值模型為，
3.如權利要求2所述的交通路徑搜索系統，其特徵在於，該最短路徑計算模組至少包括初始化模組，用於初始化蟻群；轉換概率計算模組，用於從起始點開始，對所有螞蟻根據一轉換概率搜索下一個節點， 直至所有螞蟻都到達目的節點；更新模組，用於根據一更新模型更新每隻螞蟻從起點到終點所選路徑上的信息素； 全局極值計算模組，用於根據該糊期望值模型計算出螞蟻的期望值，並根據該目標值， 計算各螞蟻的適應度函數值，並於各螞蟻當前的適應度函數值比其歷史最優值好時，將當前的適應度函數值代替代其歷史最優值；判斷模組，根據一收斂規則判斷該全局極值計算模組所計算出結果是否為最優解；以及輸出模組，若滿足收斂規則，則輸出交通路網節點和節點之間的最短路徑及其長度。
4.如權利要求3所述的交通路徑搜索系統，其特徵在於該初始化模組初始化各條邊上的信息素濃度與邊啟發信息。
5.如權利要求4所述的交通路徑搜索系統，其特徵在於，該轉換概率為P^it) =. ,j e allowedΣjg allowed0其他其中，α表示信息素的相對重要性，α >0，β表示啟發信息的相對重要性，β彡0，τ u(t)為t時刻連接節點i到節點j的邊上的信息素濃度，為邊啟發信息， ι7Iv = '"7Z"其中，dij表示節點i和節點j之間的距離，dJn表示節點j到終點η之間的直線距離。
6.如權利要求5所述的交通路徑搜索系統，其特徵在於，該更新模型為 τ Jj (t+m) = P τ υ (t) + Δ τ (t+m)其中，Δ、.表示螞蟻k在時間段t到(t+m)的過程中，在i到j的邊上留下的殘留信息素濃度，參數P表示信息激素物質的保留率。
7.如權利要求6所述的交通路徑搜索系統所述的交通路徑搜索系統，其特徵在於該更新模型根據信息素更新策略的不同，採用如下模型, ^1/《，如果螞蟻經過//+ 、jo,如果螞蟻Λ不經過々+其中Ql是常量，信息素的增量與節點i與節點j之間的距離有關。
8.如權利要求3所述的交通路徑搜索系統所述的交通路徑搜索系統，其特徵在於，該適應度函數值為J(X1) =——-—— E[f (X,C)]
9.如權利要求3所述的交通路徑搜索系統所述的交通路徑搜索系統，其特徵在於該收斂規則可以預設的循環次數。
10.一種交通路徑搜索方法，包括如下步驟將交通路網節點和節點之間的距離描述成模糊變量的形式，建立模糊期望值模型； 初始化蟻群；將所有螞蟻置於起始點，對所有螞蟻根據一轉換概率選擇下一個節點，直至所有螞蟻都到達目的節點；根據一更新模型更新每隻螞蟻從起點到終點所選路徑上的信息素； 根據該模糊期望值模型模擬計算螞蟻的期望值，根據該期望值計算各螞蟻的適應度函數值，並於各螞蟻當前的適應度函數值比其歷史最優值好時，將當前的適應度函數值代替代其歷史最優值；根據一收斂規則判斷所計算出的適應度函數值是否為最優解；以及若滿足該收斂規則，則輸出交通路網節點和節點之間的最短路徑及其長度。
11.如權利要求10所述的交通路徑搜索系統所述的交通路徑搜索方法，其特徵在於 若不滿足該收斂規則，則轉至該將所有螞蟻置於起始點，對所有螞蟻根據一轉換概率選擇下一個節點，直至所有螞蟻都到達目的節點的步驟。
12.如權利要求10所述的交通路徑搜索系統所述的交通路徑搜索方法，其特徵在於該初始化蟻群的步驟為初始化各條邊上的信息素濃度與邊啟發信息。
全文摘要
本發明公開了一種交通路徑搜索系統及方法，該系統至少包括模糊期望值模型建立模組，通過將交通路網節點與節點之間的距離描述成模糊變量的形式，建立模糊期望值模型；以及最短路徑計算模組，根據獲得的模糊期望值模型利用蟻群算法計算獲得交通路網節點和節點之間的最短路徑和長度，本發明通過採用蟻群算法解決交通路徑搜索的優化問題，具有實現簡單，收斂速度快，魯棒性好的優點，能更快地搜索到交通網絡的最短路徑。
文檔編號G06F17/30GK102521391SQ201110436928
公開日2012年6月27日 申請日期2011年12月22日 優先權日2011年12月22日
發明者寧建紅 申請人:上海電機學院