基于混合遺傳算法的MPRM最小化

卜 登 立

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

?

基于混合遺傳算法的MPRM最小化

卜 登 立1,2

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

摘要：MPRM(Mixed-Polarity Reed-Muller)最小化是RM(Reed-Muller)電路邏輯綜合過程中一個非常重要的階段，對于輸入數(shù)較多的布爾函數(shù)，傳統(tǒng)遺傳算法(Genetic Algorithm, GA)在解決MPRM最小化問題時收斂過早. 提出了一種基于混合遺傳算法(Hybrid Genetic Algorithm, HGA)的MPRM最小化算法，該算法將基于相異度的局部改善策略結(jié)合到GA算法的迭代過程中. 局部改善策略對種群中最佳個體和與之相異度最大的個體實(shí)施交叉操作生成新個體，并將新個體與最佳或最差個體進(jìn)行競爭. 將所提算法應(yīng)用于一組具有較多輸入數(shù)的MCNC基準(zhǔn)電路，并與其他智能MPRM最小化算法進(jìn)行比較. 結(jié)果表明，局部改善策略能夠避免算法陷入局部極小，增強(qiáng)了全局收斂能力. 與模擬退火遺傳算法(Simulated Annealing Genetic Algorithm, SAGA)相比，HGA算法在獲得類似結(jié)果的前提下提高了時間效率；與Hybrid multi-valued DPSO算法相比，HGA在得到基本相同的算法結(jié)果時，時間效率亦基本相同.

關(guān)鍵詞：混合極性Reed-Muller; 邏輯最小化; 遺傳算法; 相異度; 局部改善

BU Dengli1,2

(1.SchoolofElectronicsandInformationEngineering,JinggangshanUniversity,Ji’an343009,JiangxiProvince,China; 2.SchoolofSoftwareEngineering,TongjiUniversity,Shanghai201804,China)

布爾函數(shù)可由基于AND/OR的布爾邏輯表示，也可由基于AND/XOR的Reed-Muller(RM)邏輯表示. 對于線性電路、通信系統(tǒng)和算術(shù)邏輯等電路而言，相對于布爾邏輯，RM邏輯可獲得面積、功耗和可測性方面的優(yōu)勢[1-2]. 混合極性RM(Mixed-Polarity Reed-Muller, MPRM)是一種RM標(biāo)準(zhǔn)形表示，由于其對變量的出現(xiàn)形式?jīng)]有任何限制，因而能夠獲得較為簡潔的表示. MPRM最小化[2]即盡可能減少M(fèi)PRM多項(xiàng)式表示中的乘積項(xiàng)數(shù)，則有助于降低電路實(shí)現(xiàn)的面積開銷[1]. 因此，MPRM最小化成為RM電路邏輯綜合過程中一個非常重要的階段，并且得到了廣泛的關(guān)注.

本文針對MPRM最小化問題，提出一種基于混合遺傳算法(Hybrid Genetic Algorithm, HGA)的MPRM最小化算法，將基于相異度的局部改善策略與傳統(tǒng)GA相結(jié)合，避免算法陷入局部極小，以增強(qiáng)算法的全局收斂能力.并將之應(yīng)用于一組輸入數(shù)大于20的電路，再與文獻(xiàn)[2, 4]中的算法進(jìn)行比較.

1MPRM最小化

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

(1)

MPRM最小化通過對極性值進(jìn)行選擇使得式(1)所示的MPRM表達(dá)式中的非零系數(shù)向量個數(shù)最少，即令MPRM表達(dá)式所包含的乘積項(xiàng)數(shù)最少. MPRM最小化問題可以描述為[2]：

minC(h)，s.t.0≤h≤3n-1，

(2)

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

