[發明專利]交通路徑搜索系統及方法

在審

• 申請號: 201210434872.X
• 申請日: 2012-11-02
• 公開（公告）號: CN102902823A
• 公開（公告）日: 2013-01-30
• 發明（設計）人: 寧建紅
• 申請（專利權）人: 上海電機學院
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/12
• 代理公司: 上海思微知識產權代理事務所(普通合伙) 31237
• 代理人: 鄭瑋

技術領域

本發明涉及一種交通路徑搜索系統及方法，特別是涉及一種基于云遺傳算法的不確定環境的交通路徑搜索系統及方法。

背景技術

傳統的交通最短路徑的選擇往往是城市任意兩個地點的最短路徑，而駕駛員需要搜尋的是行駛時間最短的路徑?，F實生活中行駛長度最短的路徑不一定就是行駛時間最短的路徑，因為隨時都有可能出現交通阻塞等意外情況，路網交通狀態具有實時可變的特點，具有不確定性的因素。根據這種情況，當前最常見的做法是把交通路網節點和節點之間的距離描述成模糊變量的形式，該模糊變量符合某種隸屬函數的分布，建立模糊期望值模型求解模糊最短路徑問題。由于一般模糊變量其隸屬函數的形式是多種多樣的，對于有些模糊變量來說，很難求出其具體的期望值，因此只能采用一些智能算法來進行求解，當前最常使用的則為遺傳算法。

遺傳算法來源于達爾文的進化論、魏茨曼的物種選擇學說和孟德爾的群體遺傳學說，其基本思想是模擬自然界遺傳機制和生物進化論而形成的一種過程搜索最優解的算法。它模擬了自然選擇和自然遺傳過程中發生的繁殖、交配和變異現象，根據適者生存、優勝劣汰的自然法則，通過選擇、交叉和變異等遺傳算子，使群體一代一代地進行到搜索空間中越來越好的區域，直至獲得最優解。

遺傳算法有三個基本算子：選擇、交叉和變異。這三個算子的實現也有許多參數，如交叉概率和變異概率，并且這些參數的選擇嚴重影響解的品質，而目前這些參數的選擇大部分是依靠經驗。遺傳算法善長全局搜索，然而其局部搜索能力卻明顯不足，搜索到最優解或滿意解的速度太慢，存在易陷入局部最優解和選擇壓力過大造成的早熟收斂等問題。

發明內容

為克服上述現有技術存在的不足，本發明的主要目的在于提供一種交通路徑搜索系統及方法，其將云模型與遺傳算法相結合，利用了正態云模型的隨機性和穩定傾向性的特點，實現了不確定環境下交通最短路徑的選擇，本發明將云模型的Y條件云發生器算法實現交叉操作，基本云發生器算法實現變異操作，使概率值既具有傳統的趨勢性，滿足快速尋優能力，又具有隨機性，實現交叉概率和變異概率的自適應調整，從而提高了避免陷入局部最優的能力，能更快地搜索到交通網絡的最短路徑。

為達上述及其它目的，本發明一種交通路徑搜索系統，至少包括：

模糊期望值模型建立模組，通過將交通路網節點與節點之間的距離描述成模糊變量的形式，建立模糊期望值模型；以及

最短路徑計算模組，根據獲得的模糊期望值模型，通過建立云模型并利用云遺傳算法計算獲得交通路網節點和節點之間的最短路徑和長度。

進一步地，該模糊期望值模型為，

其中，為模糊變量，表示節點i到節點j的距離，設函數f(X,c~)=Σi=1nΣj=1nc~ijxij,]]>則期望值為：