摘? 要：?給出了基于演化計算的硬件自動設計方法" title="設計方法">設計方法的實現過程，分析了該方法的特點、存在的問題" title="存在的問題">存在的問題及解決方案，討論了演化計算在該應用領域的發展方向。

　　關鍵詞：?演化計算? 可演化硬件(EHW)? 可編程邏輯器件(PLD)

?

　　演化計算是一種通過模擬自然界的生物演化過程搜索最優解的方法，主要包括遺傳算法(GA)、遺傳程序設計(GP)、演化策略(ES)、演化規劃(EP)等。演化計算具有自組織性、自適應性、自學習性等智能特性。由于這些智能特性，該方法已被成功地應用到那些難以用傳統方法進行求解的復雜問題中^[1]。

　　演化計算對待求解問題本身一無所知，但只要給出了表示方案、適應函數、遺傳算子、控制參數、終止準則和指定結果的方法等，演化算法就可以按不依賴于問題本身的方式對未知空間進行有效地搜索，最后找出問題的解。

1 演化計算概述

　　演化計算求解問題，不是從單個點，而是從一個點的群體開始搜索。它將問題的可行解進行編碼，這些已編碼的解作為群體中的個體(即搜索空間中的點);將問題的目標函數轉換為個體對環境的適應性;模擬遺傳學中的雜交、變異、復制來設計遺傳算子;用優勝劣汰的自然選擇法則來指導學習和確定搜索方向。

　　演化計算對由個體組成的群體進行演化，利用遺傳算子產生具有更高平均適應值和更好個體的群體。在整個演化過程中，起關鍵作用的是個體的適應值，它驅使遺傳算子創造出新的適應性更強的個體，從而推動整個群體的演化。經過若干代后，選出適應值最好的個體，它就是問題的最優解或近似最優解。

　　演化算法的基本結構如下:

{

??? 隨機產生一初始群體，計算其中每個個體的適應值;

repeat

? 　　應用遺傳操作(復制、雜交等)產生下一代群體;

? 　　計算群體中每個個體的適應值;

??????until 滿足算法的終止準則;

??????指定算法的執行結果

}

　　由此可知，演化計算對問題本身的領域并不了解，它所做的只是對算法產生的每個個體進行評價，并通過遺傳操作產生新一代群體，使適應值好的個體比適應值差的個體有更多的繁殖機會。如此一代代演化下去，直到算法滿足給定的終止準則。

2 演化計算在硬件自動設計中的應用

　　對于傳統的硬件設計" title="硬件設計">硬件設計，必須提供詳細的硬件功能規范說明，才能由設計人員按照這些規范說明進行相應的設計。隨著硬件設計復雜度和密度的不斷增加，這種按照藍圖設計方法進行的手工設計，極大地增加了設計者的工作量。硬件設計的自動化勢在必行。那么，如何才能實現硬件設計的自動化呢?芽利用演化計算的智能特性和PLD的可重構特性即可完成這項任務，稱之為可演化硬件EHW(Evolvable Hardware)。

　　EHW是一種可重構的硬件，它建立在PLD之上，每當環境發生變化，EHW就自動地改變自身的硬件結構" title="硬件結構">硬件結構以適應所處的環境。進行EHW的設計不需要硬件功能的規范說明，它利用演化計算的自組織、自適應、自學習等智能特性，不斷地重構自身的硬件結構，最終達到設計的要求。因此，EHW特別適用于事先不知道硬件規范說明的場合。

　　EHW是在PLD上實現的。PLD也是一種硬件，其結構是可變的，由一個被稱為結構位串的二進制位串來決定。改變結構位串就能夠立即實現任何的硬件結構。也就是說，若需要PLD實現某種特定的硬件功能，只須尋找相應的結構位串即可。這樣，硬件設計問題就轉化為搜索問題，在結構位串空間搜索合適的結構位串。如果把結構位串當作演化算法中的個體，把對硬件功能的評價轉換成適應函數。那么，通過演化計算，就能夠找到最合適的結構位串并根據它來改變EHW自身的結構，以滿足設計的要求。這樣一來，硬件設計的任務也就自動地完成了。

3 應用過程中應解決的問題

　　將演化計算用于硬件的自動設計，是一種全新的設計方法，它提出了許多具有挑戰性的問題。

3.1 群體的規模

　　演化計算是對自然界中生物演化過程的模擬，但由于群體的規模較大程度地影響著演化算法的模擬消耗，目前硬件演化的群體規模還遠遠小于生物演化規模。必須研制數量更加接近自然物種的群體以便能夠得到更好的結果。

3.2 參數的選擇

