基于MapReduce的量子蟻群算法

賈瑞玉，李亞龍

安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

基于MapReduce的量子蟻群算法

賈瑞玉，李亞龍

安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230601

1 引言

隨著信息和通信技術(shù)的快速發(fā)展，計(jì)算模式經(jīng)歷了把任務(wù)集中交付給大型處理機(jī)的模式，基于網(wǎng)絡(luò)的分布式任務(wù)處理的模式，發(fā)展到了按需處理的云計(jì)算[1]模式。許多智能算法可以在云計(jì)算系統(tǒng)實(shí)現(xiàn)分布式計(jì)算，從而充分利用云計(jì)算系統(tǒng)的強(qiáng)大計(jì)算能力。

蟻群算法最早由意大利學(xué)者Dorigo M于1991年提出，該算法具有較好的尋優(yōu)能力和較強(qiáng)的魯棒性，并成功地用于TSP求解、工件排序、背包問(wèn)題、車(chē)輛調(diào)度等多目標(biāo)組合優(yōu)化問(wèn)題[2-6]。量子進(jìn)化算法（QEA）[7]是KuK-Hyuan Han等人于2002年提出的，是一種基于量子理論的進(jìn)化算法。它吸收了量子計(jì)算[8]中的疊加態(tài)、相干性和糾纏性等思想，使得量子算法突破了傳統(tǒng)算法的極限，表現(xiàn)出更好的性能。該算法以其獨(dú)特的計(jì)算性能成為研究的熱點(diǎn)，引起國(guó)內(nèi)外眾多學(xué)者的研究興趣，并取得了許多研究成果。量子蟻群算法則將量子計(jì)算和蟻群算法相結(jié)合，把量子計(jì)算中的態(tài)矢量和量子旋轉(zhuǎn)門(mén)引入到蟻群算法中，采用量子旋轉(zhuǎn)門(mén)及最優(yōu)解對(duì)信息素更新，加快了算法的收斂速度并且避免了早熟收斂。量子蟻群算法已成功地求解出許多NP難題，文獻(xiàn)[9]使用量子蟻群算法對(duì)0-1背包問(wèn)題（0/1 knapsack problem）進(jìn)行求解，并用數(shù)值實(shí)驗(yàn)說(shuō)明了其有效性；文獻(xiàn)[10]分析了量子蟻群算法的優(yōu)缺點(diǎn)，提出一種新的量子蟻群算法用于求解旅行商問(wèn)題（Traveling Salesman Problem，TSP），并設(shè)計(jì)了一種量子交叉策略，避免搜索陷入局部最優(yōu)，進(jìn)一步提高了量子蟻群算法的性能。但量子蟻群算法對(duì)這些問(wèn)題的求解是在串行環(huán)境下進(jìn)行的，國(guó)內(nèi)尚沒(méi)有利用云計(jì)算將量子蟻群算法并行化的研究。

Google提出的MapReduce編程模型，允許用戶(hù)方便地在數(shù)據(jù)中心開(kāi)發(fā)分布式應(yīng)用程序，但是許多智能算法需要一種迭代的方式，并不遵循MapReduce的兩個(gè)階段的模式。文獻(xiàn)[11]提出了一個(gè)具有層次處理階段的MapReduce模型，可以自動(dòng)地使遺傳算法并行化。本文受此模型的啟發(fā)，將QACA與MapReduce結(jié)合，實(shí)現(xiàn)了QACA在云環(huán)境中的并行化，并應(yīng)用于0-1背包問(wèn)題的求解；實(shí)驗(yàn)結(jié)果證明了其有效性與可行性。

2 MapReduce并行計(jì)算編程模型

2.1 MapReduce模型簡(jiǎn)介

受函數(shù)式語(yǔ)言中的Map和Reduce函數(shù)的啟發(fā)，Google公司提出了MapReduce（映射-歸并算法）的抽象模型，該模型可以使用戶(hù)能夠輕松地開(kāi)發(fā)大型分布式應(yīng)用程序。在該模型中，每個(gè)Map函數(shù)是獨(dú)立的，并使用出現(xiàn)故障后重新執(zhí)行的容錯(cuò)機(jī)制，可以很容易地實(shí)現(xiàn)大型并行化計(jì)算。Apache開(kāi)源社區(qū)的Hadoop[12]項(xiàng)目用Java語(yǔ)言實(shí)現(xiàn)了該模型，同時(shí)也為云計(jì)算提供了一個(gè)開(kāi)源實(shí)現(xiàn)平臺(tái)。

