1、引言

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

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

2、染色體編碼

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

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

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

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

3、演化算法

采用了Hereboy算法，這是一個類似模擬退火算法的優化算法，它不像標準遺傳算法那樣對群體中選擇的個體進行交叉、變異，而是通過單個個體的變異來探索搜索空間。

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

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

4、實現

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

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

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

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

5、實驗結果

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

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

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

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

6、結論

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

本文作者創新點：以JBits API和XESS開發板作為EHW平臺，以Led控制器的演化為目標，實現了能夠進行在線進化的閉環結構，形成了一個較為實用的EHW實驗和應用環境的具體方法。

責任編輯：gt