基于M-AFSA 的MPRM 邏輯電路面積優(yōu)化

邵藝璇，何振學(xué)，*，周宇豪，霍志勝，肖利民，王翔

(1.河北農(nóng)業(yè)大學(xué) 河北省農(nóng)業(yè)大數(shù)據(jù)重點實驗室，保定 071001；2.河北農(nóng)業(yè)大學(xué) 信息科學(xué)與技術(shù)學(xué)院，保定 071001；3.北京航空航天大學(xué) 計算機學(xué)院，北京 100191；4.北京航空航天大學(xué) 電子信息工程學(xué)院，北京 100191)

數(shù)字邏輯電路既可以采用基于“與/或/非”運算的傳統(tǒng)布爾邏輯實現(xiàn)，也可以采用基于“與/異或”運算的Reed-Muller(RM)邏輯來實現(xiàn)?；凇芭c/異或”運算的RM 邏輯是區(qū)別于布爾邏輯的另一種電路表達方式。研究表明，與傳統(tǒng)的布爾邏輯電路相比，利用RM 邏輯實現(xiàn)部分電路(如運算電路、奇偶校驗電路等功能電路)具有更緊湊的結(jié)構(gòu)和良好的可測性[1-3]。RM 邏輯分為混合極性RM（mixed polarity Reed-Muller, MPRM）邏輯和固定極 性RM（fixedpolarity Reed-Muller，F(xiàn)PRM）邏 輯。其中，MPRM 邏輯表達式是RM 邏輯中常見的一種規(guī)范表達形式。對于輸入變量數(shù)為 n的Boolean 邏輯電路來說，具有2n個 固定極性，對應(yīng)有2n個不同F(xiàn)PRM表達式；具有 3n個 不同的混合極性，對應(yīng)有 3n個不同的MPRM 表達式。顯然，對于同一電路來說，MPRM 邏輯比FPRM 邏輯具有更大的優(yōu)化空間。

極性是RM 電路的重要屬性，決定著RM 電路表達式的繁簡，進而影響RM 電路的性能。MPRM電路面積優(yōu)化是在極性優(yōu)化空間中搜索對應(yīng)某一/組電路性能最好的最佳極性。因此，MPRM 電路面積優(yōu)化屬于組合優(yōu)化問題。對于中大規(guī)模MPRM 電路來說，其極性優(yōu)化空間隨輸入變量數(shù)的增加呈指數(shù)型增長，窮盡搜索法無法在有限的時間內(nèi)獲得最優(yōu)解。為滿足中大規(guī)模MPRM 邏輯電路快速、有效搜索最佳極性的需求，需結(jié)合并行搜索能力更強、優(yōu)化效率更高的智能優(yōu)化算法。

智能優(yōu)化算法在MPRM 電路面積優(yōu)化領(lǐng)域得到了廣泛應(yīng)用。文獻[4]將基于相異度的局部改善策略融入傳統(tǒng)遺傳算法，提出了一種基于混合遺傳算法的MPRM 最小化算法，以避免算法陷于局部最優(yōu)，增強了全局搜索能力。文獻[5]將模擬退火算法與粒子群算法相結(jié)合提出一種模擬退火離散粒子群優(yōu)化（simulated annealing and discrete particle swarm optimization , SADPSO)算法，基于該算法對MPRM 電路進行面積優(yōu)化。文獻[6]提出三值多樣性粒子群算法并應(yīng)用于MPRM 電路的綜合優(yōu)化，表現(xiàn)出了一定的性能優(yōu)勢。然而，由于受傳統(tǒng)智能優(yōu)化算法種群多樣性差、收斂速度慢、易陷入局部最優(yōu)等問題的影響，使得現(xiàn)有MPRM邏輯電路面積優(yōu)化方法的優(yōu)化效果有待提高。