MapReduce計(jì)算模型的核心是Map和Reduce兩個(gè)函數(shù)，這兩個(gè)函數(shù)均由用戶(hù)編寫(xiě)。Map函數(shù)對(duì)用戶(hù)輸入的鍵值對(duì)(k/ν)進(jìn)行計(jì)算并產(chǎn)生一系列中間鍵值對(duì)(k1/ν1)。MapReduce框架將關(guān)鍵字是k1的鍵值對(duì)聚合起來(lái)產(chǎn)生關(guān)于k1鍵的值集合list(ν1)傳給用戶(hù)定義的Reduce函數(shù)。Reduce函數(shù)再進(jìn)一步處理、合并該中間鍵的值集合，最后形成一個(gè)相對(duì)較小的鍵值對(duì)集合list(k2，ν2)。

整個(gè)過(guò)程可用如下形式表示：

2.2 MapReduce處理階段

在MapReduce計(jì)算模型中，整個(gè)作業(yè)的計(jì)算流程包含5個(gè)階段。

（1）Input階段：用戶(hù)輸入的數(shù)據(jù)會(huì)被自動(dòng)切分成m個(gè)數(shù)據(jù)分片（splits）并被轉(zhuǎn)換為(k/ν)的形式分配給m個(gè)Map任務(wù)，每個(gè)Map任務(wù)會(huì)被分派到集群的某一臺(tái)機(jī)器上運(yùn)行，這些Map任務(wù)在不同的機(jī)器上是并行執(zhí)行的，對(duì)每一個(gè)Map任務(wù)都要指明輸入/輸出的路徑和其他運(yùn)行參數(shù)。

（2）Map階段：使用Map函數(shù)中用戶(hù)定義的Map操作對(duì)(k/ν)鍵值對(duì)進(jìn)行處理后，以list(k1，ν1)鍵值對(duì)形式輸出。

（3）Shuffle階段：在調(diào)用Reduce函數(shù)之前會(huì)對(duì)Map任務(wù)處理完成的數(shù)據(jù)進(jìn)行分割，具有相同關(guān)鍵字的鍵值對(duì)合并在一起形成(k1，list(ν1))，每一個(gè)(k1，list(ν1))就會(huì)分配到一個(gè)Reduce任務(wù)，每個(gè)Reduce任務(wù)也是被分派到集群中的某一臺(tái)機(jī)器上，這樣在整個(gè)Hadoop集群中就會(huì)有多個(gè)Reduce任務(wù)并行執(zhí)行。

（4）Reduce階段：此階段對(duì)每一個(gè)唯一的ki鍵值對(duì)執(zhí)行用戶(hù)定義的Reduce函數(shù)，Reduce任務(wù)執(zhí)行完成后，輸出結(jié)果list(k2，ν2)。

（5）Output階段：此階段把Reduce輸出結(jié)果寫(xiě)入到輸出目錄的文件中。

3 量子蟻群算法（QACA）

下面結(jié)合0-1背包問(wèn)題來(lái)說(shuō)明量子蟻群算法。0-1背包問(wèn)題描述為：給定n個(gè)物品和1個(gè)背包，物品i的重量是wi(i=1，2，…，n)，其價(jià)值為νi，背包的容量為c，現(xiàn)從這n個(gè)物品中選出若干個(gè)放入背包，使得放入的物品重量不超過(guò)c，且總價(jià)值達(dá)到最大。使用蟻群算法求解0-1背包問(wèn)題時(shí)，某一物品上聚集的信息素越多，則該物品被選擇的概率就越大。在QACA中，對(duì)螞蟻在物品上聚集的信息素進(jìn)行量子比特編碼，采用量子旋轉(zhuǎn)門(mén)更新螞蟻攜物品的量子比特，聚集在物品上的信息素更新轉(zhuǎn)變成量子位概率幅的更新。

