林超

摘? 要： 蟻群算法與同類智能算法相比具有計算速度快、收斂迅速、算法穩(wěn)定性好等優(yōu)點，但是隨著數(shù)據(jù)量的增大，計算用時呈現(xiàn)指數(shù)型增長。為了更好地解決大數(shù)據(jù)量蟻群算法計算慢的問題，結(jié)合蟻群算法天然的并行性，基于最新的GPU并行化接口C++ AMP實現(xiàn)了并行蟻群算法，使計算用時大幅度減少。經(jīng)試驗分析，該算法可以達到3倍的加速效果。

關(guān)鍵詞： 蟻群算法； 并行蟻群算法； C++ AMP； GPU計算

中圖分類號： TN911.7?34； TP18??????????? 文獻標識碼： A??????????????????????? 文章編號： 1004?373X（2014）23?0069?03

Abstract： Compared with similar intelligent algorithms， ant colony algorithm has the advantages of faster calculation， more rapid convergence and more perfect stability. However， with the increasing amount of data， its computation time emerges the exponential growth. In order to solve the problem that the large amount of data ant colony algorithm is slow， by utilizing the natural parallelism of ant colony algorithm， the parallel ant colony algorithm was achieved on the basis of the latest GPU parallel interface C++AMP， which realized the substantial reduction of computation time. The analysis result indicates that the reduction extent is up to 3 times the acceleration effect.

Keyword： ant colony algorithm； parallel ant colony algorithm； C++ AMP； GPU computation

蟻群算法是由Macro Dorigo等人于1991年提出的一種啟發(fā)式智能算法[1]。蟻群算法的設(shè)計靈感源于蟻群尋找食物的過程，一群螞蟻通過相互協(xié)作就能找到從螞蟻巢穴到食物的最短路徑。其算法核心為路徑上的信息素積累，導致更多的螞蟻選擇這一路徑，最后幾乎所有螞蟻選擇經(jīng)過該路徑，于是就找出了一條從螞蟻巢穴到食物的最短路徑。蟻群算法有著較高的隱含并行性，并且其在很多經(jīng)典問題上有著出色的表現(xiàn)，如旅行商問題TSP（Traveling Salesman Problem）[2?5]、車輛調(diào)度問題[6?7]、集成電路設(shè)計[8]以及通信網(wǎng)絡(luò)負載[9]等問題。隨著數(shù)據(jù)量的增大，串行程序的計算用時成指數(shù)型增長，顯然不滿足人們的需要。為了更快求解這類問題，基于蟻群算法天然的并行性，把算法并行化是很好的選擇。文獻[10]應(yīng)用云計算技術(shù)將蟻群算法并行化，提出了基于MapReduce的蟻群算法；文獻[11?13]實現(xiàn)了基于MPI并行計算的蟻群聚類算法；文獻[14?15]研究了基于OpenMP技術(shù)的多核架構(gòu)下并行蟻群算法；文獻[16?17]建立了一種基于CUDA的并行蟻群算法。本文基于最新的GPU并行化接口C++ AMP實現(xiàn)蟻群算法的并行化，并通過數(shù)值驗證加速效果。

1? C++ AMP介紹

GPU計算由來已久，已經(jīng)成熟的接口包括NVIDIA的CUDA C和AMD的OPENCL接口，隨著微軟公司Visual Studio 2012的發(fā)布，在Build大會上微軟向大家呈現(xiàn)了一種新的GPU并行計算模式C++ AMP，其最低運行環(huán)境是：Win7系統(tǒng)+Visual Studio 2012+DirectX11，所以它比另外兩種并行端口適用范圍更廣，可以實現(xiàn)真正意義上的跨平臺運行。C++ AMP采用面向?qū)ο蟮腃++語言開發(fā)，支持CPU，GPU等跨平臺編譯運行，具有邏輯結(jié)構(gòu)簡單、數(shù)據(jù)隱式拷貝、自動負載均衡等特點，可以快速、穩(wěn)定地實現(xiàn)并行計算。

一個C++ AMP計算過程中最重要的包括：

（1）數(shù)據(jù)，其基本數(shù)據(jù)類型有array<；T，N>；，array_view<；T，N>；，index<；N>；，extent<；N>；，tiled_extent<；D0，D1，D2>；，title_index（D0，D1，D2>；，accelerator，accelerator_view，texture<；T，N>；等；

