1、引言

演化硬件（EHW）是指能根據(jù)外部環(huán)境變化自動(dòng)改變自身結(jié)構(gòu)和功能的一類硬件，它把可編程邏輯器件的結(jié)構(gòu)位串當(dāng)作染色體，通過演化算法進(jìn)行搜索，用符合要求的染色體配置可編程邏輯器件，得到要設(shè)計(jì)的硬件電路。這一研究方法能夠探索新穎的電路設(shè)計(jì)方案，尋找許多未被人類發(fā)現(xiàn)高效的捷徑；實(shí)現(xiàn)電路的在線自適應(yīng)與容錯(cuò)，以適應(yīng)很多應(yīng)用需求對(duì)硬件的靈活性要求。它正在成為未來電路設(shè)計(jì)的發(fā)展方向。

本文進(jìn)行了數(shù)字電路的演化實(shí)驗(yàn)，目的是在FPGA中演化出8個(gè)LED小燈的控制電路，使其實(shí)現(xiàn)根據(jù)時(shí)鐘脈沖從1到8號(hào)按順序依次閃亮的功能。以驗(yàn)證硬件演化的有效性，探索數(shù)字電路演化設(shè)計(jì)的基本方法。

2、染色體編碼

用3個(gè)二進(jìn)制位代表1個(gè)小燈的點(diǎn)亮次序，這樣染色體長度為3×8＝24位。三個(gè)二進(jìn)制位的值為0表示在第一個(gè)時(shí)鐘時(shí)點(diǎn)亮的小燈，以此類推， 值為7表示最后點(diǎn)亮的小燈，允許有多個(gè)小燈同時(shí)點(diǎn)亮。

適應(yīng)度分為二部分，其百位表示將染色體從小到大排序后與目標(biāo)相符的小燈的個(gè)數(shù)，最大為8；十位和個(gè)位表示排序所需的次數(shù)，理想順序?yàn)?1234567，其交換次數(shù)為0，最差情況為76543210，需要交換28次，所以最大適應(yīng)度為828。圖1給出了一個(gè)染色體的例子，排序后共有6個(gè)小燈符合目標(biāo)，其中沒有值4和6，有3個(gè)5，這表示在時(shí)鐘5和7時(shí)沒有小燈點(diǎn)亮，而在時(shí)鐘6時(shí)5、6、7號(hào)三個(gè)小燈都點(diǎn)亮。排序共進(jìn)行了14次，此染色體的適應(yīng)度為6×100＋28-14＝614。

染色體： 111 101 001 011 000 010 101 101

排序后： 000 001 010 011 101 101 101 111

3、演化算法

采用了Hereboy算法，這是一個(gè)類似模擬退火算法的優(yōu)化算法，它不像標(biāo)準(zhǔn)遺傳算法那樣對(duì)群體中選擇的個(gè)體進(jìn)行交叉、變異，而是通過單個(gè)個(gè)體的變異來探索搜索空間。

此算法需要用戶來確定二個(gè)參數(shù)：變異率和搜索率。圖2顯示了算法的一個(gè)循環(huán)。算法根據(jù)變異率計(jì)算染色體中出現(xiàn)變異的位數(shù)，位置是隨機(jī)選擇的，把相應(yīng)的位置反。然后對(duì)計(jì)算出染色體的適應(yīng)度值，如果值比變異前高，就保留此變異，如果低，則染色體以一定概率（即搜索率）保留較差變異，否則恢復(fù)變異前的狀態(tài)。保留較差變異的目的是允許它們與其它較好變異結(jié)合起來，加快收斂速度。然后此過程不斷重復(fù)。

算法運(yùn)行中采用了一個(gè)自適應(yīng)方案逐步減少變異率和搜索率。如圖3所示，它們?cè)谑褂脮r(shí)被乘以一個(gè)系數(shù)β，染色體中變異的位數(shù)和接受一個(gè)較差變異的概率隨著逐漸收斂到最優(yōu)解而不斷減小，這樣開始時(shí)系統(tǒng)以較大步伐搜索，隨著當(dāng)前最優(yōu)成績的增加把變異速率調(diào)整的更精細(xì)。既能加快收斂速度，又防止了演化陷于局部最優(yōu)。

4、實(shí)現(xiàn)

我們選擇了XESS公司的XSV300開發(fā)板［4］作為實(shí)驗(yàn)的硬件平臺(tái)，它以25針并口電纜與主機(jī)相連，通過一片XILINX公司的XC95108 CPLD來控制XCV300 FPGA的配置。板上的條狀Led塊由10個(gè)Led組成，選用其中的1到8號(hào)用于顯示輸出。