量子蟻群算法流程[9]：

為了使算法初始搜索時(shí)所有狀態(tài)以相同概率出現(xiàn)，A(0)中所有的αi，βi(i=1，2，…，m)取值均為1/2。

步驟2設(shè)定各參數(shù)α、β、ρ的值，最大迭代次數(shù)NMAX，當(dāng)前迭代次數(shù)t=0，信息素τi(0)=1。

步驟3每只螞蟻獨(dú)立地構(gòu)造一個(gè)解。螞蟻k(k=1,2,…，n)隨機(jī)選擇一個(gè)物品i裝入背包，然后按概率計(jì)算剩余的各個(gè)物品被選擇的概率來(lái)選擇物品放入背包，直到背包不能再裝入物品。物品被選擇概率如公式（4）所示：

式（4）中，τi(t)表示第t次迭代時(shí)物品i所含信息素的量，啟發(fā)函數(shù)ηi(t)表示物品i單位質(zhì)量的價(jià)值，即ηi(t)=νi/wi，α和β分別表示物品所含信息素的量和物品單位質(zhì)量?jī)r(jià)值的權(quán)重，J(k)為螞蟻k沒(méi)有選擇的物品的集合；信息素更新方程：

其中，Δτi(k)表示螞蟻k在第i個(gè)物品上留下的信息素的量，Q為一常數(shù)，ρ為信息素的揮發(fā)性(0≤ρ＜1)。

步驟4若n只螞蟻都構(gòu)造完成各自的解，則轉(zhuǎn)步驟5；否則轉(zhuǎn)步驟3。

步驟5記錄本次迭代中m只螞蟻構(gòu)造出來(lái)的最優(yōu)解。

步驟6應(yīng)用量子旋轉(zhuǎn)門(mén)規(guī)則[13]更新A(t)。

步驟7若滿(mǎn)足結(jié)束條件，即t＞NMAX，輸出最優(yōu)解；否則t=t+1，轉(zhuǎn)步驟3。

4 基于MapReduce的量子蟻群算法（MQACA）

對(duì)于0-1背包問(wèn)題，QACA的時(shí)間復(fù)雜度為O(NMAX·m·n)，計(jì)算量主要集中在步驟3，螞蟻獨(dú)自求解的過(guò)程。MQACA算法用MapReduce來(lái)完成種群每一代進(jìn)化的過(guò)程。Map完成螞蟻的獨(dú)立求解過(guò)程，其中螞蟻家族的索引號(hào)作為鍵，螞蟻的最優(yōu)解和量子信息作為值，這一部分可以并行操作；Reduce表達(dá)求得較優(yōu)解和更新量子螞蟻信息過(guò)程，輸出信息轉(zhuǎn)換為Map輸入的格式作為下一代Map函數(shù)的輸入，進(jìn)入下一代循環(huán)。

4.1 MQACA算法的步驟

具體步驟如下：

步驟1初始化種群，產(chǎn)生鍵值對(duì)(k/ν)，以文件形式存放于Hadoop文件系統(tǒng)，k表示螞蟻家族的索引，ν表示螞蟻的解和量子信息。

步驟2 Map函數(shù)接收(k/ν)，計(jì)算每個(gè)量子螞蟻的適應(yīng)度值，產(chǎn)生中間結(jié)果list(k1，ν1)，k1表示螞蟻家族的索引，ν1表示本家族單個(gè)螞蟻求得的解和量子信息。

步驟3 Reduce函數(shù)接收Map函數(shù)產(chǎn)生的鍵值對(duì)list(k1，ν1)，應(yīng)用量子旋轉(zhuǎn)門(mén)規(guī)則更新量子螞蟻及全局信息素，判斷是否達(dá)到最大代數(shù)，如果是則輸出最優(yōu)值；否則保存最優(yōu)值同時(shí)輸出list(k2，ν2)，k2表示螞蟻家族的索引，ν2表示螞蟻的解和量子信息。將list(k2，ν2)保存在Hadoop文件系統(tǒng)中，進(jìn)入下一次循環(huán)。

4.2 Map階段

