基于ERWOA 的多輸出MPRM 電路面積優化

何俊才，何振學，*，王福順，霍志勝，肖利民

(1.河北農業大學 智能農業裝備研究院，保定 071001；2.河北農業大學 河北省農業大數據重點實驗室，保定 071001；

3.北京航空航天大學 高性能計算平臺，北京 100191；4.北京航空航天大學 軟件學院，北京 100191；5.北京航空航天大學 計算機學院，北京 100191)

邏輯函數可以使用Boolean 邏輯表示或使用(Reed-Muller, RM)邏 輯 表 示[1]。Boolean 邏 輯 表 達式是以AND/OR/NOT 為運算基礎，而RM 邏輯表達式是以AND/XOR 為運算基礎[2]。對部分電路來說，RM 邏輯電路在面積、功耗、可測試性等方面比Boolean 邏輯電路更有優勢[3-4]?；旌蠘O性Reed-Muller(mixed polarity Reed-Muller, MPRM)邏輯電路優化得到了廣泛關注，并已成為集成電路設計領域的研究熱點[5-6]。

n輸入變量的Boolean 邏輯電路有 3n個MPRM電路表達式[7]，對應著 3n個不同極性。表達式所含與項個數多少決定了MPRM 電路的面積大小[8]。因此，在 3n個MPRM 表達式中尋找一個與項個數最少的MPRM 表達式屬于組合優化問題[9]。李輝等[9-10]利用模擬退火遺傳算法和枚舉法求解多輸出MPRM電路面積。卜登立等[11]利用遺傳算法解決多輸出MPRM 電路面積與SER 折中優化，用混合多值離散粒子群算法解決多輸出MPRM 電路面積優化問題[12]，得到了較好的效果，但是還存在收斂速度較慢的問題。實際電路大多都是多輸出電路，而現有多輸出MPRM 電路面積優化研究較少。因此，研究多輸出MPRM 電路面積優化具有重要意義和應用價值。

澳大利亞學者Mirjalili 于2016 年提出了一種新的啟發式群體智能算法—鯨魚優化算法(whale optimization algorithm, WOA)[13]。鯨魚優化算法具有原理簡單、易于計算機編程實現和參數較少的優點[14]。鯨魚優化算法已成功應用于大規模函數優化[14]、0-1 背包[15]、云計算資源調度[16]、噪聲圖像邊緣檢測[17]等問題。然而，傳統鯨魚優化算法無法直接用于求解多輸出MPRM 面積優化這樣的三值組合優化問題。

針對上述問題，本文提出一種多輸出MPRM 電路面積優化方法。與現有多輸出MPRM 電路面積優化方法相比，本文的主要創新點如下：

1）提出一種基于爆炸機制和重啟機制的鯨魚優化算法（explosion strategy and restart strategy based whale optimization algorithm, ERWOA）。爆炸機制提高了鯨魚優化算法的收斂速度，重啟機制提高了算法的穩定性。

2）提出一種基于二叉樹的極性轉換算法。因為二叉樹的查找效率較高，所以本文基于二叉樹來描述多輸出MPRM 電路，以提高多輸出MPRM 電路的極性轉換效率。

3）提出一種多輸出MPRM 電路面積優化方法。該方法基于改進的鯨魚優化算法和改進的極性轉換算法來搜索含與項個數最少的多輸出MPRM電路，以實現多輸出MPRM 電路面積優化。

1 基礎知識

1.1 多輸出MPRM 表達式

一個輸入變量位數為n和輸出變量位數為m的Boolean 函 數 系 統F={0,1}n→{0,1}m[18]由m個(1)[8]所示的n輸入變量位的Boolean 函數對應的乘積和的標準形表示。

式中：Xi為 最小項表達式；ai為 第i個最小項是否存在，1 為存在，0 為不存在。

任意輸入變量位數為n的單輸出Boolean 邏輯函數都可以由基于AND/XOR 的MPRM 展開式表示，即[8]

式中：P為MPRM 表達式的極性；πi為與項。

因此，一個輸入變量位數為n且輸出變量位數為m的MPRM 表達式可表示為

式中：f tp(xn?1,xn?2,xn?3,···,x0)[8]為第t位輸出變量的MPRM 表達式。

1.2 極 性

