基于遺傳算法的組合邏輯電路設(shè)計的FPGA實現(xiàn)

周雄偉，熊慶國，況海龍，孫艷琴，李 倩

（武漢科技大學(xué) 信息科學(xué)與工程學(xué)院，湖北 武漢 430081）

遺傳算法（Genetic Algorithm）是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計算模型，是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法，它最初是由美國Michigan大學(xué)J.Holland教授于1975年首先提出來的。隨著經(jīng)濟(jì)社會的快速發(fā)展，人類科學(xué)研究與生產(chǎn)活動的廣度與深度都大大拓展了。科研與生產(chǎn)實踐中涌現(xiàn)出的大量新課題對作為社會發(fā)展催化劑的信息與控制科學(xué)提出了前所未有的挑戰(zhàn)[1]。傳統(tǒng)信息處理算法在面對各種非線性、不確定、不能精確解析以及建模機(jī)理復(fù)雜的問題時，往往顯得捉襟見肘。正是在這種背景下，各種智能信息處理算法如雨后春筍般涌現(xiàn)出來。作為智能信息處理算法中的重要一員，遺傳算法近年來以其獨特而卓越的性能日漸引起了人們的關(guān)注[2]。

組合邏輯電路其特點是功能上無記憶，結(jié)構(gòu)上無反饋，即電路在任意時刻的輸出狀態(tài)只取決于該時刻各輸入狀態(tài)的組合，而與電路的原狀態(tài)無關(guān)。本文通過實例介紹組合邏輯電路的設(shè)計方法，并通過電子設(shè)計自動化EDA（Electronic Design Automation）進(jìn)行仿真分析，使組合邏輯電路的設(shè)計變得更方便，更實用。

隨著FPGA性能的不斷提高，基于FPGA的計算加速已經(jīng)逐漸成為提高計算速度和計算效率的重要手段之一。FPGA能夠?qū)崿F(xiàn)程序的并行化處理，不僅結(jié)構(gòu)簡單，而且有效地減少了運算時間、提高了運行效率，為遺傳算法能在一些實時、高速的場合得到應(yīng)用提供了依據(jù)[3]。

1 基于FPGA遺傳算法設(shè)計

遺傳算法是一種多點并行的迭代搜索算法，它的每一代稱為一個種群，由多個個體組成，每個個體稱為染色體，染色體由一定數(shù)目的字符組成。每個字符稱為一個基因，基因在染色體中的位置決定了基因所表達(dá)的特性[4]。

文中基于FPGA的遺傳算法，整個系統(tǒng)分為4個單元，4個單元分別為：選擇單元、交叉單元、變異單元和適應(yīng)度計算單元。

1.1 選擇單元

選擇單元執(zhí)行遺傳算法中的選擇操作。選擇策略決定哪些個體存活并得以繁殖，因其直接關(guān)系到遺傳算法的運行導(dǎo)向問題故對遺傳算法的性能有直接并且重大的影響。標(biāo)準(zhǔn)遺傳算法所采用的輪盤賭選擇策略簡便直觀，但可能會產(chǎn)生較大的抽樣誤差。于是，各種改進(jìn)的選擇策略產(chǎn)生了。

最早提出的使用濃度控制的選擇策略可以保證群體的多樣性從而避免了早熟現(xiàn)象并且提高了算法的魯棒性及運算效率。后來通過對浮點遺傳算法早熟收斂現(xiàn)象的分析，有人提出了一種新的父代選擇策略，即使用當(dāng)前代的子代個體作為下代的父代個體，可使交叉算子持續(xù)地探索和開發(fā)新空間。目前，人們又發(fā)現(xiàn)可以通過選擇策略的改變調(diào)控并維持種群多樣性。這類研究成果中，文獻(xiàn)中提到的重復(fù)串的適應(yīng)度處理是一個有益的嘗試。

1.2 交叉單元