在MPRM最小化過程中需要進(jìn)行MPRM的極性轉(zhuǎn)換，當(dāng)前主要的極性轉(zhuǎn)換方法有基于系數(shù)矩陣的極性轉(zhuǎn)換方法[1]、列表轉(zhuǎn)換技術(shù)[2]以及基于OKFDD(OrderedKroneckerFunctionalDecisionDiagram)的極性轉(zhuǎn)換方法. 基于OKFDD的極性轉(zhuǎn)換方法采用OKFDD表示電路，位于OKFDD中同一層變量的分解類型相同. 在進(jìn)行極性轉(zhuǎn)換時，根據(jù)變量的極性屬性通過布爾操作改變OKFDD中變量的分解類型. 對于多輸出布爾函數(shù)，可以采用基于共享OKFDDs的極性轉(zhuǎn)換方法，在多個OKFDD之間共享OKFDDs子圖，由共享OKFDDs可以得到如式(1)所示的MPRM多項(xiàng)式[8].

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

2基于HGA的MPRM最小化算法

GA通過對問題的解進(jìn)行編碼，采用選擇、交叉、變異、替換等[9]一系列操作，令種群進(jìn)化，并以一定概率收斂于全局最優(yōu)解. 但對于輸入數(shù)較多的布爾函數(shù)的MPRM最小化問題，傳統(tǒng)GA存在過早收斂的問題[2].

本文通過將基于相異度的局部改善與GA相結(jié)合，在GA迭代過程中對種群進(jìn)行局部改善，使群算法跳出局部極小，以避免傳統(tǒng)GA存在的過早收斂問題，增強(qiáng)全局收斂能力.

2.1編碼和適應(yīng)度函數(shù)

GA在進(jìn)行編碼選擇時需要遵守完備性、健全性和非冗余性3個基本原則[10]. 由于MPRM中變量的極性為三進(jìn)制表示，因此選擇三進(jìn)制編碼，并將極性向量作為個體的基因編碼向量Dj=[dj,n-1,…,dj,0][4]，dj,l表示種群中索引為j的個體第l維的編碼，即MPRM第l個變量的極性.

采用的適應(yīng)度函數(shù)為式(2)中的C(h).

2.2GA基本操作

選擇操作：采用輪盤賭選擇，先根據(jù)個體適應(yīng)度值的倒數(shù)計算個體的累積概率，然后進(jìn)行選擇. 每一次選擇，均生成一個[0,1]的隨機(jī)數(shù)，使用該隨機(jī)數(shù)作為輪盤指針進(jìn)行選擇. 適應(yīng)度值較小的個體被選擇的概率較大，可以使該個體的基因能夠在種群中傳播.

交叉操作：采用單點(diǎn)交叉，即隨機(jī)生成一個交叉位置對2個父個體進(jìn)行交叉. 一定概率的交叉操作可以產(chǎn)生新個體，使種群得以進(jìn)化.

變異操作：采用單點(diǎn)變異，在進(jìn)行個體的變異運(yùn)算時，隨機(jī)改變一個基因，改變的值也是隨機(jī)產(chǎn)生的. 一定概率的變異操作，再結(jié)合交叉操作，可以擴(kuò)大搜索空間.

替換操作：采用錦標(biāo)賽替換方法[1]，從種群中隨機(jī)選擇一定數(shù)量(錦標(biāo)賽規(guī)模)的個體，并從中選取具有最大適應(yīng)度值的個體加以替換.為保持種群的多樣性，采用沒有重串的替換策略[9]，在進(jìn)行替換前，先判斷種群中是否存在相同基因編碼的個體，如果存在，則不進(jìn)行替換.

2.3基于相異度的局部改善策略

局部改善類似于局部搜索，目的是通過局部改善產(chǎn)生新個體，使算法有機(jī)會跳出局部極小.

假設(shè)已知2個個體的基因編碼分別為Di和Dj，那么根據(jù)式(3)計算其相異度D:

(3)

局部改善策略計算種群中所有個體相對于最佳個體的相異度，然后對最佳個體和具有最大相異度的個體進(jìn)行概率為1的單點(diǎn)交叉操作，生成一個新個體，計算其適應(yīng)度值，并與種群中的最佳個體進(jìn)行競爭，如果新個體的適應(yīng)度值小于最佳個體，則進(jìn)行替換；否則，與種群中最差個體進(jìn)行競爭，如果新個體優(yōu)于種群中的最差個體，則進(jìn)行替換.