（2） 迭代函數(shù)parallel_for_each函數(shù)，是C++AMP并行計算的核心部分，負責線程開辟、核函數(shù)計算等工作，基本的計算過程由核函數(shù)指定，通常核函數(shù)為Lambda表達式，也可以是由限定符restrict（amp）限定的GPU函數(shù)；

（3） 線程索引index類，線程開辟大小extent類，他們兩者是一一對應(yīng)的。如果extent是二維的，則index也是二維的，由index類對象來實現(xiàn)對線程的惟一標示；

（4） 數(shù)學函數(shù)，數(shù)學函數(shù)庫有雙精度數(shù)學函數(shù)與快速數(shù)學函數(shù)兩種，根據(jù)需要選擇。

C++ AMP的執(zhí)行模式是由CPU線程控制、由parallel_for_each函數(shù)作為詳細設(shè)置、由核函數(shù)完成核心計算任務(wù)、數(shù)據(jù)隱式拷貝的執(zhí)行模型。程序開始運行時，只有CPU主線程活動，當執(zhí)行到并行區(qū)域時，主線程根據(jù)parallel_for_each函數(shù)的設(shè)置，啟動GPU線程組來完成相應(yīng)的計算任務(wù)，最后拷貝數(shù)據(jù)回CPU主線程，這時GPU線程掛起或者退出，控制流又回到CPU主線程中。

2? 蟻群算法介紹

為了更加清楚詳細地描述蟻群算法，本文借助經(jīng)典的TSP問題來描述（TSP問題：已知[n]個城市以及城市兩兩之間的距離，求一條遍歷所有城市的最短路徑，除初始城市之外每個城市訪問且僅訪問一次）。

蟻群算法可以定義如下：設(shè)有[n]個城市，[m]個螞蟻，任意城市[i]與城市[j]之間的距離為[d（i，j）]，啟發(fā)函數(shù)定義為[η（i，j）=1d（i，j），]任意城市[i]與城市[j]之間的信息素濃度為[τ（i，j）]，并且初始時刻信息素濃度相同，螞蟻[k]經(jīng)過城市[i]轉(zhuǎn)到城市[j]的概率計算公式如下所示：

[pkij=[τ（i，j）]α?[η（i，j）]βs∈J（k）[τ（i，s）]α?[η（i，s）]β，s∈J（k）0，others] （1）

式中：[J（k）]是螞蟻[k]下一步允許選擇的城市的集合；[α，][β]為權(quán)重系數(shù)。當所有螞蟻都完成一次循環(huán)后，對信息素矩陣進行更新操作，這樣，新時刻路徑[（i，j）]上的信息素濃度采用調(diào)整式（2）進行調(diào)節(jié)：

[τ（i，j）=ρτ（i，j）+k=1mΔτk（i，j）] （2）

式中：[ρ（0<；ρ<；1）]表示信息素保留程度，其值越大表示信息素揮發(fā)速率越慢；[Δτk（i，j）]表示在本次循環(huán)中第[k]只螞蟻在路徑[（i，j）]上的信息素貢獻。每只螞蟻的信息素貢獻可以用式（3）進行計算：

[Δτk（i，j）=QLk，第k只螞蟻在本次循環(huán)中經(jīng)過（i，j）0，否則] （3）

式中：[Q]是信息素強度，它影響算法的收斂速度；[Lk]表示第[k]只螞蟻在本次循環(huán)中所有的路徑總和[4]。

3? 并行蟻群算法

根據(jù)上述介紹，可以看出每只螞蟻尋找自己路徑依賴于上次循環(huán)產(chǎn)生的信息素矩陣以及各城市之間的靜態(tài)路徑長度，兩兩螞蟻之間沒有信息素交流，經(jīng)過分析，這是一種符合SIMD模型的過程，故可以將每只螞蟻尋找最優(yōu)路徑的過程并行進行，從而加速算法計算。并行蟻群算法可以用如下算法進行描述：

Step1：初始化所有參數(shù)、變量，如權(quán)重系數(shù)[α，][β；]螞蟻個數(shù)[m；]最大迭代步數(shù)NC；信息素矩陣初始值[τ（i，j）=1。]

