基于FPGA實現(xiàn)粒子群算法解最短路徑

王飛宇，胡 靖

（黑龍江大學(xué)電子工程學(xué)院，哈爾濱 150080）

1 二進制粒子群算法硬件實現(xiàn)的優(yōu)勢

最短路徑求取是圖論的基本問題之一，它是指在有障礙物的地圖信息中，尋找一條從固體定起點到終止點的最短或者較優(yōu)的路徑，該路徑安全、不碰撞障礙，所走路程較近。常用最短路徑規(guī)劃方法包括啟發(fā)式圖搜索法、人工勢場法、神經(jīng)網(wǎng)絡(luò)法等，不同程度的提高求解最短路徑的速度與規(guī)模，但每一種算法都有其局限性。近年來，不少學(xué)者采用神經(jīng)網(wǎng)絡(luò)、蟻群算法、粒子群算法等進行最短路徑求解，用仿生算法進行路徑規(guī)劃成為明顯的發(fā)展趨勢。為了進一步探索更適合路徑規(guī)劃方法，近年也有學(xué)者嘗試用通過硬件實現(xiàn)粒子群算法進行路徑規(guī)劃，該方法可以在可以獲得最優(yōu)或最短路徑，而且其時間較短。然而該方法采用傳統(tǒng)粒子群優(yōu)化算法實現(xiàn)，而傳統(tǒng)的粒子群算法是一種用于連續(xù)優(yōu)化的數(shù)學(xué)模型，這就限制了工作環(huán)境不能離散模型而必須是連續(xù)模型，而且也會增加計算量增添機器負(fù)擔(dān)，因此這種情況在硬件實現(xiàn)上并不占有優(yōu)勢。為彌補這一不足，本文提出了一種采用二進制編碼粒子群算法的硬件實現(xiàn)方法。該算法采用柵格法對地圖信息建模，在此基礎(chǔ)上，將路徑表示為粒子位置的二進制編碼，并以路徑長度為適應(yīng)值，產(chǎn)生初始種群后，根據(jù)粒子更新策略進行速度位置更新，經(jīng)過一定迭代次數(shù)后即可獲得一條我們所需要的最優(yōu)路徑或最短路徑。

2 實現(xiàn)方法與模型建立

最短路徑的求取問題中，首先要解決的就是環(huán)境的模型化，將環(huán)境路況信息生成數(shù)字模型地圖，使機器識別。常見的建模方法有，人工勢場法、權(quán)值路徑法、鏈圖法等，這些方法可以較為精確的實現(xiàn)地圖的映射，同時也較為精確的求解出最短路徑。但是其數(shù)據(jù)量較大計算速度較慢，地圖更新數(shù)據(jù)量更為巨大，在硬件實現(xiàn)上，龐大的數(shù)據(jù)量以及較為復(fù)雜的運算并沒有體現(xiàn)出其優(yōu)勢，為了減小硬件實現(xiàn)的難度，以及使其更適合硬件實現(xiàn)，采用柵格法實現(xiàn)地圖，該方法計算量較小，簡單。

將需要做最短路徑求取的地圖信息采集、處理。根據(jù)將要實現(xiàn)的精度，將地圖柵格化為只含有0和1的矩陣信息，該矩陣中1代表障礙，0代表可以行駛的道路，每一個0和1對應(yīng)著現(xiàn)實環(huán)境中的路況信息，將障礙物根據(jù)所應(yīng)用的精度化成矩陣中1的信息。將地圖信息存至RAM上根據(jù)節(jié)點的個數(shù)設(shè)置RAM的深度，寬度為1位。因在FPGA中只可以通過地址進行操作，需要設(shè)計一個地址坐標(biāo)轉(zhuǎn)換電路，將需要計算的地圖坐標(biāo)信息，轉(zhuǎn)換為地址對RAM進行存取操作。該部分通過對矩陣的長寬，與地址關(guān)系的對應(yīng)關(guān)系，進行編碼，用case語句實現(xiàn)坐標(biāo)轉(zhuǎn)換的計算。

3 算法的實現(xiàn)流程

因為我使用FPGA來實現(xiàn)粒子群算法，為了應(yīng)用硬件的優(yōu)勢來做到速度提升，所以采取下面的方法來實現(xiàn)二進制粒子群算法。粒子群算法的來源于生活中動物的行為，機器與動物較為不同的一點是動物是獨立的個體，而且之間是可以交流的。通過硬件來實現(xiàn)粒子群算法，的核心就是應(yīng)用硬件的并行特性，來實現(xiàn)粒子群優(yōu)化算法并行運算特性。將整體的算法劃分為下面幾個模塊：路徑存儲模塊、路徑計算模塊（初始化路徑生成模塊）、路徑比較模塊、全局與局部距離比較模塊、速度，位置更新模塊、核心計算模塊。具體流程如下：（1）我們將外部采取到的地圖信息通過接口將其存與10塊并行的RAM，將地圖信息存儲為十份。（2）這10個RAM塊上進行算法的初步操作，計算出10條初始路徑與其長度。（3）將計算得出的10條路徑的長度進行一次比較。（4）將比較中結(jié)果長度最短的路徑信息進行存儲。（5）通過粒子群算法的公式對路徑進行優(yōu)化。（6）將優(yōu)化信息反饋到初始化路徑求取模塊，進行路徑的更新。（7）更新后的路徑最為局部最優(yōu)路徑與之前的最優(yōu)路徑進行比較，將最小的值進行存儲。將這個過程迭代20次，輸出最優(yōu)解。同時再此期間如果得出最短距離等于起點到終點的曼哈頓距離，則視為已求出最短路徑跳出循環(huán)輸出最短路徑。

在算法的實現(xiàn)過程中。因為我們引用硬件實現(xiàn)其中的一些部分因硬件實現(xiàn)起來較為困難，對其進行改進，使算法更適合硬件實現(xiàn)，重點改進部分有如下幾個部分：（1）因要進行路徑的比較，要將路徑存儲起來，在FPGA上如果對存儲區(qū)進行操作只能將內(nèi)容一個一個取出作比較。數(shù)據(jù)量較多時，將會降低速度有較高的延時，這里我們通過將信息存儲到寄存器組上，使比較以及更新更為簡單。（2）初始化路徑生成為隨機生成，我們需要進行隨機輸?shù)漠a(chǎn)生，這里使用LFSR這種偽隨機的硬件結(jié)構(gòu)產(chǎn)生，通過改變初始變量可得到在一定范圍內(nèi)較多的隨機數(shù)。（3）一些較大的浮點數(shù)的操作計算采用查找表來實現(xiàn)。

4 結(jié)束語

通過對算法的硬件改進，是該方法更易于硬件實現(xiàn)，但是并沒有完全采取并行操作，對速度和面積兩個方面都做了考慮，提升了算法的速度。