面向量子可逆逻辑自动综合的多目标进化算法研究

摘要

随着科学技术和计算机产业的不断发展，集成电路(Integrated Circuits，IC)正在进入以极大规模、极高密度、系统集成等为特征的SOC(System-on-a-chip)时代。计算机芯片的集成度正遵循着摩尔定律(Moore's Law)不断地提高，更快、更小、更复杂的系统级芯片已经开始量产。若摩尔定律继续适用，计算机芯片的线宽将很快达到原子水平。集成度的提高可使计算机的性能得到大幅提升，但也不可避免的导致以下两大问题:第一，随着时钟频率的增加和封装在芯片中晶体管数目的增多，计算机芯片的能耗将不断增大，发热成为一大难题;第二，随着计算机制程的不断发展，晶体二极管的尺寸将达到原子水平，而由于电子的“波粒二象性”使其显现出量子效应，导致经典物理定律失效的窘境。上述问题是IC发展所面临的共性问题，它们也都清楚地表明，现行的计算机制造方法在提高集成度方面已显得越来越力不从心。
　　 可逆逻辑电路(Reversible Logic Circuits)以可逆方式进行逻辑运算、不丢失输入信息，是一种可避免信息损失和相应能量损耗的新型电路，因而可有效降低能耗甚至达到零损耗，使其成为未来进一步降低IC功耗的必由之路。同时，量子计算机遵循量子力学规律，天生服从量子物理定律。可利用量子逻辑门级联( Cascade)实现不存在热耗散且满足指定可逆操作的量子电路，进而构成计算能力较经典计算机有巨大提高的量子计算机，因此可逆计算是量子计算(Quantum Computing)的核心问题，可逆逻辑电路以量子实现形式为佳，而可逆逻辑综合(Synthesis of Reversible Logic)则是实现量子计算机的关键技术。综上所述，可逆性将成为未来电路设计的基本要求，基于量子实现的可逆逻辑电路将成为进一步降低IC功耗的重要手段，是实现量子计算机的必备条件。因此，研究和解决量子可逆逻辑综合问题将有望推动超低功耗IC设计和量子计算（机）等相关领域的发展，因而成为了国际性的研究热点。
　　 由于量子可逆逻辑电路和常见的不可逆电路存在较大差异，因此其综合方法截然不同于现行的非可逆逻辑电路，生成与优化的难度均更大。目前常规的量子可逆逻辑综合方法普遍不够成熟、自动化程度不高以及缺乏实用性，究其原因主要是由于量子可逆逻辑综合实际上是一种带有强约束且缺乏领域知识的多目标优化问题(Multi-objective Optimization Problems)。如何显著地提高量子可逆逻辑综合的速度、规模、自动化和实用化程度等，目前仍是极具挑战的开放性问题。而进化设计(Evolutionary Design)是利用进化计算(Evolutionary Computation)的高效自动求解能力，寻求不依赖于先验知识和人工干预，通过人工进化(Artificial Evolution)来获得具备预期功能的设计结果，故可探索更为广阔的设计空间，解决常规方法因知识、经验缺乏而无法胜任的复杂问题，实现相关系统的自动设计，因此进化设计是解决量子可逆逻辑综合复杂性问题的有效途径。
　　 本文在系统地论述量子可逆逻辑综合的基本原理、技术特点和研究现状的基础上，将进化设计技术应用于量子可逆逻辑综合，以提高综合水平和实用化程度为目标，寻求以较少的运算量和人工参与，可自动地生成和优化量子可逆逻辑电路的自动综合方法。主要从进化算法、编解码方案、多目标评估方法和自动化简与修复策略等方面入手，对有关设计理论和实验方法进行了较为全面和深入的研究，获得了一些关键性的研究成果，可主要概括为以下几个方面:
　　 (1)通过讨论进化算法的分类和特点，为克服现有遗传算法存在的局部搜索能力差、早熟收敛、随机漫游以及最终解精度不高等主要缺陷，详细地讨论了通过引入有性繁殖、Baldwin效应以及自适应机制来提高进化速度和收敛概率的生物学机理与一般方法，并针对量子可逆逻辑自动综合的特点，提出了一种基于Baldwin效应的自适应有性繁殖混合遗传算法(BSAGA)，并对算法进行了收敛性分析。
　　 (2)在分析和比较已有算法的基础上，根据量子可逆逻辑自动综合的进化设计需要，研究了一种基于进化计算新的重要分支——差分进化(DifferentialEvolution)的自适应离散差分进化策略，并结合Pareto快速分层排序策略和基于聚集密度的按层修剪操作，提出了一种基于Pareto最优的多目标自适应离散差分进化算法( MDDE)，其特点是利用差分进化增强算法的全局搜索能力以获得更优的Pareto近似解，利用Pareto快速分层排序策略和基于聚集密度的按层修剪操作对进化种群进行更新与维护以保持Pareto解集的良好分布性与多样性。
　　 (3)根据文献资料和相关仿真结果，分析、比较常用的量子逻辑门，从中选取最为适用者，构建了用于可逆逻辑自动综合的通用且完备的量子逻辑门级器件库——NCT库。基于上述器件库，研究了支持量子可逆逻辑电路结构自动生成的高效编解码方案（即:基于量子可逆逻辑门级进化阵列模型的网表级编码方案）、实用的综合子目标、高效的适应度评估方法（包括:多目标动态评估方法和基于Pareto最优的评估方法）以及自动化简与修复策略（即:“前位优先”修复机制和基于知识的局部转换策略）等。
　　 (4)面向量子可逆逻辑自动综合问题，分别以基于Baldwin效应的自适应有性繁殖混合遗传算法(BSAGA)和基于Pareto最优的多目标自适应离散差分进化算法( MDDE)为进化设计的基础，同时兼顾功能、实现代价和资源利用率等多个综合目标，并结合上述编解码方案、评估方法和自动化简与修复策略，提出并研究了两种量子可逆逻辑自动综合方法:基于动态多目标评估的量子可逆逻辑自动综合方法、基于Pareto最优的多目标量子可逆逻辑自动综合方法。对上述方法，均通过实验、分析和对比，验证了其有效性和先进性。
　　 本文对量子可逆逻辑综合中的关键性问题进行了有效的探索和尝试，提出了新的自动化解决方法，理论分析和实验结果表明本文方法能够有效地解决相应问题，是对现有常规量子可逆逻辑综合方法的有益增强，并对提高量子可逆逻辑综合的设计水平和实用化程度具有一定的理论价值和应用价值，有望为推动超低功耗IC设计和量子计算（机）等相关领域的发展做出一定的贡献。

目录

声明

东华大学学位论文版权使用授权书

摘要

第一章 绪论

1.1 研究背景

1.2 研究目的和意义

1.3 主要研究内容及创新点

1.3.1 主要研究内容

1.3.2 创新点

1.4 论文的内容安排

第二章 量子可逆逻辑综合概述

2.1 引言

2.2 量子信息与量子计算

2.3 量子计算机与可逆计算

2.4 量子逻辑门

2.4.1 (1，1)量子逻辑门

2.4.2 (2，2)量子逻辑门

2.4.3 (3，3)量子逻辑门

2.5 量子可逆逻辑电路的特点

2.6 量子可逆逻辑综合的研究进展

2.7 量子计算的物理实现研究

2.8 本章小结

第三章 进化计算与多目标进化算法

3.1 引言

3.2 进化计算原理

3.2.1 生物学基础

3.2.2 基本概念

3.2.3 框架模型

3.3 进化计算的研究内容和应用领域

3.4 进化算法的分析与比较

3.4.1 遗传算法

3.4.2 进化策略

3.4.3 进化规划

3.4.4 遗传编程

3.4.5 差分进化

3.5 多目标优化问题

3.6 多目标进化算法简介

3.6.1 发展简史

3.6.2 算法分类

3.6.3 一般流程

3.7 多目标进化算法与传统多目标算法的比较

3.8 多目标进化算法研究进展

3.8.1 关键理论问题研究

3.8.2 应用研究

3.8.3 开放性研究课题

3.9 本章小结

第四章 基于Baldwin效应的自适应有性繁殖混合遗传算法

4.1 引言

4.2 Baldwin效应

4.3 有性繁殖技术

4.4 箅法的设计与实现

4.4.1 算法结构

4.4.2 性别确定方法

4.4.3 适应度评估

4.4.4 选择配对方法

4.4.5 自适应交叉、变异算子

4.4.6 收敛性分析

4.4.7 仿真实验与结果讨论

4.5 本章小结

第五章 基于Pareto最优的多目标自适应离散差分进化算法

5.1 引言

5.2 Pareto最优问题

5.3 一种新型的自适应离散差分进化策略

5.4 算法的设计与实现

5.4.1 算法结构

5.4.2 Pareto快速分层排序策略

5.4.3 种群的更新与维护操作

5.4.4 实例仿真与性能比较

5.5 本章小结

第六章 基于进化计算的多目标量子可逆逻辑自动综合方法研究

6.1 引言

6.2 可逆逻辑基本定义

6.3 量子代价

6.4 电路抽象模型

6.5 编解码方案

6.6 修复与化简方法

6.6.1 前位优先修复机制

6.6.2 基于知识的化简方法

6.7 基于动态多目标评估的量子可逆逻辑自动综合方法

6.7.1 动态多目标评估方法

6.7.2 综合方法的流程设计

6.8 基于Pareto最优的多目标量子可逆逻辑自动综合方法

6.8.1 基于Pareto最优的综合子目标设计

6.8.2 进化综合的结构流程

6.9 综合实验与结果分析

6.9.1 综合基准实例与性能评估准则

6.9.2 门级器件库选用

6.9.3 实验环境与参数设置

6.9.4 性能比较与结果分析

6.10 本章小结

第七章 结论与展望

7.1 结论

7.2 展望

参考文献

致谢

附录

附录A 攻读博士学位期间主持和参与的项目

附录B 攻读博士学位期间发表和投稿的论文

附录C 攻读博士学位期间获得的奖励