局部改善策略是希望以當(dāng)前最佳個體為領(lǐng)袖，通過和相異度最大個體間的交叉運(yùn)算生成與當(dāng)前種群中個體位于不同空間的新個體，從而擴(kuò)大搜索空間. 因此，盡可能保留所產(chǎn)生的新個體，只有在新個體劣于種群中的最差個體時，才放棄此次改善.

由于局部改善策略總是通過對種群中的最佳個體和與之相異度最大的個體進(jìn)行概率為1的單點(diǎn)交叉操作產(chǎn)生新個體，并與最佳個體或最差個體進(jìn)行競爭，因此，局部改善策略不會增加任何算法參數(shù).

2.4HGA算法描述

下面給出結(jié)合局部改善策略和GA并用于MPRM最小化的HGA算法. 該算法對GA每次迭代的結(jié)果實(shí)施局部改善策略，如果滿足結(jié)束條件則結(jié)束算法，此時種群的全局最優(yōu)解即為算法的結(jié)果.

(1) 初始化GA相關(guān)參數(shù)：種群規(guī)模、錦標(biāo)賽規(guī)模、最大迭代次數(shù)、交叉概率和變異概率；

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

(3) 生成初始種群，計算種群中個體的適應(yīng)度值，并應(yīng)用基于相異度的局部改善策略；

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

(5) 使用選擇、交叉、變異算子生成臨時種群，并計算臨時種群中個體的適應(yīng)度；

(6) 根據(jù)錦標(biāo)賽替換策略使用臨時種群中的個體替換掉種群中的個體形成新種群；

(7) 對新種群應(yīng)用基于相異度的局部改善策略；

(8) 迭代次數(shù)+1，統(tǒng)計種群最優(yōu)累計沒有改善的次數(shù)，如果不滿足結(jié)束條件則轉(zhuǎn)步驟(5)；

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

在達(dá)到最大迭代次數(shù)之前，如果HGA的尋優(yōu)結(jié)果沒有改變，所累計的次數(shù)達(dá)到20×ln(n)[4]，算法也將結(jié)束.

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

為進(jìn)行分析，將本文的HGA算法與傳統(tǒng)GA算法(TGA)、文獻(xiàn)[2]中的SAGA算法以及文獻(xiàn)[4]中的HDPSO算法進(jìn)行了對比. 4種算法均采用基于共享OKFDDs的MPRM極性轉(zhuǎn)換方法，以及如式(2)所示的成本函數(shù)和優(yōu)化目標(biāo)，并用C++實(shí)現(xiàn)，在Linux下使用g++編譯器編譯. 使用4種算法分別對一組輸入數(shù)大于20的MCNC基準(zhǔn)電路在配置為Intel Core i3-2350M CPU 6 GB RAM的個人計算機(jī)上進(jìn)行了MPRM最小化.

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

共設(shè)置了2組實(shí)驗(yàn)，一是與TGA比較驗(yàn)證本文所提出的局部改善策略，二是與文獻(xiàn)[2]中基于SAGA以及文獻(xiàn)[4]中基于HDPSO的MPRM最小化算法進(jìn)行比較.

HGA的種群規(guī)模為30，錦標(biāo)賽規(guī)模為5，最大迭代次數(shù)為180，交叉概率為0.6，變異概率為0.2. TGA除了不采用局部改善策略外，其他均與HGA相同，參數(shù)設(shè)置也相同. HDPSO和SAGA的參數(shù)設(shè)置則采用文獻(xiàn)[4]和[2]中的設(shè)置.

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

3.2局部改善策略驗(yàn)證

表1給出了TGA以及HGA的運(yùn)行結(jié)果，其中“I/O”表示電路的輸入數(shù)和輸出數(shù).

由表1可以看出，除b03外，TGA能夠得到與HGA完全相同的最小值結(jié)果，但對于某些電路而言，TGA結(jié)果的均值和標(biāo)準(zhǔn)差偏大，如cordic、frg1、ts10和vg2，特別是電路cordic，結(jié)果的標(biāo)準(zhǔn)差達(dá)到了69.33. 可見，傳統(tǒng)GA存在過早收斂的問題，對于輸入數(shù)較多的電路，無法很好地解決其MPRM最小化問題. 對于HGA，由于采用了局部改善策略，使得算法精度大大提高，算法結(jié)果的均值等于或者非常接近于最小值，并且標(biāo)準(zhǔn)差也都小于5.

