基于OpenMP多核架構下并行蟻群算法研究*

趙 輝 , 徐俊剛

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

蟻群算法是由意大利學者DORIGO M提出的，主要應用于求解組合優(yōu)化問題，該算法首先應用在旅行商(TSP)問題并取得較好的效果。蟻群算法不僅能夠智能搜索、全局優(yōu)化，而且具有穩(wěn)健性、正反饋、分布式計算、易與其他算法結合等特點。然而該算法基本上都是基于單CPU串行執(zhí)行的,在求解問題規(guī)模較大時,存在收斂速度較慢等缺點。

隨著多核處理器的普及,如何讓傳統(tǒng)的單CPU串行程序充分發(fā)揮高性能多核處理器的功效,是一個現實而嚴峻的問題。解決這一難題的有效途徑之一就是并行計算。為了將計算能力最大化,需要將算法代碼中的計算任務劃分為多個部分,并交由多個處理器核心同時處理。要實現這一目標,需要一種全新的程序設計模型,目前比較流行的并行程序設計模型之一就是用于共享內存編程的OpenMP。本文將對基于OpenMP的多核架構下并行蟻群算法的實現進行介紹，并通過對大規(guī)模TSP問題進行實驗驗證OpenMP多核并行計算技術能夠大大提高蟻群算法的運行效率。

1 OpenMP簡介

OpenMP是一種面向共享內存以及分布式共享內存的多處理器多線程并行編程語言,具有良好的可移植性，同時支持Fortran、C和 C++。OpenMP程序設計模型提供了一組與平臺無關的編譯指導、指導命令、函數調用和環(huán)境變量，可以顯式地指導編譯器利用應用程序中的并行性。它能夠為編寫多線程應用程序提供一種簡單的方法，通過編譯指導語句，可以將串行的程序逐步地改造成一個并行程序，從而減少程序編寫人員的負擔。

