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

柏 磊，俞成龍

（船舶重工集團(tuán)公司723所，揚(yáng)州225001）

0 引 言

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

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

1 電路表達(dá)模型及編碼方法

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

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

具體模型如圖1所示。

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

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

2.1 多染色體表達(dá)

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

2.2 多染色體進(jìn)化策略

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

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

圖3 （1＋λ）多染色體進(jìn)化策略示意圖

（1＋λ）EMC－ES進(jìn)化過(guò)程如下：

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

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

（3）利用適應(yīng)度評(píng)價(jià)擴(kuò)展方法對(duì)新種群中每個(gè)個(gè)體的子染色體進(jìn)行適應(yīng)度評(píng)價(jià)，利用以下方法生成最優(yōu)個(gè)體：

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

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

（4）回到步驟（2）直到得到問(wèn)題的解。

3 實(shí)驗(yàn)結(jié)果與分析

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

表1 用于實(shí)驗(yàn)測(cè)試的問(wèn)題

表2 實(shí)驗(yàn)參數(shù)

對(duì)于每一個(gè)實(shí)驗(yàn)問(wèn)題，所有獨(dú)立運(yùn)行的結(jié)果均采用一種稱(chēng)為“計(jì)算工作量”（CE）的統(tǒng)計(jì)量進(jìn)行評(píng)估。CE建立在所有獨(dú)立運(yùn)行結(jié)果基礎(chǔ)上，是一種計(jì)算解決問(wèn)題所需要的計(jì)算工作量的度量手段。

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

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

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

表3 實(shí)驗(yàn)問(wèn)題的計(jì)算工作量

表4 計(jì)算工作量對(duì)比

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

4 結(jié)束語(yǔ)

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

［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án)璐，等.基于適應(yīng)度評(píng)價(jià)擴(kuò)展自適應(yīng)遺傳算法的門(mén)級(jí)電路進(jìn)化設(shè)計(jì)［J］.南京理工大學(xué)學(xué)報(bào)，2011，35（2）：240－244.