基于精英池演化算法的數(shù)字電路在片演化方法

1、基于精英池演化算法的數(shù)字電路在片演化方法 本課題得到國家自然科學(xué)基金資助項目(60773009,60775035)、國家高科技研究發(fā)展計劃 (2007AA01Z290,2007AA01Z132)和國家“九七三”重點基礎(chǔ)研究發(fā)展規(guī)劃項目基金(2007CB311004)資助. 何國良, 男，1974年生，博士，講師，主要研究方向為演化硬件、演化計算和數(shù)據(jù)挖掘. E-mail: glhe. 李元香，男，1962年生，教授，博士生導(dǎo)師，主要研究方向為演化計算、并行計算等. 史忠植，男，1941年生，研究員，博士生導(dǎo)師，主要研究領(lǐng)域為人工智能、機(jī)器學(xué)習(xí)、多主體系統(tǒng)、語義Web等.何國良1,2李元香1,2

2、 史忠植31武漢大學(xué)軟件工程國家重點實驗室 武漢4300722武漢大學(xué)計算機(jī)學(xué)院武漢4300723中國科學(xué)院計算技術(shù)研究所智能信息處理重點實驗室北京100190摘要：世紀(jì)末演化硬件技術(shù)的提出，為實現(xiàn)硬件系統(tǒng)的自適應(yīng)與智能化等特征提供了一種可行的新技術(shù)，現(xiàn)階段電路進(jìn)化是演化硬件研究的熱點之一。本文引入人工經(jīng)驗與規(guī)則，提出一種擴(kuò)展矩陣編碼法，保護(hù)具有較優(yōu)結(jié)構(gòu)的電路個體不易淘汰；其次，基于多目標(biāo)和局部尋優(yōu)技術(shù)，結(jié)合子電路雜交與單元重要性的自適應(yīng)變異策略，提出了一種設(shè)計數(shù)字電路的精英池演化算法，并在可編程邏輯器件上實現(xiàn)電路的自主動態(tài)重構(gòu)與評價等演化過程。關(guān)鍵詞：演化硬件演化算法電路演化在片演化中圖分類

3、號： TP302Elitist Pool Evolutionary Algorithm for on-line evolution of digital circuitsHE Guo-Liang1,2 LI Yuan-Xiang1,2 SHI Zhong-Zhi31 State Key Laboratory of Software Engineering, Wuhan University, Wuhan, 4300722 College of Computer Science, Wuhan University, Wuhan, 4300723 Key Laboratory of Intelli

4、gent Information Processing, Institute of Computing Technology, Beijin 100190 Abstract: Evolvable hardware (EHW) refers to reconfiguration hardware design with natural algorithms, which could change its architecture and behavior dynamically and autonomously by interacting with its environment. At pr

5、esent, the auto-design of electronic and analog circuits is a one of hot issues in the field of EHW. In this paper, an elitist pool evolutionary algorithm (EPEA) with some evolution techniques is proposed to optimize the evolutionary design of logic circuits efficiently. First, an extended matrix en

6、coding method is proposed based on human experiences and principles to increase the fitness value of some evolved circuits quickly. This representation can be expected to reflect the potential performance of circuits and avoid deleting some inferior circuits with a good developing potential during t

7、he evolution. Then, a novel sub-circuit crossover operator and an adaptive mutation strategy are introduced to improve design efficiency in terms of the techniques of the multi-objective and local searching optimization. Moreover, a framework of on-line evolution is employed to implement EPEA on fie

8、ld-programmable gate array (FPGA). Experiments show that the proposed methods can design digital circuits automatically and efficiently.Keywords: evolvable hardware, evolutionary algorithm, evolutionary design of circuits, on-line evolution1 引言演化硬件技術(shù)(Evolvable Hardware, EHW)自從世紀(jì)九十年代初被Hugo de Gairs等提

9、出以來，引起各國政府部門和學(xué)者們的廣泛關(guān)注與深入研究，極大地促進(jìn)了該技術(shù)的發(fā)展和應(yīng)用。演化硬件的實現(xiàn)過程與演化算法類似，根據(jù)個體適應(yīng)值的評估方式，演化硬件可分為離線演化與在線演化兩種設(shè)計技術(shù)。離線演化一般是通過軟件仿真評估每代演化的所有個體，只下載最優(yōu)個體到可編程器件上驗證；而在線演化則將硬件測試嵌入到演化硬件設(shè)計過程中，所有個體都下載到硬件設(shè)備進(jìn)行在線實測和評價。作為一個新的研究領(lǐng)域，演化硬件是計算機(jī)科學(xué)、電子學(xué)、生物學(xué)的交叉學(xué)科，為硬件系統(tǒng)設(shè)計的自動化與智能化提供了新的技術(shù)手段和設(shè)計方法，目前將演化硬件技術(shù)用于數(shù)字電路和模擬電路的設(shè)計是該領(lǐng)域研究熱點之一，希望實現(xiàn)復(fù)雜電路的自動設(shè)計與優(yōu)化，

