基于人口遷移算法的三值FPRM電路面積最佳極性搜索

厲康平， 汪鵬君， 張會紅（寧波大學電路與系統(tǒng)研究所，浙江寧波 315211）

基于人口遷移算法的三值FPRM電路面積最佳極性搜索

厲康平， 汪鵬君， 張會紅
（寧波大學電路與系統(tǒng)研究所，浙江寧波 315211）

人口遷移算法是一種新的全局優(yōu)化搜索算法，主要模擬人口隨著經(jīng)濟重心發(fā)生轉(zhuǎn)移和隨著壓力增加而擴散的機制，其收斂性和全局尋優(yōu)能力較強。三值固定極性RM（Fixed-polarity Reed-Muller，F(xiàn)PRM）電路的面積大小與其極性有關(guān)。通過對人口遷移算法的研究，提出了一種三值FPRM電路面積優(yōu)化方案。首先根據(jù)三值FPRM表達式和電路面積之間的內(nèi)在聯(lián)系，建立面積優(yōu)化模型；然后利用人口遷移算法對三值FPRM電路進行面積最佳極性搜索；最后對10個MCNC Benchmark電路進行測試。結(jié)果表明：與整體退火遺傳算法相比，本文算法在面積和時間上分別平均節(jié)省10.04%和56.59%。

人口遷移算法；三值FPRM電路；面積優(yōu)化；極性搜索

search

任意三值邏輯函數(shù)均可以用布爾邏輯和Reed-Muller（RM）邏輯來表示［1］，與傳統(tǒng)的布爾邏輯相比，基于RM邏輯的通信電路、奇偶校驗電路、運算電路等具有更緊湊的結(jié)構(gòu)［2］和更好的可測性［3］。RM邏輯通常采用固定極性（Fixed-polarity Reed-Muller，F(xiàn)PRM）和混合極性（Mixed-polarity Reed-Muller，MPRM）兩種表達方式。在n變量的三值FPRM邏輯函數(shù)中有3n個固定極性，對應(yīng)3n個不同的三值FPRM表達式，其表達式的簡單與復(fù)雜程度由極性決定，因此，極性對三值FPRM電路的功耗、面積等性能指標產(chǎn)生很大的影響。對較小規(guī)模的電路進行優(yōu)化時，可以使用窮舉法遍歷每個極性；對較大規(guī)模電路進行優(yōu)化時，由于極性與變量存在指數(shù)關(guān)系使得搜索空間急劇增加，窮舉法很難在有限的時間內(nèi)得到優(yōu)化結(jié)果。因此，需要尋求一種高效、智能的算法提高搜索效率，以便盡快得到三值FPRM電路的最優(yōu)或近最優(yōu)極性［4］。

人口遷移算法（Population Migration Algorithm，PMA）是周永華等［5］根據(jù)人口遷移規(guī)律提出的一種新的全局優(yōu)化搜索算法，主要模擬人口隨著經(jīng)濟重心發(fā)生轉(zhuǎn)移和隨著壓力增加而擴散的機制。人口遷移算法是一種概率搜索算法［6］，實現(xiàn)全局并行搜索，并在搜索過程中不斷地向可能包含最優(yōu)解的空間轉(zhuǎn)移，尋找最優(yōu)或近最優(yōu)解。人口遷移算法原理簡單易操作，與遺傳算法相比［5］，部分函數(shù)的優(yōu)化效果明顯提高，且收斂性和全局尋優(yōu)能力較強。本文在三值FPRM電路極性優(yōu)化中結(jié)合人口遷移算法，提出了一種基于人口遷移算法的三值FPRM電路面積最佳極性搜索方法。

1　三值FPRM電路面積估計模型和極性轉(zhuǎn)換技術(shù)

1.1三值FPRM電路面積估計模型

n變量的三值FPRM邏輯函數(shù)有3n個固定極性，與之對應(yīng)的有3n個不同的FPRM表達式。當極性為p時，任意三值FPRM邏輯函數(shù)的表達式可表示為［7］

表1　查找表Table 1 Look up table of

表1　查找表Table 1 Look up table of

pjijx·ijj 0 0 1 0 1 x j 0 2 x 2j 1 0 1 1 1 x j⊕1 1 2 （x j⊕1）2 2 0 1 2 1 x j⊕2 2 2 （x j⊕2）2