　　在進行硬件的演化之前，必須確定一些參數，如算法執行的最大代數、各種遺傳操作的概率等，它們對算法的執行效率有很大的影響。但關于如何選擇這些參數的知識還很不完整，有很強的經驗性，需要做更進一步的研究。

3.3 結構位串的長度

　　EHW的實質是一個算法問題，只是此算法與硬件聯系在一起。在算法的設計過程中，一個關鍵性的問題就是結構位串的長度。對一個實際的硬件進行演化，其長度可達幾十萬位，甚至更多。對于這樣的硬件是難以演化的。為了解決這個問題，可采用變長結構位串表示法、邏輯函數表示法等方法。這些方法可以有效地減少結構位串的長度，以便在較短的時間內生成較大規模的硬件。

3.4 執行的速度

　　一個較小的硬件設計，有時需幾天的時間才能完成。要想使EHW達到實用的目的，就必須提高演化算法的執行速度。演化算法屬于一種群體搜索算法，具有內在大規模并行性。如何充分發揮其并行性，是提高EHW的執行速度的關鍵所在。

3.5 算法的收斂

　　在硬件的演化過程中有兩個重點:群體的多樣性和選擇性壓力。這兩個因素密切相關，增加選擇性壓力就會降低群體的多樣性，導致算法的執行趨向于在找到最優解前過早收斂;反之則又會使搜索毫無效率。過早收斂是演化算法和其它優化算法共同存在的問題。

4 與其它實現方法" title="實現方法">實現方法的比較

　　為了完成硬件自動設計的任務，有很多的實現方法。與其它的方法相比，基于演化計算的實現方法有以下特點:

　　(1)執行速度非?？?。EHW自適應的結果是新的硬件結構自身，因此EHW與其它基于軟件的自適應系統相比，能得到顯著的加速。這種優點是實時應用所希望的。

　　(2)能夠實現聯機自適應。通常的硬件自適應是脫機的，這樣的系統只有在自適應之后或學習階段完成之后才能使用。而理想的自適應機應該能在實時應用中改變自已的結構(即聯機自適應)。

　　(3)能夠直接將學習的結果儲存在它的硬件結構中。這就導致了一種與人工神經網絡(ANN)或其它基于規則的系統完全不同的新的學習方法。

　　(4)學習結果的可理解性較好。ANN的學習結果是用閥值與權系數來表示的。一旦系統出錯，很難猜測出錯的原因，不利于系統的維護。而EHW的學習結果是用可見的布爾函數表示的，它大大地改進了學習結果的可理解性。

5 實現實例

　　EHW把PLD的結構位串當作群體中的個體，利用演化算法去尋找更好的結構位串(即更好的硬件結構)。一旦算法發現了好的結構位串，則將它下載到相應的PLD中^[2]，如圖1所示。

?

?

　　假設一個群體由{θ₁、θ₂、θ₃、θ₄}4個個體組成。若演化算法選擇θ₁、θ₂進行雜交，θ₃進行變異，θ₄進行復制，其演化過程如下:

　　(1)雜交:該操作可以產生新的個體，從而檢測搜索空間中新的點。若在演化算法中采用單點雜交，隨機產生的雜交點為18，則雜交過程為:

　　(2)變異:該操作可增加群體的多樣性，防止群體過早收斂。若隨機產生的變異點為3，變異過程為:

　　(3)復制:該操作可提高群體的平均適應值。如:

　　這樣，就得到了一個新的群體{θ₁’、θ₂’、θ₃’、θ₄’}。通過對新群體中每個結構位串進行評價，發現θ1’的適應值更好，則將其下載到相應的PLD中。

　　基于演化計算的硬件設計方法是一種很有前途的硬件自動設計方法，該方法所涉及的研究領域比較廣泛，在自適應控制、硬件容錯、復雜電路的設計等方面都有應用。所使用的研究方法通常有兩種:外部演化和內在演化。外部演化在演化過程中并不將算法所產生的結構位串下載到PLD中，而是用軟件模擬的方式對每個結構位串進行評價，最后再將算法找到的適應性最好的結構位串下載到相應的PLD中去。這是目前常用的一種硬件演化方法。內在演化則將算法產生的每一個結構位串都下載到PLD中，通過PLD所實現的硬件功能對相應的結構位串進行評價。這種演化方法的演化速度很快，是EHW發展的主要方向。

?

參考文獻

1 Back T， Hammel U， Schwefel H P. Evolutionary Computation：Comments on the History and Current State.

? IEEE Trans.on Evolutionary Computation，1997;1(1):3～17

2 Kajitani I， Hoshino T， Iwata M， Higuchi T.Variable length chromosome GA for evolvable hardware，In Proc.

? of the 1996 IEEE ICEC＇96 ， 1996： 443～447