摘? 要：?給出了基于演化計(jì)算的硬件自動(dòng)設(shè)計(jì)方法" title="設(shè)計(jì)方法">設(shè)計(jì)方法的實(shí)現(xiàn)過(guò)程，分析了該方法的特點(diǎn)、存在的問(wèn)題" title="存在的問(wèn)題">存在的問(wèn)題及解決方案，討論了演化計(jì)算在該應(yīng)用領(lǐng)域的發(fā)展方向。

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

?

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

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

1 演化計(jì)算概述

　　演化計(jì)算求解問(wèn)題，不是從單個(gè)點(diǎn)，而是從一個(gè)點(diǎn)的群體開(kāi)始搜索。它將問(wèn)題的可行解進(jìn)行編碼，這些已編碼的解作為群體中的個(gè)體(即搜索空間中的點(diǎn));將問(wèn)題的目標(biāo)函數(shù)轉(zhuǎn)換為個(gè)體對(duì)環(huán)境的適應(yīng)性;模擬遺傳學(xué)中的雜交、變異、復(fù)制來(lái)設(shè)計(jì)遺傳算子;用優(yōu)勝劣汰的自然選擇法則來(lái)指導(dǎo)學(xué)習(xí)和確定搜索方向。

　　演化計(jì)算對(duì)由個(gè)體組成的群體進(jìn)行演化，利用遺傳算子產(chǎn)生具有更高平均適應(yīng)值和更好個(gè)體的群體。在整個(gè)演化過(guò)程中，起關(guān)鍵作用的是個(gè)體的適應(yīng)值，它驅(qū)使遺傳算子創(chuàng)造出新的適應(yīng)性更強(qiáng)的個(gè)體，從而推動(dòng)整個(gè)群體的演化。經(jīng)過(guò)若干代后，選出適應(yīng)值最好的個(gè)體，它就是問(wèn)題的最優(yōu)解或近似最優(yōu)解。

　　演化算法的基本結(jié)構(gòu)如下:

{

??? 隨機(jī)產(chǎn)生一初始群體，計(jì)算其中每個(gè)個(gè)體的適應(yīng)值;

repeat

? 　　應(yīng)用遺傳操作(復(fù)制、雜交等)產(chǎn)生下一代群體;

? 　　計(jì)算群體中每個(gè)個(gè)體的適應(yīng)值;

??????until 滿足算法的終止準(zhǔn)則;

??????指定算法的執(zhí)行結(jié)果

}

　　由此可知，演化計(jì)算對(duì)問(wèn)題本身的領(lǐng)域并不了解，它所做的只是對(duì)算法產(chǎn)生的每個(gè)個(gè)體進(jìn)行評(píng)價(jià)，并通過(guò)遺傳操作產(chǎn)生新一代群體，使適應(yīng)值好的個(gè)體比適應(yīng)值差的個(gè)體有更多的繁殖機(jī)會(huì)。如此一代代演化下去，直到算法滿足給定的終止準(zhǔn)則。

2 演化計(jì)算在硬件自動(dòng)設(shè)計(jì)中的應(yīng)用

　　對(duì)于傳統(tǒng)的硬件設(shè)計(jì)" title="硬件設(shè)計(jì)">硬件設(shè)計(jì)，必須提供詳細(xì)的硬件功能規(guī)范說(shuō)明，才能由設(shè)計(jì)人員按照這些規(guī)范說(shuō)明進(jìn)行相應(yīng)的設(shè)計(jì)。隨著硬件設(shè)計(jì)復(fù)雜度和密度的不斷增加，這種按照藍(lán)圖設(shè)計(jì)方法進(jìn)行的手工設(shè)計(jì)，極大地增加了設(shè)計(jì)者的工作量。硬件設(shè)計(jì)的自動(dòng)化勢(shì)在必行。那么，如何才能實(shí)現(xiàn)硬件設(shè)計(jì)的自動(dòng)化呢?芽利用演化計(jì)算的智能特性和PLD的可重構(gòu)特性即可完成這項(xiàng)任務(wù)，稱之為可演化硬件EHW(Evolvable Hardware)。