10、以提高設(shè)計效率、降低能耗、發(fā)現(xiàn)新的規(guī)則與知識。針對離線演化硬件技術(shù)，為提高演化硬件的編碼效率，提出了各種電路編碼技術(shù)，如矩陣編碼法1、CGP(Cartesian Genetic Programming) 2編碼法等；為了優(yōu)化硬件并降低演化的時間復(fù)雜度，提出了各種有效的智能算法，如并行遺傳程序法3、多目標(biāo)自適應(yīng)遺傳算法4、單元雜交法5、評估技術(shù)6等。此外，分而治之與生長式方法也是演化復(fù)雜演化硬件的有效技術(shù)，如基于商農(nóng)分解定理的自動分解方法GDD (Generalized Disjunction Decomposition) 7以提高演化電路的規(guī)模，MDCGP (Modular Developme

11、ntal Caresian Genetic Programming) 8技術(shù)可縮短演化時間，提高容錯率。與此同時，在線演化硬件和內(nèi)部演化技術(shù)的研究也取得了許多新進(jìn)展，如直接演化電路的配置串9、通過API函數(shù)對配置串讀寫并修改相關(guān)基因段10、或基于可編程邏輯器件(field-programmable gate array，F(xiàn)PGA)的物理結(jié)構(gòu)和待演化系統(tǒng)的特點設(shè)計特定的演化結(jié)構(gòu)實現(xiàn)演化電路的動態(tài)重構(gòu)11等。本文引入人工設(shè)計電路的經(jīng)驗和規(guī)則，提出擴(kuò)展矩陣編碼法，設(shè)計一種精英池演化算法(elitist pool evolutionary algorithm、EPEA)，結(jié)合子電路雜交法與基于單元共享

12、度的自適應(yīng)變異策略演化數(shù)字電路，并采用一種在片演化技術(shù)實現(xiàn)電路的演化過程。實驗結(jié)果表明，該方法在一定程度上可提高演化電路的規(guī)模及其設(shè)計效率。2. 演化電路的編碼2.1矩陣編碼法采用演化硬件技術(shù)自動設(shè)計數(shù)字電路，首先需將電路表示成便于算法設(shè)計的一種編碼方式，目前一般采用矩陣編碼法1表示一個組合邏輯電路，如圖1所示。其中每個單元表示一個邏輯函數(shù)，單元間的互連形成邏輯函數(shù)間的關(guān)聯(lián)，構(gòu)成一個數(shù)字電路。為了完全表示一個組合邏輯電路，需定義矩陣中單元的函數(shù)類型以及單元間的連接關(guān)系。其中，單元的函數(shù)類型可以定義為基本的邏輯門類型或自定義的函數(shù)類型，表列舉了部分基本邏輯函數(shù)類型。其次是單元間互連關(guān)系，某些單元

13、的輸出信號和電路輸入端信號可作為其它單元的輸入信號。對于組合邏輯電路的編碼，為避免單元間的連接形成回路，先定義單元間連接關(guān)系一個基本概念: 單元的連接度。定義：在矩陣編碼Hmn(m為矩陣的行數(shù)，n為矩陣的列數(shù))中，若某個單元cij(表示此單元的位置在矩陣中的第i行、第j列)的輸入端信號可與其前k列單元的輸出端信號相連，即在第j-k列至j-1列位置上所有單元的輸出端信號都可為此單元的輸入端信號，則稱此單元cij的連接度D為k。以單元編碼為基礎(chǔ)，每個單元的編碼信息包括此單元的全部輸入端信號信息和函數(shù)類型，如表2所示。矩陣中全部單元的編碼信息即可表示一個電路的完整結(jié)構(gòu)。該矩陣編碼法也可用于對時序邏輯

