基于自適應(yīng)免疫進(jìn)化算法的邏輯電路設(shè)計(jì)

摘 要：針對現(xiàn)有進(jìn)化算法在進(jìn)行邏輯電路設(shè)計(jì)時(shí)存在的進(jìn)化緩慢和容易陷入局部解等問題，提出一種自適應(yīng)免疫進(jìn)化算法（adaptive immune evolutionary algorithm，AIEA）。該算法引入了免疫記憶機(jī)制和抗體差異調(diào)節(jié)算子，能夠很好地保證個(gè)體的多樣性，有利于跳出局部最優(yōu)解；通過采用自適應(yīng)交叉率和變異率，提高了算法的搜索能力和收斂速度。通過與多目標(biāo)進(jìn)化算法（MOEA）、簡單免疫算法（SIA）的實(shí)驗(yàn)比較，證明了該自適應(yīng)免疫進(jìn)化算法的有效性。

關(guān)鍵詞：進(jìn)化算法；邏輯電路設(shè)計(jì)；免疫進(jìn)化算法；自適應(yīng)

中圖分類號：TN702； TP18文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695(2009)06-2276-03

doi:10.3969/j.issn.1001-3695.2009.06.084

Immune-based adaptive evolutionary algorithm for logic circuit design

XU Hai-qin1， DING Yong-sheng1， 2， HU Zhi-hua1

(1. College of Information Sciences Technology， Donghua University， Shanghai 201620， China; 2. Engineering Research Center of Digitized Textile Fashion Technology， Ministry of Education， Shanghai 201620， China)

Abstract:

To solve the problems of traditional evolution algorithm， such as slowness evolution speed and premature convergence， this paper presened an adaptive immune evolutionary algorithm (AIEA) for combinational logic circuit design. The AIEA draws into the mechanisms existing in biological immune system such as immune memory， immune regulation， and antibody diversity. Besides， the AIEA featured an adaptation strategy that enabled crossover probability and mutation probability to vary with genetic-search process. The results were compared with those produced by the multi-objective evolutionary algorithm (MOEA) and by the simple immune algorithm (SIA). The simulation results show that AIEA overcomes the disadvantages of premature convergence， and improve the global searching efficiency and capability.

Key words：evolutionary algorithm; logic circuit design; immune evolutionary algorithm; adaptive

0 引言

作為可進(jìn)化硬件（evolvable hard-ware， EHW）研究的重要分支，近年來興起的電路進(jìn)化設(shè)計(jì)^[1]研究已初步展示其在實(shí)現(xiàn)電路設(shè)計(jì)自動(dòng)化方面的潛力。它是利用進(jìn)化計(jì)算技術(shù)配置電路的內(nèi)部結(jié)構(gòu)以獲得所需的電路功能，可在不依賴先驗(yàn)知識(shí)和規(guī)則的條件下探索更為廣闊的設(shè)計(jì)空間。其不但有望實(shí)現(xiàn)復(fù)雜電路的自動(dòng)設(shè)計(jì)并獲得新穎、優(yōu)化的設(shè)計(jì)結(jié)果，而且是研究和實(shí)現(xiàn)具有自修復(fù)與自復(fù)制能力的機(jī)器所必需的基本前提，因而成為國際上的研究熱點(diǎn)。

電路進(jìn)化設(shè)計(jì)當(dāng)前是以進(jìn)化算法（EA）特別是遺傳算法（GA）為主要工具，盡管GA已成功用于解決某些簡單電路的設(shè)計(jì)^[2，3]，但隨著電路規(guī)模的增大和輸入、輸出的增加，搜索空間和計(jì)算的復(fù)雜性將大大增加，算法的收斂速度大大降低，且易陷入局部最優(yōu)解。