人工魚群算法(artificial fish swarms algorithm,AFSA)是一種全新的群智能優(yōu)化算法，通過魚群中人工魚的覓食、聚群、追尾等行為以搜索全局最優(yōu)解,具有魯棒性強和全局尋優(yōu)能力強等優(yōu)點，在組合優(yōu)化領(lǐng)域得到了廣泛應(yīng)用[7-14]。研究表明，在求解NP-Hard 優(yōu)化問題上，人工魚群算法效果明顯優(yōu)于遺傳算法和粒子群算法[15-16]。

本文針對現(xiàn)有MPRM 電路面積優(yōu)化效果差的問題，提出一種有效的MPRM 邏輯電路面積優(yōu)化方法。與現(xiàn)有MPRM 電路面積優(yōu)化方法相比，主要貢獻如下：

1）提出一種多策略協(xié)同進化人工魚群算法（multi-strategies artificial fish swarms algorithm, MAFSA），以用于求解三變量組合優(yōu)化問題。該算法引入基于反向?qū)W習(xí)的種群初始化策略以提高了種群多樣性及初始種群解的質(zhì)量；引入提出覓食與追尾交互性策略，以加強人工魚個體之間的信息交流提高收斂速度；引入自適應(yīng)擾動策略，以增大算法進化后期人工魚位置變異的隨機性、避免陷入局部最優(yōu)、增強算法的全局尋優(yōu)能力。

2）提出一種MPRM 邏輯電路面積優(yōu)化方法，該方法利用提出的M-AFSA 算法搜索電路面積最小的最佳極性。

3）基于北卡羅萊納州微電子中心（Microelectronics Center of North Carolina, MCNC）Benchmark基準(zhǔn)測試電路，所提算法分別與基于遺傳算法（genetic algorithm，GA）的 面 積 優(yōu) 化 方 法、基 于AFSA 的面積優(yōu)化方法、文獻[4]所提的混合遺傳算法(hybrid genetic algorithm, HGA)及文獻[17]中煙花進化人工魚群算法（fireworks evolution AFSA,FEAFSA）的面積優(yōu)化方法進行了實驗對比，實驗結(jié)果驗證了所提算法的有效性。

一個輸入變量數(shù)為n 的MPRM 邏輯電路中，對應(yīng)的邏輯函數(shù)表達式具有 3n個不同的極性。若極性為 p，則該極性對應(yīng)的MPRM 邏輯電路表達式可表示為

極性是MPRM 電路的重要屬性，不同的極性對應(yīng)著不同的MPRM 電路表達式。因此，極性決定著MPRM 電路表達式的繁簡程度，進而影響MPRM電路的性能。

例1 以3 輸入變量的Boolean 表達式f(x0,x1,x2)=x0x1xˉ2+xˉ0x1xˉ2+xˉ0xˉ1x2為 例，其 對 應(yīng) 極 性 為6（三 進制表示為020）、11（三進制表示為102）和17（三進制表示為122）的MPRM 電路表達式分別為

1 相關(guān)知識

1.1 MPRM 邏輯表達式

可以明顯看出，不同極性對應(yīng)的MPRM 表達式的繁簡程度差別很大，其中，極性為17 的MPRM 電路表達式最簡潔，具有潛在的功耗和面積等性能優(yōu)勢。

1.2 人工魚群算法

人工魚群算法由浙江大學(xué)李曉磊和錢積新[18]于2003 年提出，是一種全新的群智能優(yōu)化算法。魚個體數(shù)目最多的地方一般就是本水域中富含營養(yǎng)物質(zhì)最多的地方，依據(jù)這一現(xiàn)象及魚的特性，模仿魚的覓食、聚群、追尾等行為，從而實現(xiàn)全局尋優(yōu)。人工魚的初始種群隨機生成，人工魚個體w=0,1,···,n-1；設(shè)種群規(guī)模為 popSize，pBest為個體最優(yōu)值，gBest為全局最優(yōu)值。人工魚群算法對應(yīng)的偽代碼如下所示，其中，AF_follow()表示追尾行為，AF_swarm()表示聚群行為，AF_prey()表示覓食行為。

1.2.1 覓食行為

式中：prey(a)為人工魚a 的覓食行為。

1.2.3 聚群行為