　　EHW是一種可重構(gòu)的硬件，它建立在PLD之上，每當(dāng)環(huán)境發(fā)生變化，EHW就自動(dòng)地改變自身的硬件結(jié)構(gòu)" title="硬件結(jié)構(gòu)">硬件結(jié)構(gòu)以適應(yīng)所處的環(huán)境。進(jìn)行EHW的設(shè)計(jì)不需要硬件功能的規(guī)范說(shuō)明，它利用演化計(jì)算的自組織、自適應(yīng)、自學(xué)習(xí)等智能特性，不斷地重構(gòu)自身的硬件結(jié)構(gòu)，最終達(dá)到設(shè)計(jì)的要求。因此，EHW特別適用于事先不知道硬件規(guī)范說(shuō)明的場(chǎng)合。

　　EHW是在PLD上實(shí)現(xiàn)的。PLD也是一種硬件，其結(jié)構(gòu)是可變的，由一個(gè)被稱為結(jié)構(gòu)位串的二進(jìn)制位串來(lái)決定。改變結(jié)構(gòu)位串就能夠立即實(shí)現(xiàn)任何的硬件結(jié)構(gòu)。也就是說(shuō)，若需要PLD實(shí)現(xiàn)某種特定的硬件功能，只須尋找相應(yīng)的結(jié)構(gòu)位串即可。這樣，硬件設(shè)計(jì)問(wèn)題就轉(zhuǎn)化為搜索問(wèn)題，在結(jié)構(gòu)位串空間搜索合適的結(jié)構(gòu)位串。如果把結(jié)構(gòu)位串當(dāng)作演化算法中的個(gè)體，把對(duì)硬件功能的評(píng)價(jià)轉(zhuǎn)換成適應(yīng)函數(shù)。那么，通過(guò)演化計(jì)算，就能夠找到最合適的結(jié)構(gòu)位串并根據(jù)它來(lái)改變EHW自身的結(jié)構(gòu)，以滿足設(shè)計(jì)的要求。這樣一來(lái)，硬件設(shè)計(jì)的任務(wù)也就自動(dòng)地完成了。

3 應(yīng)用過(guò)程中應(yīng)解決的問(wèn)題

　　將演化計(jì)算用于硬件的自動(dòng)設(shè)計(jì)，是一種全新的設(shè)計(jì)方法，它提出了許多具有挑戰(zhàn)性的問(wèn)題。

3.1 群體的規(guī)模

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

3.2 參數(shù)的選擇

　　在進(jìn)行硬件的演化之前，必須確定一些參數(shù)，如算法執(zhí)行的最大代數(shù)、各種遺傳操作的概率等，它們對(duì)算法的執(zhí)行效率有很大的影響。但關(guān)于如何選擇這些參數(shù)的知識(shí)還很不完整，有很強(qiáng)的經(jīng)驗(yàn)性，需要做更進(jìn)一步的研究。

3.3 結(jié)構(gòu)位串的長(zhǎng)度

　　EHW的實(shí)質(zhì)是一個(gè)算法問(wèn)題，只是此算法與硬件聯(lián)系在一起。在算法的設(shè)計(jì)過(guò)程中，一個(gè)關(guān)鍵性的問(wèn)題就是結(jié)構(gòu)位串的長(zhǎng)度。對(duì)一個(gè)實(shí)際的硬件進(jìn)行演化，其長(zhǎng)度可達(dá)幾十萬(wàn)位，甚至更多。對(duì)于這樣的硬件是難以演化的。為了解決這個(gè)問(wèn)題，可采用變長(zhǎng)結(jié)構(gòu)位串表示法、邏輯函數(shù)表示法等方法。這些方法可以有效地減少結(jié)構(gòu)位串的長(zhǎng)度，以便在較短的時(shí)間內(nèi)生成較大規(guī)模的硬件。

3.4 執(zhí)行的速度

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

3.5 算法的收斂

　　在硬件的演化過(guò)程中有兩個(gè)重點(diǎn):群體的多樣性和選擇性壓力。這兩個(gè)因素密切相關(guān)，增加選擇性壓力就會(huì)降低群體的多樣性，導(dǎo)致算法的執(zhí)行趨向于在找到最優(yōu)解前過(guò)早收斂;反之則又會(huì)使搜索毫無(wú)效率。過(guò)早收斂是演化算法和其它優(yōu)化算法共同存在的問(wèn)題。

4 與其它實(shí)現(xiàn)方法" title="實(shí)現(xiàn)方法">實(shí)現(xiàn)方法的比較

