一位全加器優化設計算法的研究

羅文靜 范進高 會 丹 王娜娜 顏雪松

（中國地質大學（武漢）計算機學院，湖北武漢 430074）

電路優化技術是電路設計領域不可忽略的一個部分，電路優化能提高效率、降低能耗從而節約現實成本。近年來也出現越來越多的電路優化方法被運用到電路硬件設計領域。盡管如此，傳統電路優化技術仍然存在幾個方面的挑戰：（1）如何讓電路優化自動化；（2）設計平臺的可編程性（3）如何能在較短時間內達到理想優化結果；（4）如何減少電路器件門數。

一位加法器電路優化設計屬于電路硬件設計范疇，用傳統電路設計方法明顯達不到理想的結果。為了優化一位加法器設計，引入演化硬件技術（Evolvable Hardware，EHW ）。演化硬件技術是一種能夠被用來替代傳統電路設計的方法，用自可編程門陣列（Field Programmable Gate Arrays，FPGA）作為硬件演化平臺，能通過演化算法自動生成數字電路。

對于一位加法器硬件電路的算法設計與優化，我們采用改進遺傳算法（Modified Genetic Alogrothm，MGA）來設計組合數字電路。簡單的遺傳算法效率較差，我們通過引入跨世代精英機制和其他策略對簡單遺傳算法進行改進，設計了一種改進遺傳算法以提高演化效率。本文采用的編碼方式為矩陣單元三元組整數編碼，采用的個體評估策略為貪婪策略；設計各種不同的選擇、交叉、變異策略等其他算子，運用到各種算法中去。本文采用的算法策略以及優化方法對于設計數字濾波器、乘法器、多態數字電路等同樣適用。

1 算法編碼

1.1 矩陣單元三元組整數編碼

采用演化硬件技術自動設計數字電路，先要將電路表示成便于演化算法設計的編碼方式。該編碼方式依據硬件平臺Virtex－II系列FPGA的邏輯單元結構（見圖1）構建的。

圖1 可編程邏輯門陣列結構

經過下面的建模過程，體現基于FPGA電路設計自動化問題的可演化性，只與邏輯單元功能和其互聯關系相關。將已知的電路輸入作為邏輯單元矩陣的輸入資源，對于一個N輸入的邏輯電路，就有N個輸入資源，每一個單元都有自己的輸出。這樣矩陣單元可以成為其他單元的輸入，或者整個電路的輸出。對所有資源進行編號，以便表示整個電路單元的互連關系，作如下三元組模式的編碼：（Ai，Bi，Ci）。Ai表示將資源編號 Ai的輸出連接到邏輯單元的的第一個輸入，Bi表示將資源編號Bi的輸出連接到邏輯單元的第二個輸入，Ci用于標識邏輯單元的功能，Ci具體數字與其對應邏輯功能關系，見表1。

表1 染色體中的負數對應的邏輯門功能

引入連接度的方法來動態控制所有邏輯單元的輸入，實現動態的控制搜索空間。連接度是指：在矩陣單元Mmn（m表示矩陣的行數，n表示矩陣的列數）中，若某個單元Cij（表示該單元在矩陣的第i行、第j列）的輸入信號能與前k列單元的輸出信號相連，即在第j－k列——第j－1列位置上所有單元的輸出信號都能為該單元的輸入信號，則稱該單元Cij的連接度D為K.假設n為矩陣單元的總列數，nr和nc分別是矩陣的單元行數和列數。ni代表目標電路系統輸入數目，若第c列某單元的連接度為k；其中c∈［1，n］，定義 V（c）為整數v的集合，所以：

后面的列其連接度呈遞增趨勢，這樣通過控制k的值能夠縮小電路的搜索空間，提高演化效率。

擴展約束編碼規則即可避免染色體在個體初始化或變異時單元間連接形成回路，同時可動態調整單元的連接度，使得算法在運行時能動態調節單元的搜索空間，從而在某種程度上提高演化效率。

2 選擇策略

2.1 選擇輸出端邏輯單元

采用貪婪策略來確定電路的輸出單元，即根據給定電路功能的真值表，對于每一種電路輸入組合，將各矩陣單元輸出值與真值表各輸出值進行比較，若匹配則加1，這樣可構造出各矩陣單元對應各輸出端的匹配度；再針對每個輸出，我們分別選取匹配度最大的單元，將該單元作為該電路對應的輸出端。與盲目隨機選取輸出單元相比，貪婪策略能防止同一染色體因輸出單元選取的不同，使得它們的適應度評估值存在很大差異的缺陷，同時能更好的將有效個體電路保留下來，從而提高了演化效率。

2.2 確定每個邏輯單元的變異概率

