復(fù)雜數(shù)字電路的分解演化研究

摘 要： 針對制約演化硬件技術(shù)發(fā)展所面臨的可擴展性問題，提出了一種GD?BIE分解演化方法，它將待演化電路按照先輸出分解后輸入分解的順序，逐步分解為多個子電路，最后將演化成功的子電路有規(guī)律的綜合完成目標電路的演化設(shè)計。實驗證明，該分解方法能有效解決大規(guī)模電路演化中存在的染色體編碼長、最大適應(yīng)度高、演化代數(shù)多、輸入輸出真值表組合復(fù)雜的問題，為較大規(guī)模電路演化提供了一種有效途徑。

關(guān)鍵詞： 演化硬件； 擴展性問題； 分解演化； 大規(guī)模電路

中圖分類號： TN710?34； TP316 文獻標識碼： A 文章編號： 1004?373X（2013）23?0151?03

Research on the decomposition evolution for complex digital circuit

LOU Jian?an， LI Yang， YU Jian?hua

（Department of Vehicle and Electrical Engineering， Ordnance Engineering College， Shijiazhuang 050003， China）

Abstract： In view of the scalability problem faced by evolvable hardware technology development， a GD?BIE decomposition evolution method is proposed， which decomposes the circuit for evolves into multiple sub circuits with the order of the output decomposition before input decomposition. Finally， it achieves the evolving goals by regularly combining all sub circuits. The experiments shows that the proposed decomposition method can effectively solve the scalability problem in large scale circuit evolution， such as long chromosome coding， high maximum adaptation degree， large evolution algebras and complex truth table combination of input and output. The GD?BIE method provides an effective way for large?scale circuit evolution.

Keywords： evolvable hardware； scalability problem； decomposition evolution； large?scale circuit

1 演化硬件的可擴展性問題

演化硬件技術(shù)是一種面向行為級描述的電路綜合設(shè)計技術(shù)[1]，其不依賴于設(shè)計者的先驗知識和豐富經(jīng)驗，只需給出電路的高層次描述（如波形圖、相位圖、真值表等），演化算法根據(jù)設(shè)定條件搜索滿足條件的電路結(jié)構(gòu)，有利于提高電路設(shè)計的自動化程度。盡管演化硬件在設(shè)計小規(guī)模電路（比如乘法器、譯碼器、簡單邏輯電路等）上取得了成功，但在大規(guī)模電路設(shè)計上仍然面臨著可擴展性問題（scalability）[2]。所謂可擴展性問題是指當目標電路演化規(guī)模較大時，演化設(shè)計方法的效率十分低下，甚至不能演化出目標電路。文獻[3]分析了演化硬件技術(shù)相比于傳統(tǒng)方法的技術(shù)優(yōu)勢和自提出以來取得的重大成果，也指出了可擴展性問題是制約演化硬件技術(shù)發(fā)展和面向現(xiàn)實世界應(yīng)用的一個重要因素。

造成演化硬件可擴展性問題的因素主要有三個：

（1）染色體編碼長度過長，演化計算效率很低。染色體基因由邏輯門編碼和連接關(guān)系編碼組成，而且演化過程中還存在大量的冗余邏輯單元，因此目標電路的演化規(guī)模越大，需要的冗余單元越多，演化一個100個邏輯單元的電路，染色體長度通常達到上千位，而演化擴展計算帶來極大的困難。

（2）輸入輸出組合過多，算法搜索空間極大。隨著演化規(guī)模的增大，輸入輸出數(shù)量也越來越多。真值表的長度與輸入個數(shù)呈指數(shù)級關(guān)系，真值表的擴大給電路個體適應(yīng)度評價帶來巨大的困難。

（3）真值表的復(fù)雜度增加，使算法的搜索空間增大，直接引起個體適應(yīng)度的評估時間增加，進一步導(dǎo)致演化速度的降低。

2 分而治之的演化思想

針對以上三個造成演化硬件可擴展性問題主要因素，國外一些研究者首先提出了“分而治之”（Divide?and?Conquer）的演化分解方法[4]，以期降低單次演化的規(guī)模，減短染色體編碼程度，縮小算法搜索空間，從而解決電路演化的可擴展性問題。

