摘   要： 研究了一種基于OpenMP技術(shù)的多核架構(gòu)下并行蟻群算法，通過在TSP問題中的實驗表明，該算法易于操作，而且充分利用了多核處理器并行計算的優(yōu)勢，提高了算法的運行效率。
關(guān)鍵詞： 蟻群算法； 多核并行計算； OpenMP

　蟻群算法是由意大利學(xué)者DORIGO M提出的，主要應(yīng)用于求解組合優(yōu)化問題，該算法首先應(yīng)用在旅行商(TSP)問題并取得較好的效果。蟻群算法不僅能夠智能搜索、全局優(yōu)化，而且具有穩(wěn)健性、正反饋、分布式計算、易與其他算法結(jié)合等特點。然而該算法基本上都是基于單CPU串行執(zhí)行的, 在求解問題規(guī)模較大時, 存在收斂速度較慢等缺點。
　隨著多核處理器的普及,如何讓傳統(tǒng)的單CPU串行程序充分發(fā)揮高性能多核處理器的功效,是一個現(xiàn)實而嚴(yán)峻的問題。解決這一難題的有效途徑之一就是并行計算。為了將計算能力最大化,需要將算法代碼中的計算任務(wù)劃分為多個部分,并交由多個處理器核心同時處理。要實現(xiàn)這一目標(biāo),需要一種全新的程序設(shè)計模型,目前比較流行的并行程序設(shè)計模型之一就是用于共享內(nèi)存編程的OpenMP。本文將對基于OpenMP的多核架構(gòu)下并行蟻群算法的實現(xiàn)進行介紹，并通過對大規(guī)模TSP問題進行實驗驗證OpenMP多核并行計算技術(shù)能夠大大提高蟻群算法的運行效率。
1 OpenMP簡介
　OpenMP是一種面向共享內(nèi)存以及分布式共享內(nèi)存的多處理器多線程并行編程語言,具有良好的可移植性，同時支持Fortran、C和C++。OpenMP程序設(shè)計模型提供了一組與平臺無關(guān)的編譯指導(dǎo)、指導(dǎo)命令、函數(shù)調(diào)用和環(huán)境變量，可以顯式地指導(dǎo)編譯器利用應(yīng)用程序中的并行性。它能夠為編寫多線程應(yīng)用程序提供一種簡單的方法，通過編譯指導(dǎo)語句，可以將串行的程序逐步地改造成一個并行程序，從而減少程序編寫人員的負(fù)擔(dān)。
　OpenMP程序開始于一個單獨的主線程。主線程會一直串行地執(zhí)行，直到遇見第一個并行域才開始并行執(zhí)行。并行域表示該部分程序計算量大，需要多個處理器共同處理以提高效率和運行速度。并行域以外的部分表示該部分的程序不適宜或者不能并行執(zhí)行，只能由一個處理器來執(zhí)行。主線程創(chuàng)建一組并行線程,然后并行域中的代碼在不同的線程中并行執(zhí)行，當(dāng)主線程在并行域中執(zhí)行完后，它們可能被同步或被中斷，最后只有主線程在執(zhí)行。OpenMP的并行執(zhí)行過程如圖1所示。例如對于for循環(huán)語句for(int i=0; i<100; i++)，按常規(guī)串行處理時，i要按順序執(zhí)行從0~99。如果在雙核環(huán)境下，則分成兩個線程，兩個CPU執(zhí)行核同時處理，核0執(zhí)行i從0~49，核1執(zhí)行i從50~99，理論上可以節(jié)省一半的時間。而這種從串行執(zhí)行到并行執(zhí)行的改變，只需要一條OpenMP編譯指導(dǎo)指令就可以完成。編譯指導(dǎo)語句的含義是在編譯器編譯程序時，會識別特定的注釋，而這些特定的注釋就包含著OpenMP程序的一些語義。例如在C/C++程序中，用#pragma omp parallel來標(biāo)識一段并行程序塊。在一個無法識別OpenMP語義的普通編譯器中，會將這些特定的注釋當(dāng)作是普通的注釋而被忽略。因此，如果僅僅使用編譯指導(dǎo)語句，編寫完成的OpenMP程序就能夠同時被普通編譯器與支持OpenMP的編譯器處理。這種性質(zhì)帶來的好處就是可以用同一份代碼來編寫串行或者并行程序，或者在把串行程序改編成并行程序時，保持串行源代碼部分不變，大量的工作都由編譯器自動執(zhí)行，從而極大地方便了程序編寫人員。

