基于SADPSO的MPRM最小化算法

卜登立

(1. 井岡山大學(xué) 電子與信息工程學(xué)院，江西 吉安 343009；2. 同濟(jì)大學(xué) 軟件學(xué)院，上海 201804)

?

基于SADPSO的MPRM最小化算法

卜登立1,2

(1. 井岡山大學(xué) 電子與信息工程學(xué)院，江西 吉安 343009；2. 同濟(jì)大學(xué) 軟件學(xué)院，上海 201804)

摘要：針對混合極性Reed-Muller (mixed-polarity Reed-Muller, MPRM) 邏輯最小化問題，提出一種基于SADPSO (hybrid simulated annealing and discrete particle swarm optimization) 的智能算法。該算法將模擬退火 (simulated annealing, SA) 與離散粒子群優(yōu)化 (discrete particle swarm optimization, DPSO) 相結(jié)合，對DPSO所得到的最佳解應(yīng)用SA，幫助算法跳出局部極小。使用所提出算法和已有智能MPRM最小化算法分別對23個MCNC基準(zhǔn)電路進(jìn)行邏輯最小化，并對算法結(jié)果質(zhì)量進(jìn)行定量評價。結(jié)果表明，與已有智能MPRM最小化算法相比，所提出算法具有更好的全局收斂能力，能夠提高算法結(jié)果質(zhì)量。

關(guān)鍵詞：混合極性Reed-Muller; 邏輯最小化; 智能算法; 模擬退火; 離散粒子群優(yōu)化

0引言

Reed-Muller(RM)邏輯是布爾函數(shù)基于AND/XOR的表示，對于線性電路、通信系統(tǒng)和算術(shù)邏輯等電路而言，與基于AND/OR的布爾邏輯相比，RM邏輯可獲得面積、功耗和可測性方面的優(yōu)勢[1-2]?；旌蠘O性RM(mixed-polarity Reed-Muller, MPRM)是一種RM標(biāo)準(zhǔn)形表示，相對于固定極性RM(fixed-polarity Reed-Muller, FPRM)，MPRM有可能獲得更為簡潔的表示，因此，MPRM的最小化問題得到了廣泛的關(guān)注。

MPRM最小化是RM電路邏輯綜合過程中一個非常重要的階段，由于MPRM最小化問題屬于NP難優(yōu)化問題[2]，因此，對輸入數(shù)較多的電路，研究者傾向于采用智能優(yōu)化方法來完成MPRM最小化。在MPRM中，變量的極性屬性有3種類型[1]，由于智能優(yōu)化算法在進(jìn)行編碼選擇時需要遵守完備性、健全性和非冗余性3個基本原則[3]，因此，對于MPRM最小化不宜使用類似于FPRM最小化時常采用的二進(jìn)制編碼[4]，而應(yīng)使用三進(jìn)制編碼。因此，MPRM最小化問題屬于多值離散優(yōu)化問題[5]。

本文首先對當(dāng)前的智能MPRM最小化算法進(jìn)行概述，然后提出一種基于模擬退火離散粒子群優(yōu)化(hybrid simulated annealing and discrete particle swarm optimization, SADPSO)的元啟發(fā)式MPRM最小化算法，通過將模擬退火(simulated annealing, SA)與離散粒子群優(yōu)化(discrete particle swarm optimization, DPSO)相結(jié)合，在每次迭代中使用SA對DPSO所搜索到的最佳解實(shí)施退火操作，增強(qiáng)算法的全局收斂能力。將之應(yīng)用于輸入數(shù)較多的電路，并與文獻(xiàn)[1-2,5]中的算法進(jìn)行了比較。

1智能MPRM最小化算法概述

1.1MPRM最小化

一個n個輸入m個輸出的多輸出布爾函數(shù)，將n個變量按照一定順序進(jìn)行分解，可以得到如(1)式所示的MPRM標(biāo)準(zhǔn)形[1]。

(1)

