0 引言

　　近年來隨著社會的發展和人們生活節奏的加快，高效率、快節奏需求使得最短路徑求解成為一大新的研究課題。云計算是繼網格計算、對等計算之后產生的新的計算模式[1]，其中Apache開發的Hadoop云計算平臺被廣泛應用，其核心MapReduce能夠進行并行編碼，且編碼效率高，為大規模的最短路徑求解提供了有效的解決途徑。遺傳算法[2-3]（Genetic Algorithm，GA）由于具有潛在并行處理能力的特點，許多學者致力于并行遺傳算法的研究，以提高搜索和尋優的速率，同時克服GA在進化初期超常個體引起的種群過早收斂到局部最優解的問題[4-5]。為提高GA的局部搜索能力，許多學者也將GA與其他算法結合，研究了混合遺傳算法。其中禁忌搜索算法（Tabu Search Algorithm，TSA）的創始人將GA與TSA結合提出了混合遺傳算法HGA（Hybrid Genetic Algorithm），HGA提高了算法的局部搜索能力和收斂速度，得到了廣泛研究與應用[6-7]。同時混合遺傳算法在并行遺傳算法中也得到了一定研究，文獻[3]將并行遺傳算法和禁忌搜索算法結合，提出了混合并行遺傳算法（Hybrid parallel genetic algorithm，HPGA），由于算法利用并行遺傳算法的特征，提高了算法效率。

　　針對上述研究基礎，本文在云計算中的MapReduce并行編碼模式基礎上，提出一種基于細粒度混合并行遺傳算法的最短路徑求解方法。算法將細粒度并行遺傳算法與禁忌搜索算法相結合，提高算法的局部尋優能力和收斂速度，進而應用到提高最短路徑的求解效率的領域，具有重要意義。

1 背景知識

　　1.1 MapReduce模型

　　MapReduce是一種開源模型，適用于處理大規模數據，并對并行模型通信問題進行了很好的處理。其主要由Map函數和Reduce函數組成，其中Map函數將任務分割為多個小任務，通過相應的任務調度分配給分布在各地的計算機，再通過Reduce操作獲得最終結果。其具體工作流程見文獻[8]。

　　1.2 并行遺傳算法

　　并行遺傳算法分為主從式模型、粗粒度模型、細粒度模型等[9]。細粒度并行遺傳算法是在群體中的每個個體分配一個處理單元，相互獨立地采用GA執行進化，然后從進化后的個體中獲得最優解。

　　GA的主要因素包括參數編碼、初始種群設置、適應度函數、遺傳操作設計和控制參數設置。其流程圖如圖1所示。

　　1.3 禁忌搜索算法

　　禁忌搜索算法TSA是由F.Glover在1986年首次提出的，是一種全局尋優算法。從TSA過程可以看出，其主要因素包括禁忌列表、禁忌長度、候選集、藐視規則、終止規則。其中禁忌列表是影響TSA質量的主要因素之一。禁忌長度是被禁忌的解不能訪問的步數。候選集由大量當前解的鄰居組成。藐視規則是確保搜索過程可以釋放特定的解，進而保證當所有候選解被禁忌或某一禁忌解比當前最優解要好時能夠尋找到更好的全局最優解。終止規則規定算法進行一定步數后停止。TSA的流程圖如圖2所示。

2 基于云計算的細粒度混合并行遺傳算法

　　2.1 編碼規則

　　傳統的GA采用二進制編碼的形式表述實際應用問題，但存在計算量大和精度受限的缺陷。為表述直觀清晰且能克服上述缺陷，本文采用實數編碼方式對最短路徑求解問題進行編碼，且此種方式不用解碼。

　　采用基因表示路網節點，而染色體則表示路徑。由于采用了實數編碼方式，染色體會隨基因變化而變化，所以做出如下規定來避免環路現象[10]：

　　（1）每個基因最多出現一次；

　　（2）染色體長度不能超過節點個數；

