新穎的基于遺傳算法的數(shù)字電路的多目標優(yōu)化設計

(河南財經(jīng)政法大學計算機與信息工程學院，河南鄭州，450046)

新穎的基于遺傳算法的數(shù)字電路的多目標優(yōu)化設計

鮑治國,盧照敢

(河南財經(jīng)政法大學計算機與信息工程學院，河南鄭州，450046)

針對基于遺傳算法的數(shù)字電路的多目標優(yōu)化設計問題，采用了帶有均勻交叉的遺傳算法,并且考慮到了多種制約條件,如：電路的復雜度,功耗,信號延遲等。結(jié)果電路的正確性，構(gòu)成的復雜度，功耗和信號延遲等指標，可以采用適應度函數(shù)來評價。通過自動生出2位全加器的實驗,驗證了這種方法的有效性。實驗結(jié)果證明,新提出的方法,在最優(yōu)適應度函數(shù)值和平均適應度函數(shù)值方面,優(yōu)于傳統(tǒng)的遺傳算法。

進化算法；遺傳算法；均勻交叉；進化硬件；電路設計；多目標優(yōu)化

0 引言

在人工智能領域，進化算法（Evolutionary Algorithm,EA）是一種常用的以種群為基礎的啟發(fā)式算法。遺傳算法(Genetic Algorithm,GA)是一種典型的進化算法。

進化硬件(Evolvable Hardware,EHW)是進化算法的應用之一。進化硬件可以作為硬件設計的一種選擇。通過進化算法可以自動的生成電路，進化硬件看上去很成功，也很有前景。然而，進化硬件用于設計實際的電路時，還存在著一些問題，如：可擴展性，可維護性和通用性等。一些研究者對進化速度進行了探討，一些研究者對編碼方法進行了探討。電路的多目標優(yōu)化設計，也是一個尚待解決的問題。

本文提出的電路優(yōu)化設計方法，考慮到了電路的復雜度，功耗和信號延遲等，實現(xiàn)了電路的多目標優(yōu)化設計。不同的邏輯門，有不同的復雜度，功耗和信號延遲。在新的半導體技術(shù)中，連線的功耗和信號延遲，也不能被忽略，也要考慮進來。遺傳算法通過交叉變異等操作，可以改變電路中一些邏輯門的功能和連線方式；通過適應度函數(shù)，可以評價結(jié)果電路的正確性和優(yōu)化度。因此，遺傳算法通過進化可以找到構(gòu)造簡單，連線較短，功能正確的目標電路。用這種方法，自動生成了2位全加器的設計電路，對提出算法的有效性進行了驗證。

1 帶有均勻交叉的遺傳算法

遺傳算法是一種廣泛使用的搜索技術(shù)，對于搜索問題和優(yōu)化問題，常用于尋找最優(yōu)解或者次優(yōu)解。遺傳算法從一些個體組成的種群中開始搜索。在種群的初始狀態(tài),每個個體都是隨機產(chǎn)生的。在進化階段,用適應度函數(shù)來評價每個個體符合要求的程度。每代的最優(yōu)個體被保留下來；此外,通過選擇,交叉和變異等操作,產(chǎn)生一些新的個體。因此,將使種群像自然進化一樣,后生代種群比前代更加適應于環(huán)境的要求。

遺傳算法中起重要作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以提高。

參數(shù)化均勻交叉是用比賽選擇法選出兩個父代個體，以某個概率選出一些基因進行替換重組，重組后新的個體作為下一代的個體。參數(shù)化均勻交叉可以在較大的空間內(nèi),以比較公平的方式發(fā)揮作用,可以增強個體的多樣性，會有更強的全局搜索能力，因而，更有可能找到較好的方案。

2 基于遺傳算法的電路優(yōu)化設計

2.1 目標

在電路的優(yōu)化設計中，通過應用新穎的遺傳算法，找到較優(yōu)化的解決方案。目標電路提供符合要求的功能行為，并且需要較少的復雜度，更低的功耗和更少的信號延遲。實驗中，用2位全加器作為實例，介紹了遺傳算法如何自動生成目標電路。

2.2 遺傳編碼

為了方便的處理遺傳編碼，目標電路被看作是一個兩維的邏輯門陣列，如圖1所示。每個邏輯門，有兩個輸入，一個輸出。第一列邏輯門的輸入，來自基本輸入；以后各列邏輯門的輸入，來自前面各列邏輯門的輸出。可以用一串數(shù)字作為一個染色體表示一個電路。每三個數(shù)字表示一個邏輯門，如：