MPRM最小化通過對極性值進(jìn)行選擇以使得(1)式中的非零系數(shù)向量個數(shù)最少，即使MPRM表達(dá)式所包含的乘積項(xiàng)數(shù)最少。對于一個包含n個變量的完全確定布爾函數(shù)，其極性空間大小為3n，每個極性值可以確定一個如(1)式所示的MPRM。因此，MPRM最小化問題可以轉(zhuǎn)化為求解最優(yōu)極性值的問題，并描述為[2]

(2)

(2)式中，C(h)為成本函數(shù)，其值為極性值為h的MPRM表達(dá)式中所包含乘積項(xiàng)的個數(shù)。

1.2智能最小化算法概述

當(dāng)前用于MPRM最小化的智能算法從算法主體角度可以分為基于遺傳算法(geneticalgorithm,GA)的[1-2,6]和基于DPSO的[5, 7]兩大類。

文獻(xiàn)[6]將進(jìn)化策略(evolutionarystrategy,ES)與GA相結(jié)合，采用(μ+1)-ES策略(μ為種群大小)，每次生成一個子個體，生成子個體時，采用錦標(biāo)賽選擇策略選擇錦標(biāo)賽規(guī)模內(nèi)的最佳個體進(jìn)行交叉；當(dāng)種群再生時，采用錦標(biāo)賽替換策略替換掉錦標(biāo)賽規(guī)模內(nèi)最差的個體。但是(μ+1)-ES策略有著降低變異強(qiáng)度的傾向，會對算法的性能產(chǎn)生非常大的影響[8]。文獻(xiàn)[1]也將ES與GA相結(jié)合，但與文獻(xiàn)[6]不同，其采用了(μ+λ)-ES策略，在種群進(jìn)化時，每次生成λ(λ>1)個新個體。

對于輸入數(shù)較多的電路，采用遺傳算法可能由于過早收斂而無法得到全局最優(yōu)解[2]，因此文獻(xiàn)[2]給出了一種基于模擬退火遺傳算法(simulated annealing genetic algorithm, SAGA) 的算法，通過在GA中加入模擬退火過程避免搜索陷入到局部極小，從而改善算法的結(jié)果，采用SAGA能夠獲得比GA更好的結(jié)果和性能[2]。

粒子群優(yōu)化(particle swarm optimization, PSO)作為一種新的群智能優(yōu)化算法，已被廣泛地應(yīng)用于各種復(fù)雜的優(yōu)化領(lǐng)域[3,9-10]，近年來也被應(yīng)用于MPRM最小化問題[5, 7]。文獻(xiàn)[7]使用三進(jìn)制編碼，給出了一種用于MPRM最小化的DPSO算法，但是標(biāo)準(zhǔn)DPSO存在著多樣性損失導(dǎo)致的過早收斂問題[5, 11]，盡管該算法在由連續(xù)域映射到三進(jìn)制離散域的過程中引入了隨機(jī)因素，但是文中并未對算法結(jié)果的質(zhì)量進(jìn)行定量評價。

文獻(xiàn)[5]針對標(biāo)準(zhǔn)DPSO的過早收斂問題，提出了一種基于HDPSO(hybrid multi-valued DPSO)的算法，該算法采用多群策略，并在DPSO中引入了GA中的一些要素，如在粒子位置更新過程中引入概率變異策略及沒有重復(fù)的更新策略來維持粒子的多樣性，并加入了群間重復(fù)最佳變異策略來避免群間的碰撞，以使多個群盡可能搜索優(yōu)化空間中不同的子空間，避免算法陷入局部極小，增強(qiáng)全局搜索能力。文獻(xiàn)[5]使用基于列表技術(shù)的極性轉(zhuǎn)換方法進(jìn)行極性轉(zhuǎn)換，將HDPSO在算法結(jié)果質(zhì)量和時間效率方面與SAGA進(jìn)行了對比，得出了HDPSO在時間效率上要優(yōu)于SAGA的結(jié)論。

2SA結(jié)合DPSO的MPRM最小化算法

2.1MPRM極性轉(zhuǎn)換

