基于子种群保留的可逆电路合成混合算法

Species conservation-based hybrid algorithm for reversible circuit synthesis

为了进一步降低4bit以上中小规模可逆逻辑电路的量子代价,提出一种基于子种群保留的变长染色体编码混合算法.该算法在已有变长染色体编码混合算法的基础上,将子种群保留策略用于变长编码种群的进化,以保持种群多样性,避免陷入局部最优解;定义了变长编码染色体的近似度,以此作为种子提取和子种群划分的基础;提出了子种群重新启动策略和新的启发式子种群更新操作,克服变长编码种群进化过程中的遗传漂移,从而提高可行解率和解的质量.对4bit以上常用标准可逆函数测试结果表明该算法能大大降低合成可逆电路的量子代价.

In order to decrease the quantum cost of small and medium‐sized reversible functions with more than 4 bit ,a species conservation‐based variable‐length encoding hybrid algorithm for reversible logic circuit synthesis was proposed based on an existing variable‐length encoding hybrid algorithm . Firstly ,the species conservation mechanism was customized and introduced into variable‐length enco‐ding population to maintain the diversity of the population .The similarity definition between chromo‐somes with different lengths was given ,based on which seeds subtraction and species differentiation were conducted .Then ,the species restart strategy and heuristic species update were proposed to a‐void the genetic draft of the population with variable‐length encoding .The experimental results show that the proposed algorithm can reduce the quantum cost of common reversible benchmarks and im‐prove the feasible ratio greatly .