改良型螞蟻演算法之路徑規劃及其在FPGA之實現

Abstract

本論文所提出一改良型螞蟻演算法應用於路徑規劃，解決規劃最佳路徑時容易出現區域最佳解的問題。原先的蟻群系統演算法(Ant Colony System , ACS)雖收斂快速，卻極易陷入區域解，因此，本論文將提出一種改良型螞蟻演算法，透過所提出之費洛蒙更新機制，包含部分費洛蒙更新以及反向費洛蒙更新，使得螞蟻具有更多探索新路徑的能力，減少只追隨同一路徑的機會。為了驗證論文中所提出之方法可以確實提升路徑規劃之精確度，將會與傳統ACS比較，以多種不同路徑進行規劃與比較其性能。為了縮短運算時間，提升計算的效率，本論文所提出之改良型螞蟻演算法將以DE2-70多媒體開發平台，利用FPGA電路加以實現。實驗結果證明以全硬體設計方式可以用較少的處理時間獲得路徑規劃結果，確實提升嵌入式應用系統之效能。Although traditional ant colony system (ACS) has the ability of fast convergence, it tends to fail into local optima. To solve this problem, this thesis proposes an improved ant colony system algorithm for path planning by establishing two new mechanisms for pheromone updating, including partial pheromone updating and opposite pheromone updating. As a result, the ability of global searching of the improved ACS can be significantly enhanced in comparison to the traditional ACS algorithms in deriving an optimal path. Simulation results show the proposed approach has a better performance in terms of shortest distance, mean distance, and successful rate of the optimal paths than those obtained by the traditional ACS algorithms. To further reduce the computation time, the improved ant colony system algorithm for path planning is realized on FPGA circuit using a DE2-70 multimedia development board to verify the practicability of the proposed algorithm. Experimental results show that the execution efficiency of path planning is significantly improved by the full hardware design for embedded applications.