交叉模塊執(zhí)行遺傳算法中的交叉操作。由隨機(jī)數(shù)模塊產(chǎn)生的隨機(jī)數(shù)與事先確定的交叉概率相比較，如果隨機(jī)數(shù)小于交叉概率，則一對個體進(jìn)行交叉操作，否則該對個體不變，直接進(jìn)入變異模塊。

文中一對個體進(jìn)行交叉操作的基因位由隨機(jī)數(shù)決定。隨機(jī)數(shù)模塊產(chǎn)生一個與個體等長的隨機(jī)二進(jìn)制串，若隨機(jī)二迸制串中的某一位為1，則該對個體中該位置的基因相互交叉；否則，該對個體中該位置的基因保持不變。

1.3 變異單元

變異模塊執(zhí)行遺傳算法中的變異操作。與交叉模塊相似，變異模塊也是將隨機(jī)數(shù)模塊產(chǎn)生的隨機(jī)數(shù)與事先確定的變異概率相比較，決定是否進(jìn)行變異操作。同時個體中進(jìn)行變異操作的基因位也是由一個與個體等長的隨機(jī)二進(jìn)制字符串決定的。對個體而言，執(zhí)行變異操作的基因位不宜過多，否則容易對個體造成較大的破壞，影響種群的穩(wěn)定性[5]。本文將兩個隨機(jī)二進(jìn)制字符串 （每一位0、l等概率）進(jìn)行相與操作，這樣得到的新的隨機(jī)二進(jìn)制字符串中每一位為1的概率將降低到25%，用這個新的隨機(jī)二進(jìn)制串來決定個體變異的基因位。這樣執(zhí)行變異操作的個體中，每一位基因變異的概率也會降低到25%。

1.4 適應(yīng)度計算單元

適應(yīng)度計算模塊執(zhí)行遺傳算法中的適應(yīng)度計算比較操作，它根據(jù)適應(yīng)度計算函數(shù)來計算種群中每一個個體的適應(yīng)度，包括遺傳算法開始時初始化產(chǎn)生的種群和后來遺傳變異后產(chǎn)生的種群，并把每個個體的適應(yīng)度大小保存到存儲器中。同時，適應(yīng)度計算模塊還需要記錄每一代種群中適應(yīng)度最高的個體。適應(yīng)度計算模塊有一個內(nèi)置的計數(shù)器，計數(shù)器隨適應(yīng)度計算模塊的啟動而啟動，從0開始計數(shù)，每個時鐘周期加l。計數(shù)器數(shù)值表示當(dāng)前個體及其適應(yīng)度在存儲器模塊當(dāng)中的存放地址[6]。適應(yīng)度計算模塊停止工作時，計數(shù)器會重新歸零，等待新一輪的啟動信號。

2 遺傳算法的過程設(shè)計

遺傳算法通過對當(dāng)前種群施加選擇、交叉、變異等一系列遺傳操作，產(chǎn)生出新一代的種群，通過多次迭代，使種群逐步進(jìn)化到包含或接近最優(yōu)解的狀態(tài)，如圖1所示。一般來說，一個完整的遺傳算法包括編碼、初始種群的生成、用于進(jìn)行個體評估的適應(yīng)度函數(shù)的設(shè)計、遺傳算子（選擇、交叉和變異）以及控制參數(shù)（終止準(zhǔn)則）的設(shè)定5個方面[7]。

1）系統(tǒng)由外部給出reset信號：隨機(jī)數(shù)模塊開始產(chǎn)生隨機(jī)數(shù)種子；控制模塊重啟，重新啟動后，由該模塊控制系統(tǒng)運行。

2）控制模塊給出相應(yīng)信號，初始化模塊運行，初始化種群。

3）當(dāng)初始化完畢后，有控制模塊發(fā)出相應(yīng)信號，系統(tǒng)進(jìn)入進(jìn)化計算階段，進(jìn)行遺傳算法的具體操作。

4）各個遺傳算法功能模塊進(jìn)行算子操作，經(jīng)由交叉、變異、選擇操作產(chǎn)生新的種群，同時記錄系統(tǒng)的運行信息。如未完成本代進(jìn)化計算，則重復(fù)本步驟。