分析公式（1）可知，三值FPRM電路由多輸入模3加運算和多輸入模3乘運算組成，因此可以用兩種邏輯運算的數(shù)量來表示三值FPRM電路的面積。多輸入運算的輸入、輸出關(guān)系復(fù)雜程度不同，在估算面積之前需要把多輸入運算分解成二輸入運算，再以二輸入運算的數(shù)量來衡量電路面積。三值FPRM電路的面積即為二輸入模3加運算與二輸入模3乘運算的數(shù)量之和。

根據(jù)面積估計模型，可以設(shè)置人口遷移算法中吸引力的大小。在人口遷移算法中，吸引力越大表示人口所在地的經(jīng)濟水平越高。面積最佳極性要求面積越小越好，因此，為了便于兩者結(jié)合，采用面積的倒數(shù)表示吸引力。設(shè)置吸引力函數(shù)如下：

其中：attraction表示吸引力大小，其值越大表示面積優(yōu)化效果越好；No._of_Mod3-A表示二輸入模3加運算的數(shù)量；No._of_Mod3-M表示二輸入模3乘運算的數(shù)量；a為放大系數(shù)。

1.2三值FPRM極性轉(zhuǎn)換技術(shù)

在電路的面積優(yōu)化過程中，需要進行極性轉(zhuǎn)換來檢驗每個極性。常用的三值FPRM極性轉(zhuǎn)換方法有矩陣轉(zhuǎn)換法（Matrix Transformation Method）和圖形轉(zhuǎn)換法（Map Transformation Method）［8-9］。然而這兩種方法的極性轉(zhuǎn)換速度慢，時間復(fù)雜度大。文獻［10］提出了一種三值FPRM極性轉(zhuǎn)換算法，能有效提高極性轉(zhuǎn)換速度。其基本過程如下：

（1）極性初始化。隨機產(chǎn)生一個極性p，并用三進制表示p=（p1，p2，…，pn）。

（2）根據(jù)pi產(chǎn)生與之相應(yīng)的固定極性GF轉(zhuǎn)換矩陣G3〈pi〉，如下所示，pi∈｛p1，p2，…，pn｝。

其中π=（π1，π2，…，πn），vi=G〈pi〉3［πi，mi］，i=1，2，…，n。

（3）將最小項m表示成三進制序列m=（m1，m2，…，mn），其相應(yīng)的函數(shù)值為f（m）。

（4）根據(jù)式（2），產(chǎn)生每個最小項的新項πi。

（5）根據(jù)式（3），求出所產(chǎn)生的新項對RM系數(shù)所作的貢獻v（π），并在索引表中疊加它的貢獻值。

（6）對所有的最小項重復(fù)步驟（3）～（5），最后的累加值即為RM表達式系數(shù)。

2　基于PMA的三值FPRM電路面積優(yōu)化

2.1概述

人口遷移算法是一種全局優(yōu)化的仿生算法，將目標函數(shù)的選擇空間模擬成人類的生存空間，將目標函數(shù)值模擬成某個地域的吸引力，利用人口流動、遷移和擴散行為搜索可行解，通過個體的流動、遷移和擴散行為找到局部最優(yōu)解，最后比較多個局部最優(yōu)解得到全局最優(yōu)解。

2.2人口遷移與面積優(yōu)化的關(guān)系

基于人口遷移算法的FPRM電路面積優(yōu)化要將人口遷移與面積優(yōu)化兩者聯(lián)系起來。人口遷移含有以下幾個關(guān)鍵要素：人口所在地、人口所在地的吸引力、吸引力最大地點、最大吸引力、人口可移動地表空間、優(yōu)惠區(qū)域、遷往優(yōu)惠區(qū)域、人口壓力導致遷離優(yōu)惠

區(qū)域。FPRM電路面積優(yōu)化含有以下幾個關(guān)鍵要素：極性、相應(yīng)極性的面積大小、最佳極性、最小面積、可選擇的極性空間、最佳極性所在區(qū)間、極性向最佳極性所在區(qū)間跳變、跳出局部最佳極性。表2給出了人口遷移到FPRM面積優(yōu)化的映射。

表2　人口遷移到FPRM面積優(yōu)化映射Table 2 Mapping of population migration to FPRM area optimization

2.3人口移動