Step2：按照螞蟻個數(shù)分配線程，每個線程代表一只螞蟻。每只螞蟻獨立構(gòu)造一個解（解即一條遍歷所有城市的路徑），詳細描述為：螞蟻[k]隨機選取一個城市[i]作為自己的初始點，再根據(jù)轉(zhuǎn)移概率公式計算轉(zhuǎn)移概率[pkij；]根據(jù)概率最大者選擇下一個城市[j]，從而螞蟻走過路徑為[（i，j）。]若當前路徑長度大于上一循環(huán)求得最短路徑長度，則結(jié)束本次循環(huán)；否則繼續(xù)循環(huán)，直到螞蟻[k]尋找到一個解。

Step3：規(guī)約Step2中所有螞蟻產(chǎn)生的解，求解出所有解中的最優(yōu)解和最優(yōu)值進行保存操作。

Step4：根據(jù)當前最優(yōu)解和最優(yōu)值信息，進行信息素矩陣更新操作。

Step5：判斷是否滿足結(jié)束條件，若滿足，則輸出最優(yōu)解和最優(yōu)值；否則，循環(huán)執(zhí)行次數(shù)+1，轉(zhuǎn)Step2。結(jié)束條件為循環(huán)次數(shù)大于NC或者當前解已經(jīng)穩(wěn)定（通常兩步解出的最優(yōu)解與最優(yōu)值相同即可認為當前解已經(jīng)穩(wěn)定）。

串行蟻群算法的時間復雜度為[O（NC?m?n2）]，計算量主要集中在螞蟻各自構(gòu)造一個解的過程。蟻群算法在一代迭代中包括螞蟻獨立求解、相互交流得到較優(yōu)解和改變信息素的過程，且信息素的改變直接影響下一代概率計算的結(jié)果，從而產(chǎn)生不同的解，并向較優(yōu)解進化。由于把算法并行化，采用每只螞蟻并行尋找路徑的模式進行，則并行蟻群算法的時間復雜度減小為[O（NC?n2）]，使算法有明顯的加速。

4? 數(shù)值實驗

4.1? 實驗環(huán)境

實驗環(huán)境采用NVIDIA GeForce GT 440環(huán)境，具體參數(shù)配置如表1所示。

4.2? 數(shù)值結(jié)果

數(shù)值實驗采用的數(shù)據(jù)為隨機生成的二維坐標，取值范圍在[0，1 000]，分城市數(shù)目[n、]螞蟻數(shù)目[m、]迭代次數(shù)[NC]等三個參數(shù)進行實驗分析，實驗結(jié)果如表2所示。

由表2前三行可知，串行時間與并行時間隨著迭代次數(shù)的增加呈現(xiàn)線性增長趨勢，這也符合第3節(jié)的理論推導，此時串行時間與并行時間相當，加速比在[1-0.01，1+0.01]范圍之內(nèi)，可以認為此時沒有加速效果。由此三行知道，加速比和運行時間都與迭代次數(shù)無關(guān)。下面選取小的迭代次數(shù)來進行數(shù)值實驗，分析城市數(shù)目與螞蟻數(shù)目對串行時間、并行時間、加速比的影響。

表1 實驗環(huán)境GeForce GT 440配置參數(shù)

[項目＼&；參數(shù)＼&；操作系統(tǒng)＼&；Windows 7， 64-bits＼&；內(nèi)存＼&；4 GB＼&；運行環(huán)境＼&；Visual Studio 2012＼&；CPU＼&；Intel（R） Xeon（R） W3520@ 2.67 GHz x 4＼&；GPU＼&；顯卡型號：NVIDIA GeForce GT 440

顯存：512 MB DDR3

帶寬：54.4 GB/s

帶寬：54.4 GB/s

核心頻率：850 MHz

存儲頻率：850 MHz

渲染頻率：1 700 MHz

SM個數(shù)：2個

SP個數(shù)：96個＼&；]

表2 實驗結(jié)果

[城市數(shù)目

（n）＼&；螞蟻數(shù)目

（m）＼&；迭代次數(shù)（NC）＼&；串行時間

?；/s＼&；并行時間

?；/s＼&；加速比＼&；200＼&；200＼&；100＼&；80.153＼&；79.445＼&；1.01＼&；200＼&；200＼&；1 000＼&；796.334＼&；802.333＼&；0.99＼&；200＼&；200＼&；10 000＼&；7 849.595＼&；7 933.443＼&；0.99＼&；300＼&；300＼&；100＼&；269.303＼&；168.883＼&；1.75＼&；300＼&；600＼&；100＼&；538.044＼&；219.804＼&；2.45＼&；300＼&；1 000＼&；100＼&；895.340＼&；320.112＼&；2.80＼&；500＼&；500＼&；100＼&；1 251.692＼&；496.486＼&；2.52＼&；500＼&；1 000＼&；100＼&；2 486.281＼&；870.372＼&；2.86＼&；]