5）完成一代計算后，由控制模塊發(fā)出相應(yīng)指令，存儲相關(guān)運行參數(shù)、轉(zhuǎn)換存儲器的工作狀態(tài)。如果以完成計算，則發(fā)出完成信號，如果未完成，重復(fù)步驟4）。

圖1 遺傳算法流程圖Fig.1 Flow chart of genetic algorithm

2.1 遺傳算法編碼

把一個問題的可行解從其解空間轉(zhuǎn)化到遺傳算法所能處理的搜索空間的轉(zhuǎn)化方法叫做編碼。編碼方式應(yīng)具有如下性質(zhì)：完備性、封閉性、健全性和非冗余性。

遺傳算法的編碼方式有很多種，二進(jìn)制編碼方式是最常用的編碼方式之一，最早由Holland提出。但是二進(jìn)制編碼的遺傳算法進(jìn)行數(shù)值優(yōu)化時，存在連續(xù)到離散的映射誤差、精度不高，最優(yōu)解附近搜索較慢等缺點。雖然提高個體編碼串長度可以提高精度，但是會使遺傳算法的搜索空間增加，從而使得搜索變得異常緩慢[8]。

本文中遺傳算法主要解決的問題是組合邏輯電路的自動設(shè)計，組合邏輯電路由與門、或門、非門、同或門、異或門五種基本的門電路組成。在FPGA上進(jìn)行遺傳算法的編碼，本文采用二進(jìn)制字符串編碼的方法，每個個體都有64位二進(jìn)制數(shù)組成，由64位二進(jìn)制數(shù)解碼出一個組合邏輯電路。

2.2 隨機(jī)數(shù)產(chǎn)生模塊

隨機(jī)數(shù)控制模塊的作用是根據(jù)外部信號控制隨機(jī)數(shù)內(nèi)部模塊，發(fā)出相應(yīng)的使能、重啟信號，產(chǎn)生隨機(jī)數(shù)種子，從而產(chǎn)生隨機(jī)數(shù)。

本系統(tǒng)中隨機(jī)數(shù)模塊所產(chǎn)生的隨機(jī)序列由線性反饋移位寄存器（Linear Feedback Shift Registers，LFSR）生成。 LFSR在FPGA上易于實現(xiàn)，且所產(chǎn)生的隨機(jī)序列具有周期長、隨機(jī)性好的特點[9]。隨機(jī)數(shù)模塊需要向選擇模塊提供隨機(jī)序列，作為存儲器單元的地址，同時隨機(jī)數(shù)模塊還要向交叉模塊和變異模塊提供隨機(jī)序列，用于確定是否執(zhí)行交叉和變異操作，以及執(zhí)行交叉和變異操作的位置。

2.3 存儲器模塊

存儲器模塊用來存儲種群中的個體及其適應(yīng)度。在本系統(tǒng)中，個體和適應(yīng)度是分開存儲的，因而對整個種群而言，其存儲區(qū)可分為4個部分：父代個體存儲區(qū)，父代適應(yīng)度存儲區(qū)，子代個體存儲區(qū)以及子代適應(yīng)度存儲區(qū)[10]。

由于本系統(tǒng)中的遺傳算法采用完全流水線實現(xiàn)，因而必然會涉及到對存儲器模塊的同時讀寫操作，比如在選擇模塊從存儲器模塊中讀取父代種群中的個體及其適應(yīng)度的同時，適應(yīng)度模塊則在向存儲器模塊中寫入子代種群中的新個體及其適應(yīng)度。

3 實驗結(jié)果

系統(tǒng)在Altera公司的Cyclone系列EPlC6Q240C8型號芯片上進(jìn)行了實現(xiàn)。系統(tǒng)采用Verilog語言編寫，開發(fā)平臺為Altera公司自帶的QuartusII 6.0集成環(huán)境。為驗證系統(tǒng)的正確性和測試系統(tǒng)的性能，本文，對系統(tǒng)進(jìn)行了測試，即給出一個三輸入一輸出的組合邏輯電路的真值表，測試真值表如表1所示。