人工魚游動過程中，會自然聚集成群。設(shè)人工魚 Xc所在的位置是人工魚群的中心位置，則人工魚Xa向 Xc移動步長位置，否則進行覓食行為。人工魚的位置更新為

2 多策略協(xié)同進化人工魚群算法

傳統(tǒng)人工魚群算法的提出是為了解決連續(xù)型優(yōu)化問題，并且在算法迭代后期，人工魚搜索的盲目性較大，影響算法的收斂性及解的質(zhì)量。由于MPRM 電路面積優(yōu)化屬于三值組合優(yōu)化問題，所以本節(jié)基于人工魚群算法提出M-AFSA。所提算法的主要創(chuàng)新點為：在種群初始化階段加入反向?qū)W習(xí)機制，提出基于反向?qū)W習(xí)的種群初始化策略，以提高種群多樣性及初始種群解的質(zhì)量；為提高算法的收斂速度，提出覓食與追尾交互性策略，加強人工魚個體之間的信息交流，避免因視野和步長為固定值，導(dǎo)致算法迭代次數(shù)過多；提出自適應(yīng)擾動策略，增大算法迭代后期人工魚位置變異的隨機性，防止算法過早收斂，增強算法的全局尋優(yōu)能力。

2.1 距離計算

例2 以5 輸入變量為例，2 條人工魚的位置分別為00 020、01 210，則2 條魚之間的距離為3。

2.2 基于反向?qū)W習(xí)的種群初始化策略

初始種群的分布在一定程度上影響算法的收斂速度。為提高初始種群解的質(zhì)量，提出基于反向?qū)W習(xí)的種群初始化策略，在隨機初始化種群時，加入反向?qū)W習(xí)機制，保留最優(yōu)個體，產(chǎn)生初始種群，以擴大種群多樣性、提高初始種群解的質(zhì)量、增強算法收斂性。

反向?qū)W習(xí)概念由學(xué)者Rahnamayan 等[19]提出，其主要目的是得到當(dāng)前可行解的反向解，并對當(dāng)前可行解及其反向解進行評估，選出最優(yōu)解。該方法可有效提高種群多樣性，增強群智能算法的全局尋優(yōu)能力。

如果 d =0 且 f =1，則 s的反向解為

2.3 覓食與追尾交互性策略

在傳統(tǒng)人工魚群算法中，覓食行為是人工魚不斷地在視野范圍內(nèi)隨機尋找其他較優(yōu)位置，直至找到適應(yīng)度值優(yōu)于當(dāng)前人工魚的位置。因此，覓食行為可以使人工魚更全面地搜索整個解空間。但該行為易使算法復(fù)雜度過高，影響算法的收斂速度。并且在該行為中，參數(shù)的設(shè)定對行為的性能有很大影響。參數(shù)設(shè)置過大，算法初期收斂速度很快，但易陷入局部最優(yōu)；設(shè)置過小，會使算法的復(fù)雜程度過高，影響算法的運行效率。為解決該問題，更有效地平衡算法的開發(fā)和探索能力，本文在基于人工魚群算法的基礎(chǔ)上，對人工魚群尋優(yōu)策略進行了優(yōu)化，在追尾、覓食階段引入了覓食與追尾交互性策略。在追尾行為中，魚群不斷地向局部最優(yōu)值移動，直至找到優(yōu)于當(dāng)前值的位置。在覓食行為中，魚群不斷地隨機移動，直至找到優(yōu)于當(dāng)前值的位置。本文采用交互性追尾和覓食操作，讓表現(xiàn)較好地個體執(zhí)行先追尾后覓食的過程，以加快收斂速度。讓表現(xiàn)較差的個體執(zhí)行先覓食后追尾的過程，以跳出局部最優(yōu)解，增強全局搜索能力。覓食與追尾交互性策略增加了魚群間信息的交流，更有效地平衡算法的開發(fā)和探索能力。

2.4 自適應(yīng)擾動策略

