基于混合多值离散粒子群优化的混合极性ReedMuller最小化算法.docx

第35卷第2期电子与信息学报Vbl．35No．22013年2月JournalofElectronicsInformationTechnologyFeb．2013基于混合多值离散粒子群优化的混合极性Reed．Muller最小化算法卜登立+㈣江建慧∞(同济大学软件学院上海201804)(井冈山大学电子与信息工程学院吉安343009)摘要：针对布尔函数系统的混合极性Reed．Muller(Mixed—PolarityReed—Muller，MPRM)最小化问题，该文提出了一种混合多值离散粒子群优化算法。为解决多样性损失，改善优化结果，兼顾算法的效率和精度，算法采用多群协同优化方法，并提出了概率变异更新、没有重复的更新以及群间重复最优变异3种更新和变异策略。实验结果表明，和模拟退火遗传算法相比，所构造算法能够在获得基本相同优化结果的同时，提高MPRM最小化的时间效率。关键词：数字电路；布尔函数系统；混合极性Reed—Muller；多值离散粒子群优化；多群；更新和变异策略中图分类号：TP331．2；TP391．72文献标识码：A文章编号：1009—5896(2013)02—0361—07DOI：10．3724／SP．J．1146．2012．00790HybridMulti—valuedDiscreteParticleSwarmOptimizationAlgorithmforMixed．polarityReed．MullerMinimizationBuDeng-li①②JiangJian_hu严“(SchoolofSoftwareEngineering，TongjiUniversity，Shanghai201804，China)(SchoolofElectronicsandInformationEngzneering，以nggangshanUniversity，Ji’an343009，China)Abstract：Anovelhybridmulti—valuedDiscreteParticleSwarmOptimization(DPSO)algorithmforMixed—PolarityReed-Muller(MPRM)minimizationofBooleanfunctionsystemisproposed．Tosolvetheproblemofdiversityloss，improvetheoptimizedresultandbalancetheefficiencyandprecisionofDPSO，multi—swarmcooperativeoptimizationisemployed，andthreeupdateandmutationstrategiesofupdatewithprobabilisticmutation，updatewithnoduplicatesandmutationwithbestduplicatesbetweenswarmsareproposed．TheexperimentalresultsshowthatcomparedwithSimulatedAnnealingGeneticAlgorithm(SAGA)，theproposedalgorithmcanobtainsimilaroptimizedresultsandimprovethetimeefficiencyofMPRMminimization．Keywords：Digitalcircuit；Booleanfunctionsystem；Mixed-PolarityReed-Muller(MPRM)；Multi—valuedDiscreteParticleSwarmOptimization(DPSO)；Multi—swarm；Updateandmutationstrategies1引言小ESOP的乘积项数，因此MPRM最小化问题受相对于布尔函数的SOP(Sum0fProduct)表到了广泛的关注。示，ESOPfExclusive-ORSumOfProduct)表示能布尔函数系统的MPRM最小化是RM电路逻够得到更小更高效的实现，用ESOP表示实现的电辑综合过程中一个非常重要的阶段，求解乘积项数最少的MPRM表示可以为进一步的ESOP最小化路能够获得面积、功耗和可测性等方面的显著优势[1-3]。并且因为可以直接映射到目标电路，ESOP提供一个初始覆盖【5】o布尔函数系统的MPRM能够表示已经在可逆电路和量子电路的综合方法中得到通过其对应的混合极性值来确定，因此可以通过搜了应用心然而，由于ESOP不是标准形表示，最索布尔函数系统的混合极性空间来求解最小小ESOP很难求解【5]，因此，其子类固定极性Reed—MPRM。尽管采用穷举搜索策略遍历混合极性空间M