基于GPU加速的細(xì)粒度并行蟻群算法.pdf

1、蟻群優(yōu)化算法(Ant colony optimization algorithin，ACO)源于對(duì)螞蟻覓食行為的研究，是一種基于群體智能方法的演化計(jì)算技術(shù)，在實(shí)際工程中表現(xiàn)出巨大的潛力。但在數(shù)值建模和優(yōu)化計(jì)算等許多領(lǐng)域中，處理大量數(shù)據(jù)和求解大規(guī)模復(fù)雜問(wèn)題時(shí)，ACO算法依然需要大量的計(jì)算時(shí)間，而并行ACO算法由于能較大幅度縮減問(wèn)題求解的時(shí)間，因此成為一個(gè)研究熱點(diǎn)。當(dāng)前并行ACO算法主要在并行機(jī)上運(yùn)行或用多線程技術(shù)模擬，主要存在下述不足：進(jìn)

2、程間通信損耗限制了粒子規(guī)模；大多數(shù)研究人員沒(méi)有硬件環(huán)境，無(wú)法使用并行機(jī)解決問(wèn)題；多線程技術(shù)是在CPU上用串行模擬并行，不能真正提高性能。 近年來(lái)，計(jì)算機(jī)圖形處理器(Graphics processing unit，GPU)繪制流水線的高速度和并行性以及近年來(lái)發(fā)展起來(lái)的可編程功能，使其在通用計(jì)算領(lǐng)域的應(yīng)用有著巨大的潛力。CUDA是Nvidia公司推出的GPU編程的統(tǒng)一計(jì)算設(shè)備架構(gòu)。在統(tǒng)一計(jì)算設(shè)備架構(gòu)下，GPU執(zhí)行的模式是并發(fā)的線程

3、。多個(gè)線程可以組成一個(gè)線程塊。一個(gè)線程塊中的線程能存取同一塊公用的存儲(chǔ)空間，而且可以快速進(jìn)行同步的動(dòng)作。 本文針對(duì)傳統(tǒng)并行蟻群算法在實(shí)際應(yīng)用中的不足，結(jié)合GPU的高速并行性，提出了一種基于GPU加速的細(xì)粒度并行蟻群算法(GPUACO)，將并行ACO求解過(guò)程轉(zhuǎn)化為CUDA內(nèi)核，使用CUDA線程塊模擬螞蟻個(gè)體，使ACO算法在GPU中加速執(zhí)行。本文主要以最大最小螞蟻系統(tǒng)和蟻群系統(tǒng)的并行實(shí)現(xiàn)為例，詳細(xì)描述了算法設(shè)計(jì)思想和程序?qū)崿F(xiàn)過(guò)程，提