　　（3）從每個染色體O開始，D結束。

　　2.2 適應度函數

　　適應度函數是對染色體適應能力度量的函數，是對自然界中優勝劣汰原則的模仿，而適應度值體現了染色體的優劣程度。在城市路網最短路徑求解問題中，路徑長度最短的方法是最優解。設定義節點i與節點j之間路徑長度為L(i，j)，由某一節點m到節點n的總路徑長度可定義為：

　　其中N為所選路徑的節點個數，?仔為所選路徑節點的集合，l為所選路徑的標簽。根據最短路徑求解問題，可定義適應度函數為：

　　由式(2)可以看出，路徑長度越小，其適應度值就越大，故其最優解即為所要求的最短路徑。

　　2.3 遺傳算子

　　首先對個體選擇策略進行闡述，個體選擇對于算法的整體性能影響較大，個體選擇得好，能夠將優秀基因遺傳下去；個體選擇得不好，算法的尋優能力就會下降。本文采用種群進化常用的輪盤賭法選擇優秀個體，按照適應度值計算對應的概率分布，然后將當前種群中的個體依概率復制到新的種群中，進而提高平均適應度。其概率分布的計算如下所示：

　　其中M為種群的大小。

　　遺傳雜交算子方面，選擇單點雜交，按照設定的概率Pc進行。同時變異方面按照設定的概率Pm進行。

　　2.4 藐視規則

　　對于被禁忌的個體，被搜索一次后其禁忌次數減去1；對于經常被搜索的個體，設定一定的數值，搜索一次加1，超過一定數值后該個體被禁忌。

　　2.5 方法的步驟和流程圖

　　通過上面的描述，本文基于云計算的細粒度混合并行遺傳算法求解最短路徑方法的流程圖如圖3所示，其步驟可概括如下：

　　(1)初始化，對每個個體分配一個處理單元，設置GA和TSA的各項參數；

　　(2)調用云計算平臺中的MapReduce的Map函數定義每個個體的值，每個處理單元對個體進行適應度評估，并將結果存儲HDFS文件；

　　(3)處理單元讀取中間文件位置并傳送給Reduce，然后Reduce到相應位置的DataNode上讀取，完成個體的選擇操作；

　　(4)進行交叉變異操作，同時將結果寫入HDFS文件系統；

　　(5)利用禁忌搜索算法TSA進行尋優，獲取局部尋優更好的解；

　　(6)根據終止規則進行終止判定，當達到最大迭代步數或者得到某一穩定的解時算法停止，否則轉至步驟(2)。

3 仿真實驗與性能分析

　　為了驗證本文所提出的基于云計算細粒度混合并行遺傳算法的有效性，針對全國31個省會城市的旅行商(Traveling Salesman Problem，TSP)問題進行研究。仿真的環境為：Java語言編程，采用云計算平臺的MapReduce編程模式，計算機處理器的主頻為2.80 GHz、內存為4 GB，且采用操作系統Windows XP版本。

　　31個省會城市的仿真坐標為：[1304 2312; 3639 1315; 4177 2244; 3712 1399; 3488 1535; 3326 1556; 3238 1229; 4196 1044; 4312 790; 4386 570; 3007 1970; 2562 1756; 2788 1491; 2381 1676; 1332 695; 3715 1678; 3918 2179; 4061 2370; 3780 2212; 3676 2578; 4029 2838; 4263 2931; 3429 1908; 3507 2376; 3394 2643; 3439 3201; 2935 3240; 3140 3550; 2545 2357; 2778 2826; 2370 2975]。

　　初始種群設置為20，禁忌長度取值21，候選子集個數為200。交叉概率Pc=0.85，變異概率Pm=0.01。為了使得實驗結果更加合理，進行50次仿真，取其平均值。

　　首先在最大迭代次數為500情況下進行仿真，對比算法分別為典型的GA算法和細粒度并行GA算法，各種算法的性能見表1。