Map函數(shù)的主要功能是螞蟻家族中的各成員獨(dú)立生成解，輸出本家族每個(gè)螞蟻的解，形成list(k1，ν1)中間結(jié)果。Map函數(shù)如函數(shù)1所示。

函數(shù)1 MQACA的Map函數(shù)

4.3 Reduce階段

Reduce函數(shù)接收Map函數(shù)輸出的鍵值對(duì)，其主要功能是分解出各個(gè)螞蟻家族成員的解和值，求出其中的最優(yōu)解和最優(yōu)值，然后使用量子旋轉(zhuǎn)門(mén)規(guī)則更新螞蟻家族中各成員的量子信息，根據(jù)公式（5）對(duì)信息素文件進(jìn)行更新，判斷是否滿(mǎn)足終止條件，如果是則輸出最優(yōu)解和最優(yōu)值；否則將輸出鍵值對(duì)list(k2，ν2)保存在Hadoop文件系統(tǒng)中，k2是螞蟻家族索引ν2是更新后的解和量子螞蟻信息。Reduce函數(shù)如函數(shù)2所示。

函數(shù)2 MQACA的Reduce函數(shù)

5 數(shù)值實(shí)驗(yàn)和分析

5.1 實(shí)驗(yàn)環(huán)境

本文使用了3臺(tái)計(jì)算機(jī)搭建Hadoop集群（如圖1），1臺(tái)機(jī)器作為Master，2臺(tái)機(jī)器作為Slave。每臺(tái)節(jié)點(diǎn)硬件配置如下：Pentium?Dual-Core CPU，2.80 GHz，2 GB內(nèi)存，板載Marvell Yukon Gigabit Ethernet網(wǎng)卡控制器。軟件配置如下：Linux Ubuntu 10.04，JDK1.6.0.31，Hadoop 0.20.2，eclipse-SDK-3.7.2，Master上部署Hadoop的NameNode和JobTracker，Slave上部署TaskTracker和DataNode。

圖1 實(shí)驗(yàn)Hadoop集群

圖2 兩個(gè)集群下加速比對(duì)比

圖3 兩個(gè)集群及串行環(huán)境下運(yùn)行時(shí)間對(duì)比

圖4 兩個(gè)集群下并行效率對(duì)比

5.2 集群加速比和效率

加速比是同一個(gè)任務(wù)在單處理器系統(tǒng)和并行處理器系統(tǒng)中運(yùn)行消耗的時(shí)間的比率，用來(lái)衡量并行系統(tǒng)或程序并行化的性能和效果以及擴(kuò)展性。根據(jù)加速比的一般公式，即串行程序執(zhí)行時(shí)間與并行程序執(zhí)行時(shí)間的比值，定義如下加速比和效率。

并行加速比：

式（7）中，n為種群規(guī)模，F(xiàn)(n)表示用串行機(jī)求解該問(wèn)題所需的時(shí)間，m1和m2分別是同時(shí)運(yùn)行Map和Reduce的數(shù)量，M(n，m1)和R(n，m2)分別表示在MapReduce過(guò)程中Map和Reduce所花費(fèi)的時(shí)間，G(n)為完成任務(wù)所必須的運(yùn)算時(shí)間之外所消耗的時(shí)間，如任務(wù)部署、排序、通信傳輸時(shí)間等。

并行效率：

式（8）中，p為集群中處理器的個(gè)數(shù)，當(dāng)加速比S接近于p時(shí)，效率接近于1，影響并行效率的因素很多，如集群中機(jī)器之間的網(wǎng)絡(luò)傳輸時(shí)間，集群運(yùn)行任務(wù)部署時(shí)間等。

5.3 實(shí)驗(yàn)結(jié)果分析

5.3.1 串并行比較實(shí)驗(yàn)

實(shí)驗(yàn)內(nèi)容為比較Hadoop集群中兩個(gè)運(yùn)算節(jié)點(diǎn)與QACA算法的串行實(shí)現(xiàn)，在同樣種群規(guī)模下處理相同問(wèn)題的解的質(zhì)量。實(shí)驗(yàn)中，取α=1，β=5，ρ=0.9，Q=1，集群中每個(gè)節(jié)點(diǎn)及串行環(huán)境中群體規(guī)模m=10，隨機(jī)生成各種不同規(guī)模的0-1背包問(wèn)題實(shí)例。實(shí)例生成方法：各νi和wi在1～100內(nèi)隨機(jī)生成，背包容量c=1/3(w1+w2+…+wn)。實(shí)驗(yàn)情況見(jiàn)表1。

