基于GPU加速的并行蟻群算法求解旅行商問題研究

楊雅寧+藺勇

摘要：蟻群算法是求解旅行商問題的有效方法之一，但是隨著蟻群規(guī)模和城市規(guī)模的增大，算法的運行速度將大大降低，本文利用GPU在CUDA7.0環(huán)境下，對蟻群算法進行化加速設計，實驗結果表明，該方法取得了良好的加速效果，當蟻群規(guī)模增大時，加速倍大幅度提高。數(shù)據(jù)顯示，蟻群個體和城市規(guī)模越大，加速效果越好。

關鍵詞：蟻群算法；GPU；CUDA

中圖分類號：TP18 文獻標識碼：A 文章編號：1009-3044（2016）12-0206-02

旅行商問題（Traveling Salesman Problem，簡稱TSP）是一個典型的組合優(yōu)化問題。城市管道鋪設優(yōu)化、物流業(yè)的車輛調度、制造業(yè)中的切割路徑優(yōu)化等現(xiàn)實生活中的優(yōu)化問題都可以歸結為TSP求解問題。它解決從一個城市出發(fā)，經(jīng)過若干個城市后又返回原城市的最優(yōu)路徑的求解問題。

螞蟻在覓食路徑上會釋放一種特殊的分泌物—“信息素”，隨著時間流逝，信息素會揮發(fā)，后面的螞蟻根據(jù)路徑上的信息素濃度，選擇信息素多的路徑去覓食，這樣便形成了一個正反饋機制。在整個尋徑過程中，雖然單只螞蟻的選擇能力有限，但它們的行為具有非常高的自組織性，相互之間交換路徑，最終尋找到最優(yōu)路徑。受到蟻群系統(tǒng)信息共享機制的啟發(fā)，意大利學者DorigoM于1992年首次系統(tǒng)提出了蟻群算法，并成功地將該方法應用到求解TSP問題中[1]。該算法是啟發(fā)式搜算算法的一種，采用了分布式并行計算機制，易于與其他方法結合，具有強的魯棒性。同時，相對于其他搜算法，對初始路線要求不高，在搜索過程中不需要人工調整。研究表明，蟻群算法是解決TSP問題有效的算法之一，因此也成為近年來的研究熱點。

近年來，基于GPU（圖像處理器）的大規(guī)模通用并行計算，大大提高了計算機圖形處理的效率[2]。GPU的高速浮點運算能力、并行計算和可編程功能也為通用計算提供了良好的并行計算平臺，同時也為蟻群算法的高速并行實現(xiàn)提供了可能。NVIDIA公司的統(tǒng)一計算設備架構（CUDA），為研究人員利用CPU進行數(shù)據(jù)并行處理提供了便捷的手段[3]。通過GPU加速并行算法，是蟻群算法并行化、提高算法執(zhí)行速度的有效途徑之一。

1 蟻群算法基本原理

蟻群算法受蟻群行為和反應特征的啟發(fā)而得來的。覓食的螞蟻在走過的路上釋放信息素，其他覓食螞蟻將沿著留有信息素的路徑在相同位置找到食物。因此，信息素可用來實現(xiàn)間接通信的目的[4]?；谛畔⑺氐某鞘刑街D移概率公式：

2 基于GPU并行的蟻群算法

通過對CUDA和GPU并行程序設計的研究，將基于蟻群算法的TSP求解優(yōu)化路徑問題轉化為GPU中的多線程的并行處理過程，充分利用GPU的高速浮點運算和并行計算的特性， 以提高算法的速度。

在螞蟻遍歷城市的過程中，每只螞蟻獨立地建立自己的遍歷路徑，對螞蟻來說，自然地存在并行性。根據(jù)CUDA的編程模型[5]，我們很自然地會將每只螞蟻個體映射到CUDA的一個線程上，用線程來模擬你螞蟻個體，每個線程完成一只螞蟻的城市周游回路。

設螞蟻個數(shù)為M，城市個數(shù)為N，CUDA中Block個數(shù)為4，蟻群算法的GPU并行化模型中，總線程個數(shù)為M，每個Block中線程個數(shù)為M/4，如圖3所示。在模型中，將路徑狀態(tài)初始化、路徑轉移概率計算、路徑長度計算、更新信息素定義為CUDA函數(shù)。首先，M個線程被分配在4個Block中，同時啟動，計算各自的城市轉移概率，尋找轉移城市；其次，由N個線程分成N個Block，計算路徑上信息素增量；再次，用一個線程計算路徑長度和最優(yōu)路徑；最后N個線程分成N個Block，更信路徑信息素。

3 實驗與分析

實驗結果表明，采用GPU并行化蟻群算法取得了良好的加速效果，當蟻群規(guī)模由256增大到1024、城市規(guī)模由21增大到76時，加速倍數(shù)由3.0增大到10.75。數(shù)據(jù)顯示，問題規(guī)模越大，蟻群個體和城市規(guī)模越大，加速效果越好，對于更大規(guī)模的復雜問題，基于GPU的并行化蟻群算法將取得更高的加速比。

4 結束語

本文研究了基本蟻群算法的原理，并基于GPU和CUDA高速并行計算模型，利用GPU在CUDA7.0環(huán)境下，對蟻群算法進行化加速設計，實驗結果表明，該方法取得了良好的加速效果，當蟻群規(guī)模增大時，加速倍大幅度提高。數(shù)據(jù)顯示，蟻群個體和城市規(guī)模越大，加速效果越好。

參考文獻：

[1] 宗德才， 王康康， 丁勇. 蟻群算法求解旅行商問題綜述[J]. 計算機與數(shù)字工程， 2014（11）.

[2] 占正鋒， 李戈， 張學賀， 伊旭悅. 基于CUDA的圖像預處理并行化研究[J]. 智能工程， 2014.

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

[4] Shi-An Li，Min-Hao Yang，Chung-Wei Weng，Yi-Hong Chen，Chia-Hung Lo，Ching-Chang Wong. Ant Colony Optimization algorithm design and its FPGA implemention[J]. IEEE International Symposium on Intelligent Signal Processing and Communication Systems， 2012.

[5] David B.KirK， Wen-mei W. Hwu. 大規(guī)模并行處理器編程實戰(zhàn)[M]. 北京： 清華大學出版社， 2013.