由表2整體可以看出，當城市數(shù)目及螞蟻數(shù)目較大時，對數(shù)據(jù)普遍有加速效果。由表2第4～6行分析可知，固定城市數(shù)目，隨著螞蟻數(shù)目增大，串行時間呈現(xiàn)線性增長，而并行時間的增長率小于線性，加速比越來越大。這是由于并行線程數(shù)目是以螞蟻數(shù)目為參數(shù)的，螞蟻數(shù)目越大，并行線程數(shù)目越多，從而使得并行時間增長率比線性還小。但是此時并行時間并沒有遵循第3節(jié)分析的函數(shù)[O（NC?n2）]，這是由于雖然并行線程開辟了[m]個，但是最終的物理執(zhí)行過程同時運行的線程個數(shù)為96個（SP個數(shù)），又涉及到CPU?GPU異構(gòu)通信時間，從而使得整體并行時間沒有按照理論分析的結(jié)果。并行線程數(shù)目m越大，負載相對越均衡，物理資源占用越充分，從而加速效果越來越明顯，直到達到相應(yīng)的物理瓶頸。這也可以由表2的7，8行得出。

由表2中的第5，7行和第6，8行可以對比出，螞蟻數(shù)目[m]一定時，城市數(shù)目[n]對于串行、并行算法時間的影響。對比5，7兩行可以看出，螞蟻數(shù)目大體一樣，城市數(shù)目改變量比較大，其加速比相差不大；對比6，8兩行可以看出，螞蟻數(shù)目一樣時，城市數(shù)目的改變對于整個算法的加速比影響并不是很大。這個也可以從并行程序中串行執(zhí)行部分、數(shù)據(jù)交換所用時間以及算法本身所用時間方面進行分析，這個加速效果是合理的。

5?； 結(jié)?； 論

本文基于最新的GPU并行化接口C++ AMP，設(shè)計實現(xiàn)了并行蟻群算法，經(jīng)過數(shù)值實驗分析，可以達到3倍的加速效果，對于大數(shù)量的蟻群算法求解提供了新的解決思路。加速效果不是很明顯，原因是CPU配置較高，GPU性能不是很好導致。

參考文獻

[1] COLORNI A， DORIGO M， MANIEZZO V， et al. Distributedoptimization by ant colonies [C]// Proceedings of European Conference on Artificial Life. Paris： [s.n.]， 1991： 134?142.

[2] 蔣騰旭.改進的遺傳蟻群混合算法在TSP中的應(yīng)用[J].計算機與現(xiàn)代化，2013（12）：30?33.

[3] 余鵬，何學軍.基于蟻群算法的艦艇編隊海上補給路徑規(guī)劃方法[J].海軍工程大學學報，2014（2）：108?112.

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

[5] 王勝訓，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學學報，2013（6）：840?844.

[6] 楊浩雄，胡靜，何明珂.配送中多車場多任務(wù)多車型車輛調(diào)度研究[J].計算機工程與應(yīng)用，2013（10）：243?246.

[7] 于濱，楊忠振，程春田.并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用[J].大連理工大學學報，2007（2）：211?214.

[8] 黃訓誠，耿阿囡，莊奕琪，等.基于蟻群算法的集成電路無網(wǎng)格布線[J].電子器件，2006（3）：874?877.

[9] 王愛靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負載均衡問題的研究[J].計算機工程與應(yīng)用，2011（36）：112?114.

[10] 吳昊，倪志偉，王會穎.基于MapReduce的蟻群算法[J].計算機集成制造系統(tǒng)，2012（7）：1503?1509.

[11] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計與實現(xiàn)[J].控制工程，2013（3）：411?414.

[12] 劉彩云，陳忠.一種蟻群算法的并行實現(xiàn)[J].長江大學學報（自科版）理工卷，2007（4）：9?11.

