賈瑞玉，李亞龍

安徽大學計算機科學與技術學院，合肥 230601

基于MapReduce的量子蟻群算法

賈瑞玉，李亞龍

安徽大學計算機科學與技術學院，合肥 230601

1 引言

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

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

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

2 MapReduce并行計算編程模型

2.1 MapReduce模型簡介

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

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

整個過程可用如下形式表示：

2.2 MapReduce處理階段

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

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

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

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

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

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

3 量子蟻群算法（QACA）

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

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

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

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

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

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

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

步驟4若n只螞蟻都構造完成各自的解，則轉步驟5；否則轉步驟3。

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

步驟6應用量子旋轉門規(guī)則[13]更新A(t)。

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

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

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

4.1 MQACA算法的步驟

具體步驟如下：

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

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

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

4.2 Map階段

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

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

4.3 Reduce階段

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

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

5 數(shù)值實驗和分析

5.1 實驗環(huán)境

本文使用了3臺計算機搭建Hadoop集群（如圖1），1臺機器作為Master，2臺機器作為Slave。每臺節(jié)點硬件配置如下：Pentium?Dual-Core CPU，2.80 GHz，2 GB內存，板載Marvell Yukon Gigabit Ethernet網卡控制器。軟件配置如下：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 實驗Hadoop集群

圖2 兩個集群下加速比對比

圖3 兩個集群及串行環(huán)境下運行時間對比

圖4 兩個集群下并行效率對比

5.2 集群加速比和效率

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

并行加速比：

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

并行效率：

式（8）中，p為集群中處理器的個數(shù)，當加速比S接近于p時，效率接近于1，影響并行效率的因素很多，如集群中機器之間的網絡傳輸時間，集群運行任務部署時間等。

5.3 實驗結果分析

5.3.1 串并行比較實驗

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

表1 實驗結果比較

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

5.3.2 集群加速比性能實驗

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

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

6 結束語

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

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

[2]郭平，鄢文晉.基于TSP問題的蟻群算法綜述[J].計算機科學，2007，34（10）：181-184.

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

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

[5]冀俊忠，黃振，劉椿年.基于變異和信息素擴散的多維背包問題的蟻群算法[J].計算機研究與發(fā)展，2009，46（4）：644-654.

[6]劉霞，揚超.最小-最大車輛路徑問題的蟻群算法[J].解放軍理工大學學報，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背包問題的量子蟻群算法[J].計算機工程與應用，2011，47（16）：29-31.

[10]李絮，劉爭艷，譚拂曉.求解TSP的新量子蟻群算法[J].計算機工程與應用，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權威指南[M].周敏奇，王曉玲，金澈清，等譯.北京：清華大學出版社，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

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

量子蟻群算法；云計算；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.

安徽省教育廳自然科學研究基金資助重點項目（No.2011A006）。

賈瑞玉（1965—），女，副教授，碩士生導師，主要研究方向為智能計算與數(shù)據(jù)挖掘；李亞龍（1989—），男，碩士研究生，主要研究方向為智能計算。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