基于擴展多染色體笛卡爾遺傳規(guī)劃的數(shù)字電路進化設(shè)計

柏 磊，俞成龍

（船舶重工集團公司723所，揚州225001）

0 引 言

隨著演化硬件（EHW）［1］技術(shù)的發(fā)展，作為其重要分支的電路進化設(shè)計［2－3］正受到越來越多的關(guān)注。與傳統(tǒng)電路設(shè)計方法相比，電路進化設(shè)計以進化算法作為搜索和優(yōu)化工具，以可編程器件（如現(xiàn)場可編程門陣列（FPGA））［4］作為其實現(xiàn)平臺，在不依賴于先驗知識和外力推動的條件下，通過進化獲得滿足給定要求且更加新穎和優(yōu)化的電路結(jié)構(gòu)。笛卡爾遺傳規(guī)劃（CGP）［5］的編碼方式更接近于FPGA結(jié)構(gòu)，能夠?qū)崿F(xiàn)類似于網(wǎng)表級的編碼，且能獲得更加精簡的電路結(jié)構(gòu)，特有的基因型－表現(xiàn)型映射方式使得搜索更加高效，因此CGP已被廣泛應(yīng)用于組合電路［6－7］、時 序 電 路［8］、多 態(tài) 電 路［9－10］等 數(shù) 字 電 路 進 化設(shè)計及電路后綜合優(yōu)化。隨著進化規(guī)模的不斷加大，數(shù)字電路進化設(shè)計面臨著進化設(shè)計方法擴展性問題［11－13］。大量研究人員正致力于擴展性問題研究，試圖找出更加有效的方法用于探索復(fù)雜問題的搜索空間，簡化進化復(fù)雜度。Vassilev等通過對于適應(yīng)度曲面的研究發(fā)現(xiàn)，相比較采用簡單邏輯門作為構(gòu)建模塊，采用功能較復(fù)雜的子電路能夠加快進化過程［11］。Li等將設(shè)計過程看做是一個壓縮映射的過程，提出基于逐步降維的進化方法，降低了進化復(fù)雜度［14］。Stomeo等提出廣義分裂分解方法，突破了擴展性問題的瓶頸，賦予了組合電路進化設(shè)計新的機遇［15］。

本文針對多輸出電路提出了一種基于擴展多染色體笛卡爾遺傳規(guī)劃的數(shù)字電路進化設(shè)計方法（EMC－CGP），通過多染色體方法將傳統(tǒng)進化設(shè)計方法中單個染色體進化求解多個輸出的復(fù)雜問題分解為多個子染色體，分別求解一個對應(yīng)輸出的較簡單問題，降低進化復(fù)雜度，采用（1＋λ）擴展多染色體進化策略實現(xiàn)進化過程，避免了進化過程中潛在解的丟失。本文利用該方法進行了多輸出電路進化設(shè)計實驗，并與傳統(tǒng)CGP方法進行了比較。

1 電路表達模型及編碼方法

本文采用CGP進行組合電路模型的建立和基因型的表達。對于陣列表達為C行L列的電路結(jié)構(gòu)，共有G＝C·L個可配置邏輯單元，每個單元Gi，j（1≤i≤C，1≤j≤L）均有K個輸入端、M個輸出端和N種備選功能組態(tài)，每個單元的輸入信號集合為GI＝｛GIi，j｜1≤i≤C，1≤j≤L｝，輸出信號集合為GO＝ ｛GOi，j｜1≤i≤C，1≤j≤L｝；p和q分別代表電路的外部輸入個數(shù)及輸出個數(shù)，則陣列的外部輸入為S＝｛Sm｜0≤m≤p－1｝，輸出為O＝｛On｜0≤n≤q－1｝。若規(guī)定各單元的輸入可來自陣列輸入、各單元輸出或邏輯常量C＝｛0，1｝，陣列輸出取自各單元輸出，即GI＝S∪GO∪C，O?GO，則允許各單元間存在信號反饋，故整個陣列表現(xiàn)為時序電路；若限制各單元僅能以前級（左側(cè)）F列單元的輸出作為輸入（將陣列輸入看作第0列虛擬單元的輸出），即禁止單元間的反饋（即前級單元引用后級輸出），則GIi，j? ｛GIx，y｜1≤x≤C，max（0，j－F）≤y，1≤j≤L｝，從而限定陣列僅表達組合電路。

