计算机CMOS芯片的热耗散限制了芯片的集成度,而传统逻辑门的不可逆操作是导致能量耗散的主要原因。要避免能量耗散,电路必须由可逆门来构造。因此,可逆电路在可逆计算、低能耗CMOS设计,光计算、量子计算及DNA计算等领域有着广泛的应用,可逆电路综合逐渐成为新的研究热点。已有的可逆电路综合方法基本分为确定性算法、启发式算法和进化类算法。其中,一部分确定性算法能有效地获得可行解,甚至是对中、大规模可逆问题,但获得的解仍需后优化过程进行改进。后优化过程往往需要反复迭代并且作用有限。另一部分确定性算法使用穷尽式搜索方法取得最优解,但只局限于小规模三位、四位可逆电路的综合。启发式方法利用贪婪式启发策略进行解空间的约简,对中小规模电路能够在有限时间内获得有效解,但解仍需优化。进化方法由于具有全局搜索能力,已用于可逆电路综合,但相比较前两类算法,只对小规模、低复杂度可逆函数进行了测试,并没有取得突破性的成果。本文研究利用进化方法进行可逆电路综合,旨在解决穷尽式搜索力所不及的中小规模问题,并在这些问题上能够取得比确定性算法更优的解。可逆电路综合问题可以建模成具有等式约束的最小化问题,其中约束是指电路的误差,目标表示可逆电路的代价。针对可逆电路综合搜索空间巨大、最优解长度不确定、上位性和多峰等特点,主要从变长编码进化、等式约束处理、多样性保持策略、混合进化策略、适应度函数定义等方面入手,对进化可逆电路综合算法设计进行了全面深入的研究,获得了一些关键性的研究成果。主要概括为以下几个方面:(1)设计实现基本变长染色体编码进化算法。改进了约束违反评价函数,利用可逆电路的正极性Reed Muller表达式与恒等函数正极性Reed Muller表达式的差别项数做为评价标准,而不是用传统的矩阵迹距离,因而避免了计算量较大的矩阵积及矩阵克罗内克积的计算;利用从可逆函数的Reed Muller表达式中提取的因子数量信息,正确估计电路的最大长度并进行种群的初始化;采用染色体最大长度限制和无损交叉算子,使染色体长度逐渐增长,防止变长进化中的染色体膨胀。(2)设计了两种等式约束处理方法。第一种方法采用目标和约束分离的机制处理等式约束,对非支配的不可行解,计算节俭压力并与平衡因子比较,根据比较结果完成种群中染色体的排序,将其作为选择的基础。通常,约束违反降低的过程往往伴随着目标值的增加,平衡因子反映了约束违反单位下降所能容忍的目标值增加量,因此能起到防止染色体膨胀的作用。第二种方法采用基于偏好的多目标优化方法来处理约束。通过改进参考点多目标优化算法,根据解的分布动态生成并更新参考点,并定义新的基于距离的比较算子,使得搜索逐步受控地向约束违反减小的方向进行。(3)实现变长染色体编码进化算法的多样性保持机制。由于变长染色体编码进化选择过程中对具有较小约束违反的解的偏好,会使种群逐渐丧失多样性,陷入局部最优,又由于可逆电路综合问题解空间本身具有的多峰特点,进化过程中的多样性保持尤其重要。我们借鉴并改进了子种群探测和种子保留的多样性保持机制,定义了变长染色体之间的距离,增加了子种群的更新机制。实验证明采用该多样性保留机制后,可行解比例和解的质量均有所提高。(4)设计实现混合算法。将进化算法与基于PPRM的启发式算法结合,从当前解的RRPM表达式中提取优选因子构建优选门库,在进化停滞阶段进行个体的更新,从而加快进化算法的收敛速度,提高可行解的比例。(5)将进化可逆逻辑综合研究成果与基于忆阻器蕴含门的逻辑综合问题特点相结合,提出了基于忆阻器蕴含门的逻辑综合进化算法。算法将变长编码进化可逆逻辑综合算法框架用于忆阻器蕴含门的逻辑电路综合问题,提出了忆阻器蕴含门的染色体编码、评价方法及提高可行解率的局部搜索方法,实验证明了算法的有效性。本文对进化可逆逻辑电路综合中的关键性问题进行了有效的探索和尝试,实验结果分析表明本文的方法对中、小规模的可逆标准测试函数具有有效性,达到了预期的设计目的。另外,将进化可逆逻辑电路综合方法应用于基于忆阻器蕴含门的逻辑综合问题,实验结果进一步验证了该方法可以推广到其它变长编码的逻辑电路综合问题。