[13] 曹明，甘云，王勝炎，等.基于MPI的并行蟻群算法的實現(xiàn)[J].電腦知識與技術(shù)，2012（12）：2863?2864.

[14] 劉向嬌，吳素萍，劉佳梅.基于OpenMP求解旅行商問題的并行蟻群算法[J].微電子學與計算機，2011（7）：149?151.

[15] 陳昊.基于OpenMP的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配[J].傳感器與微系統(tǒng)，2013（1）：20?24.

[16] 白洪濤，歐陽丹彤，李熙銘，等.基于GPU的共享信息素矩陣多蟻群算法[J].吉林大學學報：工學版，2011（6）：1678?1683.

[17] 李建明，胡祥培，龐占龍，等.一種基于GPU加速的細粒度并行蟻群算法[J].控制與決策，2009，24（8）：1132?1136.

帶寬：54.4 GB/s

核心頻率：850 MHz

存儲頻率：850 MHz

渲染頻率：1 700 MHz

SM個數(shù)：2個

SP個數(shù)：96個＼&；]

表2 實驗結(jié)果

[城市數(shù)目

（n）＼&；螞蟻數(shù)目

（m）＼&；迭代次數(shù)（NC）＼&；串行時間

?；/s＼&；并行時間

?；/s＼&；加速比＼&；200＼&；200＼&；100＼&；80.153＼&；79.445＼&；1.01＼&；200＼&；200＼&；1 000＼&；796.334＼&；802.333＼&；0.99＼&；200＼&；200＼&；10 000＼&；7 849.595＼&；7 933.443＼&；0.99＼&；300＼&；300＼&；100＼&；269.303＼&；168.883＼&；1.75＼&；300＼&；600＼&；100＼&；538.044＼&；219.804＼&；2.45＼&；300＼&；1 000＼&；100＼&；895.340＼&；320.112＼&；2.80＼&；500＼&；500＼&；100＼&；1 251.692＼&；496.486＼&；2.52＼&；500＼&；1 000＼&；100＼&；2 486.281＼&；870.372＼&；2.86＼&；]

由表2整體可以看出，當城市數(shù)目及螞蟻數(shù)目較大時，對數(shù)據(jù)普遍有加速效果。由表2第4～6行分析可知，固定城市數(shù)目，隨著螞蟻數(shù)目增大，串行時間呈現(xiàn)線性增長，而并行時間的增長率小于線性，加速比越來越大。這是由于并行線程數(shù)目是以螞蟻數(shù)目為參數(shù)的，螞蟻數(shù)目越大，并行線程數(shù)目越多，從而使得并行時間增長率比線性還小。但是此時并行時間并沒有遵循第3節(jié)分析的函數(shù)[O（NC?n2）]，這是由于雖然并行線程開辟了[m]個，但是最終的物理執(zhí)行過程同時運行的線程個數(shù)為96個（SP個數(shù)），又涉及到CPU?GPU異構(gòu)通信時間，從而使得整體并行時間沒有按照理論分析的結(jié)果。并行線程數(shù)目m越大，負載相對越均衡，物理資源占用越充分，從而加速效果越來越明顯，直到達到相應(yīng)的物理瓶頸。這也可以由表2的7，8行得出。

由表2中的第5，7行和第6，8行可以對比出，螞蟻數(shù)目[m]一定時，城市數(shù)目[n]對于串行、并行算法時間的影響。對比5，7兩行可以看出，螞蟻數(shù)目大體一樣，城市數(shù)目改變量比較大，其加速比相差不大；對比6，8兩行可以看出，螞蟻數(shù)目一樣時，城市數(shù)目的改變對于整個算法的加速比影響并不是很大。這個也可以從并行程序中串行執(zhí)行部分、數(shù)據(jù)交換所用時間以及算法本身所用時間方面進行分析，這個加速效果是合理的。

5?； 結(jié)?； 論

本文基于最新的GPU并行化接口C++ AMP，設(shè)計實現(xiàn)了并行蟻群算法，經(jīng)過數(shù)值實驗分析，可以達到3倍的加速效果，對于大數(shù)量的蟻群算法求解提供了新的解決思路。加速效果不是很明顯，原因是CPU配置較高，GPU性能不是很好導致。

參考文獻

[1] COLORNI A， DORIGO M， MANIEZZO V， et al. Distributedoptimization by ant colonies [C]// Proceedings of European Conference on Artificial Life. Paris： [s.n.]， 1991： 134?142.