14、電路編碼，此時單元間連接允許形成回路，單元的函數(shù)類型包含觸發(fā)器等。Outputy1y2y3ymInputx1x2x3xn單元結(jié)構(gòu)I0I1IkZ0Z1Zp電路結(jié)構(gòu)圖1 組合邏輯電路的染色體結(jié)構(gòu)示意圖表1 基本邏輯單元類型函數(shù)類型函數(shù)類型0a*3a + b1!a4ab2ab*表示此函數(shù)類型不執(zhí)行任何邏輯操作(即直連線)，直接將該單元的輸入端與輸出端相連。表2 單元的編碼方式輸入端信號1輸入端信號2輸入端信號函數(shù)類型2.2擴(kuò)展矩陣編碼法雖然該矩陣編碼法能較好表示一個數(shù)字電路，便于演化算法的自動設(shè)計，但容易淘汰一些具有較優(yōu)結(jié)構(gòu)的電路個體。例如，設(shè)計一個三輸入二輸出的組合邏輯電路，其真值表如表3所示(a

15、、b、c為輸入信號，y1、y2為輸出信號)：表3 組合邏輯電路的真值表InOutOut1Out2abcy1y2x1x2z1z2000001000001001000010011000011011101100001000101011000110011101111101101若一個演化電路的功能如表3中的Out1(x1、x2)所示，通過與真值表Out相比較，可知第一個輸出端信號的功能匹配度是1/8，第二個輸出端信號的匹配度是5/8。若在該演化電路的第一個輸出端添加一個非門，則該輸出端信號的功能如表3的out2(z1、z2)所示，匹配度上升為7/8。由此可知，必要時在演化電路的某些輸出端添加非門可迅速

16、提高電路性能。Inputx1x2x3xnOutputy1y2ym0,10,10,1矩陣編碼法圖2 擴(kuò)展矩陣編碼法因此，本文引入人工設(shè)計電路的經(jīng)驗和規(guī)則，以矩陣編碼法為基礎(chǔ)提出一種擴(kuò)展矩陣編碼法，在原矩陣編碼法的每個輸出端添加一個宏模塊，它由一個非門和一個二路選擇器組成，如圖2所示。當(dāng)評價演化電路的某個輸出端功能與真值表的匹配度低于0.5時，選擇器控制端選擇信號“1”，表示在此輸出信號端添加一個非門；否則，反之。此編碼法能保護(hù)具有較優(yōu)結(jié)構(gòu)的電路個體不易被淘汰，同時增強(qiáng)了種群的多樣性。此外，本文規(guī)定所有單元的連接度為1，即每個單元的輸入端信號為電路的原始輸入信號或其前一列單元的輸出端信號，最后一列

17、單元的輸出對應(yīng)電路的輸出端信號。3. 精英池演化算法為了闡述其演化策略，先定義幾個基本概念。定義：對于一個具有n個輸出端信號的組合邏輯電路C，基于輸出端信號可將電路C分解為n個單輸出子電路，每個子電路分別對應(yīng)電路C相應(yīng)輸出端信號的功能，本文稱按此劃分的每個子電路為輸出端信號子電路。值得注意的是：在定義中，電路C中的某些邏輯單元可能是多個輸出端子電路的邏輯單元，即為多個輸出端子電路所共享，我們稱為共享單元，見定義。定義：若采用擴(kuò)展矩陣編碼表示定義中的電路C，電路的每個輸出端信號子電路都是由矩陣編碼中的某些單元及其連接構(gòu)成。若矩陣編碼中某個單元cij(表示此單元的位置在矩陣中的第i行、第j列)是電

