基于ERWOA 的多輸出MPRM 電路面積優(yōu)化

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

(1.河北農(nóng)業(yè)大學(xué) 智能農(nóng)業(yè)裝備研究院，保定 071001；2.河北農(nóng)業(yè)大學(xué) 河北省農(nóng)業(yè)大數(shù)據(jù)重點(diǎn)實(shí)驗(yàn)室，保定 071001；

3.北京航空航天大學(xué) 高性能計(jì)算平臺(tái)，北京 100191；4.北京航空航天大學(xué) 軟件學(xué)院，北京 100191；5.北京航空航天大學(xué) 計(jì)算機(jī)學(xué)院，北京 100191)

邏輯函數(shù)可以使用Boolean 邏輯表示或使用(Reed-Muller, RM)邏 輯 表 示[1]。Boolean 邏 輯 表 達(dá)式是以AND/OR/NOT 為運(yùn)算基礎(chǔ)，而RM 邏輯表達(dá)式是以AND/XOR 為運(yùn)算基礎(chǔ)[2]。對(duì)部分電路來(lái)說(shuō)，RM 邏輯電路在面積、功耗、可測(cè)試性等方面比Boolean 邏輯電路更有優(yōu)勢(shì)[3-4]。混合極性Reed-Muller(mixed polarity Reed-Muller, MPRM)邏輯電路優(yōu)化得到了廣泛關(guān)注，并已成為集成電路設(shè)計(jì)領(lǐng)域的研究熱點(diǎn)[5-6]。

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

澳大利亞學(xué)者M(jìn)irjalili 于2016 年提出了一種新的啟發(fā)式群體智能算法—鯨魚優(yōu)化算法(whale optimization algorithm, WOA)[13]。鯨魚優(yōu)化算法具有原理簡(jiǎn)單、易于計(jì)算機(jī)編程實(shí)現(xiàn)和參數(shù)較少的優(yōu)點(diǎn)[14]。鯨魚優(yōu)化算法已成功應(yīng)用于大規(guī)模函數(shù)優(yōu)化[14]、0-1 背包[15]、云計(jì)算資源調(diào)度[16]、噪聲圖像邊緣檢測(cè)[17]等問(wèn)題。然而，傳統(tǒng)鯨魚優(yōu)化算法無(wú)法直接用于求解多輸出MPRM 面積優(yōu)化這樣的三值組合優(yōu)化問(wèn)題。

針對(duì)上述問(wèn)題，本文提出一種多輸出MPRM 電路面積優(yōu)化方法。與現(xiàn)有多輸出MPRM 電路面積優(yōu)化方法相比，本文的主要?jiǎng)?chuàng)新點(diǎn)如下：

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

2）提出一種基于二叉樹的極性轉(zhuǎn)換算法。因?yàn)槎鏄涞牟檎倚瘦^高，所以本文基于二叉樹來(lái)描述多輸出MPRM 電路，以提高多輸出MPRM 電路的極性轉(zhuǎn)換效率。

3）提出一種多輸出MPRM 電路面積優(yōu)化方法。該方法基于改進(jìn)的鯨魚優(yōu)化算法和改進(jìn)的極性轉(zhuǎn)換算法來(lái)搜索含與項(xiàng)個(gè)數(shù)最少的多輸出MPRM電路，以實(shí)現(xiàn)多輸出MPRM 電路面積優(yōu)化。

1 基礎(chǔ)知識(shí)

1.1 多輸出MPRM 表達(dá)式

一個(gè)輸入變量位數(shù)為n和輸出變量位數(shù)為m的Boolean 函 數(shù) 系 統(tǒng)F={0,1}n→{0,1}m[18]由m個(gè)(1)[8]所示的n輸入變量位的Boolean 函數(shù)對(duì)應(yīng)的乘積和的標(biāo)準(zhǔn)形表示。

式中：Xi為 最小項(xiàng)表達(dá)式；ai為 第i個(gè)最小項(xiàng)是否存在，1 為存在，0 為不存在。

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

式中：P為MPRM 表達(dá)式的極性；πi為與項(xiàng)。

因此，一個(gè)輸入變量位數(shù)為n且輸出變量位數(shù)為m的MPRM 表達(dá)式可表示為

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

1.2 極 性

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

例如，給定一個(gè)3 輸入和2 輸出的Boolean 邏輯函數(shù)表達(dá)式，如下：

