摘? 要：?給出了基于演化計算的硬件自動設(shè)計方法" title="設(shè)計方法">設(shè)計方法的實現(xiàn)過程，分析了該方法的特點、存在的問題" title="存在的問題">存在的問題及解決方案，討論了演化計算在該應用領(lǐng)域的發(fā)展方向。
關(guān)鍵詞：?演化計算? 可演化硬件(EHW)? 可編程邏輯器件(PLD)
?
演化計算是一種通過模擬自然界的生物演化過程搜索最優(yōu)解的方法，主要包括遺傳算法(GA)、遺傳程序設(shè)計(GP)、演化策略(ES)、演化規(guī)劃(EP)等。演化計算具有自組織性、自適應性、自學習性等智能特性。由于這些智能特性，該方法已被成功地應用到那些難以用傳統(tǒng)方法進行求解的復雜問題中[1]。
演化計算對待求解問題本身一無所知，但只要給出了表示方案、適應函數(shù)、遺傳算子、控制參數(shù)、終止準則和指定結(jié)果的方法等，演化算法就可以按不依賴于問題本身的方式對未知空間進行有效地搜索，最后找出問題的解。
1 演化計算概述
演化計算求解問題，不是從單個點，而是從一個點的群體開始搜索。它將問題的可行解進行編碼，這些已編碼的解作為群體中的個體(即搜索空間中的點);將問題的目標函數(shù)轉(zhuǎn)換為個體對環(huán)境的適應性;模擬遺傳學中的雜交、變異、復制來設(shè)計遺傳算子;用優(yōu)勝劣汰的自然選擇法則來指導學習和確定搜索方向。
演化計算對由個體組成的群體進行演化，利用遺傳算子產(chǎn)生具有更高平均適應值和更好個體的群體。在整個演化過程中，起關(guān)鍵作用的是個體的適應值，它驅(qū)使遺傳算子創(chuàng)造出新的適應性更強的個體，從而推動整個群體的演化。經(jīng)過若干代后，選出適應值最好的個體，它就是問題的最優(yōu)解或近似最優(yōu)解。
演化算法的基本結(jié)構(gòu)如下:
{
??? 隨機產(chǎn)生一初始群體，計算其中每個個體的適應值;
repeat
? 應用遺傳操作(復制、雜交等)產(chǎn)生下一代群體;
? 計算群體中每個個體的適應值;
??????until 滿足算法的終止準則;
??????指定算法的執(zhí)行結(jié)果
}
由此可知，演化計算對問題本身的領(lǐng)域并不了解，它所做的只是對算法產(chǎn)生的每個個體進行評價，并通過遺傳操作產(chǎn)生新一代群體，使適應值好的個體比適應值差的個體有更多的繁殖機會。如此一代代演化下去，直到算法滿足給定的終止準則。
2 演化計算在硬件自動設(shè)計中的應用
對于傳統(tǒng)的硬件設(shè)計" title="硬件設(shè)計">硬件設(shè)計，必須提供詳細的硬件功能規(guī)范說明，才能由設(shè)計人員按照這些規(guī)范說明進行相應的設(shè)計。隨著硬件設(shè)計復雜度和密度的不斷增加，這種按照藍圖設(shè)計方法進行的手工設(shè)計，極大地增加了設(shè)計者的工作量。硬件設(shè)計的自動化勢在必行。那么，如何才能實現(xiàn)硬件設(shè)計的自動化呢?芽利用演化計算的智能特性和PLD的可重構(gòu)特性即可完成這項任務，稱之為可演化硬件EHW(Evolvable Hardware)。
EHW是一種可重構(gòu)的硬件，它建立在PLD之上，每當環(huán)境發(fā)生變化，EHW就自動地改變自身的硬件結(jié)構(gòu)" title="硬件結(jié)構(gòu)">硬件結(jié)構(gòu)以適應所處的環(huán)境。進行EHW的設(shè)計不需要硬件功能的規(guī)范說明，它利用演化計算的自組織、自適應、自學習等智能特性，不斷地重構(gòu)自身的硬件結(jié)構(gòu)，最終達到設(shè)計的要求。因此，EHW特別適用于事先不知道硬件規(guī)范說明的場合。
EHW是在PLD上實現(xiàn)的。PLD也是一種硬件，其結(jié)構(gòu)是可變的，由一個被稱為結(jié)構(gòu)位串的二進制位串來決定。改變結(jié)構(gòu)位串就能夠立即實現(xiàn)任何的硬件結(jié)構(gòu)。也就是說，若需要PLD實現(xiàn)某種特定的硬件功能，只須尋找相應的結(jié)構(gòu)位串即可。這樣，硬件設(shè)計問題就轉(zhuǎn)化為搜索問題，在結(jié)構(gòu)位串空間搜索合適的結(jié)構(gòu)位串。如果把結(jié)構(gòu)位串當作演化算法中的個體，把對硬件功能的評價轉(zhuǎn)換成適應函數(shù)。那么，通過演化計算，就能夠找到最合適的結(jié)構(gòu)位串并根據(jù)它來改變EHW自身的結(jié)構(gòu)，以滿足設(shè)計的要求。這樣一來，硬件設(shè)計的任務也就自動地完成了。
3 應用過程中應解決的問題
將演化計算用于硬件的自動設(shè)計，是一種全新的設(shè)計方法，它提出了許多具有挑戰(zhàn)性的問題。
3.1 群體的規(guī)模
演化計算是對自然界中生物演化過程的模擬，但由于群體的規(guī)模較大程度地影響著演化算法的模擬消耗，目前硬件演化的群體規(guī)模還遠遠小于生物演化規(guī)模。必須研制數(shù)量更加接近自然物種的群體以便能夠得到更好的結(jié)果。
3.2 參數(shù)的選擇
在進行硬件的演化之前，必須確定一些參數(shù)，如算法執(zhí)行的最大代數(shù)、各種遺傳操作的概率等，它們對算法的執(zhí)行效率有很大的影響。但關(guān)于如何選擇這些參數(shù)的知識還很不完整，有很強的經(jīng)驗性，需要做更進一步的研究。
3.3 結(jié)構(gòu)位串的長度
EHW的實質(zhì)是一個算法問題，只是此算法與硬件聯(lián)系在一起。在算法的設(shè)計過程中，一個關(guān)鍵性的問題就是結(jié)構(gòu)位串的長度。對一個實際的硬件進行演化，其長度可達幾十萬位，甚至更多。對于這樣的硬件是難以演化的。為了解決這個問題，可采用變長結(jié)構(gòu)位串表示法、邏輯函數(shù)表示法等方法。這些方法可以有效地減少結(jié)構(gòu)位串的長度，以便在較短的時間內(nèi)生成較大規(guī)模的硬件。
3.4 執(zhí)行的速度
一個較小的硬件設(shè)計，有時需幾天的時間才能完成。要想使EHW達到實用的目的，就必須提高演化算法的執(zhí)行速度。演化算法屬于一種群體搜索算法，具有內(nèi)在大規(guī)模并行性。如何充分發(fā)揮其并行性，是提高EHW的執(zhí)行速度的關(guān)鍵所在。
3.5 算法的收斂
在硬件的演化過程中有兩個重點:群體的多樣性和選擇性壓力。這兩個因素密切相關(guān)，增加選擇性壓力就會降低群體的多樣性，導致算法的執(zhí)行趨向于在找到最優(yōu)解前過早收斂;反之則又會使搜索毫無效率。過早收斂是演化算法和其它優(yōu)化算法共同存在的問題。
4 與其它實現(xiàn)方法" title="實現(xiàn)方法">實現(xiàn)方法的比較
為了完成硬件自動設(shè)計的任務，有很多的實現(xiàn)方法。與其它的方法相比，基于演化計算的實現(xiàn)方法有以下特點:
(1)執(zhí)行速度非?？臁HW自適應的結(jié)果是新的硬件結(jié)構(gòu)自身，因此EHW與其它基于軟件的自適應系統(tǒng)相比，能得到顯著的加速。這種優(yōu)點是實時應用所希望的。
(2)能夠?qū)崿F(xiàn)聯(lián)機自適應。通常的硬件自適應是脫機的，這樣的系統(tǒng)只有在自適應之后或?qū)W習階段完成之后才能使用。而理想的自適應機應該能在實時應用中改變自已的結(jié)構(gòu)(即聯(lián)機自適應)。
(3)能夠直接將學習的結(jié)果儲存在它的硬件結(jié)構(gòu)中。這就導致了一種與人工神經(jīng)網(wǎng)絡(ANN)或其它基于規(guī)則的系統(tǒng)完全不同的新的學習方法。
(4)學習結(jié)果的可理解性較好。ANN的學習結(jié)果是用閥值與權(quán)系數(shù)來表示的。一旦系統(tǒng)出錯，很難猜測出錯的原因，不利于系統(tǒng)的維護。而EHW的學習結(jié)果是用可見的布爾函數(shù)表示的，它大大地改進了學習結(jié)果的可理解性。
5 實現(xiàn)實例
EHW把PLD的結(jié)構(gòu)位串當作群體中的個體，利用演化算法去尋找更好的結(jié)構(gòu)位串(即更好的硬件結(jié)構(gòu))。一旦算法發(fā)現(xiàn)了好的結(jié)構(gòu)位串，則將它下載到相應的PLD中[2]，如圖1所示。
?
?
假設(shè)一個群體由{θ1、θ2、θ3、θ4}4個個體組成。若演化算法選擇θ1、θ2進行雜交，θ3進行變異，θ4進行復制，其演化過程如下:
(1)雜交:該操作可以產(chǎn)生新的個體，從而檢測搜索空間中新的點。若在演化算法中采用單點雜交，隨機產(chǎn)生的雜交點為18，則雜交過程為:
(2)變異:該操作可增加群體的多樣性，防止群體過早收斂。若隨機產(chǎn)生的變異點為3，變異過程為:
(3)復制:該操作可提高群體的平均適應值。如:
這樣，就得到了一個新的群體{θ1’、θ2’、θ3’、θ4’}。通過對新群體中每個結(jié)構(gòu)位串進行評價，發(fā)現(xiàn)θ1’的適應值更好，則將其下載到相應的PLD中。
基于演化計算的硬件設(shè)計方法是一種很有前途的硬件自動設(shè)計方法，該方法所涉及的研究領(lǐng)域比較廣泛，在自適應控制、硬件容錯、復雜電路的設(shè)計等方面都有應用。所使用的研究方法通常有兩種:外部演化和內(nèi)在演化。外部演化在演化過程中并不將算法所產(chǎn)生的結(jié)構(gòu)位串下載到PLD中，而是用軟件模擬的方式對每個結(jié)構(gòu)位串進行評價，最后再將算法找到的適應性最好的結(jié)構(gòu)位串下載到相應的PLD中去。這是目前常用的一種硬件演化方法。內(nèi)在演化則將算法產(chǎn)生的每一個結(jié)構(gòu)位串都下載到PLD中，通過PLD所實現(xiàn)的硬件功能對相應的結(jié)構(gòu)位串進行評價。這種演化方法的演化速度很快，是EHW發(fā)展的主要方向。
?
參考文獻
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