隨著迭代次數(shù)的增加，人工魚群算法的種群多樣性降低，易使算法陷入局部最優(yōu)。因此，在原有行為基礎(chǔ)上引入遺傳算法中的交叉和變異策略以提高種群多樣性。當(dāng)魚群完成追尾和覓食行為之后對其實施擾動，以增加跳出局部最優(yōu)解的概率，縮短尋找全局最優(yōu)解的時間。概率過小，擾動行為會失去作用，不利于跳出局部最優(yōu)解；概率過大，位置改變的隨機性會偏大，破壞最優(yōu)解收斂方向。因此，本文引入自適應(yīng)擾動行為，隨著迭代次數(shù)的增加，計算得出的概率值隨之變化。迭代前期，擾動概率較小，加快收斂速度，迭代后期，擾動概率增大，增強算法跳出局部最優(yōu)的能力。自適應(yīng)擾動策略可增加人工魚位置變異的隨機性，防止人工魚群算法過早收斂。自適應(yīng)擾動策略的數(shù)學(xué)模型為

式中：gen 為迭代次數(shù)；α 和β 為固定常數(shù)，經(jīng)過大量實驗對比可得，α=2,β=0.3時，得到的實驗數(shù)據(jù)最優(yōu)。

2.5 算法描述

根據(jù)2.1 節(jié)～2.4 節(jié)所述，M-AFSA 流程如圖1所示。

圖1 M-AFSA 流程Fig.1 Flow chart of M-AFSA

具體步驟如下：

步驟 1 利用基于反向?qū)W習(xí)的種群初始化策略進行初始化種群。各項參數(shù)如下：N 為種群規(guī)模，visual 為人工魚的視野范圍，δ為人工魚群的擁擠度因子，Try_num 為人工魚移動的最大嘗試次數(shù)，σ為自適應(yīng)擾動策略中的擾動因子，T為當(dāng)代迭代次數(shù)，Tmax為最大迭代次數(shù)。

步驟 2 公告板的初始化。比較初始種群的適應(yīng)度值，將最優(yōu)適應(yīng)度值對應(yīng)的人工魚個體的位置賦值給公告板。

步驟 3 進行聚群行為，尋找當(dāng)代種群的中心位置。若該位置的適應(yīng)度值優(yōu)于當(dāng)前人工魚的位置并且不擁擠，則向該位置方向移動，產(chǎn)生新的位置。

步驟 4 進行覓食與追尾交互性策略，判斷個體適應(yīng)度值。適應(yīng)度值高的人工魚個體執(zhí)行先追尾后覓食的過程，適應(yīng)度值低的人工魚個體執(zhí)行先覓食后追尾的過程。

步驟 5 計算擾動因子，若rand()＜ σ,則執(zhí)行自適應(yīng)擾動策略，否則進行下一步。

步驟6 判斷算法是否滿足終止條件，若滿足，結(jié)束循環(huán)；否則，重復(fù)步驟3～步驟5。

2.6 時間復(fù)雜度分析

設(shè)M-AFSA 的種群規(guī)模為 N，迭代次數(shù)為Gen。

1）初始化種群階段。由于引入反向?qū)W習(xí)概念，需要進行 2N 次操作，因此該階段的時間復(fù)雜度為 O (2N)。

2）公告板的初始化階段。進行 N次比較，找到初始種群的最優(yōu)解，因此，該階段的時間復(fù)雜度為 O (N)。

進行聚群行為與進行覓食與追尾交互性策略階段。聚群行為中每個個體需要進行一次對比，一次移動，N次擁擠度計算。在覓食行為和追尾行為階段，由于引入了覓食與追尾交互性策略，每個個體需要進行一次對比，一次移動，N次尋找視野范圍內(nèi)最優(yōu)解，Try_num 次試探次數(shù)，因此，該階段的時間復(fù)雜度為 O(2N+N2)+O(2N+N2+NTry_num)。

3）自適應(yīng)擾動策略階段。每個個體需要進行交叉操作一次，變異操作一次，因此，該階段的時間復(fù)雜度為 O(2N)。

因此，M-AFSA 在Gen 次迭代后的時間復(fù)雜度為O(2N)+O(Gen(2N2+7N+NTry_num))。