最典型的“分而治之”的分解演化方法是Tatiana Kalganova提出的雙向增量演化（Bi?direction Incremental Evolution，BIE）[5]和E.Stomeo等提出的通用分解演化算法（Generalized Disjunction Decomposition，GDD）[6]。BIE的主要思想是首先將電路分解成若干個子電路，分別進行演化，當所有的子電路都演化完成后，再把它們組合成整個電路，并在不影響電路功能的前提下進行必要的優(yōu)化，但是該方法對電路輸入組合多的情況顯得無能為力。GDD的基本思想是在演化過程開始之前根據(jù)經(jīng)驗對整個系統(tǒng)進行輸入分解，將整個待演化系統(tǒng)分解成可演化部分（G）和固定部分（H）：可演化部分的輸入是待演化系統(tǒng)輸入的一部分，其個數(shù)必須足夠小到利用 BIE 分解算法能夠進行充分演化；而固定部分則是由事先設(shè)計好的選擇器組成，原系統(tǒng)余下輸入是其選擇信號端，G 的輸出是其輸入信號。GDD方法有效解決了電路輸入組合多的難題，但對于電路輸出多的情形下，仍然存在適應(yīng)度評價困難的問題。

文獻[7?8]介紹了通用分解演化結(jié)合雙向增量演化（GD?BIE）的演化方法，該方法綜合的GDD方法的輸入分解優(yōu)勢和BIE方法輸出分解的特點可演化出較大規(guī)模的電路，但分解過程需依賴于設(shè)計者的經(jīng)驗。本文提出一種改進的GD?BIE分解演化方法，該方法只需設(shè)定好固定部分的參數(shù)，對于不同的目標電路需從細微處調(diào)整分解算法就能演化出同等規(guī)模范圍的數(shù)字電路，基本實現(xiàn)電路的設(shè)計自動化。

3 改進GD?BIE分解演化實現(xiàn)

3.1 分解原理

本文提出的改進GD?BIE方法，是結(jié)合GDD方法的真值表分解和BIE方法的全自動分解及組合優(yōu)勢而提出的一種分解演化方法，其主要的思想仍然是“分而治之”的分解演化策略。分解演化的方法稱作分而治之的方法，也可以作為是自生長的演化方法[9]，其通過多個子系統(tǒng)演化來降低演化算法的搜索空間，降低每次的演化難度，每次先演化簡單的模塊，最后通過簡單模塊的組合生成復(fù)電路。

如圖1所示為GD?BIE方法的分解設(shè)計描述，圖1（a）是一個待演化的普通[m]輸入[n]輸出的目標電路，如果該電路中[m]和[n]過大，直接對其演化將導(dǎo)致演化過程出現(xiàn)可擴展性問題，從而導(dǎo)致演化設(shè)計效率低下，甚至是設(shè)計失敗。圖1（b）是對輸出進行分解的演化模型，借鑒BIE分解特點，對其輸出分解為兩個及其以上的子電路，從而以多次演化的方式減少單次電路演化的輸出個數(shù)。圖1（c）是將輸入和輸出都進行分解的演化模型，該步驟選取電路的[m]個輸出中的[（m-t）]個作為待演化子電路的輸出，剩下的輸入不再參與演化，而是進入固定部分H作為演化輸出的選擇信號。圖1（d）是對分解后的子電路進行組合的模型，最后完成整個目標電路的演化。

圖1 GD?BIE分解

3.2 分解描述

實驗以四位全加器為例，直觀說明電路的分解、演化和組合過程。四位全加器電路為一個8輸入5輸出組合邏輯電路，其分解過程如圖2所示。

由圖2（a）可見，電路的原始真值表輸入規(guī)模達100×8，輸出真值表達100×5，對于這種規(guī)模下的目標電路演化最大適應(yīng)度將達到500，如果對其直接演化將導(dǎo)致染色體編碼過長、演化算法搜索效率低下以及適應(yīng)度評價及其困難等大規(guī)模電路演化過程中常見的可擴展性問題。因此，要想完成如此規(guī)模的電路演化設(shè)計，分解演化的方法就具有了應(yīng)用意義。圖2（b）所示為對原始真值表進行輸出分解，將目標電路真值表分解為一個8輸入4輸出子電路和一個8輸入1輸出子電路系統(tǒng)，該步驟將降低待演化大量的最大適應(yīng)度值。圖2（c）與圖2（d）分別演示了對圖2（b）中的兩個子電路系統(tǒng)的進一步分解，其分解原理是把電路的8個輸入中的4個作為分解后子電路的演化部分輸入，另外剩下4個輸入作為子電路的選擇信號，該步驟完成后，目標電路被分解為2×16=32個子電路。

