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

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

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