2.7 空間復(fù)雜度分析

M-AFSA 中人工魚群的種群規(guī)模為 N，在算法運行過程中，需要 N 個結(jié)構(gòu)體 A_fish存儲人工魚的各項參數(shù)及長度為 l的一維數(shù)組，所需的空間為Nl；需要一個結(jié)構(gòu)體存儲種群最優(yōu)解，所需空間為l。因此，該算法需要的存儲空間為O(Nl + l)。

3 MPRM 邏輯電路面積優(yōu)化方法

MPRM 電路極性優(yōu)化空間隨電路輸入數(shù)的增加呈指數(shù)型增長。較小規(guī)模的電路面積優(yōu)化可以通過窮盡搜索方法實現(xiàn)，但是對于中大規(guī)模MPRM邏輯電路的面積優(yōu)化，窮盡搜索方法無法在有限的時間內(nèi)得到最優(yōu)解。為滿足中大規(guī)模MPRM 邏輯電路快速、有效面積優(yōu)化的需要，本文提出一種MPRM 邏輯電路面積優(yōu)化方法，該方法利用MAFSA 搜索電路面積最小的最佳極性，從而實現(xiàn)電路面積優(yōu)化。

3.1 編碼方案

人工魚的位置表示MPRM 邏輯電路中的極性，通過三進制編碼，將極性的三進制形式表示人工魚個體所在的位置。

例3 以5 輸入變量的電路為例：極性為6 的三進制表示為00020，則代表該極性的人工魚的位置為00020。

3.2 面積估算模型

適應(yīng)度值越高，則人工魚個體的質(zhì)量越好。因此，將面積計算函數(shù)的倒數(shù)作為適應(yīng)度函數(shù)：

3.3 適應(yīng)度函數(shù)

式中：finess(w)為 個體 w 的適應(yīng)度值；Area(w)為個體w的電路面積。

3.4 MPRM 邏輯電路面積優(yōu)化方法描述

圖2 MPRM 電路面積優(yōu)化方法流程Fig.2 Flow chart of MPRM circuit area optimization method

邏輯表達式；然后，通過三進制編碼方式對人工魚的位置進行編碼，并利用漢明距離表示人工魚之間的距離；最后，通過M-AFSA 搜索電路面積最小的最佳極性。

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

本文所提方法使用C 語言實現(xiàn)，軟件環(huán)境為：Windows 10操作系統(tǒng)、VS 2019 編譯器，硬 件 環(huán) 境 為：Intel (R) Core (TM)i5-10210U CPU (2.11GHZ) 8GB RAM。測試電路為MCNC Benchmark 基準(zhǔn)電路。

為了驗證所提方法的有效性，將所提算法與GA、AFSA、文獻[4]所提的HGA 及文獻[17]所提的FEAFSA 進行比較。從MCNC Benchmark 基準(zhǔn)電路測試集中隨機選取11 個電路作為實驗電路,其中，輸入變量個數(shù)為5～8 的為小規(guī)模電路，輸入變量個數(shù)為9～17 的為中大規(guī)模電路。由于5 種算法都具有隨機性，本實驗將每個算法在每個測試電路上運行20 次，并將實驗結(jié)果的最優(yōu)值和平均值作為實驗數(shù)據(jù)。

4.1 電路面積對比

5 種算法的電路面積優(yōu)化對比數(shù)據(jù)如表1、表2 所示，其中MCNC 表示電路名稱，為驗證所提方法的有效性，從小、中、大規(guī)模電路中，各隨機選取若干電路，In 表示測試電路的輸入變量個數(shù)，A_ave 表示20 次運行中求得的電路面積的平均值，T_ave 表示對應(yīng)的平均時間。S1、S2、S3、S4分別表示 M-AFSA 與 GA、HGA、AFSA 及 FEAFSA相比較，所優(yōu)化的最小面積百分比；S5、S6、S7、S8分別表示M-AFSA 與GA、HGA、AFSA 及FEAFSA比較，所優(yōu)化的面積平均值百分比。