在 多 輸 出MPRM 表 達 式 中，πi可 以 展 開 為x˙n?1,x˙n?2,x˙n?3,···,x˙0，極性和式(2)中的下標i共同決定了x˙k的 表現形式。當 (pk,ik) (0 ≤k

例如，給定一個3 輸入和2 輸出的Boolean 邏輯函數表達式，如下：

其對應極性為0(000)3的MPRM 表達式為

其對應極性為26(222)3的MPRM 表達式為

可以看出，極性為 0(000)3的MPRM 表達式含有6 個與項，極性為 26(222)3的MPRM 表達式含有5 個與項。因此，對于同一電路來說，極性不同，對應的MPRM 表達式所含有的與項個數也不同。多輸出MPRM 電路面積優化是在極性優化空間中搜索對應電路面積最小的最佳極性，故多輸出MPRM電路面積優化屬于組合優化問題。

2 快速多輸出MPRM 電路極性轉換算法

2.1 快速混合極性轉換算法

基于列表技術的混合極性轉換算法[8]，本文提出一種基于二叉樹的極性轉換算法，該算法的主要步驟如下：

步驟 1將n個輸入變量和m個輸出變量的Boolean 邏輯函數展開成最小項表達式，并將最小項表達式存放在2 棵二叉樹中，分別記為A-Ⅰ樹和A-Ⅱ樹。令i=0，目標極性為P。

步驟 2若Pi=2，則跳轉到步驟6。否則根據Pi的 值在A-Ⅰ樹的第i層 節點中找到和Pi相等的權值邊，并將這條邊的權值取反。

步驟 3記錄A-Ⅰ樹中從根節點到葉節點的路徑中權值改變過的路徑(最小項)，在A-Ⅱ樹中查找A-Ⅰ樹中新生成的最小項是否存在于A-Ⅱ樹中。如果A-Ⅱ樹中不存在，則將新生成的最小項加入A-Ⅱ樹。否則將A-Ⅰ樹中新生成的最小項的輸出項和A-Ⅱ樹中相同的最小項的輸出項按位異或，如果異或值為0，則將A-Ⅱ樹中對應的最小項刪除，否則用異或結果替換A-Ⅱ樹中對應最小項的輸出項。

步驟 4如果Pi= 1，則將A-Ⅱ樹中第i層節點的所有權值取反。否則不進行任何處理。

步驟 5釋放A-Ⅰ樹。如果i+1

步驟 6i+ +，如果i

2.2 快速極性間轉換算法

基于列表技術的極性間轉換算法[8]，本文提出一種基于二叉樹的極性間轉換算法，該算法主要步驟如下：

步驟 1將n個輸入變量和m個輸出變量且極性為P的MPRM 表達式以二叉樹的形式表示出來，分別存放在A-Ⅰ樹和A-Ⅱ樹上。令i=0，目標極性為T。

步驟 2Xi=Pi⊕Ti。如果Xi=0，轉步驟6。如果Xi= 1 或者當Xi= 3 時Pi= 2，將A-Ⅰ樹第i層節點中權值為1 的邊的權值修改為0。如果Xi=2 或者當Xi= 3 時Pi= 1，將A-Ⅰ樹第i層節點中權值為0 的邊的權值修改為1。

步驟 3判斷A-Ⅰ樹中新生成的與項在A-Ⅱ樹中是否存在。如果不存在，將與項存進A-Ⅱ樹，否則將A-Ⅰ樹中新生成的與項的輸出項和A-Ⅱ樹中相同與項的輸出項按位異或。如果異或值為0，則將A-Ⅱ樹中對應的與項刪除，否則用異或值把A-Ⅱ樹中對應與項的輸出項替換掉。

步驟 4如果Xi= 3，把A-Ⅱ樹中第i層節點的所有權值取反。

步驟 5釋放A-Ⅰ樹，如果i+1

步驟 6i++，如果i

3 多輸出MPRM 電路面積優化

多輸出MPRM 電路面積優化屬于組合優化問題?，F有多輸出MPRM 電路面積優化方法存在收斂速度較慢的問題。因此，在鯨魚優化算法的基礎上，提出一種基于爆炸機制和重啟機制的鯨魚優化算法。此外，提出一種多輸出MPRM 電路面積優化方法，該方法使用鯨魚優化算法搜索面積最小的最佳極性，以實現多輸出MPRM 電路面積優化。

3.1 鯨魚優化算法

鯨魚優化算法是針對連續問題提出的，不能直接處理像多輸出MPRM 電路優化這樣的三值組合優化問題。因此，本節提出一種基于爆炸機制和重啟機制的鯨魚優化算法。引入爆炸機制以提高算法的收斂速度，引入重啟機制提升算法的穩定性。

3.1.1 編碼方案

根據多輸出MPRM 表達式的特點，將極性作為鯨魚個體，并且編碼為三進制。若邏輯電路的輸入變量位數為n，則解空間的維度為n。

3.1.2 面積模型和適應度函數

以多輸出MPRM 表達式含有的與項個數作為面積模型[8]。適應度函數的值等于通過面積模型得到的值。

3.1.3 包圍獵物

在包圍獵物階段，由于個體位置更新以后的位置可以在目標獵物和個體位置之間的任何一個位置，因此，在包圍獵物階段只需保證個體和獵物之間的距離不再擴大即可。具體的操作如下:

式中：randInt(0,2)表示隨機生成一個屬于集合{0,1,2}的數；Xid(t)為 第i個 體第d維的位置；X?d(t)為獵物第d維的位置。

3.1.4 螺旋泡沫網攻擊

在螺旋泡沫網階段，鯨魚個體需要不斷地向獵物靠近。隨機選擇一個獵物和個體維度值不相同的維度d，使個體和獵物第d維的值保持一致。

式中：r為一個隨機數，表示在鯨魚個體Xi(t)和獵物X?(t)的所有值不相同的維度上隨機產生的一個數。

流言：前不久，網上流傳了一篇文章《咬破舌頭1個月得癌！醫生的提醒為所有人敲響警鐘》，說的是在某大學附屬醫院的口腔醫療中心，收治了一位65歲的男性舌癌病人，其病因竟然是吃飯咬破了舌頭引起的。

3.1.5 隨機搜索

在隨機搜索階段，隨機選擇一個個體作為獵物并靠近。具體操作如下:

3.2 爆炸機制

在大量實驗中發現，鯨魚優化算法針對中大規模電路優化存在如下現象：從當前最優解搜索到下一個解往往只需要在當前最優解的基礎上變換幾個維度就能找到一個更優的解。因此，只要在最優解的附近進行大量的搜索，就有可能找到比當前最優解更優的解，進而提高算法的收斂速度。但是鯨魚優化算法存在從當前最優解搜索到下一個更優解收斂速度不快的問題。由于煙花算法[19]的爆炸機制有很強的局部爆發能力[20]，將煙花算法的爆炸思想引入鯨魚優化算法，以提升算法的局部搜索能力。主要操作如下：假設爆炸半徑為r2，需要生成的火花數為n。生成一個火花時，以最優解為基準，隨機選擇r維，然后在r維上隨機生成屬于集合{0,1,2}的隨機數，重復執行n次，直到生成n個火花。最后評估生成的n個火花的適應度值。圖1 為爆炸半徑為2，生成一個火花的過程。

圖1 爆炸過程Fig.1 Explosion process

3.3 重啟機制

在傳統鯨魚優化算法中，存在2 個問題：①在種群質量極差的情況下，經過離散后的原始鯨魚優化算法可能存在不迭代的情況，導致算法在20 次的重復運行過程中可能存在鯨魚優化算法最終找到的最優值相差較大的情況。②原始鯨魚優化算法容易陷入局部最優。以圖1 為例，假設極性B是理論上的最佳極性，鯨魚優化算法要從極性A搜索到極性B需要將極性A中的第1 位的1 變為2，第2 位的2 變為1。當維數較低時，鯨魚優化算法很容易從極性A搜索到極性B。如果極性A和極性B的維數增加，且從極性A到極性B需要改變的維數越多，鯨魚優化算法很難在有限次的迭代過程中從極性A搜索到極性B。因此，受文獻[21]的啟發引入重啟機制，當鯨魚優化算法陷入局部最優以后，重新生成種群，并重新執行鯨魚優化算法。由于在重啟的過程中，鯨魚優化算法可能會找到在前面的重啟過程中找到的最優值，為了避免鯨魚優化算法陷入相同的局部最優，引入三叉樹存放在整個過程中搜索到的最優值。主要操作如下：

步驟 1 將鯨魚優化算法每次迭代找到的最優值存儲在三叉樹中。當最優值連續n代不變時，重新生成新的種群并重新執行鯨魚優化算法。

步驟 2 在執行重啟機制的過程中，如果生成的最優解在三叉樹中存在，判斷三叉樹中存在的解是不是在本次重啟過程中生成的。如果是本次重啟過程中生成的，繼續執行重啟機制，否則執行一次爆炸機制，判斷是否可以找到一個更優且未在三叉樹中儲存的解。如果不能找到一個滿足條件的解，本次重啟結束，執行下次重啟。否則繼續執行本次重啟操作。

3.4 多輸出MPRM 電路面積優化方法

本節提出一種多輸出MPRM 電路面積優化方法，該方法使用提出的鯨魚優化算法搜索對應電路面積最小的最佳極性。方法流程如圖2 所示，其實現步驟如下：

圖2 方法流程Fig.2 Algorithm flowchart

步驟 2 將生成的最小項存儲在2 棵二叉樹中，通過基于二叉樹的混合極性轉換算法轉換到0 極性。

步驟 3 設置算法的最大迭代次數Iter，歷史迭代次數history_iter=0，種群規模N。

步驟 4 初始化鯨魚優化算法參數和種群，設置當前迭代次數now_iter=0，記錄種群的最優值。

步驟 5 更新鯨魚算法參數的值。如果L≥0.5則根據式(8)更新位置，如果p<0.5且F<1則根據式(7)更新位置，如果p<0.5且A≥1根據式(9)更新位置[13]。

步驟 6 計算種群的適應度值，確定最優值。

步驟 7 執行爆炸機制，在最優值附近搜索是否還有更優的解。如果存在更優的解，更新最優解的相關信息。再判斷最優解是否好于全局最優解，如果好于全局最優解，更新全局最優解的相關信息。

步驟 8如果最優值連續n代沒有變化，執行步驟10，否則執行步驟9。

步驟 9now_iter++，history_iter++。如果now_iter

步驟 10history_iter++，如果history_iter

執行重啟機制，返回步驟4。否則結束算法，輸出全局最優值。

4 實驗結果及分析

實驗的運行環境基于windows10 64 位操作系統，Intel(R) Core(TM) i7-10700 CPU @ 2.90 GHz，32 GB RAM，visual studio community 2019×64。本文實驗算法均用C 語言實現。為了充分驗證方法的有效性，實驗分為以下3 部分：①改進的混合極性轉換算法有效性驗證。②改進的極性間轉換算法有效性驗證。③改進的鯨魚優化算法有效性驗證。

改進的鯨魚優化算法的參數通過引入5 因素4 水平的正交表確定。鯨魚優化算法、遺傳算法(GA)和人工蜂群算法(ABC)的參數通過大量實驗獲得。為了公平比較各個算法，設置評估次數4 000作為每個算法的結束條件。算法參數設置如表1所示。

表1 算法參數Table 1 Algorithm parameters

4.1 混合極性轉換算法驗證

為測試改進以后的混合極性轉換的效率，選取13 個標準MCNC Benchmark 電路進行測試。進行混合極性轉換效率的測試時，將選擇電路的最小項轉換到0 極性。測試方法為：對每個電路獨立運行10 次，統計每次從最小項轉換到0 極性的運行時間，取10 次運行時間的平均值。算法1 表示基于列表技術的極性轉換算法，算法2 表示基于二叉樹的極性轉換算法。為了驗證算法2 的正確性，執行極性轉換算法的同時計算MPRM 表達式的面積。area1 表示通過算法1 進行極性轉換得到的面積，area2 表示通過算法2 進行極性轉換得到的面積。I/O 分別代表電路的輸入位數和輸出位數。Rsave表示算法2 比算法1 節省時間的百分比，具體計算公式為

式中：TimeALGO_1為算法1 的平均運行時間；TimeALGO_2為算法2 的平均運行時間。

從表2 可以看出，13 個MCNC Benchmark 電路的area1 和area2 分別保持一致，驗證了算法2 的正確性。隨著電路輸入位數的增多，算法2 執行極性轉換所用的時間明顯少于算法1，特別對table5、in2、shift、mark1 四個電路的時間節省率達到了99.60%以上。造成以上實驗結果的原因可能是用二叉樹表達MPRM 電路時生成新項和查找重復項的效率較高。

表2 混合極性轉換實驗數據Table 2 Experimental data of mixed polarity conversion

4.2 極性間轉換算法驗證

在混合極性間轉換的過程中，可能會轉換到任意極性。極性間的轉換采取從極性0 到極性(22···22)3(n位)。所選擇的電路和4.1 節中選取的電路一致。算法3 表示基于列表技術的極性間轉換算法，算法4 表示基于二叉樹的極性間轉換算法，Rsave的計算公式和式（10）一致。

從表3 可以看出，對于電路misex1、ex1010，算法3 的運行時間和算法4 相同。對于表中的其他電路，算法3 的運行時間長于算法4 的運行時間。特別是對于電路mark1，算法3 的運行時間達到了15 102.41 s，而算法4 的運行時間只有6.42 s。出現以上實驗結果的原因可能受與項個數、去除重復的與項操作、生成新與項操作的影響。

表3 極性間轉換實驗數據Table 3 Experimental data for conversion between different polarities

4.3 多輸出MPRM 電路面積優化效果驗證

為了測試改進的鯨魚算法的優化效果，選擇WOA、GA、ABC 作比較實驗。通過式(11)得到節省電路面積百分比：

式中：AVEOTHER_ALGO為WOA、GA、ABC 三個算法在每個電路上運行20 次得到的最優值的平均值；AVEERWOA為ERWOA 算法在每個電路上運行20 次得到的最優值的平均值。從表4 中可以看出，相比于WOA、GA、ABC，EROWA 的標準差為0 的個數達到了8 個。和WOA 相比，ERWOA 的平均電路面積節省為3.45%，最大平均電路面積節省為9.72%。和GA 相比，ERWOA 的平均電路面積節省為5.54%，最大平均電路面積節省為18.32%。相比于ABC，ERWOA 的平均電路面積節省為5.00%，最大平均電路面積節省為14.41%。

表4 算法實驗數據Table 4 Experiment data of algorithm

通過以上數據說明，ERWOA 在穩定性和搜索能力方面均優于WOA、GA、ABC。出現上述實驗結果的原因可能如下:

1）WOA、GA、ABC 容易陷入局部最優解且不容易跳出。因為ERWOA 引入了重啟機制，所以可以有效跳出局部最優解，從而增強了算法的穩定性。

2）WOA、GA、ABC 搜索精度比ERWOA 低。因為ERWOA 引入了爆炸機制，所以可以在有限的迭代次數內搜索到更優解。

4.4 收斂性對比

為了進一步說明ERWOA 算法的性能，選擇4 個測試電路繪制收斂曲線。其中，橫坐標代表算法前30 次的迭代次數，縱坐標代表算法運行20 次找到的面積的平均值。

從圖3～圖6 中可以看出，和WOA、GA、ABC三種算法相比，ERWOA 在收斂速度、找到最優值方面效果較好。

圖3 newcond 電路收斂曲線Fig.3 Convergence curves of newcond circuit

圖4 misex3 電路收斂曲線Fig.4 Convergence curves of misex3 circuit

圖5 in0 收斂曲線Fig.5 Convergence curves of in0 circuit

圖6 b2 電路收斂曲線Fig.6 Convergence curves of b2 circuit

5 結 論

本文提出一種基于爆炸機制和重啟機制的鯨魚優化算法用于求解基于MPRM 電路的面積優化問題，主要結論如下:

1）提出一種基于二叉樹的極性轉換算法。和基于列表技術的混合極性轉換算法相比，轉換效率最高提升99.93%，和基于列表技術的極性間轉換算法相比，轉換效率最高提升99.96%。

2）多輸出MPRM 電路面積優化方法與GA 算法相比，節省的電路面積百分比最高為18.32%，平均為5.54%；與ABC 算法相比，節省電路面積百分比最高為14.41%，平均為5.00%；與WOA 相比，最大電路面積節省為9.72%，平均為3.45%。