电路进化设计算法研究

论文摘要

电路进化是一种基于群体搜索和可编程硬件的智能进化设计方法。它的出现是智能算法与可编程硬件共同促进的结果,正受到越来越多的关注。使用进化算法设计的电路,能发现新颖的人们难以想到的电路结构,能降低需要的门资源或晶体管数量从而提高芯片的利用率,能降低电路的连接级数提高信号的传输速度。若使用内部进化的方式设计电路,还能使所得电路具有自组织、自修复、自适应的特性。因此开展电路进化设计研究具有重要的应用价值。目前有关电路进化设计的研究还不是很成熟。不论是内部进化方式还是外部进化方式,所能设计的电路规模都比较小,很难付诸实际应用。本文旨在通过对组合逻辑电路进化设计、时序电路进化设计和多态电路进化设计等进行深入研究和探索,提出高效的进化设计算法与策略,从而提高电路进化设计算法的求解性能。论文的主要研究工作与创新点包括以下几个方面:（1）提出了基于修复技术的组合逻辑电路快速进化设计算法。该算法利用候选电路在进化的初始阶段适应度增加很快的现象,先进化出一个功能大致正确的电路;然后转入修复过程并对不正确的输出进行修正,最终设计出功能正确的电路。实验结果表明了该算法是有效的。为了能对进化出的有错误的电路进行修复,专门设计出了简单而规整的修复电路的构造方法。附加的修复电路与进化生成的对大部分输入都能输出正确结果的电路结合在一起,形成最终的功能完全正确的电路。该方法极大地减少了进化所需的时间。（2）提出了基于三步分解方法的同步时序电路进化设计算法3SD-ES。该方法结合低功耗技术中已有的时序电路分解方法、进化设计领域中的输入分解、输出分解方法及进化策略。实验结果表明该算法具有更好的可扩展性。对时序电路而言,状态分解的粒度参数、输出分解的粒度参数及输入分解的粒度参数三者之间互相关联,手工设置往往顾此失彼。针对这一问题,本文给出了自动设定分解参数的方法。（3）提出了基于加权方法的多态电路进化设计算法。该算法针对多态电路中各功能电路进化难度不同的特点,首先提出了基于加权和方法的进化算法,实验结果显示除了个别电路外,基于加权和方法的进化算法的性能好于传统进化算法。然而,加权和方法需要事先做很多实验来确定各电路的难易程度,以便设置合理的权重。针对此问题,本文又进一步提出了动态加权法。实验结果表明对大多数测试电路动态加权法的效果优于加权和方法。本论文以进化算法为基本手段,对组合电路、时序电路和多态电路的进化设计进行了较为深入的研究。这不仅对电路进化设计的研究有着重要的意义,也对促进智能计算的应用研究有重要的意义。

论文目录

• 摘要
• ABSTRACT
• 目录
• 插图目录
• 表格目录
• 第1章 绪论
• 1.1 进化型硬件简介
• 1.1.1 硬件进化工作原理
• 1.1.2 硬件进化研究现状
• 1.2 电路进化设计概述
• 1.2.1 电路进化设计的概念及其与硬件进化的关系
• 1.2.2 电路进化设计的算法框架
• 1.3 组合逻辑电路进化设计研究现状
• 1.4 时序逻辑电路进化设计研究现状
• 1.5 多态逻辑电路进化设计研究现状
• 1.5.1 多态门的概念及研究现状
• 1.5.2 多态电路的概念及研究现状
• 1.6 电路进化设计面临的问题
• 1.7 本文主要研究内容和创新之处
• 1.8 本文内容的组织与安排
• 1.9 本章小结
• 第2章 基于修复技术的电路进化设计算法
• 2.1 引言
• 2.2 适应度评估方法
• 2.3 Stalling effect现象及实例分析
• 2.4 修复技术原理
• 2.4.1 基本原理
• 2.4.2 示例
• 2.4.3 修复电路所耗的门单元数
• 2.5 算法流程
• 2.6 实验结果
• 2.6.1 修复技术与Es相结合的进化设计算法
• 2.6.2 修复技术与shannon分解法相结合的进化设计方法
• 2.7 本章小结
• 第3章 基于三步分解的时序逻辑电路进化设计算法
• 3.1 研究现状回顾
• 3.2 相关背景知识
• 3.2.1 外部进化
• 3.2.2 组合逻辑电路分解方法
• 3.2.3 时序逻辑电路分解方法
• 3.3 3SD-ES
• 3.3.1 3SD-ES框架
• 3.3.2 一个具体的例子
• 3.4 实验
• 3.4.1 小规模型时序电路的进化生成
• 3.4.2 较大规模时序电路的进化生成
• 3.4.3 三种分解方法对算法性能的影响
• 3.4.4 自动设置分解参数
• 3.5 讨论
• 3.6 本章小结
• 第4章 基于加权法的多态电路进化设计算法
• 4.1 问题的提出
• 4.2 相关工作
• 4.3 加权和方法
• 4.3.1 CGP模型及（μ,λ）ES简介
• 4.3.2 加权和方法描述
• 4.3.3 实验结果
• 4.3.4 讨论
• 4.3.5 加权和方法小结
• 4.4 动态加权法
• 4.4.1 问题及对策
• 4.4.2 相关工作
• 4.4.3 动态加权法描述
• 4.4.4 与已有方法的比较实验结果
• 4.4.5 pDWAM参数分析
• 4.4.6 用pDWAM进化设计三态和四态电路
• 4.4.7 讨论
• 4.4.8 动态加权法小结
• 4.5 本章小结
• 第5章 总结与展望
• 参考文献
• 致谢
• 读博期间发表的学术论文与参加的科研项目