18、路C多個輸出端信號子電路的一個邏輯單元，則稱此單元cij為共享單元；否則，則稱此單元cij為非共享單元。定義：在定義中，若擴(kuò)展矩陣編碼中的某個單元cij是共享單元，且此單元是電路C的m (mM。第三步：演化操作：從種群A和精英池B中分別隨機(jī)選取一個個體雜交得到一個新個體，并對新個體運用變異策略，反復(fù)此步直到生成規(guī)模為N的下一代種群A。第四步：對新種群A評價，并保留最優(yōu)個體電路。第五步：若不滿足終止條件，轉(zhuǎn)第二步；否則，結(jié)束算法。(F)1,2-1312,31,22,32131,231,31-1-19/1612/1611/161,311,2,31,21,21,31,3父體 I父體II1,21,31

19、2,31,22,321,21,21,21,31,3-1-11,3-111,2,3-1321,21,2231,331,3-114/169/1615/16(A)(B)(C)(D)(E)1,21,3-111,2,31,2321,21,21,231,331,3-11,22,31,22,321,2圖 3子電路雜交法：(A)和(B)為兩父體及其子電路；(C) 新個體的第一個輸出端信號子電路選自兩父體中第一個輸出端信號匹配度較高的父體I；(D) 新個體的第二個輸出端信號子電路選自兩父體中第二個輸出端信號匹配度較高的父體II；(E) C子電路與D子電路的融合產(chǎn)生含兩個輸出端信號的子電路；(F) E子電路與選取

20、的第三個輸出端信號子電路融合得到的新個體電路。3.4 評價函數(shù)演化過程中，評價標(biāo)準(zhǔn)能否準(zhǔn)確反映電路的優(yōu)劣程度至關(guān)重要，它直接影響到演化操作，并導(dǎo)致能否得到最優(yōu)解。對于數(shù)字電路，通過測試集對其進(jìn)行功能仿真驗證是評價的基礎(chǔ)，如組合邏輯電路功能的評價一般是通過測試所有可能的輸入組合，通過仿真測試其電路的輸出值，并與真值表比較得到演化電路的功能與真值表的匹配度，作為演化電路個體性能的評價值。另外，在設(shè)計有效電路的同時要求其結(jié)構(gòu)最優(yōu)化。本文考慮組成電路的邏輯門數(shù)作為電路優(yōu)化一個基本特征，即其所需的基本邏輯門數(shù)越少，結(jié)構(gòu)越優(yōu)。采用擴(kuò)展矩陣編碼表示數(shù)字電路時，矩陣中的一些單元為電路的冗余單元，它可分為兩類：

21、一類是指其函數(shù)類型為直連線，即表一中的函數(shù)類型0；另一類指該單元不是電路的有效邏輯單元。因此，本文中個體電路x的評價函數(shù)定義如下：定義5：電路x的適應(yīng)值函數(shù)F(x)為電路功能評價與電路有效邏輯門數(shù)之和，即F (x) =H(x) + w*V(x)H(x)為表示個體電路x全部輸出端信號與真值表的匹配程度，V(x)表示擴(kuò)展矩陣編碼表示電路個體x的冗余單元數(shù)。w是動態(tài)權(quán)系數(shù)，若個體為有效電路(滿足真值表中指定的邏輯功能)，其值取1；否則，取很小的正數(shù)。4在片演化的原理框架基于FPGA的物理結(jié)構(gòu)及在片演化硬件技術(shù)的特點，本文采用在片演化硬件設(shè)計原理如圖4所示， XUP-V2P板具有大容量的靜態(tài)和動態(tài)存儲

22、空間，且芯片Virtex-II Pro嵌有IBM PowerPC 405處理器，便于在片演化硬件的設(shè)計。PC機(jī)與FPGA的交互在于系統(tǒng)初始化和演化結(jié)果的輸出，進(jìn)化過程中FPGA板自動下載演化電路的染色體、實測驗證。在片演化的硬件結(jié)構(gòu)可分為兩個模塊：第一個是固定模塊，它包括PowerPC微處理器，RISC結(jié)構(gòu)，單獨的32位指令和數(shù)據(jù)總線用于執(zhí)行算法和FPGA與外部存儲器的數(shù)據(jù)交換。此外，它還包括一些外圍接口，如通過GPIO (general purpose input/output)與可重配置模塊通訊，或參與內(nèi)存管理的一些接口等。第二個模塊為可重配置模塊，它通過總線與GPIO相聯(lián)系，允許算法控制

23、電路的演化。同時，它包括激勵信號產(chǎn)生器對電路功能在片測試和驗證。為了便于進(jìn)行在片演化，本文采用宏結(jié)構(gòu)的虛擬電路表示擴(kuò)展矩陣編碼法中每個單元，如圖5所示。其中，多路選擇器一和多路選擇器二用于選取二輸入邏輯門的二個輸入端信號，它們分別通過寄存器1和2控制。多路選擇器三用于選取該單元的邏輯函數(shù)類型，其控制端通過寄存器3輸出。兩個輸入端信號和一個邏輯函數(shù)構(gòu)成了每個單元的邏輯功能。其中，每個多路選擇器的控制端信號都由寄存器實現(xiàn)。因此，只需改變寄存器內(nèi)容就可實現(xiàn)電路的演化。XC2VP30演化電路模塊激勵信號器XUP-V2P板FPGA 地址空間串口通訊嵌入式處理器（EPEA）PC機(jī)圖4 在片演化設(shè)計原理圖函

24、數(shù)類型1函數(shù)類型2函數(shù)類型MInput寄存器1寄存器2多路選擇器一多路選擇器二多路選擇器三寄存器3Output圖5 宏結(jié)構(gòu)電路單元5實驗與分析為了測試EPEA性能，本文先選取一個單輸出和一個多輸出的組合邏輯電路，其真值表如表4所示：例一由四個輸入(A、B、C、D)和一個輸出Y組成。例二由四個輸入(A、B、C、D)和二個輸出(Z1、Z2)組成。通過與其它智能算法的設(shè)計結(jié)果比較其最優(yōu)電路的邏輯門數(shù)、設(shè)計最優(yōu)電路的頻率、設(shè)計有效電路的頻率和最優(yōu)電路所需邏輯門數(shù)，驗證該算法的效率。為了便于比較與分析，本文采用與文獻(xiàn) 12,13相同的參數(shù)：運行算法20次，種群規(guī)模為50,可選的基本邏輯門類型如表1所示。

25、表4 邏輯電路的真值表InputOutputABCDYZ1Z20000110000111000100100011000010011001011100110100011110010000101001000101010010110011100000110100011100011111101圖6 EPEA設(shè)計例一的電路結(jié)構(gòu)表5 例一電路的設(shè)計結(jié)果與比較PSO12DEPSO13EPEA最優(yōu)電路的邏輯門數(shù)665設(shè)計最優(yōu)電路的頻率0.711設(shè)計有效電路的頻率111平均邏輯門數(shù)6.5565圖7 EPEA設(shè)計例二的電路結(jié)構(gòu)表6 例二電路的設(shè)計結(jié)果與比較GA12PSO12DEPSO13EPEA最優(yōu)電路的邏輯門數(shù)

26、7777設(shè)計最優(yōu)電路的頻率0.250.40.21設(shè)計有效電路的頻率0.750.9511平均邏輯門數(shù)10.58.67對于電路例一，由于它是單輸出電路，演化過程中沒用到雜交操作，每代僅對極少數(shù)個體電路變異及評價。由表5可知，EPEA能以概率1設(shè)計含5個基本邏輯門的最優(yōu)電路(如圖6所示)，其它算法設(shè)計的最優(yōu)電路都需要六個邏輯門。而對于多輸出電路例二，該算法采用雜交和變異策略，設(shè)計性能匯總?cè)绫?所示。從該表可知，EPEA以概率1設(shè)計出含七個基本邏輯門的最優(yōu)電路，電路結(jié)構(gòu)如圖所示。其次，為了深入分析擴(kuò)展矩陣編碼和EPEA的有效性,本文選取了二位乘法器、二位比較器和二位加法器，從多角度與相關(guān)文獻(xiàn)進(jìn)行了比較

