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

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

(1. 河北農(nóng)業(yè)大學(xué) 河北省農(nóng)業(yè)大數(shù)據(jù)重點實驗室, 保定 071001; 2. 泰安市婦幼保健院 信息管理科, 泰安 271000;3. 北京航空航天大學(xué) 高性能計算平臺, 北京 100083; 4. 北京航空航天大學(xué) 軟件學(xué)院, 北京 100083;5. 北京航空航天大學(xué) 計算機學(xué)院, 北京 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個固定極性,對應(yīng)2n個繁簡程度不同的固定極性RM(FPRM)展開式。 基于XNOR/OR 的FPRM 電路極性優(yōu)化即是在所屬極性空間中搜索一個最優(yōu)極性,使其電路目標(biāo)函數(shù)值最優(yōu)。 小規(guī)模電路一般采用窮盡搜索策略,通過對電路全部極性的評估和比較獲得最佳極性。 中大規(guī)模電路的極性優(yōu)化通常采用智能優(yōu)化算法,以便在可接受時間范圍內(nèi)獲得問題的最優(yōu)解。

2002 年,細(xì)菌覓食算法(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ù)制和遷徙操作,自適應(yīng)步長機制、群體感應(yīng)機制,以及與其他啟發(fā)式算法融合等。 Supriyono 和Tokhi[2]提出了基于各類數(shù)學(xué)函數(shù)的3 個不同的自適應(yīng)步長BFA 模型。 Majhi 等[3]用BFO 和ABFO 通過最小化均方差對基于模型的自適應(yīng)線性組合的連接權(quán)重進行優(yōu)化。 Treaty 和Mishap[4]根據(jù)各類問題,改進適應(yīng)度函數(shù),設(shè)計出了基于改進適應(yīng)度函數(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]提出了一種具有自適應(yīng)消除和分散概率的BFA,以提高參數(shù)的收斂速度。 Liu 等[10]將混合策略引入到BFA 中,避免了冗余的本地搜索。 李珺[11]在BFA 中改變了算法的復(fù)制和遷徙規(guī)則,在復(fù)制操作中,對個體優(yōu)秀程度的評價可以僅依據(jù)細(xì)菌個體當(dāng)前的適應(yīng)度值來進行,在遷徙操作中,遷徙操作的作用范圍不再是整個群體,而是排在后面的適應(yīng)度值較差的那部分個體。 Hu 等[12]提出了一種改進的多模態(tài)BFA。 在現(xiàn)有的研究中,對BFA 的改進大多是針對趨化步長,在游動、復(fù)制遷徙操作方面改進較少。

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

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個固定極性,對應(yīng)2n個復(fù)雜度不同的FPRM 展開式。

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

由式(1)可知, 基于XNOR/OR 的FPRM 電路展開式由多輸入XNOR 操作和多輸入OR 操作組成,因此,電路面積大小可以用XNOR 和OR兩操作的項數(shù)之和來表示。 由于邏輯運算的輸入輸出關(guān)系復(fù)雜,在面積計算前需要將多輸入邏輯運算分解成二輸入運算,此時,電路的面積則為二輸入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ù)學(xué)模型,可得XNOR 項和OR 項的總數(shù)為15,即電路面積為15。

2 二進制自適應(yīng)細(xì)菌覓食算法

2.1 細(xì)菌覓食算法

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

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

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

2.2 細(xì)菌覓食算法的分析及改進

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

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

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

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

2.2.1Pc和Pm自適應(yīng)變化

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

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

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

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

式中:Fmin為當(dāng)代群體的最小適應(yīng)度值。 經(jīng)過歸一化處理后,Fc和Fm的基本論域均變?yōu)?0,1)。其模糊量以Ac和Am表示,根據(jù)算法進化實際情況,將兩輸入的語言值均取為3 個:大(B)、中(C)、小(S)。 將兩輸出的變量對應(yīng)的模糊量為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),其對應(yīng)的語言值分別為S 和B,再根據(jù)表1 和表2,查詢對應(yīng)的兩輸出的變量Pc和Pm分別為VP 和VS,設(shè)定的VP 和VS 清晰化的值分別為0.9 和0.1,得出復(fù)制概率為0.9,遷徙概率為0.1。

2.2.2 趨化操作改進

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

圖2 細(xì)菌趨化半徑Fig.2 Bacterial chemotactic radius

2.2.3 算法描述

輸出最優(yōu)解。

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

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

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

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

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

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

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

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

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

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

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

步驟8 遷徙之后返回步驟2 繼續(xù)執(zhí)行趨化操作,即每進行一次復(fù)制操作細(xì)菌就要再次進行趨化操作,每進行一次遷徙操作細(xì)菌就要再次進行復(fù)制和趨化操作,直到達到最大遷徙次數(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 基準(zhǔn)電路。

為了驗證BABFA 的性能及其在固定極性XNOR/OR 電路面積優(yōu)化上的優(yōu)越性,實驗將BABFA 與傳統(tǒng)遺傳算法(TGA)、傳統(tǒng)細(xì)菌覓食算法(TBFA)、文獻[11]所提改進的細(xì)菌覓食算法(IBFA)進行比較。 4 種算法的迭代次數(shù)均設(shè)定為100,復(fù)制和遷徙次數(shù)均設(shè)定為10,種群規(guī)模設(shè)為8。 從MCNC 基準(zhǔn)電路測試集中隨機選取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)化曲線,縱坐標(biāo)為運行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é) 論

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

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

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

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