遺傳算法是一種基于自然選擇原理的優(yōu)化算法，在很多領(lǐng)域有著廣泛的應(yīng)用。但是，遺傳算法使用計算機軟件實現(xiàn)時，會隨著問題復(fù)雜度和求解精度要求的提高，產(chǎn)生很大的計算延時，這種計算的延時限制了遺傳算法在很多實時性要求較高場合的應(yīng)用。為了提升運行速度，可以使用FPGA作為硬件平臺，設(shè)計數(shù)字系統(tǒng)完成遺傳算法。和軟件實現(xiàn)相比，硬件實現(xiàn)盡管在實時性和并行性方面具有很大優(yōu)勢，但同時會導(dǎo)致系統(tǒng)的靈活性不足、通用性不強。本文針對上述矛盾，使用基于功能的模塊化思想，將基于FPGA的遺傳算法硬件平臺劃分成兩類模塊：系統(tǒng)功能模塊和算子功能模塊。針對不同問題，可以在保持系統(tǒng)功能模塊不變的前提下，選擇不同的遺傳算子功能模塊完成所需要的優(yōu)化運算。本文基于Xilinx公司的Virtex5系列FPGA平臺，使用VerilogHDL語言實現(xiàn)了偽隨機數(shù)發(fā)生模塊、隨機數(shù)接口模塊、存儲器接口/控制模塊和系統(tǒng)控制模塊等系統(tǒng)功能模塊，以及基本位交叉算子模塊、PMX交叉算子模塊、基本位變異算子模塊、交換變異算子模塊和逆轉(zhuǎn)變異算子模塊等遺傳算法功能模塊，構(gòu)建了系統(tǒng)功能構(gòu)架和遺傳算子庫。該設(shè)計方法不僅使遺傳算法平臺在解決問題時具有更高的靈活性和通用性，而且維持了系統(tǒng)架構(gòu)的穩(wěn)定。本文設(shè)計了多峰值、不連續(xù)、不可導(dǎo)函數(shù)的極值問題和16座城市的旅行商問題 (TSP)對遺傳算法硬件平臺進行了測試。根據(jù)測試結(jié)果，該硬件平臺表現(xiàn)良好，所求取的最優(yōu)解誤差均在1％以內(nèi)。相對于軟件實現(xiàn)，該系統(tǒng)在求解一些復(fù)雜問題時，速度可以提高2個數(shù)量級。最后，本文使用FPGA實現(xiàn)了粗粒度并行遺傳算法模型，并用于 TSP問題的求解。將硬件平臺的運行速度在上述基礎(chǔ)上提高了近1倍，取得了顯著的效果。關(guān)鍵詞：遺傳算法，硬件實現(xiàn)，并行設(shè)計，F(xiàn)PGA，TSP
標簽：
FPGA
算法
硬件實現(xiàn)
上傳時間：
2013-06-15
上傳用戶：hakim