2.3.1概述 人口移動是指人口在地域或空間位置上的移動，包括人口流動、人口遷移和人口擴散。人口流動是人口在各自區(qū)域內(nèi)的移動，是帶有自發(fā)性質(zhì)、移動規(guī)律較差的人口行為。人口遷移是人口跨越各自區(qū)域在整個生存空間上的移動，是帶有選擇性質(zhì)、移動規(guī)律較強的人口行為。人口擴散是指人口在優(yōu)惠區(qū)域壓力達到某一程度后遷往其他區(qū)域的人口行為，在一定程度上可以理解為人口遷移。2.3.2 人口流動 在人口遷移算法中，人口流動表示人口在各自區(qū)域內(nèi)帶有某種自發(fā)性質(zhì)的人口行為，將其運用到三值FPRM電路面積優(yōu)化中表示在某一極性區(qū)間內(nèi)極性的變動。因為人口流動的規(guī)律性較差，因此將人口流動處理為隨機的。為了使區(qū)域內(nèi)每個極性的搜索機會相等，將人口流動處理成均勻隨機變動。模擬時，可以在每個極性區(qū)間均勻隨機產(chǎn)生多個極性：

Xi=2×Δt×rand（）＋（centeri－Δt）（5）

其中：Δt表示極性區(qū)間的半徑；rand（）為隨機函數(shù)；centeri表示第i個極性區(qū)間的中心。

2.3.3人口遷移 在人口遷移算法中，人口受吸引力最大地點的吸引，遷往優(yōu)惠區(qū)域。在三值FPRM電路面積優(yōu)化中可以表示為極性向最佳極性所在區(qū)間跳變。模擬時，以面積最小所對應(yīng)的極性為中心，按Δt的大小確定最佳極性所在區(qū)間，在此區(qū)間內(nèi)均勻隨機產(chǎn)生若干個極性，替換原有極性。2.3.4 人口擴散 在人口遷移算法中，當優(yōu)惠區(qū)域的人口壓力達到一定程度后，人口就會向外遷移。在三值FPRM電路面積優(yōu)化中可以表示為當極性區(qū)間收縮到一定程度，即Δt＜q（q表示人口壓力，為預(yù)先給定的正小量），極性發(fā)生跳躍。模擬時可以簡單化處理，在整個極性空間內(nèi)均勻隨機產(chǎn)生若干個極性，替換原有極性。

2.4參數(shù)設(shè)置

人口遷移算法需設(shè)置5個參數(shù)：人口規(guī)模w、人口流動次數(shù)l、人口壓力參數(shù)q、收縮系數(shù)c，人口擴散次數(shù)s。人口遷移算法的參數(shù)設(shè)置對優(yōu)化效果會產(chǎn)生重要影響。人口規(guī)模決定參與搜索最佳極性的人口基數(shù)，規(guī)模越大，人口基數(shù)越大；人口流動次數(shù)決定搜索次數(shù)，流動次數(shù)越多，搜索次數(shù)越多；人口壓力參數(shù)決定搜索區(qū)域的極限范圍，人口壓力參數(shù)越小，搜索區(qū)域的極限范圍越小；收縮系數(shù)決定搜索區(qū)域的收縮速度，收縮系數(shù)越小；收縮速度越慢。人口擴散次數(shù)決定跳出局部最優(yōu)解的概率，人口擴散次數(shù)越多，跳出局部最優(yōu)解的概率越高。增大人口規(guī)模w，增加人口流動次數(shù)l和人口擴散次數(shù)s，減小人口壓力參數(shù)q和收縮系數(shù)c，可以使搜索更充分，增加找到全局最優(yōu)極性的概率。另外，減小人口壓力參數(shù)q和收縮系數(shù)c還可以提高搜索精度。

人口遷移算法的參數(shù)為事先設(shè)置好的固定值，然而在三值FPRM電路優(yōu)化中，電路的規(guī)模存在很大差異，如果參數(shù)值固定會影響算法的搜索效率。針對此問題，本文結(jié)合人口遷移算法和三值FPRM電路，提出了一種動態(tài)參數(shù)設(shè)置法，參數(shù)設(shè)置隨電路規(guī)模的變化而變化。具體參數(shù)設(shè)置如下：人口規(guī)模為三值FPRM電路的輸入變量個數(shù)；人口流動次數(shù)為極性所在區(qū)間的半徑大小Δt，其大小由式（4）求得；人口壓力參數(shù)為Δt/10；收縮系數(shù)c=0.3；人口擴散次數(shù)設(shè)置為s=15（小規(guī)模電路）或s=2（較大規(guī)模電路）。這是因為當電路規(guī)模較小時，人口流動次數(shù)較小，需要增加人口擴散次數(shù)提高搜索能力；而電路規(guī)模較大時，人口流動次數(shù)較大，僅僅需要進行人口擴散防止陷入局部最優(yōu)解。Δt=3w/w2（6）其中w表示人口規(guī)模，即三值FPRM電路的輸入變量個數(shù)。

