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

Reversible circuits optimization algorithm based on KFDD and evolutionary algorithm

为降低由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.