各功能單元均設(shè)為二輸入邏輯門（K＝2，M＝1），對所有單元（包括虛擬單元）Gi，j按先行后列的順序編號GN＝i＋j×C，1≤i≤C，0≤j≤L，則［IS1GN，IS2GN，TSGN］即可作為Gi，j的編碼，其中IS1GN和IS2GN為其輸入來源（即所連接的前級單元的編號）；TSGN為其功能組態(tài)編號，陣列輸出編碼為［OS0，…，OSq－1］，則 整 個 陣 列 的 網(wǎng) 表 級 編 碼 為：［IS11，IS21，TS1］… ［IS1G，IS2G，TSG］［OS0，…，OSq－1］。

具體模型如圖1所示。

圖1 指定輸出位的3×3可配置邏輯單元陣列

2 基于擴展多染色體笛卡爾遺傳規(guī)劃的電路進化設(shè)計方法

2.1 多染色體表達

擴展多染色體笛卡爾遺傳規(guī)劃電路模型和編碼結(jié)構(gòu)與CGP基本相同，唯一的區(qū)別是前者的基因型被分為1組相同長度的子染色體。每個個體基因型中包含的子染色體個數(shù)由待求解問題的輸出個數(shù)決定，每個子染色體對應(yīng)1個輸出，也就是說每個子染色體用于求解問題的1個輸出，因此具有多個輸出的復(fù)雜問題（通常編碼在單個染色體中）就被分解為多個具有單輸出的簡單問題（編碼在單個子染色體中）進行進化求解，降低了求解的復(fù)雜度。當(dāng)某個子染色體獲得了對應(yīng)輸出的解時，該子染色體將直接進入下一代個體，這樣確保待求解問題的部分解不會在進化過程中被破壞。同時，由于所有子染色體仍然編碼在一個染色體中（即單個基因型），因此所有的輸出是同步進化的。每個子染色體均包含相同數(shù)量的節(jié)點，其染色體長度是相同的，可以將其看作具有單個輸出的待求解問題的基因型。每個子染色體內(nèi)部節(jié)點的連接是嚴格限制的，其輸入只能來自于同一個子染色體中前列節(jié)點的輸出或者程序終端輸入，這樣實際上劃分了各子染色體間的界限，切斷了相互間的連接，保證了相對獨立。圖2為采用多染色體模型編碼的2位乘法器問題的基因型。2位乘法器共有4個輸出，因此原始染色體被分為4個子染色體，每個子染色體用于單獨求解乘法器的1個輸出。

2.2 多染色體進化策略

本節(jié)采用（1＋λ）進化策略（（1＋λ）ES）作為基礎(chǔ)實現(xiàn)電路的進化，EMC－CGP針對多染色體表達的特殊性變相引入了一種交叉操作，結(jié)合適應(yīng)度評價擴展方法提出了一種改進的進化策略，稱為（1＋λ）擴展多染色體進化策略（（1＋λ）EMC－ES）。多染色體方法中每個子染色體與一個理想輸出位相對應(yīng)，用于求解該輸出位。每個個體包含n個適應(yīng)度評價值，n為待求解問題的輸出個數(shù)。對于種群中的多個個體而言，將每個個體相同位置子染色體的適應(yīng)度值相互進行比較，（1＋λ）EMC－ES從種群個體對應(yīng)輸出子染色體中選擇適應(yīng)度最高的用于組成一個新的當(dāng)代最優(yōu)個體，并將其作為父代個體進入子代繼續(xù)參與進化。該個體包含對應(yīng)于每個輸出位而言適應(yīng)度最高的子染色體，因而其總適應(yīng)度應(yīng)當(dāng)是高于或等于原始種群中的任意一個個體的，該方法保護了種群中的最優(yōu)子染色體。（1＋λ）EMC－ES選擇過程如圖3所示，每一列對應(yīng)不同個體中用于求解相同輸出位的子染色體，實線表示其中適應(yīng)度最高的子染色體（如輸出位c0對應(yīng)的DFit（2，c0））。圖中5個個體P1～P5的適應(yīng)度如圖右側(cè)所示，分別為31～41，通過選擇不同輸出位對應(yīng)的最優(yōu)子染色體并組合成新的染色體基因型后，其適應(yīng)度值為53，高于原始種群中任意一個染色體。對于每個子染色體，其變異操作是相互獨立的，即每個染色體內(nèi)部按照預(yù)先設(shè)定的變異概率進行變異。