2.5面積優(yōu)化算法

本文算法的基本流程如下：

（1）初始化。在極性空間內(nèi)均勻隨機產(chǎn)生w個極性，并根據(jù)Δt確定每個極性所在的區(qū)域，初始化最佳極性和面積最優(yōu)值。

（2）極性變動。在各極性區(qū)間內(nèi)隨機變動每個極性，更新最佳極性和面積最優(yōu)值，隨機變動l次。

（3）極性轉(zhuǎn)移。以面積最優(yōu)值對應(yīng)的極性為中點，按Δt的大小確定最佳極性區(qū)間。在該區(qū)域內(nèi)均勻隨機產(chǎn)生w個極性，替換原來的極性，更新最佳極性和面積最優(yōu)值。

（4）收縮最佳極性區(qū)間。令Δt=（1－c）Δt （c為收縮系數(shù)，0＜c＜1），收縮極性所在區(qū)間，重復(fù)步驟（3），直到Δt＜q。

（5）極性跳躍。當收縮最佳極性區(qū)域到一定程度（Δt＜q）后，在極性空間內(nèi)均勻隨機產(chǎn)生w個極性，替換原來的極性，更新最佳極性和面積最優(yōu)值，重復(fù)步驟（2）～步驟（4），直到滿足人口擴散次數(shù)s，算法結(jié)束。

基于PMA算法的三值FPRM電路面積優(yōu)化偽代碼如下：

3　實驗驗證與分析

本文算法在Windows 7，64位操作系統(tǒng)，Intel （R）Core（TM）i3-2130 CPU 3.40 GHz，4 G RAM運行環(huán)境下，用C語言通過VC6.0編譯實現(xiàn)，采用10個MCNC Benchmark電路進行仿真驗證，優(yōu)化結(jié)果與文獻［11］的整體退火遺傳算法進行比較。在進行最佳極性搜索之前需要讀入PLA格式電路，然而目前只有標準的二值PLA格式電路，因此先用文獻［12］中的方法將標準的二值PLA格式電路轉(zhuǎn)換為三值PLA格式電路，然后運用本文算法進行最佳極性搜索。

三值FPRM電路面積最佳極性搜索結(jié)果如表3所示。表中InputsB為二值電路輸入變量個數(shù)，Inputs T為三值電路輸入變量個數(shù)，Polarity表示最佳極性，Mod3-A，M表示模3加，模3乘運算數(shù)量，Time為算法的運行時間。

與整體退火遺傳算法相比，本文算法在面積和時間上節(jié)省的百分比如表4所示。

表3　三值FPRM電路面積最佳極性搜索結(jié)果Table 3 Search results of the best area polarity of ternary FPRM circuit

表4　三值FPRM電路面積和時間節(jié)省百分比Table 4 Percentage saves of the area for ternary FPRM circuit and the optimization time

面積和時間節(jié)省的百分比定義如下：

其中：SaveArea和SaveTime表示面積和算法運行時間的節(jié)省；AreaWAGA和TimeWAGA表示整體退火遺傳算法的優(yōu)化面積和優(yōu)化時間；AreaPMA和TimePMA表示所提算法的優(yōu)化面積和優(yōu)化時間。

分析表4數(shù)據(jù)可知，本文方法優(yōu)化效果明顯。與文獻［11］的整體退火遺傳算法相比，10個測試電路面積和時間平均節(jié)省10.04%和56.59%。

4　結(jié) 論

本文通過對人口遷移算法的研究，提出了一種三值FPRM電路面積優(yōu)化方案。通過對10個MCNC Benchmark電路進行仿真驗證表明，本文方案優(yōu)化后極性與整體退火遺傳算法相比具有明顯的優(yōu)化效果。由于人口遷移算法發(fā)展較晚，本身還存在缺陷，因此在今后的研究中，將利用算法融合思想對人口遷移算法加以改進，使優(yōu)化效果更明顯。