在MPRM最小化過程中需要進(jìn)行MPRM極性轉(zhuǎn)換，以得到不同形式的MPRM?；贠KFDD (ordered Kronecker functional decision diagram)的極性轉(zhuǎn)換方法采用OKFDD表示電路，位于OKFDD中同一層變量的分解類型相同。如果將OKFDD中由根結(jié)點(diǎn)到值為1的葉結(jié)點(diǎn)且能夠得到一個乘積項(xiàng)的路徑稱為有效1路徑，那么遍歷OKFDD中的有效1路徑即可得到如(1)式所示的MPRM表達(dá)式[12]。對于多輸出布爾函數(shù)，可以采用基于共享OKFDDs的極性轉(zhuǎn)換方法[12]，共享OKFDDs在多個輸出的OKFDD之間共享子圖。使用共享OKFDDs表示MPRM，可通過統(tǒng)計(jì)共享OKFDDs中有效1路徑的數(shù)量來統(tǒng)計(jì)MPRM表達(dá)式中乘積項(xiàng)的個數(shù)。

由于OKFDDs是簡約表示[12]，與基于系數(shù)矩陣[1]和列表技術(shù)[2]的極性轉(zhuǎn)換方法相比，基于共享OKFDDs的極性轉(zhuǎn)換方法有可能得到更為緊湊的MPRM表示。因此，本文在進(jìn)行MPRM最小化時采用基于共享OKFDDs的極性轉(zhuǎn)換方法。

2.2編碼和成本函數(shù)

由于MPRM中變量的極性屬性為三進(jìn)制表示，因此選擇三進(jìn)制編碼[5]，并將極性向量作為粒子的位置向量Dj=[dj,n-1,…,dj,0]，dj,l表示粒子群中索引為j的粒子在n維搜索空間中第l維的位置，即MPRM第l個變量的極性屬性。

所采用的成本函數(shù)為(2)式中的C(h)，在計(jì)算C(h)時，先根據(jù)極性向量對OKFDDs進(jìn)行極性轉(zhuǎn)換，然后再統(tǒng)計(jì)其中有效1路徑的數(shù)量。

2.3SADPSO算法

DPSO算法是一種全局搜索算法，雖具有較快的收斂速度，但卻存在著過早收斂問題[5, 11]。SA具有較強(qiáng)的局部搜索能力，通過引入隨機(jī)搜索并在搜索過程中以一定概率接受惡化解，從而可以使搜索跳出局部極小[13-14]。

本文提出的SADPSO算法根據(jù)DPSO的快速收斂特點(diǎn)和SA較強(qiáng)局部搜索能力的特點(diǎn)，將SA與DPSO相結(jié)合，利用SA跳出局部極小，避免DPSO的過早收斂問題，以增強(qiáng)全局收斂能力。

2.3.1DPSO算法

假設(shè)粒子的速度向量用Vj=[vj,n-1,…,vj,0]表示，vj,l表示群中索引為j的粒子在n維搜索空間中第l維的速度，第j個粒子的個體歷史最佳位置用Pj=[pj,n-1,…,pj,0]表示，粒子群的全局最佳位置用G=[gn-1,…,g0]表示，則粒子的速度更新公式為

(3)

(3)式中：W為慣性權(quán)重；C1和C2分別為認(rèn)知和社會尺度參數(shù)；r1和r2是在[0,1]均勻分布的隨機(jī)數(shù)；上標(biāo)t表示第t次迭代。另外，速度限制參數(shù)Vmax可以改善搜索的分辨率[5]。

本文DPSO所采用的粒子位置更新公式為[5]

(4)

(4)式中，?y」為下取整函數(shù)。

算法1給出在SADPSO的一次迭代過程中的DPSO算法，其中N為粒子群規(guī)模。

算法1DPSO算法。

1)令j=0；

