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

摘要：基于遺傳算法的組合邏輯電路的自動(dòng)設(shè)計(jì)，依據(jù)給出的真值表，利用遺傳算法自動(dòng)生成符合要求的組合邏輯電路。由于遺傳算法本身固有的并行性，采用軟件實(shí)現(xiàn)的方法在速度上往往受到本質(zhì)是串行計(jì)算的計(jì)算機(jī)制約，因此采用硬件化設(shè)計(jì)具有重要的意義。為了證明基于FPGA的遺傳算法的高效性，設(shè)計(jì)了遺傳算法的各個(gè)模塊，實(shí)現(xiàn)了基于FPGA的遺傳算法。
關(guān)鍵詞：遺傳算法；組合邏輯電路；FPGA；隨機(jī)數(shù)

遺傳算法(Genetic Algorithm)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過(guò)程的計(jì)算模型，是一種通過(guò)模擬自然進(jìn)化過(guò)程搜索最優(yōu)解的方法，它最初是由美國(guó)Michigan大學(xué)J．Holland教授于1975年首先提出來(lái)的。隨著經(jīng)濟(jì)社會(huì)的快速發(fā)展，人類科學(xué)研究與生產(chǎn)活動(dòng)的廣度與深度都大大拓展了?？蒲信c生產(chǎn)實(shí)踐中涌現(xiàn)出的大量新課題對(duì)作為社會(huì)發(fā)展催化劑的信息與控制科學(xué)提出了前所未有的挑戰(zhàn)。傳統(tǒng)信息處理算法在面對(duì)各種非線性、不確定、不能精確解析以及建模機(jī)理復(fù)雜的問(wèn)題時(shí)，往往顯得捉襟見(jiàn)肘。正是在這種背景下，各種智能信息處理算法如雨后春筍般涌現(xiàn)出來(lái)。作為智能信息處理算法中的重要一員，遺傳算法近年來(lái)以其獨(dú)特而卓越的性能日漸引起了人們的關(guān)注。
組合邏輯電路其特點(diǎn)是功能上無(wú)記憶，結(jié)構(gòu)上無(wú)反饋，即電路在任意時(shí)刻的輸出狀態(tài)只取決于該時(shí)刻各輸入狀態(tài)的組合，而與電路的原狀態(tài)無(wú)關(guān)。本文通過(guò)實(shí)例介紹組合邏輯電路的設(shè)計(jì)方法，并通過(guò)電子設(shè)計(jì)自動(dòng)化EDA(Electronic Design Automation)進(jìn)行仿真分析，使組合邏輯電路的設(shè)計(jì)變得更方便，更實(shí)用。
隨著FPGA性能的不斷提高，基于FPGA的計(jì)算加速已經(jīng)逐漸成為提高計(jì)算速度和計(jì)算效率的重要手段之一。FPGA能夠?qū)崿F(xiàn)程序的并行化處理，不僅結(jié)構(gòu)簡(jiǎn)單，而且有效地減少了運(yùn)算時(shí)間、提高了運(yùn)行效率，為遺傳算法能在一些實(shí)時(shí)、高速的場(chǎng)合得到應(yīng)用提供了依據(jù)。

