第6卷第5期 智能系统学报 Vol.6 No.5 2011年10月 CAAI Transactions on Intelligent Systems 0ct.2011 doi:10.3969/i.issn.16734785.2011.05.010 一种染色体编码新方法的硬件进化 张超，刘峥，赵伟 (西安电子科技大学雷达信号处理国家重点实验室，陕西西安710071) 摘要：提出了基于FPLA的染色体编码及在此基础上的并行硬件进化方法.该编码方式以与或非门为基本单元，进 化时将电路编码染色体按逻辑门分解，进行适应度计算时采用分解逆过程使染色体合并，可以有效缩短进化时间， 有利于大规模复杂电路的进化.以4位二进制码转换为格雷码的电路为例进行试验，该方法在20次实验中平均速度 提高了32.25%.为实现内进化编写了由染色体生成Verilog硬件语言的C程序，该编码方式同时适用于多输入多输 出电路进化且染色体长度可变，利用此特性生成了异构电路，完成了容错，对于实现故障模块在线修复，提高太空恶 劣环境中电子系统可靠性具有一定意义· 关键词：硬件进化：染色体编码；PLA;Verilog硬件语言 中图分类号：TP18;TP302.8文献标志码：A文章编号：16734785(2011)05045006 Hardware evolution based on a new chromosome encoding method ZHANG Chao,LIU Zheng,ZHAO Wei National Laboratory of Radar Signal Processing,Xidian University,Xi'an 710071,China) Abstract:This paper proposed an FPLA-based chromosome encoding approach and a parallel hardware evolution method on the basis of a new encoding approach.The AND-OR-NOT gates are the basic units of the chromosome, so by decomposing the chromosome while evolving and integrating it when computing the adaptation,the evolution time can be shortened.This benefits the evolution of massive and complex circuits.Taking the circuit of changing 4 bits binary code to gray code as an example,the result shows that the average speed increases 32.25 percent over 20 evolutions when using the proposed method.In order to facilitate intrinsic evolutions,the C program was also exploited for translating the chromosome to Verilog hardware language.The encoding method was able to handle multi-input and multi-output circuit evolution,and the chromosome's length was variable.According to the evolu- tion of the heterogeneous circuits based on this feature,fault tolerance was achieved.This work is significant for on- line repair used to improve the reliability of electronic systems exposed to harsh space environments. Keywords:hardware evolution;chromosome encoding;field programmable logic array(FPLA);Verilog HDL 进化硬件(evolvable hardware,EHW)也称演化件技术取到了一定的研究成果，例如Torresen等采 硬件或仿生硬件，是一种具有自组织、自适应和自修用“分解法”，将电路划分成多个较小的子电路分别 复特性的新型智能硬件)，它将计算机技术与基于 予以进化[3)]；Kalganova等提出了能自动且逐步将复 优胜劣汰、自然选择的进化算法结合在一起，可以不 杂任务分解成多个子任务的双向积累式进化方法 在人工干预的条件下通过进化来获得满足给定条件 (bidirectional incremental evolution)[4等.虽然这些 的电路和系统，进而使系统自动、实时地调整其内部 方法使得大规模复杂电路的进化实现成为可能，并 结构，以适应内部条件（如局部故障）和外部环境的 且在进化时间上得到一定改善，不过染色体长度较 变化2].为解决大规模电路的进化问题，可进化硬 长以及耗时较大的问题，依然制约着大规模复杂电 路的形成.另外PGA厂商对其产品中配置的形成、 收稿日期：2010-1220. 基金项目：陕西省自然科学基础研究计划资助项目(SJ08F19) 数据流下载格式及相应的校验方法等资料不予开 通信作者：张超.E-mail:gzzc@163.com 放，使得直接通过染色体位串下载配置而进行内进
第5期 张超，等：一种染色体编码新方法的硬件进化 ·451· 化的实验不易实现.在进化过程中硬件系统与环境 位，第1位代表原输入，第2位代表非门，后面的M 始终保持交互，而处于宇宙空间中的电子系统极易 列代表或门.将编码矩阵展开成一维序列，即可得基 受工作环境的影响，特别是由于高能粒子辐射而产 本的染色体的编码.以半加器为例，其最小项结构所 生的单粒子翻转效应(single-event upset,SEU).所 对应的二进制编码染色体为{100101101010110001}. 以EHW的出现为电子系统容错尤其是空间应用中 前12位为与非门，其中非门和与门交替出现，后6 系统自修复提供了一种新的方法。 位为或门.一般在进化前电路的结构未知，故电路中 文章首先提出了一种长度可变且能实现多输入 所用门的数量同样未知.若采用此种编码，矩阵的列 多输出组合逻辑的染色体编码方式，并结合Torres- 数由于与输入和输出所对应而固定，而行数可以相 en“分解法”提出了能显著提高进化速度的并行进 对自由地调整，于是可通过对编码矩阵行数的控制 化方法，对其性能进行了验证.接着为实现内进化编 来调整门的数量.这样在进化前需要对逻辑门的数 写了染色体至Verilog语言的C语言翻译程序.最后 量有一个初始的估计，并输入一定的参数， 在分析文章所提出的染色体编码特性的基础上进行 了异构电路进化，结果表明EHW可以很好地完成 inl in2 inN 或门阵列 与非门 或门 00…001可 硬件电路在空间环境中的容错，实现系统故障的在 0100.10 1 线修复 1基于FPLA的染色体编码分析 … 010-0匝可 0 现场可编程逻辑阵列(field programmable logic 与非门阵列 outl out2 out/ aray,FPLA)是在可编程只读存储器(programmable 图1基于FPLA的染色体编码过程 read-only memory,PROM)的基础上发展起来的可 Fig.1 Chromosome encoding based on FPLA 编程逻辑器件(programmable logic device,PLD),它 的与阵列及或阵列均可编程.采用PLA实现逻辑 1.2基于外进化的功能验证 函数时只需运用化简后的与或式F:=∑m,(K为 为验证基于PLA的染色体编码可行性并分析 输出端口数，m为最小项)由与阵列产生与项，再由 其进化性能，以4位二进制码转换为格雷码的电路为 或阵列完成与项相或的运算后便可得到输出函数， 例进行试验.此电路为4输入4输出，染色体矩阵列 这种结构在电路功能实现上具有很大的灵活性.如 数为12列，假设进化生成的电路用最小项表示，则其 果以PLA结构为基础进行染色体编码那么可以很 对应的二进制一维染色体编码有84位，具体结构为 {1000000010010000011000000010010000011000000010 容易实现多输入多输出系统，这有助于复杂电路的 01000001101000000011000000011000000011 编码和生成.并且其编码方式是以与或非门为基本 逻辑单元，故可以通过染色体分解，对3种逻辑门所 试验采用简单遗传算法(SGA),随机产生初始 属的染色体采用分开的并行进化方法，这为提高进 种群(initial population,P),选择算子采用赌轮选 择法，交叉算子为单点交又，交叉率为0.8，变异算 化速度和实现较大规模电路的进化提供了可能性， 1.1染色体编码 子为一点变异，变异率为0.006.由于采用外部进 染色体的编码方式也称为基因表达方式(gene 化，故以子代染色体与所需染色体的匹配性能为适 representation).在遗传算法中，种群中的个体，即染 应度函数(fitness function),如式(1)所示， 色体是由基因构成的.所以染色体与问题的解如何 万：1-a16-41 (1) 对应，就需要通过基因来表示，即对染色体进行正确 的编码.染色体编码主要有二进制编码、实数编码、 式中：i为种群数量；c:为个体，d为所需染色体向 序列编码、树编码等.Holland提出的简单GA(sim- 量，c:为染色体长度.适应度f维持在0~1之间，0 ple genetic algorithms,SGA)使用二进制编码，即使 表示完全不匹配，1表示完全匹配，既进化成功，适 用0-1字符串表示一个染色体.这里采用二进制编 应度越高则相似度越高.任意4次的进化曲线如图 码.假设系统为N输人M输出，则基于PLA结构的 2所示 编码过程如图1所示.每个输入在每一行中占据2
·452· 智能系统学报 第6卷 (P2)及变异率(Pm)如式(2)所示，其中Pa和Pml为 1.0 1.0 原始交叉率和变异率，N为分解后的染色体个数，实 09 08A 验中N等于3.分析式(2)可知，并行进化时交叉率 0.6 906 和变异率都增大了，不过这与简单地增大原染色体 的交叉、变异率不同.分解染色体后，整条染色体不 0.4 12345×100.4 1234x10 是发生某一种定义好的变异，它可以以不同的概率 进化代数 进化代数 发生一点变异、两点变异及三点变异，其概率由式 (a)进化过程1 b)进化过程2 (3)可得，且它们是由限定在不同染色体区域的变 1.0 1.0r 异组合而成，不过对于分解后的某一区域只可能在 一代遗传过程中发生一次变异，这样避免了变异过 ,0.8 0.8 别 度集中而保证了全局的最优及高效的进化速度，同 月0.6 0.6 时保留了不同部分独立进化的性能优势.整条染色 体的某一位在一代遗传中也只可能发生一次变异， 0.4 1 2345×10 0.4 1 23410 进化代数 进化代数 这样不会出现变异抵消的情形.对于交叉的分析，其 (c进化过程3 (d)进化过程4 情况与变异相同，其一次、两次及三次交叉概率由式 图2任意4次进化曲线 (4)可得.由式(3)、(4)可知，从一点变异到三点变 Fig.2 Arbitrary four evolution curves 异概率依次降低，从一次交叉到三次交叉概率依次 1.3基于染色体分解的并行进化 增加. 由图2可以看出在随机产生初始种群的基础 上，在200~500代电路可以进化成功.文献[4]提 Pa=(2）41-2产=1-1-y 出了一种将整个系统划分成多个子系统进行进化的 方法，以提高进化性能.参考其划分电路的思想，考 e=ka-产=1-4- 虑将整个电路编码后的染色体进行分解.这样不仅 (2) 可以使系统进行并行的进化，而且每个进化的染色 体长度会大大减少 实验中染色体采用基于PLA的编码方法，故 (3) 可以将染色体中与或非门进行分离，由于每个与门 的入口都对应一个非门，故与门和非门的数量相同， Pne3 =Pm 其对应染色体长度也相等，剩下的既为或门染色体 实验中与非门编码长度为28位，或门编码也为28 Pa - 位.每一代进化时，各段染色体独立进行交叉、变异 (4) 等运算，进化参数相同.而进行适应度计算时应用分 解的逆运算过程将染色体进行合并，组成完整的染 P23=p2. 色体而进行评估及选择，合并时采用顺序合并，即将 编号相同的染色体进行合并. 分别采用改进前和改进后的进化方法各自进行 与文献[4]中分解法不同的是这里的分解对象 了20次试验，统计了其进化成功所用的代数，结果 为整条染色体，且不是以电路功能进行模块化的划 如表1所示.由进化结果可以看出，在20次进化试 分，这样避免了进化时对电路尤其对复杂电路划分 验中，采用逻辑门分离的方法每一次进化所需的代 的工作，进化时各染色体之间也不是毫无关联的独 数都小于改进前进化所需的代数，而在平均代数上 立进化，而是共同参与适应度计算和父代选择， 并行进化比改进前减少了84.1代，平均速度提高了 对于整条染色体，并行进化方法下的交叉率 32.25%
第5期 张超，等：一种染色体编码新方法的硬件进化 ·453· 表1进化代数比较 Table 1 Comparison of generations 进化次数 3 4 5 67 8910 11 改进前进化代数 255 175190274192413366187219187184 改进后进化代数 153 172 187170 190209 161150 215 172170 进化次数 12 13 14 15 16 17 18 19 20 平均代数 改进前进化代数 250361198 292240 269 239 225 500 260.8 改进后进化代数 175172164146195 208 169 157 199 176.7 此外，如前所述，从编码结构来看，染色体矩阵 获取端凵数目 的行数不固定.如果通过对电路规模的初始估计或 者随机给予比较小的初始行数，那么可以进一步通 读取染色体编码 过进化代数的设定来控制进化时间与成功率.如果 设定的进化代数达到而尚未得到所需要电路的结 构，那么EHW可以自动增加资源量继续进行进化， 分离瑞口信息 区分与非门和或门 这样保证了进化的成功率.硬件资源使用少（染色 体编码长度小)也可以使得电路结构的进化结果趋 模块起始与 区分与非门 结束部分生成 于最简化，相应地可以预测，如果硬件资源量多，那 么进化会生成多种此最简电路复杂的异构体，如果 非门硬件 与]硬件 或门使件 这样，可以通过控制染色体长度对系统的结构进行 语言生成 话言生成 语言生成 控制，而异构电路有可能避开硬件逻辑出错的部分， 完成对电路的容错，这将在第3节进行分析。 Verilog程序 2染色体转换至解码程序设计 图3染色体解码流程示意 可进化硬件技术分为内部进化和外部进化，内 Fig.3 Flow chart of decomposing chromosome 部进化时硬件电路的进化在硬件里实现，而外部进 仍以4位二进制码转换为格雷码的电路为例进 化的电路进化和评估在软件中进行51.商业PGA 行试验.输入端口数目及染色体编码得到的翻译结 芯片的内部结构不公开，不能接收随机配置位 果如图4所示.其中func为模块名称，inl、in2、in3、 串6)，若进行内部进化实验则需要对所用器件进行 in4为输人端口，out1、out2、ou3、out4为输出端口， 十分复杂的数据流格式分析，人工干预将每一次进 assign为组合逻辑赋值语句，~为“取反”运算符，& 化的结构进行翻译下载至FPGA(field programmable 为“按位与”运算符，|为“按位或”运算符.经过后续 gate array)中运行、检测.因此，对于基于FPGA的 的语法完善便可以直接进行综合及下载到可编程器 EHW研究，设计高效的硬件编程语言生成器，使其 件中进行试验： 能够直接将基于二进制编码格式的染色体位串转换 module func: 至以文本方式表示的硬件语言代码，并自动进行后 assign a0=inl: assign al=in1&-in2: 续处理，以避免人工操作或干预，是完成“演化一实 assign a2=~inl&in2: 现一反馈一评估一再演化”闭环结构的关键可 assign a3=in2&~in3: assign a4=-in2&in3: 翻译染色体时，首先需要告知程序进化电路输 assign a5=in3&~in4: assign a6=-in3&in4; 入与输出接口的数目与具体的染色体编码.根据这 assign outl=a0; 些信息，程序通过染色体编码固有的规则对与非门 assign out2=alla2: assign out3=a3la4: 进行划分，分别进行与非门的识别和互联结构的解 assign out4=a5la6; endmodule 码，最后将3种逻辑门再重新组合并最终通过程序 语言体现出来.染色体编码至Verilog语言的程序流 图4染色体翻译结果 程示意如图3所示 Fig.4 Results of decoding chromosome
454 智能系统学报 第6卷 3异构容错 电路并应用，当3个异构电路有1个出错时，系统即 对故障电路进行屏蔽，待修复成功后再重新投入运 由于EHW采用了进化算法而具有适应环境的 行9].这样EHW可以很好地实现系统故障的修复， 特性，所以它本身固有容错功能，而基于PLA的染 对于受太空辐射影响的空间电子系统具有很广阔的 色体编码长度可调，这为基于异构电路的容错提供 应用前景。 了条件.以4位二进制码转换为格雷码的转换电路 4 为例进行外部进化试验，利用第2节中设计的程序 结束语 进行染色体解码并生成TL级文件。 文章对可进化硬件从染色体编码到进化实现进 a.5 行了研究，提出了基于PLA的染色体编码方法.试 0ut4-0 验证明此种编码可用于多输人多输出电路的生成， a 同时应用并行进化思想，通过染色体分解，在20次 的进化试验中平均速度提高了32.25%.通过改变 染色体长度可以控制电路的复杂度和进化代数，同 11t3-0 时可以用于进化功能相同的异构电路进而保证进化 out3 成功率.实验表明，通过异构电路的进化可以避开硬 件故障区，进而完成容错，这为受空间辐射影响而产 生的硬件永久性故障修复，提供了一种新的思路. 0112~0 out2 文章提出的方法仍需要后续深入的研究.首先 对二进制编码进行改进，防止存储和计算资源随演 out 化电路规模增长而指数性增长，进一步减少染色体 图5最简进化结果 的长度与初始种群数量，从而提高进化速度.其次， Fig.5 The simplest evolution result 对时序电路的生成进行研究，完善电路的进化功能。 再次，对染色体分解和组合的策略进行深入的研究， a5 0ut2-3 out2-4 最后，构建硬件电路，进行内仿真，进一步分析进化 in4 ●out2 out4-0 性能以及确定进化中的各种参数设定对系统进化的 ●out4 影响 out2-0 参考文献： out3-0 a4 ●out3 [1]王友仁，姚睿，朱开阳，等.仿生硬件理论与技术的研究 out2 现状与发展趋势分析[J].中国科学基金，2004,18(5)： in. 273-277. 出错部分 WANG Youren,YAO Rui,ZHU Kaiyang,et al.The pres- ent state and future trends in bio-inspired hardware research ●out [J].Bulletin of National Science Foundation of China, 2004,18(5):273-277. 图6图5所示电路的异构进化结果 [2]XIN Y,HUGICHI T.Promises and challenges of evolvable Fig.6 The different evolution results of the circuit hardware[J].IEEE Transactions on Systems,Man,and shown in Fig.5 Cybernetics-Part C:Applications and Reviews,1999,29 当染色体的长度满足进化最简电路的条件时， (1):8797. 其进化的结果如图5所示.假设图5中al和2输 [3]TORRESEN J.A divide-and-conquer approach to evolvable 出后的或门出现故障，因图5为最简电路，故此时增 hardware[C]//Proceedings of the Second International Con- 加染色体长度，继续进化得到非最简的异构电路如 ference on Evolvable Systems:From Biology to Hardware 图6所示.可以看出，异构电路的布局布线绕开了出 (ICES'98).London,UK:Springer-Verlag,1998:57-65. [4]KALGANOVA T.Bidirectional incremental evolution in ex- 错部分，保证了电路正常工作.如果结合TMR(t- trinsic evolvable hardware[C]//Proceedings of the Second ple-module redundancy)利用进化算法进化出3个能 NASA/DOD Workshop on Evolvable Hard-ware (EH'00). 够实现需求功能的电路，然后每进化成功一个电路， Washington,DC,USA:IEEE Computer Society,2000:65- 进行一次非相似度评价，保留3个非相似度最大的 74
第5期 张超，等：一种染色体编码新方法的硬件进化 ·455· [5]JACKSON D.Partitioned incremental evolution of hardware 三模冗余系统设计及实验研究[J].电子学报，2010,38 using genetic programming[C]//Proceedings of the 11th (1):177-183. European Conference on Genetic Programming.Berlin,Ger- YAO Rui,WANG Youren,YU Shenglin,et al.Design and many:Springer-Verlag,2008:86-97. experiments of enhanced fault-tolerant triple-module redun- 6]Xilinx Ine.Two flows for partial reconfiguration:module- dancy systems capable of online self-repairing[].Acta based or difference based [EB/OL].[2010-05-11].http: Electronica Sinica,2010,38(1):177-183. //www.xilinx.com /support/documentation/application_ 作者简介： notes/xapp290.pdf. 张超，男，1986年生，硕士研究生， [7]原亮，丁国良，褚杰，等.EHW实现过程中VHDL程序自 主要研究方向为空间信号处理系统及 动生成研究[J].军械工程学院学报，2008,20(4)：66- 其容错技术 69. YUAN Liang,DING Guoliang,CHU Jie,et al.Automatic making of VHDL program for EHW processing[J].Journal of Ordnance Engineering College,2008,20(4):66-69. [8]姚爱红，张国印，关琳.基于动态可重构PGA的自演化 刘峥，男，1964年生，教授，博士生 硬件概述[J].智能系统学报，2008,3(5)：436442. 导师，西安电子科技大学雷达信号处理 YAO Aihong,ZHANG Guoyin,GUAN Lin.A survey of dy- 国家重点实验室副主任，主要研究方向 namically and partially reconfigurable FPGA-based self- 为多源信息融合、雷达信号处理及精确 evolvable hardware[J].CAAI Transactions on Intelligent 制导技术.目前承担国家“863”计划重 Sy8tems,2008,3(5):436-442. 点项目、空军重大工程研发项目、国防 [9]姚容，王友仁，于盛林，等.具有在线修复能力的强容错 科技预研项目等多项科研项目！ ET自动控制和人工智能国际会议 The International Conference on Automatic Control and Artificial Intelligence (ACAI 2012) The International Conference on Automatic Control and Artificial Intelligence(ACAI 2012)will be held from March 24th to 26th,2012 in Xiamen,China.ACAI 2012 aims to provide a high-level interational forum for researchers and engineers to present and discuss recent advances,new techniques and applications in the field of control engineering,manufacturing engineering and artificial intelligence. In addition to the conference proceedings,papers,which are presented in this conference and related to the area of nano- materials or nanotechnology,will be selected and published in a special section in J.Nanoscience All the conference pa- pers will be published by IET,included in the IEEE. Important Dates: Papers due:Nov.10,2011 Acceptance notification:Dec.1,2011 Registration:Jan.10,2012 Conference date:Mar.24-26,2012 Contact us: E-mail:acaiconf@gmail.com acaiconf@vip.163.com Tl:+86-136-9695-1720+86-151-6001-9681+860592-6035272 Website:http://www.acaiconf.org/