首先將每個邏輯單元賦一個初始值P＿MUTATION。對于輸出端的變異概率，若某個輸出端已經正確輸出，則變異概率為0，否則輸出端概率為0.5＊P＿MUTATION。若相關聯邏輯單元的變異概率比該輸出單元小，則不變；否則，將輸出單元的變異概率賦給該邏輯單元。

3 遺傳操作

3.1 交叉操作

采用子電路交叉法。子電路交叉法是基于多目標技術，若將數字電路的每個輸出端信號單獨作為一個目標，一個多輸出數字電路的設計即為一個帶約束的多個目標優化問題。由于一個多輸出組合邏輯電路可分解為多個輸出端信號子電路，因此，一個多輸出組合邏輯電路可由所有單輸出端信號子電路構成。該文基于多目標與局部優化技術，提出子電路雜交策略。新個體電路的每個輸出端子電路產生規則為：根據兩父體電路中同一輸出端信號的功能評價值，選取較優的子電路作為新個體電路對應輸出端信號子電路，然后將新產生的所有輸出端信號子電路組合形成新個體電路。若某邏輯單元產生沖突，則直接用后續輸出單元的相關邏輯單元賦值。

3.2 變異操作

采用自適應變異。在三元組的三個位置中隨機產生一個變異位置和該位置的變異概率，若該變異概率小于該邏輯單元的初始變異概率，則變異。變異的原則是：隨機產生該位置滿足條件的值，直到不與原來的值相等。

3.3 個體保留策略

采用跨世代精英機制。上一代種群與通過交叉變異操作產生的新種群混合起來，從中按一定概率選擇較優的個體。具體操作過程如下：

第一步：將規模為N的當前種群P1通過交叉變異操作產生下一代子種群P2。

第二步：將當前種群P1和下一代子種群P2混合形成臨時種群。

第三步：對臨時種群按適應度值降序排序后，保留最優的N個個體形成新一代種群P1。

跨世代精英機制在健壯性和遺傳多樣性保持以及排序方法上都有著一定的特質，即使當交叉變異操作產生較劣個體偏多時，由于原種群大多數個體殘留，不會引起個體的評價值降低；由于大種群操作，可以更好地保持種群演化過程中的遺傳多樣性，最后它很好的克服了比列適應度計算的尺度問題。

4 實驗與分析

采用改進的遺傳算法進行一位加法器的優化設計，其實驗運行參數見表2（使用“與”門、“或”門和“非”門）。

表2 算法運行參數

在以上算法參數設置下，獨立運行算法5次，實驗結果統計如表3。

表3 5次實驗結果統計表

對表3實驗結果統計表進行分析，得出如表4實驗結果分析表。

表4 實驗結果分析表

實驗結果分析表明，進行5次實驗，設計最優電路的邏輯門數為9，設計有效電路的頻率達到100%，設計電路的平均邏輯門數為5。實驗數據說明電路演化優化設計能較好地用于一位加法器的演化優化設計。

5 結 語

將演化算法引入到硬件設計技術中，已經成為一門新興技術，引起許多學者的廣泛關注與深入研究。本文首先在人工設計電路的基礎上，引入基于硬件設計的演化算法。采用的是矩陣單元三元組整數編碼，編碼規則為擴展約束編碼規則，采用貪婪策略來確定電路的輸出單元，在產生新一代時，采用輪盤賭算法進行隨機選擇，交叉采用子電路交叉法，變異采用自適應變異，最后的最優個體保留機制采用跨世代精英機制。實驗結果表明，演化算法在電路優化設計上有效實用，在采用適當的算法的基礎上，能獲得比較優化的電路，這些電路可作為基本模塊用于設計更復雜的硬件系統，這將會在大型硬件系統設計中占據重要的地位。

1 .F.Miller，P.Thomson，and T.Fogarty.Designing Electronic Circuits Using Evolutionary Algorithms.Arithmetic Circuits：A Case Study，chapter 6，in Genetic Algorithms and Evolution Stategies in Engineering and Computer Science：Recent Advancements and Industrial Applications.Wiley Press，1997（November）：36－60.

2 Thompson A.Hardware Evolution：Automatic design of electronic circuits in reconfigurable hardware by artificial evolution.Doctoral thesis，University of Sussex，UK，1996.

3 Coello C Carlos A.An Empirical Study of Evolutionary Techniques for Multiobjective Optimization in Engineering Design，PhD thesis，Tulane University，New orleans，1996.

4 Kalganova T.Evolvable Hardware Design for Combinational Logic Circuits.PhD thesis，Napier University，Edinburgh，UK，2000.

5 Zebulum R S.Synthesis of Electronic Circuits Through Artificial Evolutionary Systems.PhD Thesis，Catholic University of Rio，Portuguese，1998.