黔南州合作社大多設(shè)置較低的入社門檻并積極吸納小農(nóng)戶社員，帶動小農(nóng)戶的意愿較強(qiáng)。統(tǒng)計(jì)結(jié)果顯示，42家合作社都在積極擴(kuò)大社員規(guī)模，占總樣本量的85.71%；不設(shè)置入社門檻的合作社為29家，占樣本量的61.70%；僅有2家合作社設(shè)置最低種植規(guī)模門檻。值得注意的是，隨著“村社合一”模式的大力推廣，黔南州出現(xiàn)不少旨在帶動全村農(nóng)戶，尤其是貧困戶的“村社合一”型合作社，在帶動小農(nóng)戶發(fā)展方面發(fā)揮了重要作用。這類合作社是由村干部領(lǐng)辦組建，以村集體資產(chǎn)或扶貧項(xiàng)目資金幫助全村農(nóng)戶或貧困戶入股，通過抱團(tuán)發(fā)展產(chǎn)業(yè)帶動全村農(nóng)戶發(fā)展。在49家樣本合作社中有9家“村社合一”型合作社。

2)令l=0；

3)分別根據(jù)(3)式和(4)式更新vj,l和dj,l，并令l=l+1，如果l

4)令j=j+1，如果j

2.3.2SA算法

SA與有限長度馬爾可夫鏈相對應(yīng)，由一個初始狀態(tài)開始，每一步狀態(tài)的轉(zhuǎn)移都是在當(dāng)前狀態(tài)Su的鄰域N(Su)中隨機(jī)產(chǎn)生新狀態(tài)Sv，然后根據(jù)Metropolis準(zhǔn)則接受新狀態(tài)。狀態(tài)轉(zhuǎn)移概率如(5)式所示[13]。

(5)

(5)式中：ΔCuv=C(Su)-C(Sv)為成本函數(shù)差值；Tt為第t次迭代時的溫度。

SA從初始溫度T0開始，對每一溫度Tt按(5)式所示轉(zhuǎn)移概率進(jìn)行隨機(jī)搜索，直至平穩(wěn)分布[13]，然后根據(jù)退溫函數(shù)降溫，直至達(dá)到冷凍狀態(tài)[14]，此時得到的平穩(wěn)分布即為所搜索到的最優(yōu)解。

初始溫度T0的選擇會影響算法的結(jié)果和效率，本文通過n2[2]次隨機(jī)變換，使用成本函數(shù)的平均增量確定初始溫度[14]。假設(shè)初始接受概率為pa，則初始溫度可由(6)式計(jì)算。

(6)

退溫函數(shù)采用如(7)式所示的指數(shù)冷卻調(diào)度方案[2, 15]。

(7)

算法2給出在SADPSO算法的一次迭代過程中的SA算法，其中，OD為DPSO所得到的最佳解，L=N×n[2]為馬爾可夫鏈的最大長度。狀態(tài)Su由極性向量Du表示，其鄰域N(Su)由與Du格雷碼距為1的極性向量構(gòu)成。

算法2SA算法。

1)將OD作為SA的初始狀態(tài)S0，計(jì)算C(S0)；令b=0，u=0；

2)從狀態(tài)Su的鄰域N(Su)隨機(jī)產(chǎn)生新狀態(tài)Sv，計(jì)算C(Sv)和ΔCuv，并按(5)式所示的概率接受新狀態(tài)Sv，如果Sv不被接受，則轉(zhuǎn)步驟3)，否則令u=u+1，Su=Sv；如果u

3)令b=b+1，如果b

4)將上述過程得到的最優(yōu)解OS與OD進(jìn)行競爭，如果OS的成本小于OD的成本，則使用OS替換OD，并更新OD的歷史最佳信息。

2.3.3算法結(jié)束條件

本文從兩方面來考慮SADPSO算法的結(jié)束條件。如果DPSO的尋優(yōu)結(jié)果沒有改變所累計(jì)的次數(shù)達(dá)到20×ln(n)[5]則結(jié)束算法。隨著溫度的衰減，SA接受惡化解的概率逐漸減小，SA將收斂于最優(yōu)解。因此，如果在一次模擬退火過程中，沒有被接受新狀態(tài)的比例達(dá)到50%則結(jié)束算法[2]。

2.3.4SADPSO算法描述

下面給出DPSO和SA結(jié)合并用于MPRM最小化的SADPSO算法。

算法3SADPSO算法。