(輸入1， 輸入2，函數(shù)功能)。

一個染色體可以是一串數(shù)字,如:

這里，xi是((now_columns)*(number_of_rows) - 1)，now_columns是邏輯門所在的當前列，取值范圍是[1,5]；number_of_rows是邏輯門陣列的行數(shù)，值為5。當xi＜=4時，輸入是基本輸入；當xi＞=5時，輸入是邏輯門xi的輸出。函數(shù)的功能編碼如表1所示。

2.3 適應度函數(shù)

適應度函數(shù)的目標是得到功能正確的電路，并且在電路構(gòu)成的復雜度，功耗和信號延遲方面盡量優(yōu)化。函數(shù)F1被用作評價結(jié)果電路輸出的正確性，函數(shù)F2被用作結(jié)果電路在構(gòu)成的復雜度，功耗和信號延遲方面的評價。

如表1所示，在電路構(gòu)成的復雜度，功耗和信號延遲方面，不同的邏輯門被指定不同的評價值。復雜度的設定，考慮了邏輯門用到的晶體管的數(shù)量，也可以理解為晶體管的數(shù)目，或者邏輯門的面積。如圖1所示，每個邏輯門的輸入和輸出被指定不同的坐標，便于計算電路中連線的長度。

num_testdata 是測試數(shù)據(jù)的數(shù)量，num_rightout是結(jié)果電路的正確輸出結(jié)果的數(shù)量。

Ev: 電路的復雜度，功耗，信號延遲的綜合評價值。Tmax:固定的大于Ev的數(shù)，實驗中被設定為1.5*1010。

Cg: 結(jié)果電路中所有邏輯門的復雜度的評價值。αcg: 邏輯門復雜度的權(quán)重。cgi:邏輯門i的復雜度。

Pg: 結(jié)果電路中所有邏輯門的功耗評價值。αpg: 邏輯門功耗的權(quán)重。pgi: 邏輯門i的功耗的評價值。

SD: 結(jié)果電路的信號延遲的評價值。αsd: 信號延遲的權(quán)重。sdouti: 邏輯門i輸出處的信號延遲。sdgi: 邏輯門i自身的信號延遲。sdw(i,inx): 連接到邏輯門i的輸入inx的連線的信號延遲。sdout(i,inx): 連接到邏輯門i的輸入端inx的邏輯門的輸出端的信號延遲。sdwj: 連線j的信號延遲。xbwj:連線j的開始端點的X坐標。ybwj: 連線j的開始端點的Y坐標。xewj: 連線j的結(jié)束端點的X坐標。yewj: 連線j的結(jié)束端點的Y坐標。βsdw: 連線的信號延遲的系數(shù)，實驗中被設定為1。

Pw: 結(jié)果電路中所有連線的功耗。αpw: 連線功耗的權(quán)重。pwj: 連線j的功耗。βpw: 連線的功耗的系數(shù)，實驗中被設定為1。

N: 結(jié)果電路中邏輯門的數(shù)量。

在計算式2中，評價項目的優(yōu)先順序是:Cg＞Pg＞S D＞Pw。在這個實驗中，αcg被指定為 1*108,αpg 被指定為1*106, αsd被指定為 1*103, αpw 被指定為 1.

函數(shù)F1被用作評價結(jié)果電路輸出的正確性，函數(shù)F2被用作結(jié)果電路在構(gòu)成的復雜度，功耗和信號延遲方面的評價。當結(jié)果電路不完全正確時(F1＜100)，主要關(guān)注電路的正確性；當結(jié)果電路正確時(F1=100)，主要關(guān)注電路的優(yōu)化度。

表2 進化參數(shù)的設置Table 2 Conditions for evolution

3 實驗和分析

實驗是為了驗證新穎的遺傳算法在電路優(yōu)化設計方面的有效性。遺傳算法用到的遺傳參數(shù)的設置如表2所示。為了確定適合這個實驗的參數(shù),做了一些前期的實驗。

實驗是在Eclipse SDK 3.5.1環(huán)境下用Java Runtime Environment 1.6.0實現(xiàn)的；測試是在個人電腦上完成的，Inter(R) Core(TM)2 的內(nèi)核，主頻 2.67G 赫茲，2G 的內(nèi)存。

