[發明專利]一種基于遺傳算法的多模式多標準路徑選擇方法

無效

• 申請號: 201010185830.8
• 申請日: 2010-05-21
• 公開（公告）號: CN101853294A
• 公開（公告）日: 2010-10-06
• 發明（設計）人: 于海璁;陸鋒
• 申請（專利權）人: 中國科學院地理科學與資源研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30;G06N3/12
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術領域

本發明涉及一種交通路徑搜索方法，特別是一種計算機實現的基于遺傳算法的多模式、多標準交通路徑搜索方法，適用于公共出行服務應用。

背景技術

城市公共出行服務體系涵蓋公共汽車、出租車、地鐵、輕軌、自行車、步行等多種交通出行模式。多模式交通體系的建立與發展極大地豐富了公眾出行交通模式的選擇，同時也激發了個性化的出行需求。距離最短、時間最短、換乘最少、費用最低等單一評價標準已不能滿足多樣化的綜合出行需求。提供滿足出行者多種綜合需求的多標準出行路徑服務成為城市公共出行服務的研究熱點。

考慮多種標準的路徑搜索問題通常采用兩種方法。一種是加權法，即轉化多種標準為標量，采用線性加權求和等方法，為各種標準確定一個權重值，綜合后得到一個標量值，再利用現有單標準算法計算；另一種是約束法，即將k個標準中的k-1個標準轉換為約束條件，剩下一個標準作為單標準優化問題的目標函數。前者在各種標準權重值的確定上缺乏科學的理論基礎，并且不能在非凸性的均勻曲面上得到所有最優解；后者的結果主要依賴于被確定為目標函數的單標準，同樣依靠個人經驗，并且可能導致該單標準問題無解。

目前，隨著智能計算方法的不斷發展和完善，利用進化算法尤其是遺傳算法求解多標準優化問題取得了一些研究成果。這些成果為本發明提供了理論支持。然而，應用遺傳算法求解多模式多標準換乘路徑規劃問題的難點在于如何將路徑編碼成染色體。現有成果大多在單模式環境下進行，并且僅適用于小規模網絡。而現實世界的城市網絡多為大規模、多模式復雜環境，現存的研究成果無法解決這一問題。另外，遺傳操作算子要應用于多模式網絡環境，當前成果缺乏相應的模式間和模式內遺傳操作算子，因此不能直接應用于解決多模式交通體系下的多標準優化路徑搜索問題。

發明內容

本發明提供一種計算機實現的基于遺傳算法解決多模式多標準交通路徑搜索方法(交通路徑，下文簡稱為“路徑”)，該方法對遺傳算法進行擴展以適應多模式交通環境，采用遺傳算法和優化理論處理多標準優化路徑搜索，以解決現有公共出行服務技術無法提供多模式多標準路徑服務的問題，為公眾出行信息服務提供更好的技術支持。

本發明的技術解決方案：一種基于遺傳算法解決多模式多標準路徑搜索方法，其特征包括：

(1)輸入多模式交通網絡模型數據

(2)多模式路徑編碼

(3)模式內交叉、變異算子與模式間交叉、變異算子定義及其操作

(4)執行用于多模式路徑搜索的多標準遺傳算法

(5)推薦路徑結果集輸出

所述多模式交通網絡模型，是根據城市多種交通模式數據，利用地理信息系統空間分析技術，對城市多模式交通的網絡連通關系進行自動化處理，建立多模式一體化交通網絡模型。

所述多模式路徑編碼，即遺傳算法中的個體(Individual)編碼，就是將路徑以某種編碼方法表達出來。其中，多模式路徑要求個體編碼能夠體現多種交通模式組合，同時又不產生過多數據冗余；遺傳算法要求個體編碼易于遺傳算子操作。

因此，定義多模式個體編碼為：采用帶模式標識的不定長表現型編碼，由模式標記區與ID編碼區組成，形如：

Indivicual＝{T₁，I₁，...，I_j，T₂，I₁，...，I_k，T₃，...，T_m，...}

上式中，T_i為模式標識，I_i為各種出行模式(如：公共汽車、出租車、地鐵、輕軌、自行車、步行等)下的ID值。

所述模式內交叉、變異算子與模式間交叉、變異算子定義及其操作，是不同于傳統遺傳算法進化算子的新定義的進化算子。由于傳統遺傳算子針對的個體編碼是同質的(同類的)，也就是說各個位置的基因是同等重要的。但是在多模式路徑中，不同模式間的基因段之間是非同質的。因此，要求重新定義滿足多模式(多類型)特征的遺傳算子。遺傳算子通過對基因進行交叉、變異，生成新個體，即得到新路徑。

因此，定義crossover與mutation算子分別為模式內交叉與變異算子，即只在相同模式內(如：同在公交模式中)進行遺傳算子操作。定義hypercrossover與hypermutation算子分別為模式間交叉與變異算子，即只在不同模式間(如：公交模式--＞步行模式)進行遺傳算子操作。

上述模式內交叉與變異算子的特點是，不引入新的交通模式，即最大化控制換乘次數的增加。