表1 實(shí)驗(yàn)結(jié)果比較

在MQACA中，每一次迭代后不同節(jié)點(diǎn)所求得的解都會(huì)經(jīng)過(guò)Reduce函數(shù)處理，增加集群中節(jié)點(diǎn)之間的交互，加速算法的收斂。表1為MQACA與QACA對(duì)于不同規(guī)模的背包問(wèn)題分別獨(dú)立運(yùn)行50次所得到的結(jié)果，從表1可以看出，隨著問(wèn)題規(guī)模的增大，MQACA的解的質(zhì)量和收斂速度都有較好的表現(xiàn)，表明了MQACA求解背包問(wèn)題的可行性。

5.3.2 集群加速比性能實(shí)驗(yàn)

選擇100個(gè)物品的背包問(wèn)題，在搭建的Hadoop集群環(huán)境下進(jìn)行MQACA算法的集群加速比性能實(shí)驗(yàn)，數(shù)據(jù)規(guī)模為10 000到200 000。對(duì)每個(gè)問(wèn)題分別在節(jié)點(diǎn)數(shù)為2和節(jié)點(diǎn)數(shù)為3的集群中進(jìn)行實(shí)驗(yàn)，集群中節(jié)點(diǎn)數(shù)代表集群中處理器的個(gè)數(shù)，用p表示；串行環(huán)境求解時(shí)間是在單機(jī)環(huán)境下，根據(jù)種群規(guī)模求解所得到的時(shí)間，并行環(huán)境求解時(shí)間是在集群中根據(jù)種群規(guī)模求解所得到的時(shí)間，實(shí)驗(yàn)結(jié)果如圖2～圖4所示。

分析圖2、圖3，隨著數(shù)據(jù)量的增大，并行程度越高，并行加速比相應(yīng)的越大，當(dāng)計(jì)算數(shù)據(jù)規(guī)模較大時(shí)，處理器數(shù)由2增加到3運(yùn)行時(shí)間也相應(yīng)的縮短，說(shuō)明并行程度直接影響MapReduce執(zhí)行時(shí)間。從圖4可以看出，集群中處理器的個(gè)數(shù)越多，集群部署耗費(fèi)的時(shí)間也相應(yīng)增加，并行效率越低，但總體并行效率是隨著數(shù)據(jù)規(guī)模的擴(kuò)大而上升的，根據(jù)數(shù)據(jù)規(guī)模選擇合適的處理器數(shù)可獲得較好的并行效率。上述結(jié)果也體現(xiàn)出在處理大規(guī)模數(shù)據(jù)方面，MapReduce相對(duì)于傳統(tǒng)串行環(huán)境的優(yōu)勢(shì)。

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

本文在Hadoop云環(huán)境中，應(yīng)用MapReduce將量子蟻群算法并行化，提出基于MapReduce的量子蟻群算法，并用0-1背包問(wèn)題驗(yàn)證了該算法在處理大規(guī)模數(shù)據(jù)的有效性。今后，將進(jìn)一步對(duì)MQACA算法參數(shù)調(diào)優(yōu)方面進(jìn)行研究，提高算法性能，并設(shè)計(jì)新的MQACA算法來(lái)解決更為實(shí)際的問(wèn)題。

[1]李莉，廖劍偉，歐靈.云計(jì)算初探[J].計(jì)算機(jī)應(yīng)用研究，2010，27（12）：4419-4422.

[2]郭平，鄢文晉.基于TSP問(wèn)題的蟻群算法綜述[J].計(jì)算機(jī)科學(xué)，2007，34（10）：181-184.

[3]朱慶保，揚(yáng)志軍.基于變異和動(dòng)態(tài)信息素更新的蟻群優(yōu)化算法[J].軟件學(xué)報(bào)，2004，15（2）：185-192.