從算法效率角度看，對表1中所有電路，TGA的平均迭代次數(shù)為132，平均算法時間為5.63 s，而HGA的平均迭代次數(shù)為117，平均算法時間為4.72 s. 相對于TGA，HGA的平均迭代次數(shù)減少了11.36%，平均算法時間縮短了16.16%. 可見，HGA的算法效率要高于TGA.

綜上，將局部改善策略加入到GA的迭代過程中，避免了傳統(tǒng)GA容易陷入局部極小的問題，并且增強(qiáng)了全局收斂能力，提高了收斂速度.

表1　HGA與TGA算法的運(yùn)行結(jié)果

3.3與其他算法比較

表2給出了HDPSO和SAGA算法的運(yùn)行結(jié)果. 從表1和2中HGA、HDPSO和SAGA算法獨(dú)立運(yùn)行20次的結(jié)果可以看出，3種算法都能得到類似的結(jié)果，除電路mux、pcler8和ts10外，3種算法均能得到相同的最小值，均值也相差不大；對于mux和pcler8，HGA和SAGA所得結(jié)果要略優(yōu)于HDPSO，而對于ts10，盡管SAGA所得結(jié)果中“min”要優(yōu)于HDPSO和HGA，但是3種算法結(jié)果的“avg”卻基本相同. 從表1和2中HGA、HDPSO和SAGA算法結(jié)果中“min”“avg”的平均值來看，3種算法基本相同. 可見，3種算法能夠得到類似的結(jié)果精度.

為進(jìn)一步比較3種算法，圖1給出了3種算法結(jié)果的變異系數(shù)[4](圖1中不包括3種算法變異系數(shù)均為0的結(jié)果)，變異系數(shù)可用于衡量算法結(jié)果的穩(wěn)定性. 由圖1可以看出，從結(jié)果的穩(wěn)定性角度看，HDPSO相對要好一些，HGA與SAGA具有類似的結(jié)果穩(wěn)定性.

由表1和2中的“平均”一行結(jié)果可知，從算法的時間效率來看，SAGA時間效率相對較低，HGA與HDPSO時間效率基本相同. 從迭代次數(shù)來看，SAGA最少，HDPSO和HGA基本相同. 雖然SAGA算法迭代次數(shù)比HGA少，但由于SAGA在迭代過程中加入了相對較為耗時的模擬退火過程[4]，因此每次迭代過程所花費(fèi)的時間要比 HGA長.

綜上所述，HGA算法的時間效率高于SAGA，

HGA和HDPSO具有基本相同的算法結(jié)果和時間效率.

圖1　HDPSO、SAGA和HGA結(jié)果的變異系數(shù)Fig.1　Variation coefficients of results obtained by HDPSO, SAGA and HGA

電路HDPSOminavgstd時間/s迭代次數(shù)SAGAminavgstd時間/s迭代次數(shù)b03176179.10.837.78144176177.901.1829.99136b088787.900.443.511208790.506.0617.26124b10132132.651.014.83159132132016.07114c85555.100.302.03110555508.1989cc363600.5393363601.796cm150a1717.100.446.59911718.200.937.2361cordic129112954.904.610212911291.502.1822.25117duke2146146.601.0710.1169146146019.1170frg1181185.751.094.8122181185.251.7917.86119in7464602.13129464607.81118lal9797.300.93.35142979708.85105mux171705.311011616.100.305.5571pcler8333301.39833232.100.306.62128ts1013613607.9274128135.601.7429.4291vg238438409.6117384384020.9655平均188.93189.90-4.96117188.27189.54-14.59100

4結(jié)語