1)初始化DPSO和SA相關(guān)參數(shù)；

2)讀取邏輯網(wǎng)表并轉(zhuǎn)換為OKFDDs；

4)生成初始粒子群，計(jì)算群中粒子的成本，并更新粒子的個體歷史最佳及全局最佳；

5)迭代次數(shù)初始化為0；

6)運(yùn)行算法2，如果新狀態(tài)Sv沒有被接受的比例達(dá)到50%，則轉(zhuǎn)步驟8)，否則采用(7)式進(jìn)行退溫操作，并轉(zhuǎn)步驟7)；

7)運(yùn)行算法1，迭代次數(shù)+1，計(jì)算群中粒子的成本，并更新粒子個體歷史最佳以及全局最佳，統(tǒng)計(jì)群最佳沒有改變所累計(jì)的次數(shù)，如果該次數(shù)等于20×ln(n)或迭代次數(shù)達(dá)到最大迭代次數(shù)則轉(zhuǎn)步驟8)，否則轉(zhuǎn)步驟6)；

8)輸出最優(yōu)MPRM結(jié)果，算法結(jié)束。

算法3的第4)和7)步，在計(jì)算群中粒子的成本函數(shù)值時，采用文獻(xiàn)[1]中基于最短個體距離的成本函數(shù)計(jì)算方法。

SADPSO利用SA對DPSO所搜索到的全局最佳解實(shí)施模擬退火操作，在DPSO進(jìn)行全局探索的同時，SA進(jìn)行局部精搜以改善DPSO的搜索效率[15]，從而增強(qiáng)全局收斂能力。由于SA能夠?qū)崿F(xiàn)較好的局部精搜，因此DPSO應(yīng)該著力于全局探索，在參數(shù)設(shè)置時，可通過設(shè)置較大的W值來實(shí)現(xiàn)這個目的。

3實(shí)驗(yàn)設(shè)置及結(jié)果分析

為進(jìn)行驗(yàn)證和分析，將本文的SADPSO算法與文獻(xiàn)[1]中的GAES、文獻(xiàn)[2]中的SAGA算法以及文獻(xiàn)[5]中的HDPSO算法進(jìn)行比較。4種算法均采用基于共享OKFDDs的MPRM極性轉(zhuǎn)換方法，以及(2)式的成本函數(shù)和優(yōu)化目標(biāo)，并用C++實(shí)現(xiàn)，在Linux下使用g++編譯器編譯。使4種算法分別對一組輸入數(shù)大于14的MCNC基準(zhǔn)電路在配置為IntelCorei3-2350MCPU6GBRAM的個人計(jì)算機(jī)上進(jìn)行MPRM最小化。

3.1實(shí)驗(yàn)設(shè)置

SADPSO中的DPSO的參數(shù)設(shè)定為N=30，W=1.2，C1=C2=2，Vmax=4，SA的參數(shù)設(shè)定與文獻(xiàn)[2]相同。HDPSO算法的參數(shù)與文獻(xiàn)[5]相同。SAGA中GA的種群規(guī)模設(shè)定為30，SAGA除了根據(jù)接受概率設(shè)置結(jié)束條件外，如果GA的尋優(yōu)結(jié)果沒有改變的累計(jì)次數(shù)達(dá)到20×ln(n)也將結(jié)束SAGA。GAES的種群規(guī)模也為30，由于本文是對輸入數(shù)較多的電路進(jìn)行MPRM最小化，因此選擇次數(shù)參數(shù)設(shè)為8，如果在達(dá)到最大迭代次數(shù)之前，尋優(yōu)結(jié)果沒有改變累計(jì)次數(shù)達(dá)到20×ln(n)也將結(jié)束GAES，其他參數(shù)與文獻(xiàn)[1]相同。4種算法的最大迭代次數(shù)均設(shè)定為180。

由于4種算法均具有一定的隨機(jī)特性，因此實(shí)驗(yàn)中對于每個基準(zhǔn)電路，每種算法均獨(dú)立運(yùn)行20次，并統(tǒng)計(jì)運(yùn)行結(jié)果的最小值、均值和標(biāo)準(zhǔn)差，以及算法迭代次數(shù)和所花費(fèi)CPU時間的平均值。