[4]王欣盛，馬良.工件排序的改進(jìn)蟻群算法優(yōu)化[J].上海理工大學(xué)學(xué)報(bào)，2011，33（4）：362-366.

[5]冀俊忠，黃振，劉椿年.基于變異和信息素?cái)U(kuò)散的多維背包問(wèn)題的蟻群算法[J].計(jì)算機(jī)研究與發(fā)展，2009，46（4）：644-654.

[6]劉霞，揚(yáng)超.最小-最大車(chē)輛路徑問(wèn)題的蟻群算法[J].解放軍理工大學(xué)學(xué)報(bào)，2012，13（3）：336-341.

[7]Han K H，Kim J H.Quantum-inspired evolutionary algorithm with a new term ination criterion[J].IEEE Transactions on Evolutionary Computation，2004，8（2）：156-169.

[8]Han K H，Kim J H.Genetic quantumalgorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 IEEE Congress on Evolutionary Computation，2000： 1354-1360.

[9]何小鋒，馬良.求解0-1背包問(wèn)題的量子蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（16）：29-31.

[10]李絮，劉爭(zhēng)艷，譚拂曉.求解TSP的新量子蟻群算法[J].計(jì)算機(jī)工程與應(yīng)用，2011，47（32）：42-44.

[11]Chao Jin，Vecchiola C.MRPGA：an extension of MapReduce for parallelizing genetic algorithms[C]//Proceedings of the IEEE 4th International Conference on Science，2008：214-221.

[12]White T.Hadoop權(quán)威指南[M].周敏奇，王曉玲，金澈清，等譯.北京：清華大學(xué)出版社，2011.

[13]Han K H，Kim J H.Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J].IEEE Transactions on Evolutionary Computation，2002，6（6）：580-593.

JIA Ruiyu,LI Yalong

School of Computer Science and Technology,Anhui University,Hefei 230601,China

The Quantum-inspired ant colony algorithm is a new algorithm which is based on the combination of ant colony optimization and quantum computing,and has better diversity and global search capacity.This paper aims at the parallelism of Quantum-inspired ant colony algorithm,uses cloud computing to parallel Quantum-inspired ant colony algorithm,makes it to meet the key/value programming model of MapReduce,puts forward MapReduce-based Quantum-inspired ant colony algorithm and runs the algorithm on Hadoop platform.Using 0-1 knapsack problem for test,with the expansion of data set,improvement of parallelism,MQACA exhibits good speed-up ratio and parallel efficiency,proves the feasibility of MQACA.

Quantum-inspired ant colony algorithm;cloud computing;MapReduce model

量子蟻群算法是在蟻群算法的基礎(chǔ)上結(jié)合量子計(jì)算而提出的，該算法具有較好的全局尋優(yōu)能力和種群多樣性。應(yīng)用MapReduce的key/value編程模型，將量子蟻群算法并行化，提出了基于MapReduce的量子蟻群算法（MQACA），并將其部署到Hadoop云計(jì)算平臺(tái)上運(yùn)行。對(duì)0-1背包問(wèn)題的測(cè)試結(jié)果證明，隨著數(shù)據(jù)規(guī)模的擴(kuò)大和并行程度的提高，MQACA具有良好的加速比和并行效率。

量子蟻群算法；云計(jì)算；MapReduce模型

A

TP301

10.3778/j.issn.1002-8331.1302-0036

JIA Ruiyu,LI Yalong.Quantum-inspired ant colony algorithm based on MapReduce model.Computer Engineering and Applications,2013,49（19）：246-249.

安徽省教育廳自然科學(xué)研究基金資助重點(diǎn)項(xiàng)目（No.2011A006）。

賈瑞玉（1965—），女，副教授，碩士生導(dǎo)師，主要研究方向?yàn)橹悄苡?jì)算與數(shù)據(jù)挖掘；李亞龍（1989—），男，碩士研究生，主要研究方向?yàn)橹悄苡?jì)算。E-mail：jiaruiyu267@yahoo.com.cn

2013-02-05

2013-05-07

1002-8331（2013）19-0246-04

CNKI出版日期：2013-05-29http://www.cnki.net/kcms/detail/11.2127.TP.20130529.1519.001.html