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

1)系統(tǒng)由外部給出reset信號：隨機數(shù)模塊開始產(chǎn)生隨機數(shù)種子；控制模塊重啟，重新啟動后，由該模塊控制系統(tǒng)運行。
2)控制模塊給出相應信號，初始化模塊運行，初始化種群。
3)當初始化完畢后，有控制模塊發(fā)出相應信號，系統(tǒng)進入進化計算階段，進行遺傳算法的具體操作。
4)各個遺傳算法功能模塊進行算子操作，經(jīng)由交叉、變異、選擇操作產(chǎn)生新的種群，同時記錄系統(tǒng)的運行信息。如未完成本代進化計算，則重復本步驟。
5)完成一代計算后，由控制模塊發(fā)出相應指令，存儲相關(guān)運行參數(shù)、轉(zhuǎn)換存儲器的工作狀態(tài)。如果以完成計算，則發(fā)出完成信號，如果未完成，重復步驟4)。
2．1 遺傳算法編碼
把一個問題的可行解從其解空間轉(zhuǎn)化到遺傳算法所能處理的搜索空間的轉(zhuǎn)化方法叫做編碼。編碼方式應具有如下性質(zhì)：完備性、封閉性、健全性和非冗余性。
遺傳算法的編碼方式有很多種，二進制編碼方式是最常用的編碼方式之一，最早由Holland提出。但是二進制編碼的遺傳算法進行數(shù)值優(yōu)化時，存在連續(xù)到離散的映射誤差、精度不高，最優(yōu)解附近搜索較慢等缺點。雖然提高個體編碼串長度可以提高精度，但是會使遺傳算法的搜索空間增加，從而使得搜索變得異常緩慢。
本文中遺傳算法主要解決的問題是組合邏輯電路的自動設計，組合邏輯電路由與門、或門、非門、同或門、異或門五種基本的門電路組成。在FPGA上進行遺傳算法的編碼，本文采用二進制字符串編碼的方法，每個個體都有64位二進制數(shù)組成，由64位二進制數(shù)解碼出一個組合邏輯電路。
2．2 隨機數(shù)產(chǎn)生模塊
隨機數(shù)控制模塊的作用是根據(jù)外部信號控制隨機數(shù)內(nèi)部模塊，發(fā)出相應的使能、重啟信號，產(chǎn)生隨機數(shù)種子，從而產(chǎn)生隨機數(shù)。
本系統(tǒng)中隨機數(shù)模塊所產(chǎn)生的隨機序列由線性反饋移位寄存器(Linear Feedback Shift Registers，LFSR)生成。LFSR在FPGA上易于實現(xiàn)，且所產(chǎn)生的隨機序列具有周期長、隨機性好的特點。隨機數(shù)模塊需要向選擇模塊提供隨機序列，作為存儲器單元的地址，同時隨機數(shù)模塊還要向交叉模塊和變異模塊提供隨機序列，用于確定是否執(zhí)行交叉和變異操作，以及執(zhí)行交叉和變異操作的位置。
2．3 存儲器模塊
存儲器模塊用來存儲種群中的個體及其適應度。在本系統(tǒng)中，個體和適應度是分開存儲的，因而對整個種群而言，其存儲區(qū)可分為4個部分：父代個體存儲區(qū)，父代適應度存儲區(qū)，子代個體存儲區(qū)以及子代適應度存儲區(qū)。
由于本系統(tǒng)中的遺傳算法采用完全流水線實現(xiàn)，因而必然會涉及到對存儲器模塊的同時讀寫操作，比如在選擇模塊從存儲器模塊中讀取父代種群中的個體及其適應度的同時，適應度模塊則在向存儲器模塊中寫入子代種群中的新個體及其適應度。

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