3.2結(jié)果分析

表1給出了4種算法的運(yùn)行結(jié)果，其中“I/O”表示電路的輸入數(shù)和輸出數(shù)，min，avg和std分別表示算法20次獨(dú)立運(yùn)行所得到的最優(yōu)MPRM所包含乘積項(xiàng)數(shù)的最小值、均值及標(biāo)準(zhǔn)差。

從表1中算法多次獨(dú)立運(yùn)行的結(jié)果可以看出，GAES對于很多電路均不能穩(wěn)定地得到MPRM最小結(jié)果，特別是對于電路ts10，算法結(jié)果的均值和標(biāo)準(zhǔn)差均比較大，算法不能很好地收斂于全局最優(yōu)解。可見，對于輸入數(shù)較多的電路，GAES不能很好地解決過早收斂的問題。

對于SADPSO，HDPSO和SAGA，3種算法能夠得到基本類似的結(jié)果，除電路ts10和mux外，3種算法結(jié)果的最小值都相同，均值也基本相同，均值都等于或者非常接近最小值，并且對于某些電路而言，這3種算法均能穩(wěn)定地獲得最小MPRM結(jié)果，對其余電路而言，標(biāo)準(zhǔn)差也都比較小。對于能夠穩(wěn)定地得到最小MPRM結(jié)果的電路，SADPSO共有19個，比例達(dá)到82.61%，HDPSO共有11個(不包括ts10和mux)，比例為47.83%，SAGA共有14個，比例為60.87%。對于電路ts10和mux，盡管20次獨(dú)立運(yùn)行HDPSO都能夠得到乘積項(xiàng)數(shù)分別為136和17的結(jié)果，但該結(jié)果并不是最小結(jié)果，而SADPSO與SAGA盡管不能穩(wěn)定地獲得最小結(jié)果，但是卻具備搜索到最小結(jié)果的能力。從多次獨(dú)立運(yùn)行能夠穩(wěn)定獲得最小解的比例來看，SADPSO最高，這表明SADPSO具有非常強(qiáng)的全局收斂能力。

為進(jìn)一步比較，圖1給出了3種算法結(jié)果的變異系數(shù)[5](其中，不包括3種算法變異系數(shù)均為0的結(jié)果)，變異系數(shù)可用來衡量不同均值時數(shù)據(jù)的穩(wěn)定性。由圖1可以看出，SADPSO具有最好的結(jié)果穩(wěn)定性，HDPSO次之，SAGA由于存在著較高的尖峰(cm150a)，穩(wěn)定性相對較差。

表2給出了4種算法分別20次獨(dú)立對基準(zhǔn)電路進(jìn)行MPRM最小化所花費(fèi)的CPU時間(time)和算法迭代次數(shù)(iter)的平均值，時間的單位為秒。

由表2中的平均結(jié)果可以看出，從算法時間效率上來看，盡管GAES所用的迭代次數(shù)最多，但時間效率最高，這是因?yàn)镚AES每次迭代過程僅生成少量的新個體，計(jì)算新個體適應(yīng)度所花費(fèi)的時間較少。盡管時間效率較高，但是對于某些電路，如ts10，由于算法容易陷入局部極小而導(dǎo)致過早收斂，犧牲了算法結(jié)果的質(zhì)量。

對于算法SADPSO，HDPSO和SAGA，從時間效率角度來看，HDPSO最優(yōu)，SADPSO與SAGA時間效率相對較低，但是SADPSO略優(yōu)于SAGA。從迭代次數(shù)角度來看，SADPSO最少，SAGA次之，HDPSO所需迭代次數(shù)最多。雖然對于大部分電路而言，SADPSO與SAGA算法迭代次數(shù)均比HDPSO少，但是由于SADPSO和SAGA算法在迭代過程中加入了較為耗時的模擬退火操作，每次迭代過程所花費(fèi)的時間要比 HDPSO 長。另外，SA確定初始溫度的過程也使算法所花費(fèi)的時間有所增加。盡管SADPSO采用了與SAGA類似的模擬退火過程以及相同的SA參數(shù)，但SADPSO算法所需迭代次數(shù)以及所花費(fèi)的時間要低于SAGA，這說明了DPSO比GA具有更快的收斂速度。

