0 引言

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

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

1 背景知識

　　1.1 MapReduce模型

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

　　1.2 并行遺傳算法

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

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

　　1.3 禁忌搜索算法

　　禁忌搜索算法TSA是由F.Glover在1986年首次提出的，是一種全局尋優(yōu)算法。從TSA過程可以看出，其主要因素包括禁忌列表、禁忌長度、候選集、藐視規(guī)則、終止規(guī)則。其中禁忌列表是影響TSA質(zhì)量的主要因素之一。禁忌長度是被禁忌的解不能訪問的步數(shù)。候選集由大量當(dāng)前解的鄰居組成。藐視規(guī)則是確保搜索過程可以釋放特定的解，進而保證當(dāng)所有候選解被禁忌或某一禁忌解比當(dāng)前最優(yōu)解要好時能夠?qū)ふ业礁玫娜肿顑?yōu)解。終止規(guī)則規(guī)定算法進行一定步數(shù)后停止。TSA的流程圖如圖2所示。

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

　　2.1 編碼規(guī)則

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

　　采用基因表示路網(wǎng)節(jié)點，而染色體則表示路徑。由于采用了實數(shù)編碼方式，染色體會隨基因變化而變化，所以做出如下規(guī)定來避免環(huán)路現(xiàn)象[10]：

　?。?）每個基因最多出現(xiàn)一次；

　　（2）染色體長度不能超過節(jié)點個數(shù)；

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

　　2.2 適應(yīng)度函數(shù)

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

　　其中N為所選路徑的節(jié)點個數(shù)，?仔為所選路徑節(jié)點的集合，l為所選路徑的標簽。根據(jù)最短路徑求解問題，可定義適應(yīng)度函數(shù)為：

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

　　2.3 遺傳算子

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

　　其中M為種群的大小。

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

　　2.4 藐視規(guī)則

　　對于被禁忌的個體，被搜索一次后其禁忌次數(shù)減去1；對于經(jīng)常被搜索的個體，設(shè)定一定的數(shù)值，搜索一次加1，超過一定數(shù)值后該個體被禁忌。

　　2.5 方法的步驟和流程圖

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

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

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

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

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

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

　　(6)根據(jù)終止規(guī)則進行終止判定，當(dāng)達到最大迭代步數(shù)或者得到某一穩(wěn)定的解時算法停止，否則轉(zhuǎn)至步驟(2)。

3 仿真實驗與性能分析

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

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

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

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

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

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

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

4 結(jié)束語

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

　　參考文獻

　　[1] 林闖，蘇文博，孟坤，等.云計算安全：架構(gòu)、機制與模型評估[J].計算機學(xué)報，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] 焦翠珍，戴文華.基于混合并行遺傳算法的多目標約束優(yōu)化技術(shù)研究[J].沈陽農(nóng)業(yè)大學(xué)學(xué)報，2006，37(1)：125-127.

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

　　[5] 李想，魏加華，傅旭東.粗粒度并行遺傳算法在水庫調(diào)度問題中的應(yīng)用[J].水力發(fā)電學(xué)報，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] 鄔開俊，魯懷偉.云環(huán)境下基于DPSO的任務(wù)調(diào)度算法[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] 楊慶芳，梅朵，鄭黎黎，等.基于云計算的城市路網(wǎng)最短路徑遺傳算法求解[J].華南理工大學(xué)學(xué)報(自然科學(xué)版)，2014，42(3)：47-51，58.