基于混合遗传算法的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.