论文部分内容阅读
数字电路演化设计是演化硬件(EHW:Evolvable Hardware)的一个分支,演化硬件是指用演化算法等智能计算方法自动地设计电路系统。到目前为止,遗传算法、演化策略、基因表达式编程、遗传程序设计、粒子群优化等智能算法均已被应用到演化硬件中。演化硬件主要关注两方面的内容,一方面是,电路的自动化设计,另一方面是,电路的自适应性。
演化硬件的概念萌生于冯·诺依曼提出的研制能够进行自我繁殖、自我修复并能进行通用计算的机器的设想。Hugo de Garis和瑞士联邦工学院的科学家在1992年正式将此构想提出,随后的十几年,演化硬件获得了广泛的关注。
演化硬件有着很大的发展和应用前景,特别是在工业和太空领域,工业中硬器件的高负荷运作,太空中恶劣环境的影响,硬件很容易出错,一般这种情况,只能人工更换或修理,产生了工作寿命的瓶颈,而且在太空领域,如果有器件出错,更为浪费资源。
另外,人工设计电路需要较多的硬件知识基础,设计过程较为繁琐,一般采用分块组合的方式进行设计,无法保证电路是最优的。采用演化硬件方法进行电路优化设计,可以不需要太多的硬件知识,直接对目标电路进行演化。数字电路演化设计是演化硬件中的一个方面,也是基础,对其进行研究有着很大的意义。
数字电路应用广泛,在很多领域有着不可替代的作用。小规模的数字电路可以通过人工方法手动设计出来,而随着数字电路的规模逐渐增大,手工设计方法的难度成倍增大,当规模到达一定的程度,手工设计方法就没有可行性。而演化算法则可以解决这一难题,演化算法利用自然界中的生物进化规律,结合计算机的超级计算能力,可以解决那些人工方法无法完成的难题。本文就演化数字电路中的单支问题展开研究。
本文首先在第一章介绍演化硬件的相关概念,国内外研究现状,以及存在的问题和前景分析。在第二章则主要介绍几种常用的演化算法,以及演化算法的基础知识,适应度函数的选取和各种常见的遗传算子。
第三章首先介绍了经典的三元组编码模型,分析其中的不足之处,引出单支问题,即本文研究的核心内容。三元组编码模型也称为CGP(Cartesian Genetic Programming),用三个实数构成的三元组来表示一个逻辑门及其在电路中的连接关系。因此任何一个电路都可以用一个三元组串来表示。这种编码方法已经被国内外的研究人员广泛采用,并在其基础上提出了很多的改进方法。三元组编码有许多缺陷,采用此编码时,交叉算子对算法影响小,实际操作时,一般不用交叉算子,而是只采用变异算子;还有算法容易陷入“stallingeffect”状态。本文所研究的单支问题正是针对这些缺陷提出来的,在演化数字电路算法的后期,只有一个输出端不正确,问题就退化为单输出端数字电路问题。这时,采用本文中的树型编码方法,可以快速解决。再对两部分电路加以整合,就可以得到我们想要的结果。通过实验结果可以总结出,每一种类型的数字电路都会侧重某几种逻辑门,用于构成该电路,这里称为“高效门”。加法器的“高效门”有“异或”、“二路选择器”、“或”,乘法器的“高效门”有“与”、“异或”、“二路选择器”,奇偶校验器的“高效门”有“异或”、“同或”。因此我们会根据不同类型的电路对所有逻辑门设定不同的权值。
第四章是实验部分,主要以加法器、乘法器、奇偶校验器为实例,利用本文中的方法进行实验,实验结果表明,本文的研究很成功,可以得到目前同行的最好实验结果。本文在最后还指出了一些需要改进的地方,以及以后的工作和下~步的研究目标。