基于混合遗传算法的MPRM最小化

摘要 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在得到基本相同的算法结果时,时间效率亦基本相同