（电路与系统专业论文）基于演化硬件的遗传编程改进研究.pdf

摘要 摘要 演化硬件是将演化算法和可编程器件进行有机结合的一种全新的设计领域。 本文先对演化硬件的基本原理和分类以及可编程器件平台进行了基本的介绍。其 次本文详细的研究了四种演化算法基本原理和算法的详细步骤，并对这四种算法 的优缺点做了比较和研究。 针对演化硬件电路自动设计的特点，本文从编码的角度选择了遗传编程算法 并对其进行改进。本文首先采用分组混合法对遗传编程中初始群体的产生方法做 了改进，提高了初始群体的个体质量。紧接着本文遗传编程中的子代个体选择方 式采用最优法和竞争选择法结合的方式进行改进，以期增加遗传编程中子代个体 的多样性和最优性。针对遗传编程中交换算子对算法树构造块结构破坏的情况， 我们采用多次交换操作根据适应度取最优个体的方法对其改进。最后本文针对遗 传编程演化过程中个体复杂度的控制提出了一种动态节点控制法，该方法在保证 个体多样性和优秀度的同时对个体的复杂度以节点数为标准进行控制。 在算法改进完后本文先在m a t l a b 仿真实验平台上对符号回归问题进行仿真实 验。然后我们通过构建一个n i o si i 软核，在a l t e r a 公司的q u a r t u s 9 0 软件和n i o s i i9 0i d e 仿真平台实现了全加器电路的仿真设计实验。对仿真结果比较显示改进 后的算法提高了初始群体生成的质量，在演化过程中控制了个体复杂度，并且在 平均收敛次数和平均迭代代数方面有了明显提高。 关键词：演化算法遗传编程选择交换复杂度 a b s t r a c t a b s t r a c t t h ee v o l v a b l eh a r d w a r ei san e wd e s i g nm e t h o d o l o g yt h a ti n t e g r a t e s t h e e v o l u t i o n a r ya l g o r i t h mi n t ot h ep r o g r a m m a b l el o g i cd e v i c e ( p l d ) t h i sp a p e rr e c a l l s t h ep l a t f o r m so fp r o g r a m m a b l ed e v i c e sa n dt h eb a c k g r o u n dk n o w l e d g eo fe v o l v a b l e h a r d w a r ei n c l u d i n gb a s i cp r i n c i p l e sa n dc l a s s i f i c a t i o n so fe v o l v a b l e h a r d w a r e i n a d d i t i o n ，f o u rt y p e so fe v o l u t i o n a r ya l g o r i t h ma r ei l l u s t r a t e da n dc o m p a r e di nd e t a i l ， i n c l u d i n gt h e i ro w n m a i ni d e a sa n dc h a r a c t e r i s t i c s d u et ot h ea u t o m a t i cd e s i g n i n gm e t h o d o l o g yo ft h ee v o l v a b l eh a r d w a r ec i r c u i t ，a l l i m p r o v e dg e n e t i ca l g o r i t h mi sa p p l i e df r o mt h ee n c o d i n gp o i n to fv i e w f i r s t l y , t h e i n i t i a lp o p u l a t i o ng e n e r a t i o ni sr e a l i z e db yt h eu s a g eo ft h eg r o u pc r o s s o v e ro p e r a t o r , w h i c hl e a d st oa ne n h a n c e m e n to ft h eq u a l i t yo ft h ei n i t i a lp o p u l a t i o n 。s e c o n d l y , i n o r d e rt oi n c r e a s et h ed i v e r s i t ya n ds u p e r i o r i t yo ft h eg e n e r a t e do f f s p r i n g ，an e wm e t h o d w h i c hc o m b i n e st h eo p t i m i z a t i o na n dc o m p e t i t i o nm e t h o d si sa p p l i e df o rt h ec h o i c eo f o f f s p r i n g o w i n gt o t h ed i s a d v a n t a g eo ft h ec r o s s o v e ro p e r a t o ri nd e s t r o y i n gt h e s t r u c t u r eo fa l g o r i t h mt r e eb l o c k s ，a ni m p r o v e dm u l t i c r o s s o v e ro p e r a t o rb yc o n s i d e r i n g t h em e t h o do ft a k i n gt h eo p t i m u mi nt e r m so ft h e i rf i t n e s si sd e v e l o p e d f i n a l l y , t o g u a r a n t e et h ed i v e r s i t ya n ds u p e r i o r i t yo f i n d i v i d u a l sa sw e l la st oc o n t r o lt h en u m b e ro f g e n e r a t e dn o d e s ，ad y n a m i cn o d e sa l g o r i t h mi sp r o p o s e dt oc o n t r o l t h ec o m p l e x i t y t h ec o n t r i b u t i o na n dt h es y m b o l sr e g r e s s i o np r o b l e m si nt h i sp a p e ra l es i m u l a t e d o nt h es i m u l a t i o ne x p e r i m e n tp l a t f o r mm a t l a b t h e n ，ad e s i g no f s i m u l a t i o ne x p e r i m e n t o ft h ef u l la d d e rc i r c u i ti sr e a l i z e do nt h es o f t w a r ee n v i r o n m e n tq u a r t u s 9 0a n dt h e s i m u l a t i o np l a t f o r mn i o si i9 0i d eb yc o n s t r u c t i n gan i o si is o f tc o r e t h es i m u l a t i o n r e s u l t a n t ss h o wt h a tt h ep r o p o s e da l g o r i t h mi m p r o v e st h eq u m i t yo ft h e i n i t i a l p o p u l a t i o na n dt h ec o m p l e x i t yo fi n d i v i d u a l si s w e l l c o n t r o l l e dd u r i n gt h ee v a l u a t i o n p r o c e s s t h ea v e r a g en u m b e ro fc o n v e r g e n c ei si n c r e a s e d ，a n dt h em e a na m o u n to f i t e r a t i o ni sd e c r e a s e de v i d e n t l y k e y w o r d s ：e v o l u t i o n a r ya l g o r i t h m g e n e t i cp r o g r a m m i n gs e l e c tc r o s s o v e r c o m p l e x i t y 第一章绪论 第一章绪论 1 1 选题背景 生命自从在地球上诞生以来，就开始了漫长的生物进化历程，低级、简单的 生物类型逐渐发展为高级、复杂的生物类型。这一过程已经由古生物学、胚胎学 和比较解剖学等方面的研究工作所证实。生物进化的原因自古至今有着各种不同 的解释，其中被人们广泛接受的是达尔文的自然选择学说。 而自2 0 世纪下半叶以来，微电子技术迅猛发展，集成电路设计和工艺水平有 了很大的提高，单片集成度已经达到上亿个晶体管，这从数量上已经大大超过了 绝大多数电子系统的要求。应如何利用这一近乎无限的晶体管集成度，就成了电 子工程师们的一项重大挑战。事实上，现有的硬件电路设计方法和传统设计理念 已经不太适应当前硬件电路的发展速度。在这种背景下，随着人工智能，自适应 控制以及人工神经网络训练等概念的提出和发展。让硬件电路实现自我设计和自 我修复慢慢成为了一种发展趋势。而达尔文的自然选择学说事实上说明了自然界 的生物进化是一个不断循环的过程，在这一过程中，生物群体进行不断的竞争， 完善，发展或淘汰。由此可见，生物进化的过程本身就是一种优化过程，而且是 一种自适应的最优化过程。这在硬件电路设计中具有直接的借鉴意义。而随着仿 生学在多种领域中的成功应用，这一概念也被证明是可以移植和借鉴的。演化硬 件( e v o l v a b l eh a r d w a r e ，简称e h w ) 就是在这种背景下被提出的。 演化硬件n 3 的概念从提出发展到今天已基本被定义为演化算法和可重构硬件 平台的有机组合，即e h w = e a + h w 。因此，在研究过程中，我们也可以将演化硬 件分成可重构硬件平台和算法研究两个领域。 演化算法经过发展到如今已经基本形成了四种主要方法：遗传算法( g e n e t i c a l g o r i t h m ，g a ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、进化策略 ( e v o l u t i o n a r ys t r a t e g y ，e s ) 、遗传编程( g e n e t i cp r o g r a m m i n g ，g p ) 等。上述四种 演化算法在结构和进化原则大体上是一致的，只是在个体表达方式，子代群体的 产生机制等方面各有特点，互不相同。 而可重构硬件平台的发展则得益于二十世纪7 0 年代初出现的可编程逻辑器件 ( p r o g r a m m a b l el o g i cd e v i c e ，简称p l d ) ，而发展至今已经出现了简单p l d ( s i m p l ep r o g r a m m m a b l el o g i cd e v i c e ，s p l d ) ，复杂p l d ( c o m p l e xp r o g r a m m a b l e l o g i cd e v i c e ，c p l d ) 和现场可编程门阵列( f i e l d - - p r o g r a m m a b l eg a t ea r r a y ， f p g a ) 等各类器件。基于f p g a 更高的集成度，更复杂的布线结构和逻辑实现， 2 基于演化硬件的遗传编程改进研究 现有的演化硬件设计多是以f p g a 为硬件平台进行实现。 总体来说演化硬件是指这样一种硬件，它能够通过硬件与环境之间的相互作 用来自适应地和动态地改变和调整其自身的结构和行为1 ，它能通过自身的进化来 完成其功能：或适应“外界环境”的变化，或达到具备设计者预期功能的电路和 系统结构，或修复自身的故障。e h w 强调的不仅仅是硬件。e h w 具有2 层含义： 首先，它是一种具有可进化能力的硬件。这种可进化能力的硬件必须是可重新配 置的，即能适应内部资源调整和外部环境变化，并且各个单位资源之间的连接是 活动的。其次，在这个可进化的硬件平台上以演化计算( 包括在线和离线两种方式) 为手段，使e h w 能自动地调配系统的资源以适应环境或任务的变化。 1 2 国内外发展现状 e h w 是目前非常活跃的一个研究领域，单从演化算法与计算机硬件相结合角 度来看，e h w 的起源可以追溯到上个世纪六十年代。早在上个世纪五十年代，就 有研究人员利用计算机系统模拟生物的遗传系统。1 9 6 5 年德国的i r e c h e n b e r g 等 人正式提出了进化策略( e s ) 的概念，这也是演化算法的起源【3 】。但当时的进化 策略还并不完善，操作对象只有一个个体，而演化操作方法也只有变异( m u t a t i o n ) 一种。同在1 9 6 5 年，美国的l j f o g e l 等正式提出了进化规划( e p ) 。这种算法将 进化对象扩大到多个个体的规模种群，但操作方法也依然只有变异一种。在六十 年代的同期，美国芝加哥大学的j h h o l l a n d 教授在研究自适应系统时，提出了系 统本身和外部环境相协调的遗传算法( g a ) ，并在1 9 6 8 年提出了相应的模式理论， 而这种模式理论也最终成为遗传算法的主要理论基础。 上个世纪七十年代中期至八十年代末期，特别是八十年代中期以来，演化算 法进入了一个高速发展的时期。1 9 7 5 年，j h h o l l a n d 教授的专著自然界和人工 系统的适应性( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) 正式出版。在书中 j h h o l l a n d 教授全面系统的介绍了遗传算法( g a ) 4 1 。该书的出版也被看做遗传 算法问世的标志。而j h h o l l a n d 教授也被公认为遗传算法( g a ) 理论的创始人【5 j 。 1 9 7 5 年，德国h p s c h w e f e l 在其博士论文中对进化策略( e s ) 进行了完善，不 光将进化对象扩展成个体群体，而且演化操作方式也包括了变异( m u t a t i o n ) 和重 组( r e c o m b i n a t i o n ) ，这也使得进化策略的适用性大大加强。1 9 8 9 年，j h h o l l a n d 教授的学生d e g o l d b e r g 出版了专著遗传算法搜索、优化及机器学习( g e n e t i c a l g o r i t h m 卜勘s e a r c h ，o p t i m i z a t i o na n dm a c h i n el e a r n i n g ) 。本书全面系统的介绍 了遗传算法( g a ) ，使得这一算法迅速得到推广。 进入九十年代以后，这一时期演化算法最大突破就是出现了遗传编程( g p ) 。 1 9 8 9 年，斯坦福大学的j r k o z a 提出了遗传编程这一新的概念。其主要思想是提出 第一章绪论 在编码方式方面运用层次化的计算机程序来代替字符串表达问题。并于1 9 9 2 年出 版专著遗传规划一一应用自然选择法则的计算机程序设计( g e n e t i c p r o g r a m m i n g ：o nt h ep r o g r a m m i n go fc o m p u t e rb ym e a n s o fn a t u r a ls e l e c t i o ) 【6 1 。在 该书中全面介绍了遗传编程( g p ) 的基本原理和相关的应用实例，这也表明遗传 编程( g p ) 成为了演化算法的一个重要分支。而j r k o z a 也成为了遗传编程( g p ) 的奠基人。 而进入九十年代以后，由于可编程逻辑器件的发展迅速，特别是f p g a 的出 现，使得演化算法找到了一种比较合适的硬件平台，近年来，随着c p l d 和f p g a 等可编程逻辑器件的逻辑门密度越来越高，布线资源越来越丰富。e h w 的应用与 实现也有了很大的设计空间。 在应用实现方面，e h w 已被应用于众多领域，如数字滤波器设计，自适应均 衡器和假肢设计，自修复和容错电路设计，多态电子及新型多功能电路设计，语 音识别器及字符识别器等。 在滤波器设计方面，s u m a t h i 等以函数级功能模块作为进化操作的基本单元进 化生成了图像滤波器【_ 7 1 ，并应用于图像的增强。r a j a r a m 等人则基于x i l i n x 公司的 f p g a 器件x c v l 0 0 和遗传算法( g a ) 演化出了f i r 数字滤波器，并且在功能上实 现了自适应噪声滤波。 h i g u c h i 等人则提出利用函数级( 如加、减、正弦、余弦等) 模块代替逻辑门作 为可重构硬件的基本单元，这种方法可以减小染色体长度，并且由于采用了更高 的编码层次，使电路结构能更加适用于可重构器件。并将该方法应用于有损数据 压缩、数字移动通信中的自适应均衡器等多项实验中。其中，有些实现成果已可 投入实际应用，其中包括能根据打印内容自动调整预测函数的数据压缩e h w 、集 成了遗传算法( g a ) 及可重配置逻辑电路的肌电假肢用芯片等 在信号传输和处理方面，f a l c o n e r 等人使用内部进化方式演化硬件( i n t r i n s i c e h w ) 进行高速数据线中信号的完整性检查。 在容错设计方面，r o g g e n 等人则使用结构完全相同的细胞元( c e l l ) 电路进化出 相应的逻辑电路和机器人控制器【8 】。就像普通生物组织那样，每个细胞元都包含最 终演化出的系统的遗传编码表达，在运行时则依据相关的规则决定应表达遗传编 码中的相关部分功能及各部分之间如何连接。由t y r r e l i 带领的研究小组则设计了胚 胎电子系统中胚胎单元的硬件电路结构，提出了胚胎电子阵列系统的错误恢复机 制并对胚胎电子系统的可靠性也进行了相应的分析和研究 在多态电路设计方面，n a s aj p l ( j e tp r o p u l s i o nl a b o r a t o w ) i y j s t o i c a 9 】所带领的 研究小组则讨论了在长期太空探索任务中使用e h w 的重要性和可能性。由于太空 环境的复杂和多样性，以及长期太空探索中需要系统器件具备一定的容错功能和 自我修复能力。s t o i c a 所带领的研究小组提出了多态电子器件的概念。 基于演化硬件的遗传编程改进研究 在语音识别和字符识别方面，英国s u s s e x 大学的t h o m p s o n 等人则进行了音调 县别器的实验n 引，通过内部进化( i n t r i n s i ce h w ) 得到了能够区分l k h z 和1 0 k h z 两 中频率的电路。在系统中t h o m p s o n 引入了分而治之的方法，即将复杂的难以进化 勺电路分解成若干简单的可以进化出的子电路分别进行进化，然后再将进化出的 产电路组合起来，构成一个具有复杂功能的大电路。利用此方法，t h o m p s o n 进化 b 了能识别数字的电路。 1 3 本文主要工作及相关内容安排 本文主要实现了遗传编程算法的改进。 第一章为绪论部分，主要对本文的选题背景和国内外研究现状进行了简要的 r 绍。 第二章主要对演化硬件的基本原理，实现方法，以及可编程硬件平台的相关 i 理做了相关的研究和介绍。 本文第三章详细叙述了演化算法四种算法，遗传算法( g a ) ，遗传编程( g p ) ， 化策略( e s ) ，及进化规划( e p ) ( t q 基本原理和算法的详细步骤，并对这四种算法的 亡缺点做了比较和研究。 第四章主要是对遗传编程算法的改进，本文为了提高初始群体的个体质量， 毛用分组混合法实现了初始群体的生成。为了实现子代个体的多样性和优性，本 用最优法和竞争选择法结合的方式来选择子代个体。为了抑制交换算子对算法 ：- 构造块的破坏作用，本文对交换算子的操作方式做了改进。最后为了解决在演 匕过程中个体的复杂度增长问题，本文提出了一种动态节点控制法来抑制个体的 乏杂度。在本章最后我们采用m a t l a b 仿真平台针对符号回归问题用改进后的算法 友了仿真实验，并对实验结果做了比较分析。 第五章中本文采用a l t e r a 公司的n i o si i 软核实现了一个全加器电路的设计， i 1 根据实验结果对改进后的算法进行了验证和比较。 第二章演化硬件的定义和简介 第二章演化硬件的定义和简介 2 1 1 细胞的结构 2 1 生物学相关背景知识 细菌是迄今为止发现的最小的个体独立的细胞，它的最外层我们称之为细胞 膜( c e l lm e m b r a n e ) ，细胞膜里则包裹着细胞质( c y t o p l a s m ) 1 1 1 。细胞质的7 0 是 由水构成，而另外大约3 0 则由细胞自己产生的氨基酸( a m i n oa c i d s ) ，葡萄糖 ( g l u c o s em o l e c u l e s ) 以及三磷酸腺苷( a t p ，生命活动能量的直接来源) 等构成。 图2 1 显示了一个典型的大肠杆菌( e c o l ib a c t e r i u m ) 的细胞结构。 无论动物或植物， 图2 1 中找到： 图2 1 大肠杆菌细胞结构 所有的细胞都具有相类似的结构，这些结构构成都可以在 细胞膜( c e l lm e m b r a n e ) ： 侵袭。 包裹着细胞的所有组成部分并保护细胞不受外部 细胞质( c y t o p l a s m ) ：细胞质( c y t o p l a s m ) 是指细胞膜包围的除核区外的 一切半透明、胶状、颗粒状物质的总称。 遗传物质：生物上下代之间传递遗传信息的物质。除一部分病毒的遗传物质 是核糖核酸( r n a ) 外，绝大部分病毒及细胞的遗传物质都是脱氧核糖核酸( d n a ) 。 由于细胞里的d n a 大部分都在染色体上，所以遗传物质的主要载体就是染色体。 在演化硬件中我们在设计电子系统的基本单元时，借鉴了生物学上相应的细胞 结构。 6 基于演化硬件的遗传编程改进研究 2 1 2d n a 的结构组成以及遗传操作方式 d n a 包含了生命遗传信息中超过9 9 的部分。它是由两条脱氧多核苷酸链 反向平行盘绕所形成的双螺旋结构。由4 种主要的脱氧核苷酸( d a m p 、d g m p 、 d c m t 和d t m p ) 构成。它们的组成和排列不同，显示不同的生物功能，如编码功 能、复制和转录的调控功能等。排列的变异可能产生一系列疾病。其结构如图2 2 所示： o 自唯_ h n m m 。；： 。一 恐 图2 2 d n a 的结构示意图 如图2 2 所示d n a 是一种长链聚合物，组成单位称为脱氧核苷酸，而糖类 与磷酸分子借由酯键相连，组成其长链骨架。每个糖分子都与四种碱基里的其 中一种相接，这些碱基沿着d n a 长链所排列而成的序列，可组成遗传密码， 是蛋白质氨基酸序列合成的依据。读取密码的过程称为转录，是以d n a 双链 中的一条为模板复制出一段称为r n a 的核酸分子。多数r n a 带有合成蛋白质 的讯息，另有一些则本身就拥有特殊功能。 在细胞内，一个d n a 分子由许多基因组成，基因( 遗传因子) 是遗传的物 质基础，是d n a ( 脱氧核糖核酸) 分子上具有遗传信息的特定核苷酸序列的总称， 是具有遗传效应的d n a 分子片段。基因能组织成染色体结构，整组染色体则统 称为基因组。染色体在细胞分裂之前会先行复制，此过程称为d n a 复制。对 真核生物，如动物、植物及真菌而言，染色体是存放于细胞核内；对于原核生 物而言，如细菌，则是存放在细胞质中的类核里。染色体上的染色质蛋白，如 组织蛋白，能够将d n a 组织并压缩，以帮助d n a 与其他蛋白质进行交互作用， 进而调节基因的转录。图2 3 显示了如何从基因转录新的蛋白质的整个过程。 在演化硬件的设计理念中借鉴了d n a 的结构及遗传方式。 m i 嗨 6 h h 、。 ，o 第二章演化硬件的定义和简介 7 图2 3 基囚转录新的蛋白质 2 2 演化硬件的定义及分类 演化硬件的概念在提出的时候就借鉴了生物学进化的相关概念。现代生物学研 究指出，生物具有自我修复，适应环境进化的特性，并且可以在遗传的过程中将 进化出来的特性传递下去，这种适应性和自我调整主要是基于生物体细胞中的遗 传物质即基因的重组和变异。因此，演化硬件也具备了自适应，自我修复以及根 据外界环境进行调整等在生物体上所展现的特性。演化硬件发展到今天已经基本 上被定义为演化算法和硬件设计技术有机结合的特殊的硬件结构。 演化硬件具有两个方面的内容：电路的自主设计给定输入和输出，将待 进化电路当成一个黑盒子，通过演化算法自动进化出符合设计要求的电路结构。 这种思路主要的应用方向是电路设计，即解决现有的硬件设计资源极其丰富和工 程师设计能力不能与之匹配的矛盾；随着外部环境的变化能自主的，动态的改变 自身结构的电路。这种思路则主要运用到电路的容错性和可靠性上，可以极大的 提高硬件电路在恶劣环境下工作的可靠性以及系统的工作周期。这在太空与深海 探索以及核工业等领域意义重大。 演化硬件有两种实现方式，即内部进化方法( i n t r i n s i ce h w ) 1 2 1 和外部进化方 法( e x t r i n s i ce h w ) ，又可称之为在线仿真和离线仿真。内部进化方式直接在硬件上 调整电路结构及相关参数。这主要得益于可编程器件晶体管集成程度高，可编程 单元越来越多，开发环境友好等优点，进化速度也较快。而在演化硬件刚提出时 由于当时可编程器件还无法满足其设计要求，当时演化硬件的实现方式主要是外 部进化方法，即将所要进化的目标电路编码为演化算法可进行进化操作的个体， 先在计算机上根据相关演化算法的步骤用软件模拟进化过程，再将进化出的解决 方案下载到硬件。优点是灵活性比较强，从一个任务切换到另一个任务，只需修 8 基于演化硬件的遗传编程改进研究 改一下参数或者增减一些相关的函数模块。其缺点是与内部进化方式相比，其进 化速度较低。 演化硬件根据不同的标准，例如实现方式的不同，硬件功能的不同，演化算法 的设计及演化方式的不同，以及电路应用领域的不同等可以分为很多种类【1 3 】。根 据其实现方式的不同可以分为外部演化硬件( e x t r i n s i ce h w ) 和内部演化硬件 ( i n t r i n s i ce h w ) 。根据演化硬件设计领域的不同可分为电路的自主化设计和自适 应演化硬件。前者主要适用于超大规模电路设计，后者则主要应用于硬件电路的 自修复以及智能控制等。根据演化目标电路的种类又可分为数字逻辑电路设计及 模拟电路设计。其中数字逻辑电路设计又可细分为组合逻辑电路设计，时序逻辑 电路设计及多态电路设计等。根据演化硬件的演化级别又可分为门级，函数级， 系统级等。 2 3 演化硬件的基本工作原理 2 3 1 演化硬件的特点 演化硬件通过演化算法在各式各样的可重构硬件平台上实现电子电路的自我 重构和自主设计。演化硬件在实现自主设计的同时，同样还可实现硬件自修复， 硬件容错等非常吸引人的功能。 演化硬件的自适应、自组织、自修复的特点 1 4 1 可以具体描述如下： ( 1 ) 演化硬件的自组织及自我重构：随着现代微电子技术的迅速发展，晶体管 集成度的不断提高，现有的硬件系统设计已逐渐转向片上系统 ( s y s t e m o n a - c h i p ，s o c ) 。片上系统( s o c ) 的定义是指将微处理器，模拟i p 核， 数字i p 核和存储器( 或片外存储控制接口) 集成在单一芯片上。由此可见，其系 统设计更加的复杂，系统的可靠性和通用性要求也更高。这对设计人员来说是一 个很大的挑战，现有的复杂系统的设计需要的团队人员和设计周期也越来越长。 因此其设计成本也不断飙升，从长远来看必定会产生一定的瓶颈。而演化硬件则 无需人为的干预，只需要给定输入输出和一定的约束条件即可实现硬件的自主设 计，能够通过自身的演化来自重构自组织成具备与其功能的电路与系统结构。因 此演化硬件具有非常大的发展前景。 ( 2 ) 演化硬件的自适应：由于演化硬件是仿生学在电路设计领域的衍生和实 现，因此演化硬件也像生物体一样具备高度的环境适应性，即可根据外部环境变 化进行相应的调整和重构。这在太空探测，深海勘探及自适应机器人控制等方面 具有非常大的实用意义，而一般的硬件系统在这些领域则有着很明显的局限性。 第二章演化硬件的定义和简介 9 ( 3 ) 硬件的自我修复：对于高度集成的现代电子信息系统( 如s o c 系统) 运 行中故障的出现，由于其系统的复杂和庞大，以及在设计过程中多为很多人员共 同参与完成。因此一旦出现故障，查找故障和解决方案的提出是一件非常困难的 事情，而且周期往往较长，这在有些突发紧急情况中尤其不适用。因此演化硬件 通过硬件演化可以实现硬件自我修复这一特点就显得尤为可贵。而这种崭新的维 护硬件系统可靠性和稳定性的机制也预示着硬件设计的巨大变革。 2 3 2 演化硬件的实现方法 演化硬件与常规硬件( c o n v e n t i o n a lh a r d w a r e ，c h w ) 的设计有非常大的区别。 设计人员在确定系统的约束条件和相关的目标功能后就开始制定详细的设计方 案，然后再根据设计方案来设计一个常规的硬件系统( c h w ) ”l 。从一般意义上来 说，c h w 往往采用自上而下的设计方法，而e h w 在事先没有详细设计方案的情 况下也能够得到。因为e h w 是通过遗传学习，采用自下而上的设计方法实现的。 演化硬件设计的核心思想是将预期实现的目标电路通过特定的转化规则映射为某 一向量空间，而这一向量空间由二进制编码组成，我们称之为染色体群，它涵盖 了目标电路可能出现的所有潜在解。染色体则以演化算法的规则进行相关的演化 操作，通过不断的演化，利用目标电路的正确信息达到最优化，最终得到全局最 优个体，再通过解码将最优个体下载到可编程器件中去。 演化硬件的主要设计流程如下： ( 1 ) 根据目标电路的设计需求及相关约束条件确定设计方案，并选择相关的 电子元器件； ( 2 ) 确定电路的编码方案，由于演化算法求解电路问题并不能直接作用在问 题的解空间上，而是基于解的某种编码表示，因此选择合适的编码方案尤为重要。 而将电路的结构和相关参数作为染色体进行编码后，将电路的行为( 电路的输入 一输出特性) 与预期目标电路的符合程度作为个体的适应度，并且按照演化算法 的演化模式对系统进行演化操作。 ( 3 ) 利用事先规划好的电路模式，即给定相应的输入条件或测试集，将种群 中的每个个体加载到硬件电路中或加载到基于电路模型的仿真测试软件中，得到 电路的输出，与预期结果进行比较得到个体的适应度。 ( 4 ) 按照以上适应度评估的结果决定下一步的演化计算操作，如此一直循环 直到得出符合预期设计的最优个体。 ( 5 ) 最后将得到的最优个体解码并下载到硬件中进行相关配置。 这就完成了电路进化设计。其具体步骤如图2 4 ： 1 0 基于演化硬件的遗传编程改进研究 图2 4 演化硬件设计流程 如图2 4 所示，演化硬件的实现主要有两种方式：外部演化( e x t r i n s i ce h w ) 和内部演化( i n t r i n s i ce h w ) 。外部演化是指先用软件建立相关的电路模型，通过 软件进行染色体适应度评估及进化，只将最终结果下载到硬件中去，也就是只配 置一次硬件。这种方法主要是应用于演化硬件发展早期，由于硬件相关资源的局 限才采用的方法。而内部演化则将演化过程中每一代产生的每个染色体均下载到 实际的可编程器件中，并根据每一代电路的输出结果直接进行判定。这种方式对 硬件本身的要求非常高，硬件必须具备丰富的布线资源和快速的重构能力。而现 在可重构器件的快速发展为演化硬件提供了良好的硬件平台。 2 4 可编程硬件平台 随着现代微电子设计技术的迅速发展以及设计工艺的进步，数字集成电路已 经从最早的电子管，晶体管中小规模集成电路，超大规模( v l s i c ) 集成电路慢慢 发展到了今天的专用集成电路( a s i c ) 。a s i c 的出现不仅降低了产品的生产成本， 大大提高了系统的可靠性，而且推动了整个社会的数字化进程。但是由于其设计 周期较长，改版投资较大，灵活性能差等因素严重限制了它的应用领域。因此硬 第二章演化硬件的定义和简介 件工程师需要有一种更灵活的设计方法， 以设计甚至更改大规模的数字逻辑系统， 可编程逻辑器件从发明到目前为止， 可以根据自己的需求，在实验室中就可 这就是可编程逻辑器件诞生的初衷。 已经有了长足飞跃性的进步，从最早期 的只能存储很少数据，完成最简单的逻辑功能的可编程只读存储器( p r o m ) 、紫 外线可擦出只读存储器( e p r o m ) 、电可擦除只读存储器( e 2 p i m m ) ，发展到能 够完成中大规模的数字逻辑功能设计的可编程阵列逻辑( p l a ) 和通用阵列逻辑 ( g l a ) ，到现在得益于晶体管集成度的不断提高已经发展为可以完成超大规模的 复杂组合逻辑与时序逻辑的复杂可编程逻辑器件( c o m p l e xp r o g r a m m a b l el o g i c d e v i c e ，c p l d ) 和现场可编程逻辑阵列( f i l e dp r o g r a m m a b l eg a t ea r r a y ，f p g a ) 。 随着微电子工艺技术的不断发展与市场的需求，超大规模、高速、低功耗的新型 可编程逻辑器件不断地推陈出新，新一代的f p g a 甚至集成了中央处理器( c p u ) 或数字处理器( d s p ) i 为核，在一片f p g a 上进行软硬件协同设计，为实现片上可编 程系统( s o p c ) 提供了强大的硬件资源支持。 f p g a 是f i l e dp r o g r a m m a b l eg a t ea r r a y 的缩写，即现场可编程逻辑阵列。f p g a 是在c p l d 的基础上发展起来的高性能可编程逻辑器件，一般采用s r a m 工艺， 也有一些专用器件采用f l a s h 工艺或反熔丝( a n t i f u s e ) 工艺。f p g a 的集成度很 高，其器件密度从数万门到数千万门不等，可以完成及其复杂的时序与组合逻辑 电路功能，适用于高速高密度的高端数字逻辑电路的设计领域。它的基本组成部 分可分为可编程输入输出单元、基本可编程逻辑单元、嵌入式r a m 、丰富的布线 资源、底层嵌入功能单元、内嵌专用核等。f p g a 的主要器件供应商有x i l i n x 、a l t e r a 、 l a t t i c e 、a c t e l 和a t m e l 等。 可编程器件发展到今天，由于f p g a 具备更多的逻辑密度，更加丰富的布线 资源以及更好的性能，因此绝大部分的演化硬件都选用f p g a 来作为其硬件实现 平台。 近年来，随着f p g a 技术的发展，支持重构的f p g a 器件新品出现。x i l i n x 、 a l t e r a 、l a t t i c e 的f p g a 器件都是s r a m 查找表结构。x i l i n x 支持模块化动态部分 重构的器件族有x c 6 2 0 0 系列，9 0 n m 工艺s p a r t a n - 3 和v i r t e x - 4 、v i r t e x - i i - e 和 v i r t e x i ip r o 。a c m e l 公司的a t 6 0 0 0 系列同样基于s r a m 结构，只是s r a m 的各 单元能够单独访问配置，即支持部分重构。l a t t i c e 公司的基于f l a s h 的f p g a 通过 在f l a s h 上存储多种逻辑功能的配置数据流，经过配置实现不同逻辑功能，严格意 义上讲属于静态可重构技术。a l t e r a 公司的f l e x 、a c e x 、a p e x 、c y c l o n e 、s t r a t i x 、 a i t i a 等系列也是基于s r a m 的可重构逻辑，支持重构的f p g a 器件有数量逐渐增 加的趋势，但目前价格相对偏高。 1 2 基于演化硬件的遗传编程改进研究 2 5 本章小结 本章首先从背景知识上引入介绍了生物学的相关知识，并且从细胞层面解释 了生物个体如何通过遗传物质即基因等进行特性传递和演变，为更好地理解演化 硬件特别是演化算法的相关概念作出了一定的铺垫。 其次主要介绍了演化硬件的分类以及基本原理，并简单介绍了构建一个演化 硬件系统的基本流程。 最后介绍了演化硬件的硬件平台即可编程器件的相关情况，并且着重介绍了 f p g a 的具体结构。 本章在整个论文中属于前期概念性的说明，主要是对演化硬件做一个宏观的 介绍，并为后续的内容作出了铺垫。 第三章演化算法的研究和比较 第三章演化算法的研究和比较 3 1 引言 对于演化硬件来说，演化算法是其实现的理论基础和支撑。而演化算法的性 能好坏也是最终决定演化硬件研究进展的决定性因素。因此，在演化硬件的研究 中，演化算法是最为关键的研究内容，如何针对当前选用的硬件平台的电路结构 进行编码和演化操作是演化硬件研究的前提。 演化硬件由提出发展到今天基本上可定义为演化算法加可重构硬件平台，而 演化算法的提出甚至还在演化硬件这一概念之前。演化算法的提出可以追溯到上 个世纪六十年代，经过半个世纪的发展，演化算法基本上可以分为遗传算法 ( g e n e t i ca l g o r i t h m ，g a ) 、进化规划( e v o l u t i o n a r yp r o g r a m m i n g ，e p ) 、进化 策略( e v o l u t i o n a r ys t r a t e g y ，e s ) 、遗传编程( g e n e t i cp r o g r a m m i n g ，g p ) 这四种主 要的方法。这四种算法在算法结构和流程上有一定的相似性，但在编码方式和演 化操作方法上却又大为不同。在对演化硬件进行研究前，我们先要对各个算法进 行研究和比较，分析出各个算法的优缺点和适用范围，这样才能选用合适的算法 来对演化硬件进行操作。下面先就各个算法的基本原理及特点进行简要的介绍， 最后在进行对比分析，通过比较各个算法的优缺点和具体流程来进行相关的改进。 3 2 演化算法的基本原理和其特点 3 2 1 遗传算法( g a ) 在现有的演化算法研究中，遗传算法无疑占据着非常重要的地位，很多演化 硬件研究者都运用遗传算法来进行演化操作，下面就遗传算法的基本原理和流程 进行阐述。 遗传算法的基本操作流程可以分为以下几步： ( 1 ) 编码 编码可以说是演化算法研究的重点和难点f 1 6 1 。而演化算法几种算法最大的区别 也体现在编码这一步骤上。从生物学角度来说，编码相当于选择遗传学物质，而 从电路工程设计的角度来说，编码实际上就是将各种电路的基本模块如何映射到 演化算法可接受的操作单元上。传统的标准遗传算法( g a ) 所采用的编码方式大 多为二进制的0 1 字符编码，每个字符串则对应一个染色体。而字符串的长度l 1 4基于演化硬件的遗传编程改进研究 一般都为固定值，这样可以方便地进行后续的演化操作。 ( 2 ) 产生初始群体 初始群体是遗传算法进行全局搜索探寻最优的基础。一般来说，初始群体数目 m 取值越大，则算法要搜索的范围就越广，但其每代的遗传操作时间就越长。但 如果m 的数值较小，则搜索范围变小会出现过早收敛的问题。通常，m 的取值范 围根据实际情况在5 0 1 0 0 之间。 ( 3 ) 计算适应度 适应度是衡量染色体与目标对象符合程度的唯一度量标准，也是进行演化运算 相应操作的唯一依据。通常情况下，遗传算法中的个体适应度通常以目标函数的 形式出现。 ( 4 ) 复制 这是遗传算法演化计算操作中的第一步。其基本原理是根据个体适应度选择适 应度较高的个体复制到下一代群体。而适应度不高的个体则被淘汰，这体现了“优 胜劣汰”的生物学法则。 一般情况下，群体中被选择的个体数目通常采用期望值法，这种方法规定复制 概率为尸，即 只：旦( 3 1 ) m 式中，m 群体中的个体数目； m 群体中被复制的个体数目； 而一般情况下尸常取o 1 0 2 ，这也就意味着在每一代的复制操作中，被淘汰 个体占