基于人口迁移算法的三值FPRM电路面积最佳极性搜索

厉康平， 汪鹏君， 张会红（宁波大学电路与系统研究所，浙江宁波 315211）

基于人口迁移算法的三值FPRM电路面积最佳极性搜索

厉康平， 汪鹏君， 张会红
（宁波大学电路与系统研究所，浙江宁波 315211）

人口迁移算法是一种新的全局优化搜索算法，主要模拟人口随着经济重心发生转移和随着压力增加而扩散的机制，其收敛性和全局寻优能力较强。三值固定极性RM（Fixed-polarity Reed-Muller，FPRM）电路的面积大小与其极性有关。通过对人口迁移算法的研究，提出了一种三值FPRM电路面积优化方案。首先根据三值FPRM表达式和电路面积之间的内在联系，建立面积优化模型；然后利用人口迁移算法对三值FPRM电路进行面积最佳极性搜索；最后对10个MCNC Benchmark电路进行测试。结果表明：与整体退火遗传算法相比，本文算法在面积和时间上分别平均节省10.04%和56.59%。

人口迁移算法；三值FPRM电路；面积优化；极性搜索

search

任意三值逻辑函数均可以用布尔逻辑和Reed-Muller（RM）逻辑来表示［1］，与传统的布尔逻辑相比，基于RM逻辑的通信电路、奇偶校验电路、运算电路等具有更紧凑的结构［2］和更好的可测性［3］。RM逻辑通常采用固定极性（Fixed-polarity Reed-Muller，FPRM）和混合极性（Mixed-polarity Reed-Muller，MPRM）两种表达方式。在n变量的三值FPRM逻辑函数中有3n个固定极性，对应3n个不同的三值FPRM表达式，其表达式的简单与复杂程度由极性决定，因此，极性对三值FPRM电路的功耗、面积等性能指标产生很大的影响。对较小规模的电路进行优化时，可以使用穷举法遍历每个极性；对较大规模电路进行优化时，由于极性与变量存在指数关系使得搜索空间急剧增加，穷举法很难在有限的时间内得到优化结果。因此，需要寻求一种高效、智能的算法提高搜索效率，以便尽快得到三值FPRM电路的最优或近最优极性［4］。

人口迁移算法（Population Migration Algorithm，PMA）是周永华等［5］根据人口迁移规律提出的一种新的全局优化搜索算法，主要模拟人口随着经济重心发生转移和随着压力增加而扩散的机制。人口迁移算法是一种概率搜索算法［6］，实现全局并行搜索，并在搜索过程中不断地向可能包含最优解的空间转移，寻找最优或近最优解。人口迁移算法原理简单易操作，与遗传算法相比［5］，部分函数的优化效果明显提高，且收敛性和全局寻优能力较强。本文在三值FPRM电路极性优化中结合人口迁移算法，提出了一种基于人口迁移算法的三值FPRM电路面积最佳极性搜索方法。

1　三值FPRM电路面积估计模型和极性转换技术

1.1三值FPRM电路面积估计模型

n变量的三值FPRM逻辑函数有3n个固定极性，与之对应的有3n个不同的FPRM表达式。当极性为p时，任意三值FPRM逻辑函数的表达式可表示为［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乘运算组成，因此可以用两种逻辑运算的数量来表示三值FPRM电路的面积。多输入运算的输入、输出关系复杂程度不同，在估算面积之前需要把多输入运算分解成二输入运算，再以二输入运算的数量来衡量电路面积。三值FPRM电路的面积即为二输入模3加运算与二输入模3乘运算的数量之和。

根据面积估计模型，可以设置人口迁移算法中吸引力的大小。在人口迁移算法中，吸引力越大表示人口所在地的经济水平越高。面积最佳极性要求面积越小越好，因此，为了便于两者结合，采用面积的倒数表示吸引力。设置吸引力函数如下：

其中：attraction表示吸引力大小，其值越大表示面积优化效果越好；No._of_Mod3-A表示二输入模3加运算的数量；No._of_Mod3-M表示二输入模3乘运算的数量；a为放大系数。

1.2三值FPRM极性转换技术

在电路的面积优化过程中，需要进行极性转换来检验每个极性。常用的三值FPRM极性转换方法有矩阵转换法（Matrix Transformation Method）和图形转换法（Map Transformation Method）［8-9］。然而这两种方法的极性转换速度慢，时间复杂度大。文献［10］提出了一种三值FPRM极性转换算法，能有效提高极性转换速度。其基本过程如下：

