基于FPGA實現粒子群算法解最短路徑

王飛宇，胡 靖

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

1 二進制粒子群算法硬件實現的優勢

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

2 實現方法與模型建立

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

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

3 算法的實現流程

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

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

4 結束語

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