基于BABFA 的XNOR/OR 電路面積優(yōu)化

周宇豪 何振學 梁新藝 范新超 霍志勝 肖利民

(1. 河北農(nóng)業(yè)大學 河北省農(nóng)業(yè)大數(shù)據(jù)重點實驗室, 保定 071001; 2. 泰安市婦幼保健院 信息管理科, 泰安 271000;3. 北京航空航天大學 高性能計算平臺, 北京 100083; 4. 北京航空航天大學 軟件學院, 北京 100083;5. 北京航空航天大學 計算機學院, 北京 100083)

邏輯電路展開式越精練,電路實現(xiàn)就越簡單,所需要的門電路就越少,電路的面積、功耗也就具有顯著優(yōu)勢。 數(shù)字邏輯電路既可以由基于AND/OR/NOT 的Boolean 邏輯實現(xiàn),也可以由基于XNOR/OR 或XOR/AND 的Reed-Muller(RM)邏輯實現(xiàn)。 對部分電路來說,與Boolean 邏輯相比,RM 邏輯實現(xiàn)的電路形式具有更簡潔的結(jié)構(gòu)、更小的面積和功耗,以及更好的可靠性。 此外,與基于XOR/AND 的表達式相比,基于XNOR/OR 的部分電路表達式更加簡潔。 因此,基于XNOR/OR 的RM 電路的綜合優(yōu)化正引起越來越多研究者的參與。

極性優(yōu)化是RM 電路綜合性能優(yōu)化的重要技術(shù)手段。 任意一個n變量的邏輯函數(shù)都具有2n個固定極性,對應2n個繁簡程度不同的固定極性RM(FPRM)展開式。 基于XNOR/OR 的FPRM 電路極性優(yōu)化即是在所屬極性空間中搜索一個最優(yōu)極性,使其電路目標函數(shù)值最優(yōu)。 小規(guī)模電路一般采用窮盡搜索策略,通過對電路全部極性的評估和比較獲得最佳極性。 中大規(guī)模電路的極性優(yōu)化通常采用智能優(yōu)化算法,以便在可接受時間范圍內(nèi)獲得問題的最優(yōu)解。

2002 年,細菌覓食算法(bacterial foraging algorithm,BFA)首先由Passino 教授[1]通過模擬人體腸道中大腸桿菌的覓食行為提出。 BFA 實現(xiàn)簡單,具有較好的全局尋優(yōu)性能,一經(jīng)提出,就受到國內(nèi)外研究者的廣泛關(guān)注。 到目前為止,研究者們已經(jīng)提出了一系列的BFA 的改進方案,這些改進的BFA 有效解決了現(xiàn)實世界中的一系列優(yōu)化問題。 在對BFA 的改進中,主要涉及復制和遷徙操作,自適應步長機制、群體感應機制,以及與其他啟發(fā)式算法融合等。 Supriyono 和Tokhi[2]提出了基于各類數(shù)學函數(shù)的3 個不同的自適應步長BFA 模型。 Majhi 等[3]用BFO 和ABFO 通過最小化均方差對基于模型的自適應線性組合的連接權(quán)重進行優(yōu)化。 Treaty 和Mishap[4]根據(jù)各類問題,改進適應度函數(shù),設(shè)計出了基于改進適應度函數(shù)的BFA。 Amaresh[5]利用BFA 結(jié)合數(shù)據(jù)處理分組法估計了保護農(nóng)場的最低能耗消耗指數(shù)。 Liu等[6]把BFA 改進為一個基于五階段的啟發(fā)式算法用在生產(chǎn)計劃中。 Cai 等[7]采用了啟發(fā)式混合BFA 來搜索最優(yōu)位姿。 Ye 等[8]將粒子群算法引入到改進的BFA 中,處理數(shù)據(jù)分類問題。 Zhang等[9]提出了一種具有自適應消除和分散概率的BFA,以提高參數(shù)的收斂速度。 Liu 等[10]將混合策略引入到BFA 中,避免了冗余的本地搜索。 李珺[11]在BFA 中改變了算法的復制和遷徙規(guī)則,在復制操作中,對個體優(yōu)秀程度的評價可以僅依據(jù)細菌個體當前的適應度值來進行,在遷徙操作中,遷徙操作的作用范圍不再是整個群體,而是排在后面的適應度值較差的那部分個體。 Hu 等[12]提出了一種改進的多模態(tài)BFA。 在現(xiàn)有的研究中,對BFA 的改進大多是針對趨化步長,在游動、復制遷徙操作方面改進較少。