為了克服傳統(tǒng)進(jìn)化算法收斂速度慢和易早收斂的缺點(diǎn)，本文設(shè)計(jì)了自適應(yīng)免疫進(jìn)化算法。針對求解問題的特性設(shè)計(jì)個(gè)體的結(jié)構(gòu)與算子，阻止個(gè)體退化，加快搜索速度，通過抗體的自我調(diào)整機(jī)制維持個(gè)體的多樣性。針對群體分布不均勻時(shí)易出現(xiàn)早收斂的問題，引入生物免疫系統(tǒng)的學(xué)習(xí)、記憶、多樣性和識(shí)別的特點(diǎn)，使其有選擇、有目的地利用信息特征來抑制優(yōu)化過程中的個(gè)體退化現(xiàn)象。目前這類算法大多采用計(jì)算抗體濃度方法改進(jìn)算法的選擇操作^[4]，而沒有考慮算法本身的改進(jìn)，進(jìn)化過程仍然采用的是傳統(tǒng)EA流程。本文

中的自適應(yīng)免疫進(jìn)化算法（AIEA）通過引入動(dòng)態(tài)策略和自適應(yīng)機(jī)制以改善算法本身的性能。

1 邏輯電路模型與編碼方案

依據(jù)組合邏輯電路的特點(diǎn)，參考文獻(xiàn)[5]的編碼方案，把邏輯電路表示成如圖1所示的陣列式模型。這種電路的編碼方法已被用于成功解決邏輯電路最小化設(shè)計(jì)問題。該陣列包括R行C列，共G=R×C個(gè)功能可配置的門級單元，每個(gè)單元Vij(1≤i≤R，1≤j≤C)均有兩個(gè)輸入端、一個(gè)輸出端和八種可選的功能組態(tài){NOT， AND， OR， XOR， NAND， NOR， NXOR，WIRE}（如果某單元是一空單元就用WIRE表示）。圖1中，每個(gè)單元（用方框表示）由三個(gè)參數(shù)決定，即input 1、input 2和gate type。其中：input 1、input 2為該單元兩個(gè)輸入；gate type為該單元邏輯功能。

為了更好地理解圖中的各邏輯單元，各邏輯單元及編號如表1所示。

在將邏輯電路編碼成串結(jié)構(gòu)時(shí)，遵循列優(yōu)先編碼。對R行C列m個(gè)輸出的電路模型，其編碼長度為3×R×C+m。圖2是個(gè)體的編碼串結(jié)構(gòu)。

2 基于自適應(yīng)免疫算法的電路設(shè)計(jì)

2.1 電路設(shè)計(jì)問題及親和度函數(shù)

為了便于描述邏輯電路中邏輯單元和單元間連接關(guān)系，用一個(gè)有向圖G=(V，E)描述邏輯電路。其中，非空節(jié)點(diǎn)集V表示電路中的邏輯門（即結(jié)構(gòu)圖中的方框），V={v1，v2，…，vL}且L=R×C；有向邊集E表示電路中邏輯門之間的連接且EV×V。為了表示圖G是一個(gè)帶反饋的有向圖，圖的邊連接表示為

E=(vi，xi)∪(vi，yi)（1）

其中:1≤i≤L，vi∈V，xi，yi∈V且vi≠xi≠yi。

每個(gè)邏輯門的輸入只能從它的前級門的輸出獲得，那么可表示為

i∈Lcolumn(vi)>[column(xi)，column(yi)]（2）

每個(gè)邏輯門只有兩個(gè)輸入端，非門（NOT）和空單元（WIRE）均認(rèn)為是由兩條相同的輸入邊組成，即

i∈Ld(vi)=2（3）

