基于GPU加速的并行粒子群算法及其應(yīng)用.pdf

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

2、限制了粒子規(guī)模；大多數(shù)研究人員沒(méi)有硬件環(huán)境，無(wú)法使用并行機(jī)解決問(wèn)題；多線(xiàn)程技術(shù)是在CPU上用串行模擬并行，不能真正提高性能。 近年來(lái)，計(jì)算機(jī)圖形處理器(Graphics processing unit，GPU)繪制流水線(xiàn)的高速度和并行性以及近年來(lái)發(fā)展起來(lái)的可編程功能，使其在通用計(jì)算領(lǐng)域的應(yīng)用有著巨大的潛力。本文針對(duì)傳統(tǒng)并行粒子群算法在實(shí)際應(yīng)用中的不足，結(jié)合GPU的高速并行性，本文提出了一種基于GPU加速的細(xì)粒度并行粒子群算法(G

3、PUPSO)，將并行PSO求解過(guò)程轉(zhuǎn)化為GPU紋理并行渲染過(guò)程，使得PSO算法在GPU中加速執(zhí)行，在取得了較好的優(yōu)化效果的同時(shí)，解決了細(xì)粒度并行的粒子規(guī)模限制問(wèn)題，提高了算法的運(yùn)算速度。 變形物體的碰撞檢測(cè)一直是機(jī)器人、虛擬現(xiàn)實(shí)、動(dòng)畫(huà)仿真等領(lǐng)域中一個(gè)非常關(guān)鍵的問(wèn)題。本文針對(duì)傳統(tǒng)層次包圍盒算法在變形物體的碰撞檢測(cè)中每一幀更新數(shù)據(jù)量大，效率低的難點(diǎn)問(wèn)題，將基于GPU加速的并行粒子群算法(GPUPSO)應(yīng)用到碰撞檢測(cè)領(lǐng)域，實(shí)現(xiàn)了一種基