（1）极性初始化。随机产生一个极性p，并用三进制表示p=（p1，p2，…，pn）。

（2）根据pi产生与之相应的固定极性GF转换矩阵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），其相应的函数值为f（m）。

（4）根据式（2），产生每个最小项的新项πi。

（5）根据式（3），求出所产生的新项对RM系数所作的贡献v（π），并在索引表中叠加它的贡献值。

（6）对所有的最小项重复步骤（3）～（5），最后的累加值即为RM表达式系数。

2　基于PMA的三值FPRM电路面积优化

2.1概述

人口迁移算法是一种全局优化的仿生算法，将目标函数的选择空间模拟成人类的生存空间，将目标函数值模拟成某个地域的吸引力，利用人口流动、迁移和扩散行为搜索可行解，通过个体的流动、迁移和扩散行为找到局部最优解，最后比较多个局部最优解得到全局最优解。

2.2人口迁移与面积优化的关系

基于人口迁移算法的FPRM电路面积优化要将人口迁移与面积优化两者联系起来。人口迁移含有以下几个关键要素：人口所在地、人口所在地的吸引力、吸引力最大地点、最大吸引力、人口可移动地表空间、优惠区域、迁往优惠区域、人口压力导致迁离优惠

区域。FPRM电路面积优化含有以下几个关键要素：极性、相应极性的面积大小、最佳极性、最小面积、可选择的极性空间、最佳极性所在区间、极性向最佳极性所在区间跳变、跳出局部最佳极性。表2给出了人口迁移到FPRM面积优化的映射。

表2　人口迁移到FPRM面积优化映射Table 2 Mapping of population migration to FPRM area optimization

2.3人口移动

2.3.1概述 人口移动是指人口在地域或空间位置上的移动，包括人口流动、人口迁移和人口扩散。人口流动是人口在各自区域内的移动，是带有自发性质、移动规律较差的人口行为。人口迁移是人口跨越各自区域在整个生存空间上的移动，是带有选择性质、移动规律较强的人口行为。人口扩散是指人口在优惠区域压力达到某一程度后迁往其他区域的人口行为，在一定程度上可以理解为人口迁移。2.3.2 人口流动 在人口迁移算法中，人口流动表示人口在各自区域内带有某种自发性质的人口行为，将其运用到三值FPRM电路面积优化中表示在某一极性区间内极性的变动。因为人口流动的规律性较差，因此将人口流动处理为随机的。为了使区域内每个极性的搜索机会相等，将人口流动处理成均匀随机变动。模拟时，可以在每个极性区间均匀随机产生多个极性：

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

其中：Δt表示极性区间的半径；rand（）为随机函数；centeri表示第i个极性区间的中心。

2.3.3人口迁移 在人口迁移算法中，人口受吸引力最大地点的吸引，迁往优惠区域。在三值FPRM电路面积优化中可以表示为极性向最佳极性所在区间跳变。模拟时，以面积最小所对应的极性为中心，按Δt的大小确定最佳极性所在区间，在此区间内均匀随机产生若干个极性，替换原有极性。2.3.4 人口扩散 在人口迁移算法中，当优惠区域的人口压力达到一定程度后，人口就会向外迁移。在三值FPRM电路面积优化中可以表示为当极性区间收缩到一定程度，即Δt＜q（q表示人口压力，为预先给定的正小量），极性发生跳跃。模拟时可以简单化处理，在整个极性空间内均匀随机产生若干个极性，替换原有极性。

2.4参数设置

人口迁移算法需设置5个参数：人口规模w、人口流动次数l、人口压力参数q、收缩系数c，人口扩散次数s。人口迁移算法的参数设置对优化效果会产生重要影响。人口规模决定参与搜索最佳极性的人口基数，规模越大，人口基数越大；人口流动次数决定搜索次数，流动次数越多，搜索次数越多；人口压力参数决定搜索区域的极限范围，人口压力参数越小，搜索区域的极限范围越小；收缩系数决定搜索区域的收缩速度，收缩系数越小；收缩速度越慢。人口扩散次数决定跳出局部最优解的概率，人口扩散次数越多，跳出局部最优解的概率越高。增大人口规模w，增加人口流动次数l和人口扩散次数s，减小人口压力参数q和收缩系数c，可以使搜索更充分，增加找到全局最优极性的概率。另外，减小人口压力参数q和收缩系数c还可以提高搜索精度。