其中：d(#8226;)表示節(jié)點(diǎn)的輸入度。這樣，圖的邊與節(jié)點(diǎn)之間關(guān)系為

E=2V（4）

對于有n個(gè)輸入、m個(gè)輸出的電路真值表可表示為F{0，1}n×{0，1}m，每個(gè)布爾函數(shù)f{0，1}n→{0，1}m都表示一個(gè)布爾關(guān)系，(a，b)∈Ff(a)=b。其中：a∈{0，1}n，b∈{0，1}m，為了滿足m個(gè)輸出的布爾函數(shù)的要求，則個(gè)體的功能符合率函數(shù)F1可表示為

F1=∑Nj=1Hj/N（5）

其中：N=2n，Hj(aj，bj)=10 ，若滿足f(aj)=bj0，否則

為了在滿足符合真值表要求的條件下最簡化電路規(guī)模，本文將無效單元數(shù)和WIRE數(shù)量考慮進(jìn)個(gè)體親和度函數(shù)中，此處個(gè)體比喻為免疫系統(tǒng)中的抗體。無效單元即信號鏈路起點(diǎn)和終點(diǎn)的邏輯電平不隨輸入和時(shí)間變化的單元，如AND、OR組態(tài)但兩輸入端并聯(lián)的單元，偶數(shù)多個(gè)前后級聯(lián)但中間節(jié)點(diǎn)并未連接其他單元的NOT組態(tài)單元等。

F2=（L-U）/L（6）

其中：U為無效單元個(gè)數(shù)，可由仿真結(jié)果和陣列中各單元間的連接關(guān)系求得；L為總單元數(shù)。

F3=w/L（7）

其中：w為WIRE單元個(gè)數(shù)。

因此抗體親和度函數(shù)可定義為

Aff(t)=∑3k=1xk(t)Fk(t)（8）

其中：xk(t)為每個(gè)目標(biāo)函數(shù)隨代數(shù)t變化的權(quán)值。

2.2 克隆選擇與高頻變異

為了提高算法全局收斂速度和有效減少早熟現(xiàn)象，本文對子代個(gè)體與父代個(gè)體按免疫親和度進(jìn)行排序，對前popsize/2個(gè)個(gè)體，其個(gè)體i的選擇概率Pir定義為

Pir=Fi/∑j∈DFj（9）

其中:D為進(jìn)行選擇操作的個(gè)體總數(shù)。并且定義克隆群體規(guī)模為cpopsize=mc×popsize。其中：mc為克隆選擇的群體系數(shù)，本文取mc=3。則對于個(gè)體i，其克隆系數(shù)Ci定義為

Ci=Pir×cpopsize（10）

對于每個(gè)通過克隆選擇生成的個(gè)體，以概率1進(jìn)行單點(diǎn)高頻變異，消除克隆群體中的個(gè)體重復(fù)性，產(chǎn)生多樣性。同時(shí)，克隆群體與原群體合并。

2.3 交叉、變異策略

規(guī)模大且分布均勻的種群對于保證算法的整體性能十分重要，而交叉概率Pc和變異概率Pm的選擇直接影響著算法的搜索速度與收斂性能，因此本文設(shè)計(jì)自適應(yīng)的交叉概率Pc和變異概率Pm提高算法的搜索與收斂性，令Pc、Pm隨進(jìn)化程度緩慢而單調(diào)地遞減。在迭代初期，為了能全面和廣泛地探索整個(gè)解空間，遺傳算子取較大的值；而在迭代后期，為了能夠避免不破壞優(yōu)良的基因，使算法精確快速地收斂到全局最優(yōu)解，遺傳算子取較小值。

對于交叉概率Pc定義為

Pc=Pcoe-ε1t/tmax（11）

其中:Pco為初始交叉概率；t為當(dāng)前進(jìn)化代數(shù)；tmax為最大進(jìn)化代數(shù)；ε1為常數(shù)。另一方面，交叉算子僅僅作用在不同個(gè)體的克隆副本之間，從而避免在相近子代之間的過度繁殖。另外為了控制種群規(guī)模，采用交叉后直接替換父本的策略。

本文中的變異包括連接關(guān)系的變異和邏輯門組態(tài)的變異。任何邏輯門均可由各輸入信號或前列門的輸出作為輸入，而邏輯門的組態(tài)在給定的七種組態(tài)中進(jìn)行選擇。其變異概率為

Pm=Pmoe-ε2t/tmax（12）

其中:Pmo為初始變異概率；ε2為常數(shù)。

2.4 免疫清除與免疫記憶策略

為了保持種群規(guī)模的穩(wěn)定性，并保證種群進(jìn)化的單調(diào)性，引入免疫清除策略清除克隆種群中弱勢個(gè)體，引入免疫記憶策略存儲(chǔ)種群中的最優(yōu)個(gè)體。通過克隆選擇后，原種群規(guī)模從popsize發(fā)展到mc+1×popsize，在免疫清除算子中，對所有個(gè)體進(jìn)行排序，mc×popsize個(gè)個(gè)體被清除出種群。而最佳個(gè)體保存在作為全局記憶機(jī)構(gòu)的免疫記憶單元中，如果已經(jīng)記錄有優(yōu)勢個(gè)體，則進(jìn)行比較，保存更好的個(gè)體。

2.5 算法實(shí)現(xiàn)

基于自適應(yīng)免疫進(jìn)化算法的電路設(shè)計(jì)算法如下：

a)確定群體大小及各參數(shù)，根據(jù)編碼規(guī)則隨機(jī)產(chǎn)生大小為P0的N0個(gè)合法個(gè)體。