［1］ 汪鵬君，王振海，陳耀武，等.固定極性Reed-Muller電路最佳延時極性搜索［J］.浙江大學學報（工學版），2013，47（2）：361-366.

［2］ AL JASSANI B A，URQUHART N，ALMAINI A E A. Manipulation and optimization techniques for Boolean logic ［J］.IET Computers and Digital Techniques，2010，4（3）：227-239.

［3］ RAHAMAN H，DAS D K，BHATTACHARYA B B. Testable design of AND-EXOR logic networks with universal test sets［J］.Computers and Electrical Engineering，2009，35 （5）：644-658.

［4］ 王振海，汪鵬君，俞海珍，等.基于PSO算法的FPRM電路延時和面積優(yōu)化［J］.電路與系統(tǒng)學報，2012，17（5）：75-80.

［5］ 周永華，毛宗源.一種新的全局優(yōu)化搜索算法——人口遷移算法（I）［J］.華南理工大學學報（自然科學版），2003，31（3）：1-5.

［6］ 周永華，毛宗源.一種新的全局優(yōu)化搜索算法——人口遷移算法（Ⅱ）［J］.華南理工大學學報（自然科學版），2003，31（4）：41-43.

［7］ FALKOWSKI B J，CHENG Fu.Polynomial expansions over GF（3）based on fastest transformation［C］//33rd International Symposium on Multiple-Valued Logic.Tokyo，Japan：IEEE，2003：40-45.

［8］ FALKOWSKI B J，CHENG Fu.Fastest classes of linearly independent transforms over GF（3）and their properties［J］. IEE Proceedings-Computers and Digital Techniques，2005，152（5）：567-576.

［9］ CHENG FU，F(xiàn)ALKOWSKI B J.Ternary fixed polarity linear Kronecker transforms and their comparison with ternary Reed Muller transform［J］.Journal of Circuits，Systems，and Computers，2005，14（4）：721-733.

［10］ 孫飛，汪鵬君，俞海珍.三值FPRM電路極性間轉(zhuǎn)換算法及其在面積優(yōu)化中的應(yīng)用［J］.浙江大學學報（理學版），2014，41 （1）：43-48.

［11］ SUN Fei，WANG Pengjun，YU Haizhen.Best polarity searching for ternary FPRM logic circuit area based on whole annealing genetic algorithm［C］//2013 IEEE 10th International Conference on ASIC（ASICON）.Shenzhen：IEEE，2013：1-4.［12］ FALKOWSKI B J，LOZANO C C，RAHARDJA S.Column polarity matrix algorithm for ternary fixed polarity Reed-Muller expansions［J］.Journal of Circuits，Systems，and Computers，2006，15（2）：243-262.

Best Area Polarity Searching for Ternary FPRM Circuit Based on Population Migration Algorithm

LI Kang-ping， WANG Peng-jun， ZHANG Hui-hong
（Institute of Circuits and Systems，Ningbo University，Ningbo 315211，Zhejiang，China）

Population migration algorithm（PMA）is a new global search optimization algorithm.It simulates the mechanism that population moves along with the transformation of economic center and population diffuses with the pressure increasing.The polarity of ternary FPRM（Fixed-polarity Reed-Muller）circuit determines its area.By analyzing PMA algorithm，this paper proposes an area optimization scheme for ternary FPRM circuit.Firstly，according to the internal relation between the ternary FPRM expression and the circuit area，an area optimization model is established.Secondly，the PMA is utilized to search the best polarity for the area of FPRM circuit.Finally，ten MCNC Benchmark circuits are tested，which show that compared with the whole annealing genetic algorithm，the proposed algorithm can save 10.04%and 56.59%respectively on average on the area and the time.

population migration algorithm；ternary FPRM circuit；area optimization；polarity

TP332.2

A

1006-3080（2016）01-0104-06 DOI：10.14135/j.cnki.1006-3080.2016.01.017

2015-03-24

國家自然科學基金（61234002，61306041）；浙江省自然科學基金（LY13F040003）

厲康平（1991-），男，碩士生，主要從事高信息密度和低功耗集成電路理論及設(shè)計方面的研究。

汪鵬君，E-mail：wangpengjun@nbu.edu.cn