人口迁移算法的参数为事先设置好的固定值，然而在三值FPRM电路优化中，电路的规模存在很大差异，如果参数值固定会影响算法的搜索效率。针对此问题，本文结合人口迁移算法和三值FPRM电路，提出了一种动态参数设置法，参数设置随电路规模的变化而变化。具体参数设置如下：人口规模为三值FPRM电路的输入变量个数；人口流动次数为极性所在区间的半径大小Δt，其大小由式（4）求得；人口压力参数为Δt/10；收缩系数c=0.3；人口扩散次数设置为s=15（小规模电路）或s=2（较大规模电路）。这是因为当电路规模较小时，人口流动次数较小，需要增加人口扩散次数提高搜索能力；而电路规模较大时，人口流动次数较大，仅仅需要进行人口扩散防止陷入局部最优解。Δt=3w/w2（6）其中w表示人口规模，即三值FPRM电路的输入变量个数。

2.5面积优化算法

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

（1）初始化。在极性空间内均匀随机产生w个极性，并根据Δt确定每个极性所在的区域，初始化最佳极性和面积最优值。

（2）极性变动。在各极性区间内随机变动每个极性，更新最佳极性和面积最优值，随机变动l次。

（3）极性转移。以面积最优值对应的极性为中点，按Δt的大小确定最佳极性区间。在该区域内均匀随机产生w个极性，替换原来的极性，更新最佳极性和面积最优值。

（4）收缩最佳极性区间。令Δt=（1－c）Δt （c为收缩系数，0＜c＜1），收缩极性所在区间，重复步骤（3），直到Δt＜q。

（5）极性跳跃。当收缩最佳极性区域到一定程度（Δt＜q）后，在极性空间内均匀随机产生w个极性，替换原来的极性，更新最佳极性和面积最优值，重复步骤（2）～步骤（4），直到满足人口扩散次数s，算法结束。

基于PMA算法的三值FPRM电路面积优化伪代码如下：

3　实验验证与分析

本文算法在Windows 7，64位操作系统，Intel （R）Core（TM）i3-2130 CPU 3.40 GHz，4 G RAM运行环境下，用C语言通过VC6.0编译实现，采用10个MCNC Benchmark电路进行仿真验证，优化结果与文献［11］的整体退火遗传算法进行比较。在进行最佳极性搜索之前需要读入PLA格式电路，然而目前只有标准的二值PLA格式电路，因此先用文献［12］中的方法将标准的二值PLA格式电路转换为三值PLA格式电路，然后运用本文算法进行最佳极性搜索。

三值FPRM电路面积最佳极性搜索结果如表3所示。表中InputsB为二值电路输入变量个数，Inputs T为三值电路输入变量个数，Polarity表示最佳极性，Mod3-A，M表示模3加，模3乘运算数量，Time为算法的运行时间。

与整体退火遗传算法相比，本文算法在面积和时间上节省的百分比如表4所示。

表3　三值FPRM电路面积最佳极性搜索结果Table 3 Search results of the best area polarity of ternary FPRM circuit

表4　三值FPRM电路面积和时间节省百分比Table 4 Percentage saves of the area for ternary FPRM circuit and the optimization time

面积和时间节省的百分比定义如下：

其中：SaveArea和SaveTime表示面积和算法运行时间的节省；AreaWAGA和TimeWAGA表示整体退火遗传算法的优化面积和优化时间；AreaPMA和TimePMA表示所提算法的优化面积和优化时间。

分析表4数据可知，本文方法优化效果明显。与文献［11］的整体退火遗传算法相比，10个测试电路面积和时间平均节省10.04%和56.59%。

4　结 论

本文通过对人口迁移算法的研究，提出了一种三值FPRM电路面积优化方案。通过对10个MCNC Benchmark电路进行仿真验证表明，本文方案优化后极性与整体退火遗传算法相比具有明显的优化效果。由于人口迁移算法发展较晚，本身还存在缺陷，因此在今后的研究中，将利用算法融合思想对人口迁移算法加以改进，使优化效果更明显。

［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电路延时和面积优化［J］.电路与系统学报，2012，17（5）：75-80.

［5］ 周永华，毛宗源.一种新的全局优化搜索算法——人口迁移算法（I）［J］.华南理工大学学报（自然科学版），2003，31（3）：1-5.

［6］ 周永华，毛宗源.一种新的全局优化搜索算法——人口迁移算法（Ⅱ）［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，FALKOWSKI 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电路极性间转换算法及其在面积优化中的应用［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-），男，硕士生，主要从事高信息密度和低功耗集成电路理论及设计方面的研究。

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