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

無效

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

1.一種計算機實現的基于遺傳算法的多模式多標準交通路徑搜索方法，其特征在于主要包括以下步驟：

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

(2)多模式交通路徑編碼：

其中，定義所述編碼為：采用帶模式標識的不定長表現型編碼，由模式標記區與ID編碼區組成，形如：

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

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

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

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

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

(a)算法環境初始化，轉(b)；

(b)種群初始化，轉(c)；

(c)對初始種群進行模式間交叉算子運算，補充不完全解為完全解，轉(d)；

(d)判斷是否達到最大進化代數，若“是”轉(i)，若“否”轉(d)；

(e)計算評價值，轉(f)；

(f)對當前種群進行模式內交叉算子、模式間交叉算子、模式內變異算子和模式間變異算子運算，生成新個體記錄入下一代種群，轉(g)；

(g)對當前種群進行選擇算子運算，生成新個體記錄入下一代種群，轉(h)；

(h)新種群代替當前種群，進化代數加1，轉(d)；

(i)計算評價值，結束；

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

輸出最后一代進化種群中非重復的個體，并以某一種標準為主，依次排列輸出，該結果集合即為推薦最優路徑結果，輸出集合中的每一個個體即為一種推薦路徑方案；輸出形式包括但不局限于：文字描述、圖形路徑、語音播報等。

2.根據權利要求1所述的計算評價值，其特征在于：依據最優化理論按優劣對所有個體進行排序，其中設評價向量為f＝(C₁，C₂，...，C_n)，其中C_i表示個體在第i種標準下的耗費計算值，則評價函數為F＝ParetoRank(f)。

3.根據權利要求2所述的種群初始化，其特征在于：在各單模式環境下分別生成初始個體，再合并組成初始種群，其特點是個體為單模式并且允許不完全解。

4.根據權利要求3所述的補充不完全解為完全解，其特征在于：對于一不完全解個體，隨機選擇另一個完全解個體，進行模式間交叉算子運算，用新生成的完全解個體代替原不完全解個體。

5.根據權利要求4所述的模式間交叉算子，其特征在于：交叉點發生在不同模式中，即先確定個體1與個體2的交叉模式M，N，在相應模式中尋找可交叉基因，根據選取的可交叉基因對進行交叉，交叉時應補齊模式標識。

6.根據權利要求5所述的模式間變異算子，其特征在于：變異點發生在不同模式中，采用定向變異策略，以達到加速優秀個體產生的目的。

7.權利要求6所述選擇算子，其特征在于：根據新種群當前個體數G’和定義種群大小G確定選擇算子選擇的個體數量X；

X＝G-G’，其中G’＝G_crossover+G_mutation+G_{hypercrossover}+G_{hypermutation}

Max{G_crossover}＝G×P_crossover

Max{G_mutation}＝G×P_mutation

Max{G_{hypercrossover}}＝G×P_{hypercrossover}

Max{G_{hypermutation}}＝G×P_{hypermutation}

G_crossover、G_mutation、G_{hypercrossover}與G_{hypermutation}分別代表相應算子生成的新個體數目；

然后依次在評價值最小的種群中確定非重復個體，直至達到選擇目標個數。