其對(duì)應(yīng)極性為0(000)3的MPRM 表達(dá)式為

其對(duì)應(yīng)極性為26(222)3的MPRM 表達(dá)式為

可以看出，極性為 0(000)3的MPRM 表達(dá)式含有6 個(gè)與項(xiàng)，極性為 26(222)3的MPRM 表達(dá)式含有5 個(gè)與項(xiàng)。因此，對(duì)于同一電路來(lái)說(shuō)，極性不同，對(duì)應(yīng)的MPRM 表達(dá)式所含有的與項(xiàng)個(gè)數(shù)也不同。多輸出MPRM 電路面積優(yōu)化是在極性優(yōu)化空間中搜索對(duì)應(yīng)電路面積最小的最佳極性，故多輸出MPRM電路面積優(yōu)化屬于組合優(yōu)化問(wèn)題。

2 快速多輸出MPRM 電路極性轉(zhuǎn)換算法

2.1 快速混合極性轉(zhuǎn)換算法

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

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

步驟 2若Pi=2，則跳轉(zhuǎn)到步驟6。否則根據(jù)Pi的 值在A-Ⅰ樹的第i層 節(jié)點(diǎn)中找到和Pi相等的權(quán)值邊，并將這條邊的權(quán)值取反。

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

步驟 4如果Pi= 1，則將A-Ⅱ樹中第i層節(jié)點(diǎn)的所有權(quán)值取反。否則不進(jìn)行任何處理。

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

步驟 6i+ +，如果i

2.2 快速極性間轉(zhuǎn)換算法

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

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

步驟 2Xi=Pi⊕Ti。如果Xi=0，轉(zhuǎn)步驟6。如果Xi= 1 或者當(dāng)Xi= 3 時(shí)Pi= 2，將A-Ⅰ樹第i層節(jié)點(diǎn)中權(quán)值為1 的邊的權(quán)值修改為0。如果Xi=2 或者當(dāng)Xi= 3 時(shí)Pi= 1，將A-Ⅰ樹第i層節(jié)點(diǎn)中權(quán)值為0 的邊的權(quán)值修改為1。

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

步驟 4如果Xi= 3，把A-Ⅱ樹中第i層節(jié)點(diǎn)的所有權(quán)值取反。

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

步驟 6i++，如果i

3 多輸出MPRM 電路面積優(yōu)化

多輸出MPRM 電路面積優(yōu)化屬于組合優(yōu)化問(wèn)題。現(xiàn)有多輸出MPRM 電路面積優(yōu)化方法存在收斂速度較慢的問(wèn)題。因此，在鯨魚優(yōu)化算法的基礎(chǔ)上，提出一種基于爆炸機(jī)制和重啟機(jī)制的鯨魚優(yōu)化算法。此外，提出一種多輸出MPRM 電路面積優(yōu)化方法，該方法使用鯨魚優(yōu)化算法搜索面積最小的最佳極性，以實(shí)現(xiàn)多輸出MPRM 電路面積優(yōu)化。

3.1 鯨魚優(yōu)化算法

鯨魚優(yōu)化算法是針對(duì)連續(xù)問(wèn)題提出的，不能直接處理像多輸出MPRM 電路優(yōu)化這樣的三值組合優(yōu)化問(wèn)題。因此，本節(jié)提出一種基于爆炸機(jī)制和重啟機(jī)制的鯨魚優(yōu)化算法。引入爆炸機(jī)制以提高算法的收斂速度，引入重啟機(jī)制提升算法的穩(wěn)定性。

3.1.1 編碼方案

根據(jù)多輸出MPRM 表達(dá)式的特點(diǎn)，將極性作為鯨魚個(gè)體，并且編碼為三進(jìn)制。若邏輯電路的輸入變量位數(shù)為n，則解空間的維度為n。

3.1.2 面積模型和適應(yīng)度函數(shù)

以多輸出MPRM 表達(dá)式含有的與項(xiàng)個(gè)數(shù)作為面積模型[8]。適應(yīng)度函數(shù)的值等于通過(guò)面積模型得到的值。

3.1.3 包圍獵物

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

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

3.1.4 螺旋泡沫網(wǎng)攻擊

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

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

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

3.1.5 隨機(jī)搜索

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

3.2 爆炸機(jī)制

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

圖1 爆炸過(guò)程Fig.1 Explosion process

3.3 重啟機(jī)制

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