3.3 演化實驗

實驗時，電路采取笛卡爾遺傳程序編碼（Cartesian Genetic Programming，CGP），分解后的子電路規(guī)模分別為4×4和4×1，最大適應(yīng)度值為64和16，基本邏輯門包括：與門、或門、與非門和或非門。最終電路需要用到64輸入8輸出的多路選擇器，但其不參與演化。演化算法采用遺傳算法，種群規(guī)模為20，交叉率為0.75，變異率為0.01，最大演化代數(shù)為200 000。分解演化算法重復(fù)運行10次，32個子電路均達到100%演化設(shè)計成功，其演化代數(shù)分布如圖3所示。

由圖3中可見4×4子電路的最大演化代數(shù)在16 000代以下，有些子電路甚至只需幾百代就能演化成功，4×1子電路由于最大適應(yīng)度值為16，故所需演化代數(shù)更少。雖然GD?BIE分解演化方法進行了32次電路演化，但是卻成功演化出來了目標電路的所有功能，這在不采用分解方法演化時是不可能完成的任務(wù)。正是如此，證明了分解演化方法在大規(guī)模電路演化設(shè)計上的作用和意義。

圖3 子電路演化代數(shù)分布

4 結(jié) 論

可擴展性問題是制約演化硬件面向復(fù)雜數(shù)字電路演化設(shè)計的一項技術(shù)難題。針對這一難題，本文提出一種GD?BIE分解演化方法，該方法綜合利用BIE和GDD分解方法的特點和各自優(yōu)勢，對復(fù)雜數(shù)字電路能夠?qū)崿F(xiàn)較大規(guī)模的演化設(shè)計。實驗證明，該分解演化方法對電路真值表的輸入輸出進行分解，然后對子電路分別演化以達到降低目標電路復(fù)雜度目的，有效地解決了復(fù)雜數(shù)字電路演化設(shè)計的可擴展性問題。

參考文獻

[1] THOMPSON A. Hardware evolution： automatic design of electronic circuits in reconfigurable hardware [M]. London： Springer?Verlag， 2012.

[2] VASSILEV V K. Scalability problems of digital circuit evolution[C]// Proceedings of the 2nd NASA/DoD Workshop on Evolvable Hardware. Palo Alto， CA： NASA/DoD， 2000： 55?64.

[3] YAO X， HIGUCHI T. Promise and challenges of evolvable hardware [J]. IEEE Transactions on Systems， Man， and Cybernetics?Part C： Applications and Reviews， 1999， 29（1）： 87?97.

[4] TORRESEN J. Evolving multiplier circuits by training set and training vector partitioning [C]// Proceedings of 5th International Conference on Evolvable Hardware. Trondheim， Norway： ICES， 2003： 228?237.

[5] KALGANOVA T. Bidirectional incremental evolution in evolva? ble hardware[C]// Proceedings of 2nd NASA/DoD Workshop on Evolvable Hardware. Palo Alto， CA： 2000， NASA/DoD： 65?74.

[6] STOMEO E， KALGANOVA T. Improving EHW performance introducing a new decomposition strategy[C]// Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems. Singapore： IEEE， 2004： 439?444.

[7] STOMEO E， KALGANOVA T， LAMBERT C， et al. On evolution of relatively large combinational logic circuits[C]// Proceedings of NASA/DoD Conference Evolvable Hardware. Washington DC， USA： NASA/DoD， 2005： 59?66.

[8] STOMEO E， KALGANOVA T， LAMBERT C. Generalized disjunction decomposition for evolvable hardware [J]. IEEE Transactions on Systems， Man and Cybernetics， Part B： Cybernetics， 2006， 36（5）： 1024?1043.

[9] TORRESEN J. Increased complexity evolution applied to evolva? ble hardware[C]// Proceedings of ANNIE on Smart Engineering System Design： Neural Networks， Fuzzy Logic， Evolutionary Programming， Data Mining， and Complex Systems. St. Louis， USA： ANNIE， 1999： 429?436.