复杂数字电路的分解演化研究

侯子锦++刘晨

摘 要：随着科学技术和控制技术水平的提升，复杂数字电路的出现，各行各业由此得到极大发展。本文主要对复杂数字电路技术的分解演化进行研究，包括对国内外研究现状、演化硬件的可扩展性问题进行了探讨，然后对分解演化思想进行了详细分析。

关键词：科学技术；控制技术；数字电路；分解演化

中图分类号：TN79 文献标识码：B 收稿日期：2015-11-10

1.前沿

随着现代科学技术的迅速发展，智能控制系统广泛应用于各行各业，如家用电器、手机、航空航天、军备武器等，其控制系统的实际应用功能越来越强大。20世纪90年代可编程逻辑器件的诞生，促使电路控制系统得到快速发展。在地质勘探、海底探测以及太空探索领域，人类并不能亲身涉足，多采用智能控制系统操纵机器进行探索；但外太空的温度变化及高辐射等导致了对外探测设备的极大损坏。

2.国内外研究现状

von Neumann最早提出开发具有自繁殖和自修复能力的智能机器的构想。1992年，Garis和瑞士联邦工学院提出了EHW的概念，其后EHW得到了快速发展。

1995年10月，EHW技术第一个国际专题会议召开，并成立了研究机构。其后美国、欧洲各国等也建立了各自的EHW研究中心，其研究方向大多为对EHW的EDC方法和技术、EHW的自修复与自容错方法和技术等方面的研究；日本则主要研究EHW的数字模型；而美国、德国以及英国等国大学主要进行模拟型EHW研究。

21世纪，美国的NASA制订了EHW的科研规划，日本、英国的科学家一直进行EHW的容错和自适应的相关研究；另外，美国Xilinx公司针对EHW的研究，特意开发出来了可编程器件；日本、欧美等发达国家主要进行EHW的原理及EHW应用拓展研究。

国内研究起步晚，康立山教授率先在国内开展了EHW的研究，用简单PLD作为硬件基础，尝试对简单的电路结构进行演化。王熙法教授在设计冗余容错电路时采用EHW技术，运用遗传算法生成功能多样而结构却不同的电路。赵曙光教授等人对电路演化设计方法进行了研究，提出基于最小项表达式的编码方式。王友仁教授研究了EHW的原理及关键技术，基于FPTA模型借助离线演化方式演化了运算放大器等电路。朱明程教授主要对EHW结构和算法进行了研究，通过研究EHW算法，对多种不同算术功能的演化电路细胞结构进行演化。韩月平等人研究了基于EHW的容错技术。原亮教授对数字EHW、平台进行了研究。另外，还有部分科研机构对EHW进行了详细研究，但其成果滞后于发达国家。EHW作为一个新兴的研究领域，投入小，产出小，但距离产业化水平还有一定距离。

3.演化硬件的可扩展性问题

造成演化硬件可扩展性问题的因素有三个：①染色体基因由逻辑门编码和连接关系编码组成，且演化过程中存在大量冗余逻辑单元，导致目标电路演化规模越来越大，需冗余单元也越来越多，给演化扩展计算造成了很大困难。②组合的输入输出比较多，算法在搜索空间上所占有的资源十分大。随着算法演化工程规模的不断扩大，数量的输入与输出也越来越多，真值表长度与输入个数呈指数级关系，真值表的扩大给电路个体适应度评价带来巨大困难。③真值表的复杂度随着要求的越来越高而提升，直接导致了个体适应度所需时间不断延长，进一步导致了演化的速度不断降低。

4.分解演化思想

研究者根据上述3个因素，提出了“分而治之”的方法：以降低演化规模为研究重点，使染色体编码难度降低，最终使算法搜索空间缩小，从而解决电路演化可扩展性问题。Kalganova提出了双向增量演化，E.Stomeo提出了通用分解演化算法。BIE的思想是将电路分解为多个子电路，然后对子电路进行演化，当子电路都演化完成后，再把各个子电路组合成一个电路，并不断进行优化；但该方法还存在很多缺点，主要是遇到电路输入组合多的情况时不能进行过多的处理。GDD的主要思想是，开始演化前根据研究人员个人经验对整个控制系统进行输入分解，将整个演化系统分解为可演化和固定两部分：可演化部分的输入是待演化系统输入的一部分；而固定部分则是由事先设计好的选择器组成。GDD方法能有效解决电路输入组合的难题，但在电路输出较多的情况下，仍然存在很多需要解决的问题。

参考文献：

[1]郭晓珉，姚 睿，刘智跃，等.利用运动强度判据的高效自适应运动估计算法[J].中国图像图形学报，2012，（4）.

[2]郝国锋，王友仁，张 砦，等.可重构硬件芯片级故障定位与自主修复方法[J].电子学报，2012，（2）.