基于FPGA的蟻群算法硬件化技術(shù)研究.pdf

1、蟻群算法(ACA)是模擬蟻群覓食行為的一種啟發(fā)式仿生類(lèi)智能進(jìn)化算法。近年來(lái)它在組合優(yōu)化、函數(shù)優(yōu)化等領(lǐng)域以及網(wǎng)絡(luò)路由、數(shù)據(jù)挖掘、機(jī)器人路徑規(guī)劃等工程問(wèn)題上廣泛應(yīng)用，取得了良好的效果。蟻群算法的硬件實(shí)現(xiàn)是仿生硬件(BHW)領(lǐng)域的一個(gè)分支，也是蟻群算法發(fā)展的高級(jí)階段。蟻群算法采用分布式并行計(jì)算和正反饋機(jī)制。其硬件實(shí)現(xiàn)具有：自組織、自適應(yīng)、自修復(fù)以及執(zhí)行速度快等優(yōu)點(diǎn)，能滿(mǎn)足實(shí)時(shí)系統(tǒng)的需要。
　　 本論文中心議題是蟻群算法的硬件實(shí)現(xiàn)。針對(duì)

2、蟻群算法在FPGA上的有效映射以及實(shí)時(shí)系統(tǒng)的構(gòu)建問(wèn)題，進(jìn)行了模型選擇和算法改進(jìn)；提出并命名逐輪定位加權(quán)蟻群優(yōu)化BW-ACO算法，建立蟻群算法在迭代更新問(wèn)題上的一組經(jīng)驗(yàn)公式，代替原有的迭代算法；給出硬件實(shí)現(xiàn)方案，成功實(shí)現(xiàn)了其在FPGA上的有效映射；論文詳細(xì)討論硬件結(jié)構(gòu)及各個(gè)模塊的內(nèi)部實(shí)現(xiàn)細(xì)節(jié)。
　　 本論文的主要研究?jī)?nèi)容包括：
　　 第1章概述課題背景及蟻群硬件實(shí)現(xiàn)的研究現(xiàn)狀。
　　 第2章概述蟻群算法的基本原理及

3、本文涉及的可編程邏輯器件FPGA、開(kāi)發(fā)環(huán)境、開(kāi)發(fā)語(yǔ)言及其開(kāi)發(fā)流程。
　　 第3章詳細(xì)論述蟻群硬件實(shí)現(xiàn)技術(shù)：一是基于單機(jī)總誤時(shí)排序問(wèn)題(SMTTP)模型的群體蟻群算法(P-ACO)在FPGA上的有效實(shí)現(xiàn)；另一個(gè)是基于旅行商問(wèn)題(TSP)模型的計(jì)數(shù)器蟻群優(yōu)化(C-ACO)硬件自啟發(fā)實(shí)現(xiàn)。
　　 基于蟻群算法的離散性和并行性特點(diǎn)，本文選擇數(shù)字圖像分割問(wèn)題，作為硬件實(shí)現(xiàn)的模型。
　　 蟻群算法與圖像分割問(wèn)題相結(jié)合，有不同

4、的切入方式。目前，研究學(xué)者已提出三種不同模型：基于像素的模型、基于聚類(lèi)的模型和基于閾值的模型。模型不同，運(yùn)算量大不相同，硬件實(shí)現(xiàn)結(jié)構(gòu)及復(fù)雜程度差別很大。綜合考慮，本文選擇較適合的基于閾值的模型。
　　 本文提出并命名逐輪定位加權(quán)蟻群優(yōu)化BW-ACO算法，給出其硬件實(shí)現(xiàn)方案，其主要的創(chuàng)新點(diǎn)如下：
　　 ①提出了一種逐輪定位搜索方法：螞蟻每做一輪迭代，依次從閾值的高位向低位進(jìn)行定位，留出最后低三位作為搜索空間，在優(yōu)化搜索進(jìn)程

5、的同時(shí)避免陷入局部最優(yōu)。
　　 ②依據(jù)信息素矩陣和轉(zhuǎn)移概率矩陣的數(shù)值規(guī)律，研究出一種以簡(jiǎn)單的加減法、左右移運(yùn)算代替復(fù)雜乘除法的方法，得到下一輪迭代所需的信息素和轉(zhuǎn)移概率，在此基礎(chǔ)上提出一組經(jīng)驗(yàn)公式用于硬件實(shí)現(xiàn)時(shí)的有效映射，以適合現(xiàn)有的FPGA硬件條件。
　　 ③采用數(shù)字量化的定量加權(quán)信息素更新方式代替原有的需要復(fù)雜計(jì)算的信息素增量更新方案，同時(shí)采用精英策略以加快搜索進(jìn)程。
　　 第4章針對(duì)提出的BW-ACO算法進(jìn)