綜上所述，從總體角度來看，與SAGA相比，SADPSO具有較高的穩(wěn)定性和較高的時間效率，SADPSO能夠穩(wěn)定獲得最小解電路的個數(shù)是SAGA的1.36倍，算法時間效率相對SAGA提高了5.82%。和HDPSO相比，雖然算法時間是HDPSO的2.26倍，但SADPSO具有非常高的穩(wěn)定性，SADPSO能夠穩(wěn)定獲得最小解電路的個數(shù)是HDPSO的1.73倍。由于SADPSO具有非常強(qiáng)的全局收斂能力，因此SADPSO也是MPRM最小化一個較好的選擇。

表2　4種算法的迭代次數(shù)以及時間

4結(jié)束語

由于MPRM存在著指數(shù)級大小的極性空間，對于輸入數(shù)較多的電路，想要在合理時間內(nèi)得到最小MPRM，經(jīng)常采用智能優(yōu)化方法。本文對當(dāng)前的智能MPRM最小化算法作了概述，并提出一種基于SADPSO的MPRM最小化算法，該算法將DPSO和SA相結(jié)合，使用SA對DPSO所得到的最佳解實(shí)施模擬退火操作。實(shí)驗(yàn)結(jié)果驗(yàn)證了所提出算法的有效性，DPSO與SA能夠很好地進(jìn)行互補(bǔ)，DPSO進(jìn)行全局探索，SA則進(jìn)行局部精搜，避免了標(biāo)準(zhǔn)DPSO存在的過早收斂問題，增強(qiáng)了全局收斂能力。與HDPSO相比，SADPSO具有更高的結(jié)果質(zhì)量，和SAGA相比，SADPSO具有較高的結(jié)果質(zhì)量和較高的時間效率。

參考文獻(xiàn)：