實驗中對于遺傳算法采用不同的交叉方法進行了對比，實驗結(jié)果如表3所示。對于每種方法，都是獨立運行了30次。“best”: 30次結(jié)果中最好的適應度值。“quality”: 最優(yōu)的結(jié)果中相對于一點交叉的優(yōu)化度。“average”: 最優(yōu)的5次結(jié)果中平均的適應度值。“var”:正確的結(jié)果中適應度值的樣本方差。“quantity”: 30次運行結(jié)果中最終結(jié)果正確的運行次數(shù)。“time”: 30次運行的平均運行時間。

從實驗結(jié)果可以看出，在最優(yōu)適應度值，最優(yōu)的5次適應度值的平均值方面，均勻交叉優(yōu)于一點交叉。

適應度函數(shù)值為162.44的結(jié)果電路如圖2所示。圖2對應的結(jié)果電路，輸出結(jié)果正確，使用的邏輯門較少，功耗和信號延遲較少，因此，對應的評價值較高。

4 結(jié)束語

本文提出了一種基于遺傳算法的新型電路優(yōu)化設計的方法，除了考慮到結(jié)果電路的輸出正確性外，還考慮到電路構(gòu)成的復雜度，功耗和信號延遲等。在適應度函數(shù)中，首先考慮到了輸出結(jié)果的正確性，其次考慮到了優(yōu)化度。通過遺傳算法的進化，可以找到較優(yōu)化的結(jié)果電路。從實驗結(jié)果可以證明，采用均勻交叉的算法可以找到較優(yōu)化的電路。

這種方法也可以被用到規(guī)模較大的電路上。另外，在評價值的設定上，可以更加接近實際值。

[1] T.Schnier and Xin Yao.Using multiple representations in evolutionary algorithms [C].Proc.of the 2000 Congress on EvolutionaryComputation,La Jolla,CA,2000: 479–486.

[2] J.H.Holland.Adaptation in Natural and Artificial systems[M].The University of Michigan Press, 1975.

[3] 柏磊.數(shù)字電路進化設計算法研究（D）.博士，南京理工大學，2012.

[4] 楊華秋.可進化硬件平臺研究(D).碩士，復旦大學，2011.

[5] 姜慶輝.演化硬件技術(shù)研究(D).碩士，中國科學院研究生院(西安光學精密機械研究所)，2011.

[6] X.Yao and T.Higuchi.Promises and Challenges of Evolvable Hardware[J].IEEE Trans.on Systems, Man,and Cybernetics,Part C:Applications and Reviews,1999, 29(1): 87-97.

[7] Z.Bao and T.Watanabe.A Novel Genetic Algorithm with Cell Crossover for Circuit Design Optimization [C].Proc.of the IEEE International Symposium on Circuits and Systems(ISCAS 2009),Taipei,Taiwan, 2009:2982-2985.

[8] 柏磊，顧陳，嚴璐，等.基于適應度評價擴展自適應遺傳算法的門級電路進化設計[J].南京理工大學學報，2011，35(2):240-244.

[9] 梁騰騰，鄧平科，林寶軍.可用于演化硬件的改進自適應遺傳算法研究[J].計算機工程與設計,2012,33(2):711-717.

[10] 王婷，蘭巨龍，鄔鈞霆.基于演化硬件的硬件重構(gòu)編碼方案及演化算法研究[J].通信學報,2012,33(8):35-41.

Multi objective optimization design of digital circuit based on genetic algorithm

Bao Zhiguo,Lu Zhaogan
(College of computer and information engineering,Henan University of Economics and Law,Zhengzhou, Henan,450046)

Aiming at the multi-objective optimization design of digital circuit based on genetic algorithm, a genetic algorithm with uniform crossover is adopted, and a variety of constraints are considered,such as the complexity of the circuit, power consumption, signal delay, etc.. Results the correctness of the circuit, the complexity, power consumption and signal delay and so on, can be used to evaluate the fitness function. The validity of this method is verified by the experiment of 2 full adder. Experimental results show that the new method is better than the traditional genetic algorithm in terms of optimal fitness function value and average fitness function value.

evolutionary algorithm;genetic algorithm;uniform crossover;evolutionary hardware;circuit design;multi objective optimization

教育部留學回國人員科研啟動基金資助項目(教外司留[2013]1792號)；河南省基礎與前沿技術(shù)研究計劃項目（132300410240,132102210140）；河南省教育廳科學技術(shù)研究重點項目（13B520903,12A510001）資助.

鮑治國,男,1977年生,博士,講師, CCF會員,主要研究方向:進化計算,進化硬件,多目標優(yōu)化;盧照敢,男,1977年生,博士,講師,主要研究方向:電路設計,無線通信.