圖2 采用多染色體模型編碼的包含四個子染色體的2位乘法器基因型

圖3 （1＋λ）多染色體進化策略示意圖

（1＋λ）EMC－ES進化過程如下：

（1）隨機產(chǎn)生大小為（1＋λ）的初始種群，利用文獻［16］中所提適應(yīng)度評價擴展方法對每個個體的子染色體進行適應(yīng)度評價，選擇適應(yīng)度最高的個體成為父代最優(yōu)個體。

（2）對父代最優(yōu)個體進行點變異，操作生成λ個子代個體，父代最優(yōu)個體與λ個子代個體組成下一代種群。

（3）利用適應(yīng)度評價擴展方法對新種群中每個個體的子染色體進行適應(yīng)度評價，利用以下方法生成最優(yōu)個體：

（a）當(dāng)相同輸出位對應(yīng)的某個子代的子染色體適應(yīng)度較高時，該子染色體被選擇組成最優(yōu)個體；當(dāng)子代的子染色體與父代的子染色體適應(yīng)度相同時，選擇子代組成最優(yōu)個體；其他情況下父代的子染色體被選擇組成最優(yōu)個體；

（b）循環(huán)步驟（a）進行下一輸出位對應(yīng)的子染色體位置的選擇，直到所有輸出位對應(yīng)的子染色體都選擇完成，當(dāng)代最優(yōu)個體產(chǎn)生；

（4）回到步驟（2）直到得到問題的解。

3 實驗結(jié)果與分析

利用EMC－CGP方法本文進行了1組多輸出門級電路進化設(shè)計實驗，并將實驗結(jié)果與傳統(tǒng)CGP進行了對比。加法器和乘法器均為大規(guī)模電路的基礎(chǔ)組成模塊，被廣泛用于傳統(tǒng)電路設(shè)計方法檢測，因此二者是非常有效的用于檢驗電路進化設(shè)計方法的手段，并且已經(jīng)得到了廣泛應(yīng)用。每組實驗均運行100次，算法最大進化代數(shù)不進行設(shè)置，進化過程直到獲得問題的解才結(jié)束，因此實驗成功概率是100%。用于測試方法有效性的實驗問題種類和參數(shù)設(shè)置如表1和表2所示。用于組成電路的門電路功能設(shè)置如表2所示，乘法器設(shè)計采用設(shè)置1，加法器設(shè)計采用設(shè)置2。

表1 用于實驗測試的問題

表2 實驗參數(shù)

對于每一個實驗問題，所有獨立運行的結(jié)果均采用一種稱為“計算工作量”（CE）的統(tǒng)計量進行評估。CE建立在所有獨立運行結(jié)果基礎(chǔ)上，是一種計算解決問題所需要的計算工作量的度量手段。

用于計算CE的公式如（2）到（4）所示：

式中：Ns（i）為算法運行至第i代時成功獲得問題的解的獨立運行次數(shù)；Ntotal為 獨立運行總次數(shù)；P（M，i）為大小為M的種群在一次獨立運行中第i代時成功獲得問題的解的累積概率；R（z）為第i代時在概率z下為了滿足成功判定需要獨立運行的次數(shù)；I（M，i，z）為第i代時在概率z下獲得問題解需要處理的個體數(shù)量，本文中z＝0.99；ceil（＊）表示向上取整。

對于所有的測試問題，CGP和EMC－CGP均100%獲得了問題的解。為了更好地詮釋多染色體方法及適應(yīng)度評價擴展對提高CGP的性能所做的貢獻，表3和表4中分別列出了只使用多染色體方法（MC－CGP）和在此基礎(chǔ)上添加適應(yīng)度評價擴展（EMC－CGP）后的計算工作量。

表3 實驗問題的計算工作量

表4 計算工作量對比

通過對比可知，將復(fù)雜多輸出問題分解為簡單問題進行求解的優(yōu)勢很明顯，5種電路進化設(shè)計計算工作量對比MC－CGP是CGP的79.1%～4.7%，當(dāng)繼續(xù)使用適應(yīng)度評價擴展后，EMC－CGP是CGP的62.0%～1.0%。通過分析可以發(fā)現(xiàn)，隨著進化復(fù)雜度的加大（如從1位加法器到3位加法器，從2位乘法器到3為乘法器），EMC－CGP算法較傳統(tǒng)CGP需要的計算工作量更少，其有效性受問題復(fù)雜度增加的影響比單染色體表達下的CGP更小。因此可以推測隨著輸出位數(shù)的增多以及進化復(fù)雜度的不斷加大，該方法的性能提高將更加明顯，改善了進化方法的擴展性能。