27、與分析，表7匯總了幾種算法設(shè)計此組實驗所需的編碼規(guī)模及所需的最少邏輯門數(shù)。由此表可知，采用擴(kuò)展矩陣編碼法所需的染色體長度較短，且EPEA設(shè)計的電路結(jié)構(gòu)較優(yōu)，能有效地減少對資源的消耗。表7 組合邏輯電路設(shè)計匯總與比較二位乘法器二位比較器二位加法器編碼規(guī)模邏輯門數(shù)編碼規(guī)模邏輯門數(shù)編碼規(guī)模邏輯門數(shù)KM1481912NGA155596712557MGA16557679557EPEA447559447此外，由于三位乘法器真值表復(fù)雜，難于自動設(shè)計其電路，許多學(xué)者都用它來驗證算法的有效性。本文設(shè)計含27個邏輯門的三位乘法器電路如圖8所示。圖8 三位乘法器的電路結(jié)構(gòu)6結(jié)論演化硬件作為一個新興研究領(lǐng)域，在實際生

28、活中有著廣泛應(yīng)用，由此引起許多學(xué)者從離線演化和在線演化角度對其進(jìn)行了深入研究。本文首先引入人工設(shè)計電路的經(jīng)驗和規(guī)則，提出了一種擴(kuò)展矩陣編碼法，對于匹配度較低的電路結(jié)構(gòu)進(jìn)行微調(diào)，保護(hù)具有較優(yōu)結(jié)構(gòu)的電路個體不易淘汰。在此基礎(chǔ)上，基于多目標(biāo)和局部尋優(yōu)技術(shù)，提出一種精英池演化算法，結(jié)合子電路雜交法和基于單元重要性的自適應(yīng)變異策略在片演化數(shù)字電路。實驗結(jié)果表明，EPEA在片演化組合邏輯電路實用有效，且能獲得結(jié)構(gòu)較優(yōu)的電路，這些電路作為基本模塊用于設(shè)計更復(fù)雜的硬件系統(tǒng)。今后我們深入研究部分動態(tài)可重構(gòu)技術(shù)及在此基礎(chǔ)上基于細(xì)胞自動機(jī)的自復(fù)制和自繁殖原理研究數(shù)字硬件系統(tǒng)的自容錯、自主進(jìn)化等技術(shù)。參考文獻(xiàn)1. L

