第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