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

卜 登 立

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

?

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

卜 登 立1,2

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

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

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

BU Dengli1,2

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

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

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

1MPRM最小化

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

(1)

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

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

(2)

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

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

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

2基于HGA的MPRM最小化算法

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

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

2.1編碼和適應度函數

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

采用的適應度函數為式(2)中的C(h).

2.2GA基本操作

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

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

變異操作：采用單點變異，在進行個體的變異運算時，隨機改變一個基因，改變的值也是隨機產生的. 一定概率的變異操作，再結合交叉操作，可以擴大搜索空間.

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

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

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

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

(3)

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

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

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

2.4HGA算法描述

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

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

(2) 讀取邏輯網表并轉換為OKFDDs；

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

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

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

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

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

(8) 迭代次數+1，統計種群最優累計沒有改善的次數，如果不滿足結束條件則轉步驟(5)；

(9) 輸出最優MPRM結果，算法結束.

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

3實驗設置及結果分析

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

3.1實驗設置

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

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

由于4種算法均具有一定的隨機特性，因此對于每個基準電路、每種算法均獨立運行20次，并統計算法結果的最小值(min)、均值(avg)和標準差(std)，以及算法迭代次數和所花費CPU時間的平均值，單位為s.

3.2局部改善策略驗證

表1給出了TGA以及HGA的運行結果，其中“I/O”表示電路的輸入數和輸出數.

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

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

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

表1　HGA與TGA算法的運行結果

3.3與其他算法比較

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

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

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

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

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

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

電路HDPSOminavgstd時間/s迭代次數SAGAminavgstd時間/s迭代次數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結語

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

參考文獻(References)：

[1]卜登立,江建慧.使用系數矩陣變換極性轉換的MPRM電路面積優化[J].計算機輔助設計與圖形學學報,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]李輝,汪鵬君,王振海.混合極性列表技術及其在MPRM電路面積優化中的應用[J].計算機輔助設計與圖形學學報,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]卜登立,江建慧.基于混合多值離散粒子群優化的混合極性Reed-Muller最小化算法[J].電子與信息學報,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電路劃分問題的混合粒子群優化算法[J].軟件學報,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

文獻標志碼：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設計與優化、計算機輔助設計以及智能算法研究，E-mail：bodengli@163.com.

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

收稿日期：2015-05-11.