OpenMP程序開始于一個單獨的主線程。主線程會一直串行地執(zhí)行，直到遇見第一個并行域才開始并行執(zhí)行。并行域表示該部分程序計算量大，需要多個處理器共同處理以提高效率和運行速度。并行域以外的部分表示該部分的程序不適宜或者不能并行執(zhí)行，只能由一個處理器來執(zhí)行。主線程創(chuàng)建一組并行線程,然后并行域中的代碼在不同的線程中并行執(zhí)行，當主線程在并行域中執(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編譯指導指令就可以完成。編譯指導語句的含義是在編譯器編譯程序時，會識別特定的注釋，而這些特定的注釋就包含著OpenMP程序的一些語義。例如在C/C++程序中，用#pragma omp parallel來標識一段并行程序塊。在一個無法識別OpenMP語義的普通編譯器中，會將這些特定的注釋當作是普通的注釋而被忽略。因此，如果僅僅使用編譯指導語句，編寫完成的OpenMP程序就能夠同時被普通編譯器與支持OpenMP的編譯器處理。這種性質帶來的好處就是可以用同一份代碼來編寫串行或者并行程序，或者在把串行程序改編成并行程序時，保持串行源代碼部分不變，大量的工作都由編譯器自動執(zhí)行，從而極大地方便了程序編寫人員。

圖1 OpenMP并行執(zhí)行模型

2 蟻群算法

2.1 基本原理

根據仿生學家長期的研究發(fā)現∶螞蟻雖然沒有視覺,但運動時會在路徑上釋放出一種名為信息素的特殊分泌物來尋找路徑。螞蟻走的路徑越長,則釋放的信息素數量越小。當后來的螞蟻再次碰到這個路口的時候,選擇信息素數量較大路徑的概率就會相對較大,這樣形成了一個正反饋機制。螞蟻之間交換著路徑信息,最終通過蟻群的集體自催化行為找出最優(yōu)路徑。

2.2 蟻群算法的數學模型

為了能夠清楚地表達蟻群算法的數學模型,本文借助了經典的TSP問題。給定n個城市的集合{1,2,3,…,n-1}及城市之間環(huán)游的花費 Cij(0≤i≤n-1,0≤j≤n-1,i≠j)。TSP問題是指找到一條經過每個城市一次且回到起點的最小花費的環(huán)路。若將每個頂點看成是圖上的節(jié)點，花費Cij為連接頂點Vi和 Vj邊上的權，則TSP問題就是在一個具有n個節(jié)點的完全圖上找到一條花費最小的漢密爾頓路。

設在TSP問題中有n個城市和m個螞蟻，把m個螞蟻隨機放在n個城市中（m≤n）。每個螞蟻的行為符合下列規(guī)律：根據路徑上的信息素濃度，以相應的概率來選取下一步路徑；不再選取自己本次循環(huán)已經走過的路徑為下一步路徑。用禁忌表tabuk(k=1,2,…,m)來記錄螞蟻k當前所走過的城市，集合tabuk隨著進化過程作動態(tài)調整；當完成了一次循環(huán)后，根據整個路徑長度來釋放相應濃度的信息素，并更新走過的路徑上的信息素濃度。

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

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

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

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

3 基于OpenMP的并行蟻群算法實現

蟻群算法本身具有很高的并行性，所有螞蟻能夠獨立構建問題的可行解，每個螞蟻在構建解的過程中只與當前的信息素和啟發(fā)函數有關，只有在所有螞蟻均完成了可行解的構造之后，信息素更新時存在螞蟻間的通信。因此可以將各個螞蟻構建可行解的過程分配到不同的線程中并行執(zhí)行。

在蟻群算法中,運算量主要集中在每一只螞蟻重新計算建立回路以及每次循環(huán)結束前更新路徑上的信息素,即串行蟻群算法的大部分計算集中在for循環(huán)部分,同時也是算法復雜度的主要來源。當節(jié)點數目很大時,可以將計算循環(huán)分割成若干個部分,每個部分就可以在一個獨立的硬件線程上完成。本文給出基于OpenMP的并行算法設計,目的是在不改變算法行為的前提下提高算法的執(zhí)行效率,充分利用多核處理器的優(yōu)勢。基于OpenMP的并行蟻群算法的主要過程為∶

(1)初始化過程∶通過OpenMP中的編譯指令 #pragma omp parallel for對算法進行初始化。初始化工作主要包括計算任意兩個節(jié)點間的距離、計算τij的初始值、把m個螞蟻隨機放到n個城市上和設置螞蟻的禁忌表tabuk。通過OpenMP中的#pragma omp parallel for對初始化操作進行并行處理，把初始化工作中大量的循環(huán)迭代和循環(huán)賦值任務分配到不同的處理器核上并行執(zhí)行。

(3)更新最短路徑。當所有螞蟻遍歷完所有節(jié)點后，通過OpenMP中的編譯指令#pragma omp parallel for并行計算每個螞蟻走過的總路徑長度Lk，并更新找到的最短路徑。

(4)更新信息素。計算螞蟻產生的信息增量，更新路徑上的信息素。節(jié)點間的信息素是殘留的信息素和信息素增量的疊加。殘留信息素的循環(huán)計算是獨立的，可以通過#pragma omp parallel for進行并行處理。而信息素增量的計算需要各個螞蟻之間的通信，為了避免并行過程中頻繁的通信，不使用OpenMP并行優(yōu)化，而采用串行計算。

(5)運行結束。若循環(huán)次數沒有達到預定次數，則重復執(zhí)行第(2)步，否則運行結束，打印最佳路徑。

算法的執(zhí)行過程如圖2所示。

4 實驗結果及分析

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

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

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

本文研究了一種基于OpenMP的多核架構下并行蟻群算法，并在TSP問題中對算法進行了驗證。并行優(yōu)化計算過程簡單靈活，易于操作，而且充分利用了多核處理器的優(yōu)勢，提高了算法的運行時間效率，為解決大規(guī)模組合優(yōu)化問題提供了可能。

[1]夏鴻斌，須文波，劉淵.基于多蟻群的并行 ACO算法[J].計算機工程,2009,35(22)∶23-28.

[2]黃亞平,王萬良,熊婧.基于自適應蟻群算法的作業(yè)車間模糊調度研究[J].計算機仿真,2009,26(4)∶244-248.

[3]何麗莉，王克淼，白洪濤，等.基于 CMP的多種并行蟻群算法及比較[J].吉林大學學報(理學版),2010,48(5)∶787-792.

[4]多核系列教材編寫組.多核程序設計[M].北京∶清華大學出版社,2007.

[5]姜長元.蟻群算法的理論及其應用[J].計算機時代,2004(6)∶1-3.

[6]閻芳,楊璽,陳蕾.基于 OpenMP的并行蟻群物流調度算法研究[J].物流技術,2010(13)∶91-93.

[7]李妮,高棟棟,龔光紅.基于 TBB多核平臺的并行蟻群算法 實 現[OL-EB].http∶//www.paper.edu.cn.