步驟 1 將鯨魚優(yōu)化算法每次迭代找到的最優(yōu)值存儲(chǔ)在三叉樹中。當(dāng)最優(yōu)值連續(xù)n代不變時(shí)，重新生成新的種群并重新執(zhí)行鯨魚優(yōu)化算法。

步驟 2 在執(zhí)行重啟機(jī)制的過(guò)程中，如果生成的最優(yōu)解在三叉樹中存在，判斷三叉樹中存在的解是不是在本次重啟過(guò)程中生成的。如果是本次重啟過(guò)程中生成的，繼續(xù)執(zhí)行重啟機(jī)制，否則執(zhí)行一次爆炸機(jī)制，判斷是否可以找到一個(gè)更優(yōu)且未在三叉樹中儲(chǔ)存的解。如果不能找到一個(gè)滿足條件的解，本次重啟結(jié)束，執(zhí)行下次重啟。否則繼續(xù)執(zhí)行本次重啟操作。

3.4 多輸出MPRM 電路面積優(yōu)化方法

本節(jié)提出一種多輸出MPRM 電路面積優(yōu)化方法，該方法使用提出的鯨魚優(yōu)化算法搜索對(duì)應(yīng)電路面積最小的最佳極性。方法流程如圖2 所示，其實(shí)現(xiàn)步驟如下：

圖2 方法流程Fig.2 Algorithm flowchart

步驟 2 將生成的最小項(xiàng)存儲(chǔ)在2 棵二叉樹中，通過(guò)基于二叉樹的混合極性轉(zhuǎn)換算法轉(zhuǎn)換到0 極性。

步驟 3 設(shè)置算法的最大迭代次數(shù)Iter，歷史迭代次數(shù)history_iter=0，種群規(guī)模N。

步驟 4 初始化鯨魚優(yōu)化算法參數(shù)和種群，設(shè)置當(dāng)前迭代次數(shù)now_iter=0，記錄種群的最優(yōu)值。

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

步驟 6 計(jì)算種群的適應(yīng)度值，確定最優(yōu)值。

步驟 7 執(zhí)行爆炸機(jī)制，在最優(yōu)值附近搜索是否還有更優(yōu)的解。如果存在更優(yōu)的解，更新最優(yōu)解的相關(guān)信息。再判斷最優(yōu)解是否好于全局最優(yōu)解，如果好于全局最優(yōu)解，更新全局最優(yōu)解的相關(guān)信息。

步驟 8如果最優(yōu)值連續(xù)n代沒(méi)有變化，執(zhí)行步驟10，否則執(zhí)行步驟9。

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

步驟 10history_iter++，如果history_iter

執(zhí)行重啟機(jī)制，返回步驟4。否則結(jié)束算法，輸出全局最優(yōu)值。

4 實(shí)驗(yàn)結(jié)果及分析

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

改進(jìn)的鯨魚優(yōu)化算法的參數(shù)通過(guò)引入5 因素4 水平的正交表確定。鯨魚優(yōu)化算法、遺傳算法(GA)和人工蜂群算法(ABC)的參數(shù)通過(guò)大量實(shí)驗(yàn)獲得。為了公平比較各個(gè)算法，設(shè)置評(píng)估次數(shù)4 000作為每個(gè)算法的結(jié)束條件。算法參數(shù)設(shè)置如表1所示。

表1 算法參數(shù)Table 1 Algorithm parameters

4.1 混合極性轉(zhuǎn)換算法驗(yàn)證

為測(cè)試改進(jìn)以后的混合極性轉(zhuǎn)換的效率，選取13 個(gè)標(biāo)準(zhǔn)MCNC Benchmark 電路進(jìn)行測(cè)試。進(jìn)行混合極性轉(zhuǎn)換效率的測(cè)試時(shí)，將選擇電路的最小項(xiàng)轉(zhuǎn)換到0 極性。測(cè)試方法為：對(duì)每個(gè)電路獨(dú)立運(yùn)行10 次，統(tǒng)計(jì)每次從最小項(xiàng)轉(zhuǎn)換到0 極性的運(yùn)行時(shí)間，取10 次運(yùn)行時(shí)間的平均值。算法1 表示基于列表技術(shù)的極性轉(zhuǎn)換算法，算法2 表示基于二叉樹的極性轉(zhuǎn)換算法。為了驗(yàn)證算法2 的正確性，執(zhí)行極性轉(zhuǎn)換算法的同時(shí)計(jì)算MPRM 表達(dá)式的面積。area1 表示通過(guò)算法1 進(jìn)行極性轉(zhuǎn)換得到的面積，area2 表示通過(guò)算法2 進(jìn)行極性轉(zhuǎn)換得到的面積。I/O 分別代表電路的輸入位數(shù)和輸出位數(shù)。Rsave表示算法2 比算法1 節(jié)省時(shí)間的百分比，具體計(jì)算公式為