b)計(jì)算抗體親和度并進(jìn)行排列，取前N0個(gè)優(yōu)勢個(gè)體，設(shè)t=1。

c)對每個(gè)優(yōu)勢個(gè)體進(jìn)行克隆選擇與高頻變異，產(chǎn)生克隆種群。

d)計(jì)算自適應(yīng)的交叉概率，在不同父代的克隆個(gè)體之間進(jìn)行交叉。

e)計(jì)算自適應(yīng)的變異概率，個(gè)體進(jìn)行基因位變異。

f)t=t+1。通過免疫清除算子保持穩(wěn)定的種群，通過免疫記憶機(jī)制保留優(yōu)勢個(gè)體。

g)是否滿足終止條件，若滿足，則轉(zhuǎn)步驟h）；否則，返回步驟b）。

h)得到的適應(yīng)度最高的個(gè)體作為解輸出。

3 仿真實(shí)驗(yàn)

為了驗(yàn)證上述算法的有效性，本文分別針對三位判偶校驗(yàn)器和2×2乘法器進(jìn)行了仿真實(shí)驗(yàn)。實(shí)驗(yàn)中部分參數(shù)設(shè)置如表2所示。另外適應(yīng)度函數(shù)中各權(quán)值x1(0)=x2(0)=x3(0)=1/3，初始交叉率PC0=0.8，初始變異率Pm0=0.2。最終進(jìn)化電路如圖3、4所示。

初始群體最大迭代代數(shù)陣列規(guī)模染色體長度

3/1校驗(yàn)器1002004×337

4/4乘法器2005005×464

針對上述兩個(gè)實(shí)例的仿真實(shí)驗(yàn)中，在采用相同的初始種群數(shù)和進(jìn)化代數(shù)的情況下，分別利用多目標(biāo)進(jìn)化算法（MOEA）^[7]、簡單免疫進(jìn)化算法（SIA）^[8]和本文算法進(jìn)行了比較研究。表3、4是最終求得的優(yōu)化電路的邏輯式和所需門數(shù)。人工設(shè)計(jì)采用的是傳統(tǒng)的卡諾圖方法。通過幾種算法比較，很明顯本文算法獲得了較好的簡化效果。

圖5、6分別是兩個(gè)實(shí)驗(yàn)中平均親和度值隨進(jìn)化代數(shù)變化的曲線，AIEA因?yàn)榧尤肓丝寺∵x擇算子、自適應(yīng)地交叉與變異算子以及免疫記憶機(jī)制，所以收斂速度最快，在相同進(jìn)化代數(shù)下，取得最好的進(jìn)化個(gè)體。SIA進(jìn)化速度和效率最差，這是由于其交叉變異概率均為固定值，算法進(jìn)化過程中存在一定的隨機(jī)性且易陷入局部最優(yōu)解，而MOEA盡管效果比SIA好，但收斂速度較AIEA差。