表1 三輸入一輸出真值表Tab.1 Value table of three input and one output

遺傳算法參數(shù)設(shè)置如下：種群規(guī)模為100，交叉概率為0.6，變異概率為0.1，基因長度為16，遺傳代數(shù)為100。其中針對給出的真值表，通過代碼輸入、編譯、綜合、布局布線后，得到結(jié)果如圖2所示。

圖2 遺傳算法的最優(yōu)解Fig.2 Optimal solution of the genetic algorithm

即最優(yōu)解為：C3bFC396。經(jīng)過解碼，得到電路圖如圖3所示。所得到的電路圖滿足真值表的要求。

圖3 遺傳算法解碼得到的組合邏輯電路Fig.3 Assembly logic circuit of decoding of get the genetic algorithm

4 結(jié)束語

本文在FPGA上實現(xiàn)了基于遺傳算法的組合邏輯電路的自動設(shè)計。對整個系統(tǒng)結(jié)構(gòu)進(jìn)行了自頂而下的設(shè)計，對模塊功能進(jìn)了劃分。硬件實現(xiàn)遺傳算法能有效地縮短運行時間，為實時應(yīng)用提供了可能。隨著FPGA芯片技術(shù)的進(jìn)一步發(fā)展，大規(guī)模并行遺傳算法的實現(xiàn)也將成為可能。

[1]AltyS，Angarita-JaimesN，MillasseauSC，eta1.Arterialstiffness from the digital volume pulse waveform[J].IEEE Transactions on Biomedical Engineering，2007，54（12）:2268-2275.

[2]張麗萍，柴躍廷.遺傳算法的現(xiàn)狀及發(fā)展動向[J].信息與控制，2001，30（6）:531-536.

ZHANG Li-ping，CHAI Yue-ting.Genetic algorithm of the present situation and the development trend[J].Information and control，2001，30（6）:531-536.

[3]李敏強(qiáng).遺傳算法的基本理論與應(yīng)用[M].北京:科學(xué)出版社，2002.

[4]周穎波，鄺繼順，楊鵬.基于FPGA的遺傳算法流水線設(shè)計與實現(xiàn)[J].計算機(jī)工程，2011，37（7）:268-270.

ZHOU Ying-bo， KUANG Ji-shun， YANG Peng.Design and implementation of genetic algorithm pipelining based on FPGA[J].Computer Engineering，2011，37（7）:268-270.

[5]王金明，楊吉斌.數(shù)字系統(tǒng)設(shè)計與Verilog HDL[M].北京:北京電子工業(yè)出版社，2002.

[6]谷曉忱，張民選.一種基于FPGA的高斯隨機(jī)數(shù)生成器的設(shè)計與實現(xiàn)[J].計算機(jī)學(xué)報，2011，1（1）:165-172.

GU Xiao-chen，ZHANG Min-xuan.Design and implementation of a FPGA based gaussian random number generator[J].Chinese journal of computers，2011，1（1）:165-172.

[7]房磊，張煥春，朱立力.基于FPGA的并行遺傳算法硬件實現(xiàn)的研究[J].南京航空航天大學(xué)學(xué)報，2004，36（5）:628-632.

FANG Lei， ZHANG Huan-chun， ZHU Li-li.Research of realization the parallel genetic algorithm based on FPGA[J].Journal of Nanjing University of Aeronautics，2004，36 （5）:628-632.

[8]聶鑫，李元香，王峰.基于FPGA的遺傳算法實現(xiàn)[J].計算機(jī)與數(shù)字工程，2009，37（8）:9-11.

NIE Xin， Li Yuan-xiang， WANG Feng.Implementation of a FPGA based Genetic Algorithm [J].Computer&Digital Engineering，2009，37（8）:9-11.

[9]周明，孫樹棟.遺傳算法原理及應(yīng)用[M].北京:國防工業(yè)出版社，1999.

[10]Higuchi T， LIU Yong， YAO Xin.Evolvable Hardware[M].New York Springer，2006.