2 蟻群算法
2.1 基本原理
    根據(jù)仿生學(xué)家長期的研究發(fā)現(xiàn): 螞蟻雖然沒有視覺, 但運動時會在路徑上釋放出一種名為信息素的特殊分泌物來尋找路徑。螞蟻走的路徑越長, 則釋放的信息素數(shù)量越小。當(dāng)后來的螞蟻再次碰到這個路口的時候, 選擇信息素數(shù)量較大路徑的概率就會相對較大, 這樣形成了一個正反饋機制。螞蟻之間交換著路徑信息, 最終通過蟻群的集體自催化行為找出最優(yōu)路徑。
2.2 蟻群算法的數(shù)學(xué)模型
　為了能夠清楚地表達蟻群算法的數(shù)學(xué)模型, 本文借助了經(jīng)典的TSP問題。給定n個城市的集合{1,2,3,…,n-1}及城市之間環(huán)游的花費Cij(0≤i≤n-1,0≤j≤n-1,i≠j)。TSP問題是指找到一條經(jīng)過每個城市一次且回到起點的最小花費的環(huán)路。若將每個頂點看成是圖上的節(jié)點，花費Cij為連接頂點Vi和Vj邊上的權(quán)，則TSP問題就是在一個具有n個節(jié)點的完全圖上找到一條花費最小的漢密爾頓路。    
　設(shè)在TSP問題中有n個城市和m個螞蟻，把m個螞蟻隨機放在n個城市中（m≤n）。每個螞蟻的行為符合下列規(guī)律：根據(jù)路徑上的信息素濃度，以相應(yīng)的概率來選取下一步路徑；不再選取自己本次循環(huán)已經(jīng)走過的路徑為下一步路徑。用禁忌表tabuk(k=1,2,…,m)來記錄螞蟻k當(dāng)前所走過的城市，集合tabuk隨著進化過程作動態(tài)調(diào)整；當(dāng)完成了一次循環(huán)后，根據(jù)整個路徑長度來釋放相應(yīng)濃度的信息素，并更新走過的路徑上的信息素濃度。

3 基于OpenMP的并行蟻群算法實現(xiàn)
　蟻群算法本身具有很高的并行性，所有螞蟻能夠獨立構(gòu)建問題的可行解，每個螞蟻在構(gòu)建解的過程中只與當(dāng)前的信息素和啟發(fā)函數(shù)有關(guān)，只有在所有螞蟻均完成了可行解的構(gòu)造之后，信息素更新時存在螞蟻間的通信。因此可以將各個螞蟻構(gòu)建可行解的過程分配到不同的線程中并行執(zhí)行。
　在蟻群算法中,運算量主要集中在每一只螞蟻重新計算建立回路以及每次循環(huán)結(jié)束前更新路徑上的信息素,即串行蟻群算法的大部分計算集中在for循環(huán)部分,同時也是算法復(fù)雜度的主要來源。當(dāng)節(jié)點數(shù)目很大時,可以將計算循環(huán)分割成若干個部分,每個部分就可以在一個獨立的硬件線程上完成。本文給出基于OpenMP的并行算法設(shè)計,目的是在不改變算法行為的前提下提高算法的執(zhí)行效率,充分利用多核處理器的優(yōu)勢?；贠penMP的并行蟻群算法的主要過程為:
　(1)初始化過程:通過OpenMP中的編譯指令#pragma omp parallel for對算法進行初始化。初始化工作主要包括計算任意兩個節(jié)點間的距離、計算τij的初始值、把m個螞蟻隨機放到n個城市上和設(shè)置螞蟻的禁忌表tabuk。通過OpenMP中的#pragma omp parallel for對初始化操作進行并行處理，把初始化工作中大量的循環(huán)迭代和循環(huán)賦值任務(wù)分配到不同的處理器核上并行執(zhí)行。
　(2)螞蟻探索路徑過程：螞蟻根據(jù)概率Pijk選擇下一個節(jié)點j，將第k個螞蟻移到節(jié)點j，并將j插入到禁忌表tabuk中。在求Pijk時可以通過OpenMP中的reduction語句使循環(huán)迭代中的累加操作并行執(zhí)行。reduction語句可以為每一個線程創(chuàng)建累加變量的私有同名變量，并行代碼執(zhí)行結(jié)束后，每一個私有同名變量會按加法操作依次進行規(guī)約，更新主線程中的原始變量的值。
　(3)更新最短路徑。當(dāng)所有螞蟻遍歷完所有節(jié)點后，通過OpenMP中的編譯指令#pragma omp parallel for并行計算每個螞蟻走過的總路徑長度Lk，并更新找到的最短路徑。
　(4)更新信息素。計算螞蟻產(chǎn)生的信息增量，更新路徑上的信息素。節(jié)點間的信息素是殘留的信息素和信息素增量的疊加。殘留信息素的循環(huán)計算是獨立的，可以通過#pragma omp parallel for進行并行處理。而信息素增量的計算需要各個螞蟻之間的通信，為了避免并行過程中頻繁的通信，不使用OpenMP并行優(yōu)化，而采用串行計算。
　(5)運行結(jié)束。若循環(huán)次數(shù)沒有達到預(yù)定次數(shù)，則重復(fù)執(zhí)行第(2)步，否則運行結(jié)束，打印最佳路徑。
　算法的執(zhí)行過程如圖2所示。