本文提出了一種基于XNOR/OR 的FPRM 電路面積優(yōu)化方法,利用提出的二進制自適應BFA(BABFA)搜索對應電路面積最小的最佳極性,驗證了該方法的有效性。

1 基于XNOR/OR 的FPRM 電路面積優(yōu)化理論基礎(chǔ)

1.1 XNOR/OR 電路表達式

任意n變量的邏輯函數(shù)都可以由基于XNOR/OR 的FPRM 展開式表示,即

式中:k∈{0,1,…,n-1};dj∈{0,1},dj=0 表示sj項在表達式中出現(xiàn),dj=1 表示該項不在表達式中出現(xiàn)。 在固定極性XNOR/OR 展開式中,每個變量只能以原變量或反變量2 種形式中的一種出現(xiàn),不能同時以原變量和反變量的形式出現(xiàn)。 極性表示變量出現(xiàn)的形式,即極性0 表示變量以原變量形式出現(xiàn),極性1 表示變量以反變量形式出現(xiàn)。 因此,任意n個變量的邏輯函數(shù)都有2n個固定極性,對應2n個復雜度不同的FPRM 展開式。

1.2 電路面積優(yōu)化數(shù)學模型

由式(1)可知, 基于XNOR/OR 的FPRM 電路展開式由多輸入XNOR 操作和多輸入OR 操作組成,因此,電路面積大小可以用XNOR 和OR兩操作的項數(shù)之和來表示。 由于邏輯運算的輸入輸出關(guān)系復雜,在面積計算前需要將多輸入邏輯運算分解成二輸入運算,此時,電路的面積則為二輸入XNOR 門及二輸入OR 門的和。

由式(1)和式(2)可得,多輸入OR 門si分解為mi個二輸入OR 操作,則有

例如,1 個四變量固定極性XNOR/OR 表達式為f=☉∏(0,1,3,7,8,12,15),假設(shè)4 個輸入變量分別為x3、x2、x1、x0,極性的二進制形式為0110,即變量x1和x2在表達式中以反變量的形式來表示,而變量x0和x3在表達式中以原變量的形式表示。 該函數(shù)可表示為

式中:ˉx2表示反變量;“☉”表示XNOR(同或)。

根據(jù)上述電路面積數(shù)學模型,可得XNOR 項和OR 項的總數(shù)為15,即電路面積為15。

2 二進制自適應細菌覓食算法

2.1 細菌覓食算法

BFA 主要通過趨向性操作、復制操作和遷徙操作的迭代計算來搜索問題的最優(yōu)解。 算法流程如圖1所示。

圖1 細菌覓食算法流程Fig.1 Flow chart of bacterial foraging algorithm

BFA 主要通過趨化操作更新細菌個體的位置進行尋優(yōu),通過復制操作加速算法的收斂速度,并利用遷徙操作防止算法陷入局部最優(yōu)。 在趨化操作中,其主要步驟為游動和旋轉(zhuǎn)。 在進行趨化操作時,細菌會隨機產(chǎn)生一個方向,再進行移動,如果該方向上的適應度更好,則細菌發(fā)生游動,否則,細菌繼續(xù)停留在原地。 此外,從圖1 還可以看出,細菌群體每進行一次復制操作,就會進行最大次數(shù)的趨化操作,這就等價于種群的不斷迭代過程,而細菌的趨化操作就是不停地尋找最優(yōu)解的過程。 因此,BFA 往往迭代一次就能夠快速找到最優(yōu)解。 當達到最大復制次數(shù)時,根據(jù)遷移概率進行遷移操作,每進行一次遷移操作,細菌就要再次進行復制操作和趨化操作,直到達到最大遷移次數(shù),跳出循環(huán)。