4 結(jié)束語

本文提出了一種基于擴展多染色體笛卡爾遺傳規(guī)劃的數(shù)字電路進化設(shè)計方法。針對進化設(shè)計方法隨著多輸出電路輸入輸出組合的增加，進化復(fù)雜度加大、進化過程中潛在解丟失而面臨的擴展性問題，該方法采用多染色體表達降低了進化復(fù)雜度，提出（1＋λ）擴展多染色體進化策略實現(xiàn)了進化過程，避免了潛在解的丟失。實驗結(jié)果表明EMC－CGP方法有效性受待求解問題復(fù)雜度增加的影響較小，在100%成功概率前提下，其計算工作量是傳統(tǒng)CGP的62.0%～1.0%，改善了進化設(shè)計方法的擴展性能。

［1］Yao X，Higuichi T.Promises and challenges of evolvable hardware［J］.IEEE Transactions on Systems，Man and Cybernetics－Part C：Applications and Reviews，2005，14（3）：549－553.

［2］Thompson A，Layzell P，Zebulum R S.Explorations in design space：Unconventional electronics design through artificial evolution［J］.IEEE Transations on Evolutionary Computation，1999，3（3）：167－196.

［3］Coello Coello C A，Christiansen A D.Use of evolutionary techniques to automate the design of combinational circuits［J］.International Journal of Smart Engineering System Design，2000，2（4）：299－314.

［4］Zhao S G，Yang W H.Intrinsic hardware evolution based on a prototype of function level FPGA［J］.Chinese Journal of Computers，2002，25（6）：666－669.

［5］Miller J F，Harding S.Cartesian genetic programming［A］.Genetic and Evolutionary Computation Conference［C］.Atlanta，GA，USA，2008：2701－2725.

［6］Irfan M，Habib Q，Hassan G M，et al.Combinational digital circuit synthesis using cartesian genetic programming from a NAND gate template［A］.6th International Conference on Emerging Technologies［C］.Islamabad，Pakistan，2010：343－347.

［7］Liang H，Luo W，Li Z，et al.Designing combinational circuits with an evolutionary algorithm based on the repair technique［A］.9th International Conference on Evolvable Systems：From biology to Hardware［C］.York，United Kingdom，2010：193－201.

［8］Liang H，Luo W，Wang X.A three－step decomposition method for the evolutionary design of sequential logic circuits［J］.Genetic Programming and Evolvable Machines，2009，10（3）：231－262.

［9］Gajda Z，Sekanina L.On evolutionary synthesis of compact polymorphic combinational circuits［J］.Journal of Multiple－Valued Logic and Soft Computing，2011，17（5－6）：607－631.

［10］Sekanina L.Evolutionary design of gate－level polymorphic digital circuits［A］.6th International Conference on Evlovable Systems：From Biology to Hardware［C］.Lausanne，Switzerland，2005：185－194.

［11］Vassilev V K，Miller J E.Scalability problems of digital circuit evolution evolvability and efficient designs［A］.The Second NASA／DoD Workshop on Evolvable Hardware［C］.Los Alamitos，CA，USA，2000：55－64.

［12］Coello Coello C A，Christiansen A D，Aguirre A H.Towards automated evolutionary design of combinational circuits［J］.Computers and Electrical Engineering，2001，27（1）：1－28.

［13］Gordon T G W，Bentley P J.Development brings scalability to hardware evolution［A］.2005NASA／DoD Conference on Evolvable Hardware［C］.Washington，DC，USA，2005：272－279.

［14］Li Z，Luo W，Wang X.A stepwise dimension reduction approach to evolutionary design of relative large combinational logic circuits［A］.8th International Conference on Evolvable Systems：From Biology to Hardware［C］.Prague，Czech Republic，2008：47－58.

［15］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.

［16］柏磊，顧陳，嚴璐，等.基于適應(yīng)度評價擴展自適應(yīng)遺傳算法的門級電路進化設(shè)計［J］.南京理工大學(xué)學(xué)報，2011，35（2）：240－244.