　　為了完成硬件自動(dòng)設(shè)計(jì)的任務(wù)，有很多的實(shí)現(xiàn)方法。與其它的方法相比，基于演化計(jì)算的實(shí)現(xiàn)方法有以下特點(diǎn):

　　(1)執(zhí)行速度非?？?。EHW自適應(yīng)的結(jié)果是新的硬件結(jié)構(gòu)自身，因此EHW與其它基于軟件的自適應(yīng)系統(tǒng)相比，能得到顯著的加速。這種優(yōu)點(diǎn)是實(shí)時(shí)應(yīng)用所希望的。

　　(2)能夠?qū)崿F(xiàn)聯(lián)機(jī)自適應(yīng)。通常的硬件自適應(yīng)是脫機(jī)的，這樣的系統(tǒng)只有在自適應(yīng)之后或?qū)W習(xí)階段完成之后才能使用。而理想的自適應(yīng)機(jī)應(yīng)該能在實(shí)時(shí)應(yīng)用中改變自已的結(jié)構(gòu)(即聯(lián)機(jī)自適應(yīng))。

　　(3)能夠直接將學(xué)習(xí)的結(jié)果儲(chǔ)存在它的硬件結(jié)構(gòu)中。這就導(dǎo)致了一種與人工神經(jīng)網(wǎng)絡(luò)(ANN)或其它基于規(guī)則的系統(tǒng)完全不同的新的學(xué)習(xí)方法。

　　(4)學(xué)習(xí)結(jié)果的可理解性較好。ANN的學(xué)習(xí)結(jié)果是用閥值與權(quán)系數(shù)來(lái)表示的。一旦系統(tǒng)出錯(cuò)，很難猜測(cè)出錯(cuò)的原因，不利于系統(tǒng)的維護(hù)。而EHW的學(xué)習(xí)結(jié)果是用可見(jiàn)的布爾函數(shù)表示的，它大大地改進(jìn)了學(xué)習(xí)結(jié)果的可理解性。

5 實(shí)現(xiàn)實(shí)例

　　EHW把PLD的結(jié)構(gòu)位串當(dāng)作群體中的個(gè)體，利用演化算法去尋找更好的結(jié)構(gòu)位串(即更好的硬件結(jié)構(gòu))。一旦算法發(fā)現(xiàn)了好的結(jié)構(gòu)位串，則將它下載到相應(yīng)的PLD中^[2]，如圖1所示。

?

?

　　假設(shè)一個(gè)群體由{θ₁、θ₂、θ₃、θ₄}4個(gè)個(gè)體組成。若演化算法選擇θ₁、θ₂進(jìn)行雜交，θ₃進(jìn)行變異，θ₄進(jìn)行復(fù)制，其演化過(guò)程如下:

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

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

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

　　這樣，就得到了一個(gè)新的群體{θ₁’、θ₂’、θ₃’、θ₄’}。通過(guò)對(duì)新群體中每個(gè)結(jié)構(gòu)位串進(jìn)行評(píng)價(jià)，發(fā)現(xiàn)θ1’的適應(yīng)值更好，則將其下載到相應(yīng)的PLD中。

　　基于演化計(jì)算的硬件設(shè)計(jì)方法是一種很有前途的硬件自動(dòng)設(shè)計(jì)方法，該方法所涉及的研究領(lǐng)域比較廣泛，在自適應(yīng)控制、硬件容錯(cuò)、復(fù)雜電路的設(shè)計(jì)等方面都有應(yīng)用。所使用的研究方法通常有兩種:外部演化和內(nèi)在演化。外部演化在演化過(guò)程中并不將算法所產(chǎn)生的結(jié)構(gòu)位串下載到PLD中，而是用軟件模擬的方式對(duì)每個(gè)結(jié)構(gòu)位串進(jìn)行評(píng)價(jià)，最后再將算法找到的適應(yīng)性最好的結(jié)構(gòu)位串下載到相應(yīng)的PLD中去。這是目前常用的一種硬件演化方法。內(nèi)在演化則將算法產(chǎn)生的每一個(gè)結(jié)構(gòu)位串都下載到PLD中，通過(guò)PLD所實(shí)現(xiàn)的硬件功能對(duì)相應(yīng)的結(jié)構(gòu)位串進(jìn)行評(píng)價(jià)。這種演化方法的演化速度很快，是EHW發(fā)展的主要方向。

?

參考文獻(xiàn)

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