4 實驗結(jié)果及分析
    本文所設(shè)計的算法在Intel酷睿2雙核E7500處理器上進行實驗，串行蟻群算法和基于OpenMP的并行蟻群算法的實驗比較結(jié)果如表1所示。實驗結(jié)果表明：當(dāng)問題規(guī)模比較小時，串行蟻群算法和基于OpenMP的并行蟻群算法的運行時間相差不大，但隨著問題規(guī)模的擴大，并行算法的運行時間將會縮短到原來的50%左右，明顯提高了算法的運行效率。

    串行蟻群算法和基于OpenMP的并行蟻群算法在解決同樣規(guī)模問題時，CPU 的使用情況如圖3和圖4所示。結(jié)果表明：串行算法不能充分利用兩個處理核心的資源， CPU的使用率在50%左右，造成了資源的浪費，而OpenMP設(shè)計的并行算法充分利用了兩個處理核心資源，使CPU的使用率達到100%，這也正是蟻群算法運行效率提高的原因。

    本文研究了一種基于OpenMP的多核架構(gòu)下并行蟻群算法，并在TSP問題中對算法進行了驗證。并行優(yōu)化計算過程簡單靈活，易于操作，而且充分利用了多核處理器的優(yōu)勢，提高了算法的運行時間效率，為解決大規(guī)模組合優(yōu)化問題提供了可能。
參考文獻
[1] 夏鴻斌，須文波，劉淵. 基于多蟻群的并行 ACO 算法[J].計算機工程,2009,35(22): 23-28.
[2] 黃亞平,王萬良,熊婧.基于自適應(yīng)蟻群算法的作業(yè)車間模糊調(diào)度研究[J].計算機仿真, 2009, 26(4):244-248.
[3]  何麗莉，王克淼，白洪濤，等.基于CMP 的多種并行蟻群算法及比較[J]. 吉林大學(xué)學(xué)報(理學(xué)版),2010,48(5):787-792.
[4] 多核系列教材編寫組.多核程序設(shè)計[M].北京:清華大學(xué)出版社, 2007.
[5] 姜長元. 蟻群算法的理論及其應(yīng)用[J]. 計算機時代,2004(6):1-3.
[6] 閻芳,楊璽,陳蕾.基于OpenMP的并行蟻群物流調(diào)度算法研究[J]. 物流技術(shù),2010(13):91-93.
[7] 李妮,高棟棟,龔光紅.基于TBB 多核平臺的并行蟻群算法實現(xiàn)[OL-EB]. http://www.paper.edu.cn.