1、引言

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

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

2、染色體編碼

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

適應(yīng)度分為二部分，其百位表示將染色體從小到大排序后與目標(biāo)相符的小燈的個數(shù)，最大為8；十位和個位表示排序所需的次數(shù)，理想順序為01234567，其交換次數(shù)為0，最差情況為76543210，需要交換28次，所以最大適應(yīng)度為828。圖1給出了一個染色體的例子，排序后共有6個小燈符合目標(biāo)，其中沒有值4和6，有3個5，這表示在時鐘5和7時沒有小燈點亮，而在時鐘6時5、6、7號三個小燈都點亮。排序共進行了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算法，這是一個類似模擬退火算法的優(yōu)化算法，它不像標(biāo)準遺傳算法那樣對群體中選擇的個體進行交叉、變異，而是通過單個個體的變異來探索搜索空間。

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

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

4、實現(xiàn)

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

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

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

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

5、實驗結(jié)果

我們在一臺P4 1.7的主機上進行了外部演化實驗，對Hereboy算法中變異率和探索率的不同取值對算法收斂速度的影響進行了統(tǒng)計，每對參數(shù)分別運行30次，計算出了其平均收斂代數(shù)和時間，如表1所示。

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

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

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

6、結(jié)論

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

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

責(zé)任編輯：gt