南京航空航天大学硕士学位论文数字电路多目标在线进化及异构容错系统设计姓名：高桂军申请学位级别：硕士专业：测试计量技术及仪器指导教师：王友仁20080101南京航空航天大学硕士学位论文 i摘 要 演化硬件是一种模拟生物进化原理来实现电路设计自动化的有效方法，演化硬件通过在线进化可以实现自适应和自修复，在航空航天领域有着重要应用前景。本文主要研究内容为： 1. 研究了数字电路多目标进化设计， 改进了一种基于约束法的多目标进化算法，解决了在进化过程中电路功能、电路逻辑门数和电路延时三个目标的协同优化设计问题。针对多目标进化设计引起的收敛速度减慢缺点，引入了生长进化策略，利用优良基因“锁定”的方法，提高了多目标进化设计的收敛速度。 2. 研究了数字电路函数级进化设计， 通过逐级分解进化的方法实现较大规模数字电路在线进化，并采用生长进化策略，提高了电路的进化收敛速度。 3. 研究了异构冗余容错系统设计方法， 对比了异构系统与同构系统的容错性能，改进了“活动节点”异构评价法，提出了“拓扑结构”异构评价法，通过设计实例分析了两种设计方法的优劣。 4. 研究了异构冗余容错系统多目标优化设计技术。 针对系统逻辑门数对系统容错性能的影响，通过使用多目标优化方法，进一步改进设计系统的容错性能。 本文的研究工作受到国家自然科学基金（60374008，90505013）与航空科学基金（2006ZD52044）的资助。 关键词：演化硬件，数字电路，在线进化，多目标优化算法，函数级进化，异构冗余容错系统 数字电路多目标在线进化及异构容错系统设计 iiABSTRACT Evolvable hardware is an effective method which simulates the biological evolutionary principle to implement the circuit design automation. Evolvable hardware has an important application in the field of the aeronautics and astronautics because it can accomplish the self-adaptation and self-repair by on-line evolution. The main research contents of this paper are as follows: 1. The multi-objective evolutionary design of digital circuit was researched. A multi-objective evolutionary algorithm based on constraint method was improved. The problem of cooperative optimization design of the performance, the active logical gates and the time-delay of circuits was solved during the evolution process. Aiming at the disadvantage of the slow convergence speed of the multi-objective evolutionary design, the growth evolution strategy was used. The convergence speed of multi-objective evolutionary design was increased because the excellent genes were locked. 2. The function level evolution design of digital circuit was researched. The medium size digital circuit was implemented through decomposing aim circuit to smaller circuits gradually. The convergence speed of function level evolution was raised by the growth evolution strategy. 3. The design methods of redundancy fault-tolerant system with different structures were researched. The fault-tolerant performances of the systems between the same structures and the different structures were compared. The “active gates” evaluation method was improved. The “topological structures” evaluation method was designed. The performances of the two methods were analyzed by the example. 4. The multi-objective optimization design technology of redundancy fault-tolerant system was researched. Aiming at the fault-tolerant influence of the logical gates, the fault-tolerant performance of the system was enhanced by multi-objective optimization design method. The work presented in this paper has been funded by National Natural Science Foundation of China (60374008, 90505013) and Aeronautical Science Foundation of 南京航空航天大学硕士学位论文 iiiChina (2006ZD52044). Key Words: Evolvable Hardware, digital circuit, on-line evolution, multi-objective optimization algorithm, function level evolution, fault-tolerant system with different structures 数字电路多目标在线进化及异构容错系统设计 vi图、表清单 图 2.1 演化硬件基本原理.6 图 2.2 演化硬件实现方法基本流程.7 图 3.1 按决策过程分类的多目标优化分类图.10 图 3.2 按实现方法分类的多目标优化分类图.11 图 3.3 电路多目标进化设计过程.13 图 3.4 多目标进化元胞阵列结构图.15 图 3.5 染色体编码示意图.15 图 3.6 加速收敛进化过程示意图.16 图 3.7 “生长型”多目标进化算法实现流程图.17 图 3.8 多目标优化与单目标进化的结果对比.21 图 3.9 收敛曲线对比图.22 图 3.10 两种多目标优化算法的进化时间对比图.22 图 3.11 单目标进化的一种典型电路结构图.23 图 3.12 多目标进化的一种典型电路结构图.23 图 4.1 函数级进化实现示意图.26 图 4.2 函数级进化编码示意图.27 图 4.3 函数级进化收敛速度比较图.28 图 4.4 4*2 乘法器结构图.29 图 4.5 2 位乘法器电路结构.29 图 4.6 2 位加法器电路结构.29 图 5.1 三模冗余（TMR）结构原理图 .33 图 5.2 N 模冗余结构原理图