29、ouis S J. Genetic algorithms as a computational tool for design Ph. D. dissertation, Indiana, Indiana university, USA, 1993.2. Miller J F and Thomson P. Cartesian genetic programming /Proceedings of the 3rd European Conference on Genetic Programming, Edinburgh, UK. Springer Berlin, 2000:121-132.3. S

30、in Man Cheang, Kin Hong Lee and Kwong Sak Leung. Applying genetic parallel programming to synthesize combinational logic circuits. IEEE transactions on evolutionary computation, 2007, 11(4):503-5204. Zhao Shuguang, Zhao Jianxun and Jiao Licheng. Adaptive genetic algorithm based approach for evolutio

31、nary design and multi-objective optimization of logic circuits /Proceedings of The 2005 NASA/Dod Conference on Evolvable Hardware, Washington DC, USA. IEEE, 2005: 67-72.5. Bao Zhiguo, Watanabe T. A novel genetic algorithm with cell crossover for circuit design optimization / IEEE International Sympo

32、sium on Circuits and Systems, Taipei, Taiwan. IEEE, 2009: 2982 2985.6. Kuyucu T, Trefzer M, Greensted A, Miller J, Tyrrell A. Fitness functions for the unconstrained evolution of digital circuits /2008 IEEE Congress on Evolutionary Computation, Hong Kong, China. IEEE, 2008: 2584-2591.7. Stomeo E, Ka

33、lganova T and Lambert C. Generalized disjunction decomposition for evolvable hardware. IEEE Transactions on Systems, Man and Cybernetics, Part B, 2006, 36(5):1024-1043.8. Shanthi A P, Ranjani Parthasarathi. Practical and scalable evolution of digital circuits. Applied soft computing, 2009, 9:618-624

34、.9. Upegui A and Sanchez E. Evolving hardware with self-reconfigurable connectivity in Xilinx FPGAs / First NASA/ESA Conference on Adaptive Hardware and Systems, Istanbul, Turkey. IEEE, 2006: 153-162.10. Blodget B, James-Roxby P, Keller E, McMillan S and Sundararajan P. A self-reconfiguring platform

35、 /The 13th International Conference on Field Programmable Logic and Application, Lisbon, Portugal, 2003:565-574.11. Sekanina L and Friedl S. On routine implementation of virtual evolvable devices using COMBO6 /The 6th NASA/DoD Workshop on Evolvable Hardware (EH 2004), Seattle, USA, IEEE, 2004: 63-70

36、.12. Coello C A C, Gutierrez R L Z, Garcia B M, and Aguirre A H. Automated design of combinational logic circuits using the Ant System. Engineering Optimization, 2002, 34(2):109-127.13. Moore P W and Venayagamoorthy G K. Evolving digital circuits using hybrid particle swarm optimization and differen

37、tial evolution. International Journal of neural systems, 2006, 16(3):163-177.14. Karnaugh M. The map method for synthesis of combinational logic circuits. Transaction of the AIEE, Communications and Electronic, 1953, 72(I):593-599.15. Coello C A C, Christiansen A D and Aguirre A H. Use of evolutiona

38、ry techniques to automate the design of combinational circuits. International Journal of Smart Engineering System Design, 2000, 2:299-314.16. Coello C A C and Aguirre A H. Design of combinational logic circuits through an evolutionary multiobjective optimization approach. Artificial Intelligence for

39、 Engineering, Design, Analysis and Manufacture, 2002, 16(1):39-53.BACKGROUNDEvolvable Hardware (EHW) approach is a recently developed technology of circuit design built on the Programmable Logic Device (PLD) or Field Programmable Gate Array (FPGA). The architecture of PLD and FPGA is usually represented by chromosome, and can be reconfigured mainly by using evolutionary computation, such as genetic algorithms and genetic programming. In this paper, authors design an elitist pool evolutionary algorithm with an extended matrix