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

楊雅寧+藺勇

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

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

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

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

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

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

1 蟻群算法基本原理

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

2 基于GPU并行的蟻群算法

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

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

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

3 實驗與分析

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

4 結束語

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

參考文獻：

[1] 宗德才， 王康康， 丁勇. 蟻群算法求解旅行商問題綜述[J]. 計算機與數字工程， 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. 大規模并行處理器編程實戰[M]. 北京： 清華大學出版社， 2013.