楊雅寧+藺勇

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

關(guān)鍵詞：蟻群算法；GPU；CUDA

中圖分類號(hào)：TP18 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）12-0206-02

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

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

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

1 蟻群算法基本原理

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

2 基于GPU并行的蟻群算法

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

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

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

3 實(shí)驗(yàn)與分析

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

4 結(jié)束語

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

參考文獻(xiàn)：

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

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

[3] 李建明， 胡祥培， 龐占龍， 錢昆明. 一種基于GPU 加速的細(xì)粒度并行蟻群算法[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ī)模并行處理器編程實(shí)戰(zhàn)[M]. 北京： 清華大學(xué)出版社， 2013.