[2] 蔣騰旭.改進的遺傳蟻群混合算法在TSP中的應(yīng)用[J].計算機與現(xiàn)代化，2013（12）：30?33.

[3] 余鵬，何學軍.基于蟻群算法的艦艇編隊海上補給路徑規(guī)劃方法[J].海軍工程大學學報，2014（2）：108?112.

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

[5] 王勝訓，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學學報，2013（6）：840?844.

[6] 楊浩雄，胡靜，何明珂.配送中多車場多任務(wù)多車型車輛調(diào)度研究[J].計算機工程與應(yīng)用，2013（10）：243?246.

[7] 于濱，楊忠振，程春田.并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用[J].大連理工大學學報，2007（2）：211?214.

[8] 黃訓誠，耿阿囡，莊奕琪，等.基于蟻群算法的集成電路無網(wǎng)格布線[J].電子器件，2006（3）：874?877.

[9] 王愛靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負載均衡問題的研究[J].計算機工程與應(yīng)用，2011（36）：112?114.

[10] 吳昊，倪志偉，王會穎.基于MapReduce的蟻群算法[J].計算機集成制造系統(tǒng)，2012（7）：1503?1509.

[11] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計與實現(xiàn)[J].控制工程，2013（3）：411?414.

[12] 劉彩云，陳忠.一種蟻群算法的并行實現(xiàn)[J].長江大學學報（自科版）理工卷，2007（4）：9?11.

[13] 曹明，甘云，王勝炎，等.基于MPI的并行蟻群算法的實現(xiàn)[J].電腦知識與技術(shù)，2012（12）：2863?2864.

[14] 劉向嬌，吳素萍，劉佳梅.基于OpenMP求解旅行商問題的并行蟻群算法[J].微電子學與計算機，2011（7）：149?151.

[15] 陳昊.基于OpenMP的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配[J].傳感器與微系統(tǒng)，2013（1）：20?24.

[16] 白洪濤，歐陽丹彤，李熙銘，等.基于GPU的共享信息素矩陣多蟻群算法[J].吉林大學學報：工學版，2011（6）：1678?1683.

[17] 李建明，胡祥培，龐占龍，等.一種基于GPU加速的細粒度并行蟻群算法[J].控制與決策，2009，24（8）：1132?1136.

帶寬：54.4 GB/s

核心頻率：850 MHz

存儲頻率：850 MHz

渲染頻率：1 700 MHz

SM個數(shù)：2個

SP個數(shù)：96個＼&；]

表2 實驗結(jié)果

[城市數(shù)目

（n）＼&；螞蟻數(shù)目

（m）＼&；迭代次數(shù)（NC）＼&；串行時間

?；/s＼&；并行時間

?；/s＼&；加速比＼&；200＼&；200＼&；100＼&；80.153＼&；79.445＼&；1.01＼&；200＼&；200＼&；1 000＼&；796.334＼&；802.333＼&；0.99＼&；200＼&；200＼&；10 000＼&；7 849.595＼&；7 933.443＼&；0.99＼&；300＼&；300＼&；100＼&；269.303＼&；168.883＼&；1.75＼&；300＼&；600＼&；100＼&；538.044＼&；219.804＼&；2.45＼&；300＼&；1 000＼&；100＼&；895.340＼&；320.112＼&；2.80＼&；500＼&；500＼&；100＼&；1 251.692＼&；496.486＼&；2.52＼&；500＼&；1 000＼&；100＼&；2 486.281＼&；870.372＼&；2.86＼&；]

由表2整體可以看出，當城市數(shù)目及螞蟻數(shù)目較大時，對數(shù)據(jù)普遍有加速效果。由表2第4～6行分析可知，固定城市數(shù)目，隨著螞蟻數(shù)目增大，串行時間呈現(xiàn)線性增長，而并行時間的增長率小于線性，加速比越來越大。這是由于并行線程數(shù)目是以螞蟻數(shù)目為參數(shù)的，螞蟻數(shù)目越大，并行線程數(shù)目越多，從而使得并行時間增長率比線性還小。但是此時并行時間并沒有遵循第3節(jié)分析的函數(shù)[O（NC?n2）]，這是由于雖然并行線程開辟了[m]個，但是最終的物理執(zhí)行過程同時運行的線程個數(shù)為96個（SP個數(shù)），又涉及到CPU?GPU異構(gòu)通信時間，從而使得整體并行時間沒有按照理論分析的結(jié)果。并行線程數(shù)目m越大，負載相對越均衡，物理資源占用越充分，從而加速效果越來越明顯，直到達到相應(yīng)的物理瓶頸。這也可以由表2的7，8行得出。

