基于M-AFSA 的MPRM 邏輯電路面積優化

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關知識

1.1 MPRM 邏輯表達式

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

1.2 人工魚群算法

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

1.2.1 覓食行為

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

1.2.3 聚群行為

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

2 多策略協同進化人工魚群算法

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

2.1 距離計算

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

2.2 基于反向學習的種群初始化策略

初始種群的分布在一定程度上影響算法的收斂速度。為提高初始種群解的質量，提出基于反向學習的種群初始化策略，在隨機初始化種群時，加入反向學習機制，保留最優個體，產生初始種群，以擴大種群多樣性、提高初始種群解的質量、增強算法收斂性。

反向學習概念由學者Rahnamayan 等[19]提出，其主要目的是得到當前可行解的反向解，并對當前可行解及其反向解進行評估，選出最優解。該方法可有效提高種群多樣性，增強群智能算法的全局尋優能力。

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

2.3 覓食與追尾交互性策略

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

2.4 自適應擾動策略

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

式中：gen 為迭代次數；α 和β 為固定常數，經過大量實驗對比可得，α=2,β=0.3時，得到的實驗數據最優。

2.5 算法描述

根據2.1 節～2.4 節所述，M-AFSA 流程如圖1所示。

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

具體步驟如下：

步驟 1 利用基于反向學習的種群初始化策略進行初始化種群。各項參數如下：N 為種群規模，visual 為人工魚的視野范圍，δ為人工魚群的擁擠度因子，Try_num 為人工魚移動的最大嘗試次數，σ為自適應擾動策略中的擾動因子，T為當代迭代次數，Tmax為最大迭代次數。

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

步驟 3 進行聚群行為，尋找當代種群的中心位置。若該位置的適應度值優于當前人工魚的位置并且不擁擠，則向該位置方向移動，產生新的位置。

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

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

步驟6 判斷算法是否滿足終止條件，若滿足，結束循環；否則，重復步驟3～步驟5。

2.6 時間復雜度分析

設M-AFSA 的種群規模為 N，迭代次數為Gen。

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

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

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

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

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

2.7 空間復雜度分析

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

3 MPRM 邏輯電路面積優化方法

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

3.1 編碼方案

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

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

3.2 面積估算模型

適應度值越高，則人工魚個體的質量越好。因此，將面積計算函數的倒數作為適應度函數：

3.3 適應度函數

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

3.4 MPRM 邏輯電路面積優化方法描述

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

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

4 實驗結果與分析

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

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

4.1 電路面積對比

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

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

表1 最優面積數據Table 1 Optimal area data

表2 平均面積與平均時間數據Table 2 Average area and average time data

4.2 收斂性對比

為驗證M-AFSA 算法的收斂性，隨機選取8 個MCNC Benchmark 基準電路。4 種算法的收斂性如圖3 所示，其中，橫坐標為迭代次數，縱坐標為運行20 次測試電路面積的平均值?？梢钥闯?，與GA、AFSA 及FEAFSA 相比，M-AFSA 能夠 在迭代次 數最小的情況下，找到最小面積。

圖3 8 種基準電路最小面積優化曲線Fig.3 Optimization curves of minimum area of eight reference circuit

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

5 結 論

本文所提算法用于解決MPRM 電路面積優化問題。主要結論如下:

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

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

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