式中：TimeALGO_1為算法1 的平均運(yùn)行時(shí)間；TimeALGO_2為算法2 的平均運(yùn)行時(shí)間。

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

表2 混合極性轉(zhuǎn)換實(shí)驗(yàn)數(shù)據(jù)Table 2 Experimental data of mixed polarity conversion

4.2 極性間轉(zhuǎn)換算法驗(yàn)證

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

從表3 可以看出，對(duì)于電路misex1、ex1010，算法3 的運(yùn)行時(shí)間和算法4 相同。對(duì)于表中的其他電路，算法3 的運(yùn)行時(shí)間長(zhǎng)于算法4 的運(yùn)行時(shí)間。特別是對(duì)于電路mark1，算法3 的運(yùn)行時(shí)間達(dá)到了15 102.41 s，而算法4 的運(yùn)行時(shí)間只有6.42 s。出現(xiàn)以上實(shí)驗(yàn)結(jié)果的原因可能受與項(xiàng)個(gè)數(shù)、去除重復(fù)的與項(xiàng)操作、生成新與項(xiàng)操作的影響。

表3 極性間轉(zhuǎn)換實(shí)驗(yàn)數(shù)據(jù)Table 3 Experimental data for conversion between different polarities

4.3 多輸出MPRM 電路面積優(yōu)化效果驗(yàn)證

為了測(cè)試改進(jìn)的鯨魚算法的優(yōu)化效果，選擇WOA、GA、ABC 作比較實(shí)驗(yàn)。通過(guò)式(11)得到節(jié)省電路面積百分比：

式中：AVEOTHER_ALGO為WOA、GA、ABC 三個(gè)算法在每個(gè)電路上運(yùn)行20 次得到的最優(yōu)值的平均值；AVEERWOA為ERWOA 算法在每個(gè)電路上運(yùn)行20 次得到的最優(yōu)值的平均值。從表4 中可以看出，相比于WOA、GA、ABC，EROWA 的標(biāo)準(zhǔn)差為0 的個(gè)數(shù)達(dá)到了8 個(gè)。和WOA 相比，ERWOA 的平均電路面積節(jié)省為3.45%，最大平均電路面積節(jié)省為9.72%。和GA 相比，ERWOA 的平均電路面積節(jié)省為5.54%，最大平均電路面積節(jié)省為18.32%。相比于ABC，ERWOA 的平均電路面積節(jié)省為5.00%，最大平均電路面積節(jié)省為14.41%。

表4 算法實(shí)驗(yàn)數(shù)據(jù)Table 4 Experiment data of algorithm

通過(guò)以上數(shù)據(jù)說(shuō)明，ERWOA 在穩(wěn)定性和搜索能力方面均優(yōu)于WOA、GA、ABC。出現(xiàn)上述實(shí)驗(yàn)結(jié)果的原因可能如下:

1）WOA、GA、ABC 容易陷入局部最優(yōu)解且不容易跳出。因?yàn)镋RWOA 引入了重啟機(jī)制，所以可以有效跳出局部最優(yōu)解，從而增強(qiáng)了算法的穩(wěn)定性。

2）WOA、GA、ABC 搜索精度比ERWOA 低。因?yàn)镋RWOA 引入了爆炸機(jī)制，所以可以在有限的迭代次數(shù)內(nèi)搜索到更優(yōu)解。

4.4 收斂性對(duì)比

為了進(jìn)一步說(shuō)明ERWOA 算法的性能，選擇4 個(gè)測(cè)試電路繪制收斂曲線。其中，橫坐標(biāo)代表算法前30 次的迭代次數(shù)，縱坐標(biāo)代表算法運(yùn)行20 次找到的面積的平均值。

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

圖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 結(jié) 論

本文提出一種基于爆炸機(jī)制和重啟機(jī)制的鯨魚優(yōu)化算法用于求解基于MPRM 電路的面積優(yōu)化問(wèn)題，主要結(jié)論如下:

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

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