JBits2.8是一個(gè)Java類集合［5］，它提供了對(duì)Xilinx Virtex系列FPGA位串的應(yīng)用程序接口，既可對(duì)Xilinx設(shè)計(jì)工具產(chǎn)生的位串，也可對(duì)從實(shí)際硬件回讀的位串進(jìn)行操作。JBits使用的程序模型是一個(gè)二維CLB數(shù)組。每個(gè)CLB都有一個(gè)行、列號(hào)，使人們可以設(shè)置和檢測(cè)選中的CLB內(nèi)的所有可配置資源，在FPGA器件上設(shè)計(jì)并動(dòng)態(tài)的修改電路。

對(duì)本實(shí)驗(yàn)來說外部演化較為簡單，只要將得到的最優(yōu)染色體下載到器件中即可；內(nèi)部演化則需要用硬件進(jìn)行適應(yīng)度計(jì)算，所以每一代的染色體都要下載到器件中，運(yùn)行8個(gè)時(shí)鐘，計(jì)算出其適應(yīng)度值。圖4給出了內(nèi)部演化的基本流程。

我們采用了一種靈活的方法實(shí)現(xiàn)了從染色體產(chǎn)生控制電路，即根據(jù)染色體生成8個(gè)時(shí)鐘周期Led燈的狀態(tài)，共8×8bit等于64bit存入FPGA中的Bram，生成一個(gè)3位計(jì)數(shù)器，其輸出連接到Bram的地址線，Bram的輸出連接到Led條的輸入。這樣計(jì)數(shù)器在時(shí)鐘的控制下從Bram中選擇對(duì)應(yīng)的數(shù)據(jù)輸出到Led顯示。而且在適應(yīng)度測(cè)量時(shí)，不再需要專門的存儲(chǔ)器來記錄Led的狀態(tài)，我們可以直接從Bram中讀取電路的輸出。

5、實(shí)驗(yàn)結(jié)果

我們?cè)谝慌_(tái)P4 1.7的主機(jī)上進(jìn)行了外部演化實(shí)驗(yàn)，對(duì)Hereboy算法中變異率和探索率的不同取值對(duì)算法收斂速度的影響進(jìn)行了統(tǒng)計(jì)，每對(duì)參數(shù)分別運(yùn)行30次，計(jì)算出了其平均收斂代數(shù)和時(shí)間，如表1所示。

變異率 搜索率 平均收斂代數(shù) 平均收斂時(shí)間（ms） 最小收斂代數(shù) 最小收斂時(shí)間（ms）

當(dāng)變異率大于0.7時(shí)，收斂速度急劇下降，且絕大部分次數(shù)無法演化出最優(yōu)解。從表中可以看出，變異率和搜索率對(duì)演化的影響很大，隨著它們數(shù)值的增大，演化的平均收斂速度也不斷提高，在0.7左右時(shí)達(dá)到最優(yōu)，但對(duì)最小收斂速度來說影響不大。由于外部演化完全通過軟件計(jì)算，所以最小收斂代數(shù)和最小收斂時(shí)間與主機(jī)具體的運(yùn)行狀態(tài)有關(guān)，并不成線性比例關(guān)系。

在外部演化的基礎(chǔ)上，我們成功的進(jìn)行了內(nèi)部演化。XCV300配置位串的長度為218980字節(jié)，完全配置下載時(shí)間約為50492ms，使用JBits的部分重配函數(shù)，在首次對(duì)XCV300進(jìn)行完全配置后，每次只下載要修改的數(shù)據(jù)。此時(shí)部分位串的長度為23048字節(jié)，下載時(shí)間約為5358ms。將變異率和搜索率都設(shè)為0.7，在演化42715代，耗時(shí)60多小時(shí)后得到了目標(biāo)電路。

6、結(jié)論

從實(shí)驗(yàn)可以看出，外部演化時(shí)間等于演化收斂時(shí)間加上完全配置下載時(shí)間，不過數(shù)分鐘，而內(nèi)部演化則需要數(shù)天。所以對(duì)小規(guī)模電路演化而言，內(nèi)部演化受配置位串的下載速度的影響相對(duì)較大。如果采用標(biāo)準(zhǔn)遺傳算法，每代需要計(jì)算適應(yīng)度的染色體個(gè)數(shù)更多，內(nèi)部演化將受到更大影響。對(duì)于復(fù)雜電路演化，如果其適應(yīng)度計(jì)算時(shí)間遠(yuǎn)大于配置下載時(shí)間，此時(shí)方可發(fā)揮內(nèi)部演化硬件執(zhí)行速度快的威力，這有待于在今后的工作中進(jìn)一步研究。

本文作者創(chuàng)新點(diǎn)：以JBits API和XESS開發(fā)板作為EHW平臺(tái)，以Led控制器的演化為目標(biāo)，實(shí)現(xiàn)了能夠進(jìn)行在線進(jìn)化的閉環(huán)結(jié)構(gòu)，形成了一個(gè)較為實(shí)用的EHW實(shí)驗(yàn)和應(yīng)用環(huán)境的具體方法。

責(zé)任編輯：gt