2.2 細菌覓食算法的分析及改進

傳統(tǒng)BFA 在整個進化過程中對復制環(huán)節(jié)采用的是將個體在上一次趨向性操作循環(huán)中取得的所有適應度值求和,得到個體當前的健康度。 按照細菌個體的健康度,對整個菌群進行排序,健康度越高的個體,排序后位置越靠前。 根據(jù)優(yōu)勝劣汰法則,將排序后健康度較差的一半細菌個體淘汰,剩余的一半健康度較好的細菌個體進行自我復制,這會大大降低種群的多樣性。 因此,結(jié)合遺傳算法的交叉概率的思想,對復制操作添加一個復制概率Pc,以增加下一代種群的多樣性。 同遷移率一起用模糊控制規(guī)則來確定。

傳統(tǒng)BFA 采取固定的遷徙概率,限制了算法的尋優(yōu)能力和效率。 但是,怎樣在算法進化過程中對遷徙概率Pm采取自適應的變化是一個相對復雜的問題,用數(shù)學公式形式化描述相對困難,而基于模糊規(guī)則的參數(shù)選擇法是解決此類問題的一種有效方法。 不同于傳統(tǒng)的求解自適應概率,基于模糊規(guī)則的二進制自適應采用查詢表的方式,在實際應用中,大大縮短了求解傳統(tǒng)自適應概率所需參數(shù)所浪費的時間,具有更快的收斂速度。

自從Zandeh 在1965 年提出模糊集合的理念后,基于模糊集合理論的模糊控制開始迅速發(fā)展,研究者們把模糊控制思想引入到遺傳算法、粒子群算法等眾多智能優(yōu)化算法中,如提出模糊遺傳算法(FGA)以改善算法的優(yōu)化效果,并提高算法的收斂速度。 鄧莉和魯瑞華[13]所提的模糊遺傳算法中,將具有不確定性概念的交易時間采用模糊集理論來描述。 李擎等[14]將輸入變量Pc和Pm做了歸一化處理,改進了算法的適用范圍,但在迭代過程中,該方法需要對交叉和待變異個體分別計算交叉概率和變異概率,增加了程序的運行時間。 張會紅等[15]克服了上述缺陷,簡化了歸一化處理,但是還需要分別計算清晰化后的交叉概率和變異概率。

本文提出BABFA,Pc和Pm的值能隨著迭代的進行而自適應地變化,并采用查詢表的方式進行選擇。 這種有自組織性能的BFA 將具有更高的魯棒性、全局最優(yōu)性和更快的收斂速度。

2.2.1Pc和Pm自適應變化

Pc和Pm的確定頻率設(shè)定為每代1 次,設(shè)Fmax和Fave分別表示當代群體的最大適應度值和平均適應度值,Fng表示最大適應度值未進化代數(shù),即當前的最佳適應度值經(jīng)歷了多少次迭代依舊未找到比當前更優(yōu)秀的適應度值。 對Pc和Pm確定的基本控制思想如下:

1) 若Fmax-Fave較小,說明算法在當前適應度極值附近迭代趨于成熟,應減小Pc,增大Pm;若Fmax-Fave較大,說明算法處于正常進化趨勢,Pc和Pm可取正常值。

2) 若Fng較小,說明算法處于正常進化趨勢,Pc和Pm可取正常值;反之,說明算法有局部收斂趨勢,應減小Pc,增大Pm。

為此,需要有模糊控制器的輸入量,并將兩輸入量做如下歸一化處理:

式中:Fmin為當代群體的最小適應度值。 經(jīng)過歸一化處理后,Fc和Fm的基本論域均變?yōu)?0,1)。其模糊量以Ac和Am表示,根據(jù)算法進化實際情況,將兩輸入的語言值均取為3 個:大(B)、中(C)、小(S)。 將兩輸出的變量對應的模糊量為Pc和Pm,其模糊量以DC 和DM 表示,定義其詞集為T(DC) =T(DM) = {VS,S,C,P,VP},本文對DC 和DM 的清晰化的值均為{0.1,0. 3,0.5,0.7,0.9},其中,VS 為非常小,S 為小,C 為中等,P 為大,VP 為非常大。

根據(jù)上文所述模糊理論的基本控制思想,對Pc和Pm分別建立了9 條模糊控制規(guī)則,具體如表1和表2 所示。

表1 Pc 模糊控制表Table 1 Pc Fuzzy control table

表2 Pm 模糊控制表Table 2 Pm Fuzzy control table

將DC 和DM、Ac和Am清晰化后再利用查詢表的方式得到Pc和Pm的值。 本文對Ac和Am清晰化具體值如下:

例如,從式(8)和式(9)得出Fc和Fm分別為0.4 和8。 根據(jù)式(10)和式(11),其對應的語言值分別為S 和B,再根據(jù)表1 和表2,查詢對應的兩輸出的變量Pc和Pm分別為VP 和VS,設(shè)定的VP 和VS 清晰化的值分別為0.9 和0.1,得出復制概率為0.9,遷徙概率為0.1。

2.2.2 趨化操作改進

BFA 模擬了大腸桿菌的覓食操作,大腸桿菌全身長滿了鞭毛,它們在覓食過程中通過鞭毛的轉(zhuǎn)動來搜索富含營養(yǎng)物質(zhì)的區(qū)域,并向之翻轉(zhuǎn)和游動,把翻轉(zhuǎn)和游動統(tǒng)稱為趨向性操作。 趨向性操作是BFA 的核心操作。 如圖2 所示,BABFA在趨向性操作中使細菌在鄰域搜索,即使細菌在自己的最大半徑范圍內(nèi)搜索,最大半徑看作是細菌游動最大次數(shù),其中,箭頭表示翻轉(zhuǎn)和前進方向。 無需再計算其他細菌對自己的影響,增強了細菌的局部搜索能力,提高了BFA 的尋優(yōu)能力。

圖2 細菌趨化半徑Fig.2 Bacterial chemotactic radius

2.2.3 算法描述

輸出最優(yōu)解。

首先,初始化種群和各項參數(shù),Nc為細菌最多翻轉(zhuǎn)的方向次數(shù),Nre為細菌種群最大復制次數(shù),Ned為細菌種群最大遷徙次數(shù)。 其次,細菌開始進行趨化操作。 然后,在當前方向進行設(shè)定的最大前進次數(shù)的搜索,得到每一次搜索的適應度值,同時保存最大適應度值和最小適應度值,直到達到最大翻轉(zhuǎn)方向的次數(shù)。 當所有細菌個體進行完翻轉(zhuǎn)操作之后,計算出平均適應度值和最大適應度值未進化代數(shù),為復制操作提供參數(shù),得到種群的復制概率。 最后,選擇性地把適應度好的個體復制給適應度差的個體,在進行完復制操作之后,重復之前的趨化操作,直至重復到最大復制次數(shù)之后,進行一次遷徙操作,直到滿足最大遷徙次數(shù)。

3 基于XNOR/OR 的FPRM 電路面積優(yōu)化

固定極性XNOR/OR 電路面積優(yōu)化是典型的組合優(yōu)化問題。 小規(guī)模電路面積優(yōu)化可采取窮舉策略實現(xiàn)。 當電路輸入變量增大時,采用窮舉搜索策略將難以在較短時間內(nèi)獲得問題的滿意解。因此,本文提出一種基于XNOR/OR 的FPRM 電路面積優(yōu)化方法,該方法利用提出的BABFA 來搜索對應電路面積最小的最佳極性,從而實現(xiàn)電路面積優(yōu)化。 如圖3 所示,在BABFA 中,對極性進行二進制編碼,算法在進化搜索中基于個體的適應度和電路面積數(shù)學模型來進行搜索,其面積優(yōu)化步驟描述如下:

圖3 FPRM 電路面積優(yōu)化流程Fig.3 Flow chart of FPRM circuits area optimization

步驟1 讀入電路,初始化細菌種群規(guī)模、趨向性翻轉(zhuǎn)操作次數(shù)、游動次數(shù)、復制操作次數(shù)、遷徙操作次數(shù)等進化參數(shù),并根據(jù)適應度函數(shù),計算出初始種群的適應度值。

步驟2 細菌開始趨化操作,即進行翻轉(zhuǎn)和前進。

步驟3 細菌進行完最大翻轉(zhuǎn)次數(shù)后,得出最大、最小及平均適應度值,以及當前最大適應度值未進化代數(shù),即當前的最佳適應度值經(jīng)歷了多少次迭代依舊未找到比當前值更高的適應度值。

步驟4 得到各類模糊規(guī)則所需要的參數(shù),并采用查詢表的方式為復制操作和遷徙操作提供概率值。

步驟5 對細菌的適應度值進行評價并按照升序排列。 將前面N/2 個細菌個體的位置按照概率復制給排列在后面的N/2 個細菌個體。

步驟6 復制之后返回步驟2 繼續(xù)執(zhí)行趨化操作,直到達到最大復制次數(shù)。

步驟7 復制操作達到最大次數(shù)后,進行種群的遷徙操作,按照遷徙概率對種群進行遷徙操作,即對細菌個體的長度,隨機產(chǎn)生一個遷徙位置,將0 變?yōu)?,或者1 變?yōu)?。

步驟8 遷徙之后返回步驟2 繼續(xù)執(zhí)行趨化操作,即每進行一次復制操作細菌就要再次進行趨化操作,每進行一次遷徙操作細菌就要再次進行復制和趨化操作,直到達到最大遷徙次數(shù)。

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

本文算法均用C 語言實現(xiàn),在Windows 10 操作系統(tǒng)下,通過VS 2019 編譯,程序的硬件環(huán)境為Intel(R)Core(TM)i7-8750 CPU(2. 20 GHZ)8 GB RAM。 測試電路均采用PLA 格式MCNC 基準電路。

為了驗證BABFA 的性能及其在固定極性XNOR/OR 電路面積優(yōu)化上的優(yōu)越性,實驗將BABFA 與傳統(tǒng)遺傳算法(TGA)、傳統(tǒng)細菌覓食算法(TBFA)、文獻[11]所提改進的細菌覓食算法(IBFA)進行比較。 4 種算法的迭代次數(shù)均設(shè)定為100,復制和遷徙次數(shù)均設(shè)定為10,種群規(guī)模設(shè)為8。 從MCNC 基準電路測試集中隨機選取12 個電路作為實驗電路。 由于4 種算法都具有隨機性,實驗將每個算法在每個測試電路上運行10 次,并將實驗結(jié)果的最優(yōu)值和平均值作為實驗數(shù)據(jù)。

4.1 電路面積對比

4 種算法的電路面積優(yōu)化對比數(shù)據(jù)如表3 所示。 其中,best 表示10 次運行中求得的電路最小面積;average 表示10 次運行中求得的電路最小面積的平均值;save_best 中的save1 表示BABFA 與TGA 比較所節(jié)省的面積百分比,save2 表示BABFA與TBFA 比較所節(jié)省的面積百分比,save3 表示BABFA 與IBFA 比較所節(jié)省的面積百分比;save_average 中的save1 表示BABFA 與TGA 比較所節(jié)省的最小面積平均值百分比,save2 表示BABFA 與TBFA 比較所節(jié)省的最小面積平均值百分比,save3表示BABFA 與IBFA 比較所節(jié)省的最小面積平均值百分比。

