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

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

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

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

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

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

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