[1]卜登立, 江建慧. 使用系數(shù)矩陣變換極性轉(zhuǎn)換的MPRM電路面積優(yōu)化[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2013, 25(1): 126-135.

BU Dengli, JIANG Jianhui. Area optimization of MPRM circuits utilizing coefficient matrix transformation based polarity conversion[J]. Journal of Computer-Aided Design & Computer Graphics, 2013, 25(1): 126-135.

[2]WANG P, LI H, WANG Z. MPRM expressions minimization based on simulated annealing genetic algorithm [C]//IEEE. Proceedings of the 2010 International Conference on Intelligent Systems and Knowledge Engineering. New York, USA: IEEE Press, 2010: 261-265.

[3]郭文忠, 陳國龍, XIONG Naixue, 等. 求解VLSI電路劃分問題的混合粒子群優(yōu)化算法[J]. 軟件學(xué)報(bào), 2011, 22(5): 833-842.

GUO Wenzhong, CHEN Guolong, XIONG Naixue, et al. Hybrid particle swarm optimization algorithm for VLSI circuit partitioning[J]. Journal of Software, 2011, 22(5): 833-842.

[4]ZHANG H, WANG P, GU X. Area optimization of fixed-polarity Reed-Muller circuits based on niche genetic algorithm[J]. Chinese Journal of Electronics, 2011, 20(1): 27-30.

[5]卜登立, 江建慧. 基于混合多值離散粒子群優(yōu)化的混合極性Reed-Muller最小化算法[J]. 電子與信息學(xué)報(bào), 2013, 35(2): 361-367.

BU Dengli, JIANG Jianhui. Hybrid multi-valued discrete particle swarm optimization algorithm for mixed-polarity Reed-Muller minimization[J]. Journal of Electronics & Information Technology, 2013, 35(2): 361-367.

[6]AL-JASSANI B A, URQUHART N, ALMAINI A E A. Manipulation and optimisation techniques for Boolean logic[J]. IET Computers and Digital Techniques, 2010, 4(3): 227-239.

[7]YU H, WANG P, WANG D, et al. Discrete ternary particle swarm optimization for area optimization of MPRM circuits[J]. Journal of Semiconductors, 2013, 34(2): 118-123.

[8]BEYER H G, SCHWEFEL H P. Evolution strategies: a comprehensive introduction[J]. Natural Computing, 2002, 1(1): 3-52.

[9]BANKS A, VINCENT J, ANYAKOHA C. A review of particle swarm optimization. Part I: background and development[J]. Natural Computing, 2007, 6(4): 467-484.

[10] 周相兵. 一種基于粒子群優(yōu)化的虛擬資源分配方法[J]. 重慶郵電大學(xué)學(xué)報(bào): 自然科學(xué)版, 2014, 26(5): 686-693.

ZHOU Xiangbing. An optimization approach of virtual resources allocation based on particle swarm algorithm[J]. Journal of Chongqing University of Post and Telecommunications: Natural Science Edition, 2014, 26(5): 686-693.

[11] BLACKWELL T, BRANKE J. Multi-swarm optimization in dynamic environments[J]. Lecture Notes in Computer Science, 2004, 3005: 489-500.

[12] DRECHSLER R, BECKER B. Ordered Kronecker functional decision diagrams-a data structure for representation and manipulation of Boolean functions[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 1998, 17(10): 965-973.

[13] GLOVER F, KOCHENBERGER G A. Handbook of metaheuristics[M]. New York: Springer, 2003: 287-319.

[14] KOUVELIS P, CHIANG W C. A simulated annealing procedure for single row layout problems in flexible manufacturing systems[J]. International Journal of Production Research, 1992, 30(4): 717-732.

[15] LV H, LU C, ZHA J. A hybrid DPSO-SA approach to assembly sequence planning [C]// IEEE. Proceedings of the 2010 International Conference on Mechatronics and Automation. New York, USA: IEEE Press, 2010: 1998-2003.

MPRM minimization algorithm based on SADPSO

BU Dengli1,2

(1. School of Electronics and Information Engineering, Jinggangshan University, Ji’an 343009, P. R. China;2. School of Software Engineering, Tongji University, Shanghai 201804, P. R. China)

Abstract:A hybrid simulated annealing and discrete particle swarm optimization (SADPSO) based intelligent algorithm is proposed for mixed-polarity Reed-Muller (MPRM) logic minimization. The proposed algorithm combines simulated annealing (SA) and discrete particle swarm optimization (DPSO) by applying SA to the best solution obtained by DPSO to help the algorithm escape from local minima. Twenty-three MCNC benchmark circuits are minimized respectively by using the proposed algorithm and existing intelligent MPRM minimization algorithms, and the qualities of algorithm results are evaluated quantitatively for these algorithms. The results show that, compared to existing intelligent MPRM minimization algorithms, the proposed algorithm has better ability of global convergence, and can improve the qualities of algorithm results.

Keywords：mixed-polarity Reed-Muller; logic minimization; intelligent algorithm; simulated annealing; discrete particle swarm optimization

DOI：10.3979/j.issn.1673-825X.2016.02.014

收稿日期：2015-05-11

修訂日期：2015-07-08通訊作者：卜登立bodengli@163.com

基金項(xiàng)目：江西省自然科學(xué)基金(20122BAB201038)；江西省教育廳科技計(jì)劃項(xiàng)目(GJJ13538)

Foundation Items：The Natural Science Foundation of Jiangxi Province(20122BAB201038); The Science and Technology Project of the Education Department of Jiangxi Province(GJJ13538)

中圖分類號：TP331.2; TP391.72

文獻(xiàn)標(biāo)志碼：A

文章編號：1673-825X(2016)02-0226-07

作者簡介：

卜登立(1975-)，男，河北定州人，副教授，博士，主要研究方向?yàn)閂LSI設(shè)計(jì)和可靠性評估、智能優(yōu)化算法、計(jì)算機(jī)輔助設(shè)計(jì)。E-mail：bodengli@163.com。

(編輯：魏琴芳)