由表3 可知,對于輸入變量數(shù)較小的電路來說,4 種算法獲得的最優(yōu)解相同,但BABFA 得到的最小面積的平均值要略優(yōu)于其他3 種算法。 對于輸入變量數(shù)較大的電路來說,BABFA 得到的最小面積優(yōu)于其他3 種算法,且平均值明顯優(yōu)于其他3 種算法。 分析可得,BABFA 比TGA 在面積上平均節(jié)省了11%;BABFA 比TBFA 在面積上平均節(jié)省了18%;BABFA 比IBFA 在面積上平均節(jié)省了15%。

表3 四種算法在面積優(yōu)化上的實驗結(jié)果Table 3 Experimental results of four algorithms on area optimization

4.2 優(yōu)化時間對比

將每個算法在每個測試電路上運行10 次,并將實驗結(jié)果的平均值作為實驗數(shù)據(jù)。 4 種算法的電路運行時間對比數(shù)據(jù)如表4 所示。 其中,save1_TGA 表示BABFA 與TGA 比較CPU 運行時間所節(jié)省的百分比,save2_TBFA 表示BABFA 與TBFA比較CPU 運行時間所節(jié)省的百分比,save3_IBFA表示BABFA 與IBFA 比較CPU 運行時間所節(jié)省的百分比。

由表4 可知,在輸入變量少的電路中,BABFA節(jié)省時間的百分比較小,但在輸入變量大的電路中,BABFA 節(jié)省時間的百分比非常明顯。 分析可得,BABFA 比TGA 在時間上平均節(jié)省了46%,BABFA 比TBFA 在時間上平均節(jié)省了36%,BABFA 比IBFA 在時間上平均節(jié)省了32%。

表4 四種算法在時間上的實驗結(jié)果Table 4 Experimental results of four algorithms on time

4.3 收斂性對比

為了更好地觀察BABFA 的搜索性能,將其中4 個測試電路在迭代過程中面積最優(yōu)解分別進行累加求平均,繪出面積性能優(yōu)化曲線,縱坐標為運行10 次測試電路面積的平均值,如圖4 ～圖7所示。 可以看出,相比于其他3 種算法,BABFA能夠在迭代次數(shù)最小的情況下,尋優(yōu)速度最快且找尋的面積最優(yōu)。

圖4 br2 電路最小面積優(yōu)化曲線Fig.4 Optimization curves of minimum area of br2 circuit

圖5 amd 電路最小面積優(yōu)化曲線Fig.5 Optimization curve of minimum area of amd circuit

圖6 table5 電路最小面積優(yōu)化曲線Fig.6 Optimization curve of minimum area of table5 circuit

圖7 bcc 電路最小面積優(yōu)化曲線Fig.7 Optimization curve of minimum area of bcc circuit

5 結(jié) 論

本文提出了一種二進制自適應細菌覓食算法(BABFA)用于求解基于XNOR/OR 的FPRM 電路面積優(yōu)化問題。 主要結(jié)論如下:

1) BABFA 用于求解二值變量的組合優(yōu)化問題。 BABFA 在復制操作中添加了復制概率,提高種群的多樣性,采用二進制自適應規(guī)則對復制率和遷移率進行修正,并且使細菌在半徑范圍內(nèi)進行搜索,替代細菌的群體感應機制中的斥力操作。

2) 提出基于XNOR/OR 的FPRM 電路面積優(yōu)化方法,使用BABFA 來搜索電路面積最小的FPRM 電路。 這是有效的將BFA 應用于RM 邏輯電路極性優(yōu)化。

3) 基于MCNC 測試電路的實驗結(jié)果表明,在電路邏輯優(yōu)化中,BABFA 相比較于其他3 種優(yōu)化算法,平均面積優(yōu)化率為15%,平均時間節(jié)省率為38%。