對三位判偶校驗(yàn)器的設(shè)計(jì)由表3可知，AIEA和MOEA都能找到僅有4個(gè)邏輯門組成的優(yōu)化解，但從圖5進(jìn)化曲線來看AIEA是在迭代85代后就已求得最簡解，而MOEA卻要運(yùn)行到190代。所以從運(yùn)行速度上來看，AIEA明顯高于MOEA。對2×2乘法器的設(shè)計(jì)中，AIEA求得的解只有7個(gè)邏輯門，而MOEA和SIA求得的最終解有8個(gè)邏輯門，另外從圖6的進(jìn)化速度看，在達(dá)到同一親和度值時(shí)AIEA所需代數(shù)明顯小于MOEA與SIA。

通過以上實(shí)驗(yàn)結(jié)果可以發(fā)現(xiàn)，采用自適應(yīng)免疫進(jìn)化算法搜索到最優(yōu)解或滿意解的概率較大，較好地克服了傳統(tǒng)進(jìn)化算法的早熟現(xiàn)象，而且，由于采用了自適應(yīng)的交叉、變異概率，該算法的平均進(jìn)化代數(shù)較少，從而節(jié)約了運(yùn)算時(shí)間。實(shí)驗(yàn)還進(jìn)一步發(fā)現(xiàn)，隨著進(jìn)化代數(shù)的增加，能得到更好的較優(yōu)解。

4 結(jié)束語

本文將自適應(yīng)免疫進(jìn)化算法應(yīng)用于組合邏輯電路的設(shè)計(jì)問題。該算法在傳統(tǒng)免疫算法的基礎(chǔ)上通過引入免疫記憶機(jī)制和抗體差異調(diào)節(jié)算子，還加入了自適應(yīng)的交叉、變異算子。實(shí)驗(yàn)證明，該算法具有較好的全局搜索性能和較快的收斂性，能在較少的進(jìn)化代數(shù)下找到較優(yōu)解，能較好地避免陷入局部最優(yōu)解，可有效解決組合電路的設(shè)計(jì)問題。

參考文獻(xiàn)：

[1]趙曙光，劉貴喜，楊萬海.可進(jìn)化硬件的基本原理與關(guān)鍵技術(shù)[J].系統(tǒng)工程與電子技術(shù)，2002，24(1):70-75.

[2]LIU Rui， ZENG Sang-you. An efficient multi-objective evolutionary algorithm for combinational circuit design[C]//Proc of the 1st NASA/ESA Conference on Adaptive Hardware and Systems. 2006:215-221.

[3]NEDJAH N， De MOURELLE L M. A comparison of two circuit representations for evolutionary digital circuit design[J]. IEA/AIE， 2004，3029:594-604.

[4]DAI Yong-shou， LI Yuan-yuan. Adaptive immune-genetic algorithm for global optimization to multivariable function[J]. Journal of Systems Engineering and Electronics， 2007，18(3): 655-660.

[5]ZHAO Shu-guang， JIAO Li-cheng. Multi-objective evolutionary design and knowledge discovery of logic circuits based on an adaptive genetic algorithm[J]. Genetic Programming and Evolvable Machines， 2006，7(3): 195-210.

[6]SRINIVAS M， PATNAIK L M. Adaptive probabilties of crossover and mutation in genetic algorithm[J]. IEEE Trans on Systems Man and Cybernetics， 1994，24(4):656-667.

[7]COELLO C A ， Avan VELDHUIZEN D， LAMOUT G B. Evolutio-nary algorithms for solving multi-objective problems[M]. New York:Kluwer Academic Publishers， 2002.

[8]張義國，羅文堅(jiān)，王熙法. 基于免疫原理的邏輯電路設(shè)計(jì)算法[J].計(jì)算機(jī)工程與應(yīng)用，2006，11(1):38-40.