基于OpenMP多核架構(gòu)下并行蟻群算法研究*

趙 輝 , 徐俊剛

(1.中國(guó)科學(xué)院研究生院,北京 100049;2.北華航天工業(yè)學(xué)院 計(jì)算機(jī)科學(xué)與工程系,河北 廊坊065000）

蟻群算法是由意大利學(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í)行，從而極大地方便了程序編寫人員。

圖1 OpenMP并行執(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)濃度的信息素，并更新走過的路徑上的信息素濃度。

現(xiàn)用τij(t)表示在t時(shí)刻邊(i,j)上的信息素濃度。經(jīng)過n個(gè)時(shí)刻，當(dāng)螞蟻完成了一次循環(huán)之后，相應(yīng)邊上的信息素濃度必須進(jìn)行更新處理，對(duì)舊的信息進(jìn)行削弱，同時(shí)將最新的螞蟻訪問路徑的信息素加入到τij(t)，得到：

式中ρ為一個(gè)取值范圍在0～1之間的常數(shù)，表示信息素的殘留部分，(1-ρ)表示信息素的揮發(fā)程度，其中∶

式中，Q是一個(gè)常量，用來表示螞蟻完成一次完整的路徑搜索后，所釋放的信息素總量；Lk是第k個(gè)螞蟻的路徑總花費(fèi)，它等于第k只螞蟻經(jīng)過的各段路徑上所需的花費(fèi)Cij的總和。如果螞蟻的路徑總花費(fèi)越高，則其在單位路徑上所釋放的信息素濃度就越低。很顯然，螞蟻不會(huì)在其沒有經(jīng)過的路徑上釋放信息素。

式中，ηij=1/Cij,Cij為經(jīng)過路徑(i,j)所需的花費(fèi)。α和β兩個(gè)參數(shù)，分別用來控制信息素和路徑長(zhǎng)度的相對(duì)重要程度。allowedk是第k只螞蟻下一步可以選擇的城市的集合 。 allowedk={0,1,2,…,n-1}-tabuk。

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ì)?；贠penMP的并行蟻群算法的主要過程為∶

(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í)行。

(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)行效率。

表1 串行蟻群算法和基于OpenMP的并行蟻群算法的比較

串行蟻群算法和基于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)化問題提供了可能。

[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.