由表2中的第5，7行和第6，8行可以對比出，螞蟻數(shù)目[m]一定時，城市數(shù)目[n]對于串行、并行算法時間的影響。對比5，7兩行可以看出，螞蟻數(shù)目大體一樣，城市數(shù)目改變量比較大，其加速比相差不大；對比6，8兩行可以看出，螞蟻數(shù)目一樣時，城市數(shù)目的改變對于整個算法的加速比影響并不是很大。這個也可以從并行程序中串行執(zhí)行部分、數(shù)據(jù)交換所用時間以及算法本身所用時間方面進行分析，這個加速效果是合理的。

5?； 結(jié)?； 論

本文基于最新的GPU并行化接口C++ AMP，設(shè)計實現(xiàn)了并行蟻群算法，經(jīng)過數(shù)值實驗分析，可以達到3倍的加速效果，對于大數(shù)量的蟻群算法求解提供了新的解決思路。加速效果不是很明顯，原因是CPU配置較高，GPU性能不是很好導致。

參考文獻

[1] COLORNI A， DORIGO M， MANIEZZO V， et al. Distributedoptimization by ant colonies [C]// Proceedings of European Conference on Artificial Life. Paris： [s.n.]， 1991： 134?142.

[2] 蔣騰旭.改進的遺傳蟻群混合算法在TSP中的應(yīng)用[J].計算機與現(xiàn)代化，2013（12）：30?33.

[3] 余鵬，何學軍.基于蟻群算法的艦艇編隊海上補給路徑規(guī)劃方法[J].海軍工程大學學報，2014（2）：108?112.

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

[5] 王勝訓，李艷穎.一種求解TSP的自適應(yīng)蟻群優(yōu)化算法[J].西安工程大學學報，2013（6）：840?844.

[6] 楊浩雄，胡靜，何明珂.配送中多車場多任務(wù)多車型車輛調(diào)度研究[J].計算機工程與應(yīng)用，2013（10）：243?246.

[7] 于濱，楊忠振，程春田.并行蟻群算法在公交線網(wǎng)優(yōu)化中應(yīng)用[J].大連理工大學學報，2007（2）：211?214.

[8] 黃訓誠，耿阿囡，莊奕琪，等.基于蟻群算法的集成電路無網(wǎng)格布線[J].電子器件，2006（3）：874?877.

[9] 王愛靜，郝志峰，黃翰，等.雙向反饋蟻群算法在網(wǎng)絡(luò)負載均衡問題的研究[J].計算機工程與應(yīng)用，2011（36）：112?114.

[10] 吳昊，倪志偉，王會穎.基于MapReduce的蟻群算法[J].計算機集成制造系統(tǒng)，2012（7）：1503?1509.

[11] 楊燕，王全根，黃波.蟻群聚類算法的并行化設(shè)計與實現(xiàn)[J].控制工程，2013（3）：411?414.

[12] 劉彩云，陳忠.一種蟻群算法的并行實現(xiàn)[J].長江大學學報（自科版）理工卷，2007（4）：9?11.

[13] 曹明，甘云，王勝炎，等.基于MPI的并行蟻群算法的實現(xiàn)[J].電腦知識與技術(shù)，2012（12）：2863?2864.

[14] 劉向嬌，吳素萍，劉佳梅.基于OpenMP求解旅行商問題的并行蟻群算法[J].微電子學與計算機，2011（7）：149?151.

[15] 陳昊.基于OpenMP的并行蟻群算法求解協(xié)同空戰(zhàn)火力分配[J].傳感器與微系統(tǒng)，2013（1）：20?24.

[16] 白洪濤，歐陽丹彤，李熙銘，等.基于GPU的共享信息素矩陣多蟻群算法[J].吉林大學學報：工學版，2011（6）：1678?1683.

[17] 李建明，胡祥培，龐占龍，等.一種基于GPU加速的細粒度并行蟻群算法[J].控制與決策，2009，24（8）：1132?1136.