0 引言

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

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

1 背景知識(shí)

　　1.1 MapReduce模型

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

　　1.2 并行遺傳算法

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

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

　　1.3 禁忌搜索算法

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

2 基于云計(jì)算的細(xì)粒度混合并行遺傳算法

　　2.1 編碼規(guī)則

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

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

　　（1）每個(gè)基因最多出現(xiàn)一次；

　?。?）染色體長(zhǎng)度不能超過(guò)節(jié)點(diǎn)個(gè)數(shù)；

　?。?）從每個(gè)染色體O開(kāi)始，D結(jié)束。

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

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

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

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

　　2.3 遺傳算子

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

　　其中M為種群的大小。

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

　　2.4 藐視規(guī)則

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

　　2.5 方法的步驟和流程圖

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

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)與性能分析

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

　　31個(gè)省會(huì)城市的仿真坐標(biāo)為：[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，禁忌長(zhǎng)度取值21，候選子集個(gè)數(shù)為200。交叉概率Pc=0.85，變異概率Pm=0.01。為了使得實(shí)驗(yàn)結(jié)果更加合理，進(jìn)行50次仿真，取其平均值。

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

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

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

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

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

4 結(jié)束語(yǔ)

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

　　參考文獻(xiàn)

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

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

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