Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2016, Vol. 43 Issue (2): 184-189    DOI: 10.3785/j.issn.1008-9497.2016.02.011
电子科学     
基于混合遗传算法的MPRM最小化
卜登立1,2
1. 井冈山大学电子与信息工程学院, 江西吉安 343009;
2. 同济大学软件学院, 上海 201804
Hybrid genetic algorithm for MPRM minimization
BU Dengli1,2
1. School of Electronics and Information Engineering, Jinggangshan University, Ji'an 343009, Jiangxi Province, China;
2. School of Software Engineering, Tongji University, Shanghai 201804, China
 全文: PDF(944 KB)  
摘要： 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;  逻辑最小化;  遗传算法;  相异度;  局部改善    
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
收稿日期: 2015-05-11 出版日期: 2016-03-12
CLC:  TP331.2  
基金资助: 江西省自然科学基金资助项目(2012BAB201038);江西省教育厅科技计划项目(GJJ13538).
作者简介: 卜登立(1975-),ORCID:http://orcid.org/0000-0003-3375-7299,男,博士,副教授,主要从事VLSI设计与优化、计算机辅助设计以及智能算法研究,E-mail:bodengli@163.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
卜登立

引用本文:

卜登立. 基于混合遗传算法的MPRM最小化[J]. 浙江大学学报（理学版）, 2016, 43(2): 184-189.

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

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2016.02.011    或    https://www.zjujournals.com/sci/CN/Y2016/V43/I2/184

[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.
[1] 肖冉,安新磊,祁慧敏,乔帅. 电场作用下HR神经元的分岔分析及参数辨识[J]. 浙江大学学报（理学版）, 2022, 49(6): 691-697.
[2] 厉康平, 汪鹏君, 张会红. 基于模拟退火遗传算法的三值FPRM电路功耗优化[J]. 浙江大学学报（理学版）, 2016, 43(2): 190-194.
[3] 何江平 1,唐景昌 1,唐叔贤 2. 遗传算法在低能电子衍射结构分析中的应用[J]. 浙江大学学报（理学版）, 2000, 27(5): 503-507.
[4] 邓明荣　鲍永广　沈祖志 . 遗传算法在热电厂生产调度 优化中的应用 [J]. 浙江大学学报（理学版）, 1998, 25(4): 24-27.