[發明專利]遺傳算法與MapReduce相結合的車輛調度方法

有效

• 申請號: 201310387759.5
• 申請日: 2013-08-31
• 公開（公告）號: CN103440522A
• 公開（公告）日: 2013-12-11
• 發明（設計）人: 鄭湘涵;陳國龍;陳李瑩
• 申請（專利權）人: 福州大學
• 主分類號: G06N3/12
• 分類號: G06N3/12;G06Q10/06
• 代理公司: 福州元創專利商標代理有限公司 35100
• 代理人: 蔡學俊

1.一種遺傳算法與MapReduce相結合的車輛調度方法，其特征在于，對于采用m輛車配送n個客戶點的問題，基于云計算中的MapReduce模型和遺傳算法，按如下步驟進行車輛調度：

（1）初始化種群：采用自然數{1,2,…,n}對n個客戶點進行對應編碼，并隨機編成一條長度為n、自然數{1,2,…,n}前后順序隨機排列的染色體個體，然后根據載重約束在染色體個體中插入分隔符，所述載重約束為分隔符之間的所有編碼對應的客戶點的配送量之和不大于車輛載重量；設種群規模為P，則通過上述方法隨機產生P個染色體個體，即形成規模為P的初始種群；

（2）計算個體適應度：利用根據適應度函數構造的多個Map函數，并行計算P個染色體個體的個體適應度，并將結果輸出給Reduce函數；

（3）進行選擇、雜交、變異操作：利用根據選擇、雜交、變異算法構造的Reduce函數，將Map函數的輸出作為Reduce函數的輸入，利用Reduce函數將父代染色體中適應度較高的個體選擇出來產生子代染色體，然后以一雜交概率隨機選擇子代染色體中一部分進行雜交操作并將雜交后染色體個體添加到新種群中，以一變異概率隨機選擇子代染色體中另一部分進行變異操作并將變異后染色體個體添加到新種群中，子代染色體中的剩余部分直接復制到新種群中，從而形成新種群并輸出；

（4）判斷算法是否達到設定的最大遺傳代數，是則選出適應度最高的染色體個體所對應的路徑集合作為問題的最優解，否則返回步驟（2）。

2.根據權利要求1所述的遺傳算法與MapReduce相結合的車輛調度方法，其特征在于，步驟（3）中，Reduce函數采用輪盤賭算法進行選擇操作：計算P個染色體個體的相對適應度，以之作為概率，并按概率大小將[0,1]空間劃分成P份，然后再生成一個[0,1]范圍內的隨機數，落在哪個區域則選擇對應的染色體個體；按上述方法重復P次，產生P個染色體個體，得到子代染色體。

3.根據權利要求1所述的遺傳算法與MapReduce相結合的車輛調度方法，其特征在于，步驟（3）中，Reduce函數按如下方法進行雜交操作：隨機在一對染色體個體A、B中選擇一個交配區域，將個體B的交配區域加到個體A的前面，個體A的交配區域加到個體B的前面，然后分別刪除原個體中與交配區域相同的自然數并根據載重約束重新在染色體個體中插入分隔符，得到一對雜交后染色體個體C、D。

4.根據權利要求1所述的遺傳算法與MapReduce相結合的車輛調度方法，其特征在于，步驟（3）中，Reduce函數按如下方法進行變異操作：隨機在染色體產生兩個基因位，將所述兩個基因位上的自然數進行互換，然后根據載重約束重新在染色體個體中插入分隔符，得到變異后染色體個體。