1 基于FPGA遺傳算法設(shè)計(jì)
遺傳算法是一種多點(diǎn)并行的迭代搜索算法，它的每一代稱為一個(gè)種群，由多個(gè)個(gè)體組成，每個(gè)個(gè)體稱為染色體，染色體由一定數(shù)目的字符組成。每個(gè)字符稱為一個(gè)基因，基因在染色體中的位置決定了基因所表達(dá)的特性。
文中基于FPGA的遺傳算法，整個(gè)系統(tǒng)分為4個(gè)單元，4個(gè)單元分別為：選擇單元、交叉單元、變異單元和適應(yīng)度計(jì)算單元。
1．1 選擇單元
選擇單元執(zhí)行遺傳算法中的選擇操作。選擇策略決定哪些個(gè)體存活并得以繁殖，因其直接關(guān)系到遺傳算法的運(yùn)行導(dǎo)向問(wèn)題故對(duì)遺傳算法的性能有直接并且重大的影響。標(biāo)準(zhǔn)遺傳算法所采用的輪盤賭選擇策略簡(jiǎn)便直觀，但可能會(huì)產(chǎn)生較大的抽樣誤差。于是，各種改進(jìn)的選擇策略產(chǎn)生了。
最早提出的使用濃度控制的選擇策略可以保證群體的多樣性從而避免了早熟現(xiàn)象并且提高了算法的魯棒性及運(yùn)算效率。后來(lái)通過(guò)對(duì)浮點(diǎn)遺傳算法早熟收斂現(xiàn)象的分析，有人提出了一種新的父代選擇策略，即使用當(dāng)前代的子代個(gè)體作為下代的父代個(gè)體，可使交叉算子持續(xù)地探索和開(kāi)發(fā)新空間。目前，人們又發(fā)現(xiàn)可以通過(guò)選擇策略的改變調(diào)控并維持種群多樣性。這類研究成果中，文獻(xiàn)中提到的重復(fù)串的適應(yīng)度處理是一個(gè)有益的嘗試。
1．2 交叉單元
交叉模塊執(zhí)行遺傳算法中的交叉操作。由隨機(jī)數(shù)模塊產(chǎn)生的隨機(jī)數(shù)與事先確定的交叉概率相比較，如果隨機(jī)數(shù)小于交叉概率，則一對(duì)個(gè)體進(jìn)行交叉操作，否則該對(duì)個(gè)體不變，直接進(jìn)入變異模塊。
文中一對(duì)個(gè)體進(jìn)行交叉操作的基因位由隨機(jī)數(shù)決定。隨機(jī)數(shù)模塊產(chǎn)生一個(gè)與個(gè)體等長(zhǎng)的隨機(jī)二進(jìn)制串，若隨機(jī)二進(jìn)制串中的某一位為1，則該對(duì)個(gè)體中該位置的基因相互交叉；否則，該對(duì)個(gè)體中該位置的基因保持不變。
1．3 變異單元
變異模塊執(zhí)行遺傳算法中的變異操作。與交叉模塊相似，變異模塊也是將隨機(jī)數(shù)模塊產(chǎn)生的隨機(jī)數(shù)與事先確定的變異概率相比較，決定是否進(jìn)行變異操作。同時(shí)個(gè)體中進(jìn)行變異操作的基因位也是由一個(gè)與個(gè)體等長(zhǎng)的隨機(jī)二進(jìn)制字符串決定的。對(duì)個(gè)體而言，執(zhí)行變異操作的基因位不宜過(guò)多，否則容易對(duì)個(gè)體造成較大的破壞，影響種群的穩(wěn)定性。本文將兩個(gè)隨機(jī)二進(jìn)制字符串(每一位0、1等概率)進(jìn)行相與操作，這樣得到的新的隨機(jī)二進(jìn)制字符串中每一位為1的概率將降低到25％，用這個(gè)新的隨機(jī)二進(jìn)制串來(lái)決定個(gè)體變異的基因位。這樣執(zhí)行變異操作的個(gè)體中，每一位基因變異的概率也會(huì)降低到25％。
1．4 適應(yīng)度計(jì)算單元
適應(yīng)度計(jì)算模塊執(zhí)行遺傳算法中的適應(yīng)度計(jì)算比較操作，它根據(jù)適應(yīng)度計(jì)算函數(shù)來(lái)計(jì)算種群中每一個(gè)個(gè)體的適應(yīng)度，包括遺傳算法開(kāi)始時(shí)初始化產(chǎn)生的種群和后來(lái)遺傳變異后產(chǎn)生的種群，并把每個(gè)個(gè)體的適應(yīng)度大小保存到存儲(chǔ)器中。同時(shí)，適應(yīng)度計(jì)算模塊還需要記錄每一代種群中適應(yīng)度最高的個(gè)體。適應(yīng)度計(jì)算模塊有一個(gè)內(nèi)置的計(jì)數(shù)器，計(jì)數(shù)器隨適應(yīng)度計(jì)算模塊的啟動(dòng)而啟動(dòng)，從0開(kāi)始計(jì)數(shù)，每個(gè)時(shí)鐘周期加1。計(jì)數(shù)器數(shù)值表示當(dāng)前個(gè)體及其適應(yīng)度在存儲(chǔ)器模塊當(dāng)中的存放地址。適應(yīng)度計(jì)算模塊停止工作時(shí)，計(jì)數(shù)器會(huì)重新歸零，等待新一輪的啟動(dòng)信號(hào)。