基于KFDD与进化算法的可逆电路优化算法  

Reversible circuits optimization algorithm based on KFDD and evolutionary algorithm

作　　者：卜登立[1,2] 刘欢[1,2] 刘宇安[1,2] BU Dengli1,2,LIU Huan1,2,LIU Yu’an1,2(1.School of Electronics and Information Engineering,Jinggangshan University,Ji’an 343009,P. R. China;2. Key Laboratory of Watershed Ecology and Geographical Environment Monitoring,NASG,Ji’an 343009,P. R. Chin)

机构地区：[1]井冈山大学电子与信息工程学院,江西吉安343009 [2]流域生态与地理环境监测国家测绘地理信息局重点实验室,江西吉安343009

出　　处：《重庆邮电大学学报（自然科学版）》2018年第3期375-382,共8页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：国家自然科学基金(61640412);江西省教育厅科技计划项目(GJJ160746);流域生态与地理环境监测国家测绘地理信息局重点实验室资助课题(WE2016012);江西省自然科学基金(20171BAB202010)~~

摘　　要：为降低由Kronecker功能决策图(Kronecker functional decision diagram,KFDD)综合所得可逆电路的成本,提出一种基于进化算法的可逆电路优化算法。该算法基于遗传算法模型进行设计,分别采用离散值和整型值编码KFDD输入变量的分解类型和顺序,使用所设计的遗传算子,将量子成本作为主要目标、量子位数作为次要目标进行可逆电路的优化。为解决过早收敛问题,该算法在搜索过程的前期阶段利用多个子群搜索解空间中的不同区域,在搜索过程的后期阶段将多个子群合并为整体种群,利用整体种群进行集中搜索。使用基准函数对算法进行验证的结果表明,所提出算法具有较强的全局寻优能力,有较好的结果稳定性,能够降低可逆电路的量子成本。An evolutionary algorithm based reversible circuit optimization algorithm is proposed in order to reduce the cost of reversible circuit synthesized from Kronecker functional decision diagram （KFDD）. Based on genetic algorithm model,the proposed algorithm uses discrete and integer encoding respectively for decomposition types and variable ordering of KFDD. Using the designed genetic operators,the proposed algorithm optimizes reversible circuit by taking quantum cost as primary objective and quantum bits as secondary objective. In order to prevent premature convergence, at early stage of the search process,the proposed algorithm searches different regions of the solution space by using multiple sub-populations. At later stage of the search process,it merges multiple sub-populations into one monolithic population,and performs intensive search by using the monolithic population. The proposed algorithm is validated by using a set of benchmark functions. Re-sults show that the proposed algorithm has strong global search capability,can obtain results with good stability,and can re-duce quantum cost of reversible circuits.

关 键 词：可逆电路 Kronecker功能决策图 进化算法 变量顺序 分解类型 

分 类 号：TP331.2[自动化与计算机技术—计算机系统结构] TP391.72[自动化与计算机技术—计算机科学与技术]