表1 中數(shù)據(jù)為5 種算法求得的電路的最小面積，表2 中數(shù)據(jù)為5 種算法求得的電路的平均面積以及對應(yīng)的平均時間。由表1 可知，對于小規(guī)模電路來說，5 種算法得到的最小面積一致，但是M-AFSA得到的電路面積的平均值要優(yōu)于其他4 種算法。對于中大規(guī)模電路來說，M-AFSA 得到的最小面積優(yōu)于其他4 種算法，且平均值明顯優(yōu)于其他4 種算法。M-AFSA 比GA 在平均面積上最高節(jié)省了57.24%、平均節(jié)省了39.57%；M-AFSA 比HGA 在平均面積上最高節(jié)省了19.74%、平均節(jié)省了2.06%；比AFSA 在平均面積上最高節(jié)省了33.53%、平均節(jié)省了14.54%；比FEAFSA 在平均面積上最高節(jié)省了30.25%、平均節(jié)省了13.86%。

表1 最優(yōu)面積數(shù)據(jù)Table 1 Optimal area data

表2 平均面積與平均時間數(shù)據(jù)Table 2 Average area and average time data

4.2 收斂性對比

為驗證M-AFSA 算法的收斂性，隨機選取8 個MCNC Benchmark 基準(zhǔn)電路。4 種算法的收斂性如圖3 所示，其中，橫坐標(biāo)為迭代次數(shù)，縱坐標(biāo)為運行20 次測試電路面積的平均值。可以看出，與GA、AFSA 及FEAFSA 相比，M-AFSA 能夠 在迭代次 數(shù)最小的情況下，找到最小面積。

圖3 8 種基準(zhǔn)電路最小面積優(yōu)化曲線Fig.3 Optimization curves of minimum area of eight reference circuit

從圖3 中可以直觀地看出，通過基于反向?qū)W習(xí)的種群初始化產(chǎn)生的初始種群的平均面積，均小于其他對比算法，驗證了基于反向?qū)W習(xí)的種群初始化策略的有效性；此外，由M-AFSA 曲線與AFSA 曲線相比，可看出M-AFSA 收斂速度快，驗證了覓食與追尾交互性策略可有效地提高算法的收斂速度；最后，從圖3 中可看出M-AFSA 找到的面積絕大多數(shù)小于其他3 種算法，驗證了自適應(yīng)擾動策略可有效地避免M-AFSA 陷入局部最優(yōu)。

5 結(jié) 論

本文所提算法用于解決MPRM 電路面積優(yōu)化問題。主要結(jié)論如下:

1）提出的M-AFSA 在初始化種群方面加入反向?qū)W習(xí)機制，提高了種群的多樣性、初始種群解的質(zhì)量和算法的收斂速度；M-AFSA 在追尾和覓食這2 種基本行為中加入覓食與追尾交互性策略，增加個體之間的信息交流，提高局部搜索能力，加快算法的收斂速度；傳統(tǒng)人工魚算法隨著迭代次數(shù)的增加，人工魚群算法的種群多樣性降低，為改善這一缺點，M-AFSA 加入自適應(yīng)擾動策略，增加人工魚的位置變異隨機性，防止人工魚群算法過早收斂。

2）提出一種MPRM 電路面積優(yōu)化方法，該方法利用M-AFSA 來搜索MPRM 邏輯電路面積的最優(yōu)解。

3）通過大量MCNC 測試電路的實驗結(jié)果可表明,M-AFSA 在MPRM 邏輯電路優(yōu)化方面具有較好的收斂性和尋優(yōu)性能?；贛CNC Benchmark 電路的實驗結(jié)果表明，與GA 相比，所提算法優(yōu)化電路平均面積百分比最高為57.24%；與HGA 相比，所提算法優(yōu)化電路平均面積百分比最高為19.74%；與AFSA 相比，所提算法優(yōu)化電路平均面積百分比最高為33.53%；與FEAFSA 相比，所提算法優(yōu)化電路平均面積百分比最高為30.25%。