　　從表1可以看出，在平均迭代次數方面，典型GA算法比細粒度并行GA算法和云計算細粒度混合并行GA算法要大，即后兩者的尋優能力要優于前者，同時本文的尋優算法具有最好的尋優能力；在最大迭代次數500次的限制下，由于局部尋優能力等因素的影響，典型GA算法會有較多的次數得不到最優解，而細粒度并行GA算法的效果要好，本文所提出的云計算細粒度混合并行GA算法采用了TSA提高局部搜索能力，故每次都能得到最優解，其在收斂概率上要優于前兩者；在計算時間方面，典型GA算法采用串行的方式進行尋優，其計算時間最大，而采用并行方式的GA算法，其平均耗時得到了顯著提高。

　　其次，在最大迭代次數變化條件下對3個算法的適應度值進行分析。其他參數設置不變，最大迭代次數從100～1 000取值，步長為100。

　　從圖4可以看出，細粒度并行遺傳算法的適應度值要高于典型GA算法，而本文的云計算細粒度混合并行遺傳算法的適應度值要優于前兩者。

　　以上仿真可以看出，在云計算編程模型下，采用并行計算的方式可以有效提高遺傳算法的計算速度，而將遺傳算法與禁忌搜索算法TSA混合，可進一步提高尋優算法的局部搜索能力，進而提高整體的尋優效率。該實驗驗證了本文的云計算環境下的細粒度混合并行遺傳算法的有效性和正確性。

4 結束語

　　本文針對最短路徑求解問題，采用了云計算中的MapReduce模型，同時對細粒度并行遺傳算法和TSA進行了分析，提出了一種基于云計算的細粒度混合并行遺傳算法，并將其應用于分布式旅行商問題。尋優算法結合了并行遺傳算法和禁忌搜索算法的優點，提高了全局和局部尋優能力，同時采用MapReduce模型提高了編程的效率。仿真實驗結果驗證了方法的有效性，證明該方法是一種較好的最短路徑求解方法。

　　參考文獻

　　[1] 林闖，蘇文博，孟坤，等.云計算安全：架構、機制與模型評估[J].計算機學報，2013，36(9)：1765-1784.

　　[2] MA P，TIAN M，YANG M.An improved genetic algorithm[C].2010 First International Conference on Pervasive Computing，Signal Processing and Applications，2010：977-980.

　　[3] 焦翠珍，戴文華.基于混合并行遺傳算法的多目標約束優化技術研究[J].沈陽農業大學學報，2006，37(1)：125-127.

　　[4] 嚴曉明.粗粒度并行遺傳算法遷移算子的一種改進[J].福建師范大學學報：自然科學版，2013，29(1)：42-47.

　　[5] 李想，魏加華，傅旭東.粗粒度并行遺傳算法在水庫調度問題中的應用[J].水力發電學報，2012，31(4)：28-33.

　　[6] AZZOUZ A，ENNIGROU M，JLIFI B，et al.Combining tabu search and genetic algorithm in a multi-agent system for solving flexible job shop problem[C].Eleventh Mexican International Conference on Artificial Intelligence：Advances in Artificial Intelligence and Applications，2012：83-88.

　　[7] TONGPANG J，TANTATSANAWONG P.An application of tabu search algorithms and genetic algorithms in collabora-tive logistucs optimization[C].2011 Annual SRII Global Conference，2011：699-706.

　　[8] 鄔開俊，魯懷偉.云環境下基于DPSO的任務調度算法[J].計算機工程，2014，40(1)：59-62.

　　[9] BRUNETTI A.A fast fine-grained genetic algorithm for spectrum fitting: An application to X-ray spectra[J].Com-puter Physics Communications，2013，184(2013)：573-578.

　　[10] 楊慶芳，梅朵，鄭黎黎，等.基于云計算的城市路網最短路徑遺傳算法求解[J].華南理工大學學報(自然科學版)，2014，42(3)：47-51，58.