由于MPRM具有指數(shù)級的極性空間，對于輸入數(shù)較多的電路，為在較短時間內(nèi)得到最小MPRM，常采用現(xiàn)代啟發(fā)式方法. 本文提出了一種能夠用于具有較多輸入數(shù)MPRM最小化的HGA算法，該算法將局部改善策略與GA相結(jié)合.局部改善策略則采用基于相異度的方法生成新個體，對種群最佳或最差個體進(jìn)行競爭，實(shí)現(xiàn)對種群的局部改善，擴(kuò)大搜索空間，避免了傳統(tǒng)GA存在的過早收斂問題，增強(qiáng)了全局收斂能力.實(shí)驗(yàn)結(jié)果驗(yàn)證了所提算法的有效性. 總體來看，相較于SAGA，HGA能夠在獲得類似結(jié)果的前提下提高時間效率;相較于HDPSO，HGA具有基本相同的算法結(jié)果和時間效率.

參考文獻(xiàn)(References)：

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

[2]WANG Pengjun, LI Hui, WANG Zhenhai. MPRM expressions minimization based on simulated annealing genetic algorithm[C]// International Conference on Intelligent Systems and Knowledge Engineering. Hangzhou: ISKE,2010:261-265.

[3]李輝,汪鵬君,王振海.混合極性列表技術(shù)及其在MPRM電路面積優(yōu)化中的應(yīng)用[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2011,23(3):527-533.

LI Hui, WANG Pengjun, WANG Zhenhai. Tabular techniques for mixed-polarity and its application in area optimization of MPRM circuits [J]. Journal of Computer-Aided Design and Computer Graphics,2011,23(3):527-533.

[4]卜登立,江建慧.基于混合多值離散粒子群優(yōu)化的混合極性Reed-Muller最小化算法[J].電子與信息學(xué)報,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 and Information Technology,2013,35(2):361-367.

[5]YU Haizhen, WANG Pengjun, WANG Disheng, et al. Discrete ternary particle swarm optimization for area optimization of MPRM circuits[J]. Journal of Semiconductors,2013,34(2):118-123.

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

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

[8]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.

[9]BURKE E K, KENDALL G. Search Methodologies-Introductory Tutorials in Optimization and Decision Support Techniques[M]. New York: Springer,2005:97-125.

[10]郭文忠,陳國龍,XIONG Naixue,等.求解VLSI電路劃分問題的混合粒子群優(yōu)化算法[J].軟件學(xué)報,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.

Hybrid genetic algorithm for MPRM minimization. Journal of Zhejiang University(Science Edition), 2016,43(2):184-189

Abstract:Mixed-Polarity Reed-Muller (MPRM) logic minimization is a vital step in the logic synthesis of Reed-Muller (RM) circuits. For MPRM minimization of Boolean functions with large number of inputs, traditional genetic algorithm (GA) is subject to premature convergence. Hybrid GA (HGA) which incorporates local improvement strategy basing on dissimilarity into GA is proposed for MPRM minimization to improve the traditional GA. Local improvement strategy generates a new individual in each iteration by applying crossover operator on the current best individual and the individual which has the maximum dissimilarity to it, then the new individual is used to compete with the best or the worst individual in the population. A set of MCNC benchmark circuits with large number of inputs are minimized by HGA. The results are compared with other intelligent MPRM minimization algorithms. Experimental results show that, the proposed local improvement strategy can help GA escape from the local minima and can enhance global convergence ability. In comparison with simulated annealing GA, HGA can obtain similar results and can improve the time efficiency of MPRM minimization, and in comparison with hybrid multi-valued DPSO based algorithm, HGA can obtain similar results and time efficiency.

Key Words:mixed-polarity Reed-Muller; logic minimization; genetic algorithm; dissimilarity; local improvement

中圖分類號：TP 331.2;TP 391.72

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

文章編號：1008-9497(2016)02-184-06

DOI:10.3785/j.issn.1008-9497.2016.02.011

作者簡介：卜登立(1975-)，ORCID：http://orcid.org/0000-0003-3375-7299,男，博士，副教授，主要從事VLSI設(shè)計與優(yōu)化、計算機(jī)輔助設(shè)計以及智能算法研究，E-mail：bodengli@163.com.

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

收稿日期：2015-05-11.