（电力电子与电力传动专业论文）硬件演化理论、方法及实现.pdf

堡笪塑些望堡：查鲨墨塞堡 a b s t r a c t e v o l v a b l eh a r d w a r e ( e h w ) i sak i n do fh a r d w a r ew i t hs e l f - o r g a n i z a b l e ，s e l f - a d a p t i v e a n ds e l f - r e p a i r a b l ea b i l i t y i nt h i sp a p e r , t h em e t h o do fd i g i t a le v o l v a b l eh a r d w a r ei s s t u d i e db a s e do nt h e d y n a m i c a lr e c o n f i g u r a t i o n o ff i e l d p r o g r a m m a b l e g a t e a r r a y ( f p g a 、 i nt h ep a p e r , f i r s t l y , t h eb a s i cc o n c e p t i o na n dt h e o r yo fe h wa r er o u n d l yi n t r o d u c e d a n dt h es t r u c t u r ec h a r a c t e r so fe h w c h i pa r ea n a l y z e d s e c o n d l y , t h et h o u g h to fs t a n d a r d e v o l u t i o n a r ya l g o r i t h mi sd i s c u s s e da n dt h ef l o wo fi m p r o v e de v o l u t i o n a r ya l g o r i t h m si s a n a l y z e d t h ek e yt e c h n o l o g yo fe h wr e a l i z a t i o n i s e m p h a s i z e da n dt h er e a l i z a t i o n p r o j e c t s a r ed e e p l ys t u d i e d t h ep a p e ra d o p t st w om e t h o d so fe x t r i n s i ce v o l u t i o na n d i n t r i n s i ce v o l u t i o nt oe v o l v et h ea p p l i c a t i o nc i r c u i t s i n s t a n c e sa r eg i v e nt ot e s tt h et w oe v o l v e dm e t h o d sa n dt h er e s u l t ss h o wt h a tb o t h e h wm e t h o d sa r ev a l i d k e y w o r d s ：e v o l v a b l eh a r d w a r ee x t r i n s i ce v o l u t i o ni n t r i n s i ce v o l u t i o n e v o l u t i o n a r ya l g o r i t h m f i e l dp r o g r a m m a b l e g a t ea r r a y 南京航空航天大学硕士学位论文 第一章绪论 早在本世纪五十年代，计算机之父j o h ny o nn e u m a n n 就提出了研制具有自繁殖 与自修复能力机器的设想，由于当时技术条件的限制使这一设想未能实现。但人们探 索的脚步却从未停止，先后发明了如细胞自动机、人工神经网络与人工生命等技术， 但从根本上说它们未能超越各自划定的特殊模式“。 直到演化计算和大规模可编程芯片的出现，这一设想才成为可能。演化计算集成 了“仿生”与“拟物”演化的成就，它的发展带来了一种新的思想。演化计算是自然 科学与工程技术的高度交叉，其广泛的应用开辟了许多新的研究领域，其中最吸引人 的领域之一就是演化硬件( e h w 或e h a r d ，e v o l v a b l eh a r d w a r e ) 。 1 1 演化硬件的概念与分类 演化硬件实际上是一种特殊硬件，它可以像生物一样具有自适应、自组织、自修 复特性，从而可以根据使用环境的变化而改变自身的结构以适应其生存环境。从狭义 上来讲，演化硬件是通过演化算法实现电子硬件的自身重构；从广义上来讲，演化硬 件包括各种形式的硬件，从传感器到能够适应变化的环境，并且在运行期间增强其性 能的整个演化系统。除了生成具有新功能的电路以外，演化硬件还可用于保持现有功 能，获得容错、确定电路的功能，从而减少故障的发生。这些特点在空间应用中是相 当重要的，例如通过硬件演化可以使宇宙飞船在空间自修复、自适应，恢复由于温度 升高等因素而丧失的功能，适应恶劣的环境并延长其使用寿命3 ，4 1 。 根据演化硬件的实现方式、演化过程、芯片种类以及演化电路的规模、应用领域 不同，可以分为若干种类型【5 l ： 1 按照硬件演化的过程不同可分为内部演化硬件( 适应度在芯片中评价) 和外部 演化硬件( 适应度在软件模型中评价) 。 2 按照演化计算方法的不同可以分为遗传算法e h w 、遗传规划e h w 、演化规划 e h w 。 3 按照应用领域的不同可以分为设计性e h w ，如电路设计，v l s i 设计；自适应 e h w ，如控制与机器人，模式识别，容错。 4 按照演化芯片的不同可分为基于可编程集成电路的演化硬件和基于专用集成 电路的演化硬件。 5 按照演化的基本单元可分为函数级e h w 和门级e h w 。 6 按照演化的系统而言可分为数字e h w 、模拟e h w 和混合e h w 。 1 2 演化硬件的应用领域及研究意义 硬件演化技术的用途广泛，特别适用于电子设备需要长期工作、使用环境恶劣、 硬件演化理论、方法及实现 技术人员无法及时提供维修的情况。目前主要应用范围有：自动控制系统、智能机 器人、模式识别与人工智能、自修复系统、电路设计等，尤其在航空、航天领域具 有重要意义。 开展硬件演化技术的研究具有重要意义。随着硬件系统( 如芯片系统) 的复杂性 不断增加，系统设计繁琐、可靠性下降、通用性差，若系统出现故障，传统的基于板 级重构技术的自修复方法已不适用。利用硬件演化技术，不仅可以减轻设计人员的负 担，而且满足了环境对硬件所要求的适应性，实现硬件系统的通用化、芯片内自修复。 硬件演化这一新兴的研究领域，将演化算法与电子学有效地结合在一起。它不仅开拓 了硬件设计自动化、硬件自适应和自修复的新途径，而且为自然科学与工程技术的结 合描绘了迷人的前景。一旦突破技术上的障碍，硬件演化技术将开辟演化工程这一具 有重大实用价值和广阔应用前景的新兴产业。 1 3 演化硬件的研究背景、技术现状及发展趋势 1 3 1 演化硬件的研究背景 演化硬件的概念最初是由日本的h u g od eg a r i s 和瑞士联邦工学院于1 9 9 2 年提 出的1 ，虽然历史不长，但其发展非常迅速。1 9 9 5 年第一个硬件演化技术研究机构 在瑞士的洛桑成立。1 9 9 6 年第一届国际演化系统会议( i n t e r n a t i o n a lc o n f e r e n c e o ne v o l v a b l es y s t e m s ，简称i c e s ) 在日本召开，1 9 9 8 年第二届i c e s 会议在瑞士 召开，第三届i c e s 会议于2 0 0 0 年在英国召开，第四届i c e s 会议于2 0 0 1 年在日本 召开。从1 9 9 2 年到1 9 9 9 年，硬件演化技术的研究机构主要分布在欧洲和日本。美 国在硬件演化技术领域起步稍晚，但其发展迅速，后来居上。从1 9 9 9 年起，每年由 美国国家空间管理局n a s a ( n a t i o n a la m e r i c as p a c eh d m i n i s t r a t i o n ) 和国防 部d o d ( d e p a r t m e n to fd e f e n s e ) 主持召开硬件演化技术研究工作会议。美国在 硬件演化机理与应用基础研究方面取得了很大的成绩，已经在这一研究领域处于国 际领先地位”。 演化硬件的研究方法主要分为两大类，即面向遗传算法( g e n e t i ca l g o r i t h m - - g a ) 的方法与面向胚胎学( e m b r y o l o g y ) 方法叫j ： 1 面向g a 方法的目的在于开发一类能改变自身硬件结构的机器，同时也试图开 发一类新的硬件设计方法学( 即不要涉及人的硬件设计) 。日本的e t l 、a t r 与英国 的s u s s e x 大学采用这类方法。 2 面向胚胎学方法的目的在于开发一种能够自繁殖( s e l f - r e p r o d u c e ) 和自修复 ( s e l f - r e p a i r ) 的机器，瑞士联邦工学院及日本的a t r 人工脑小组正在进行这方面的研 究。瑞士学派根据地球上生命的起源，从种群发生学( p h y l o g e n y ) 、个体发生学( o n t o g e n y ) 以及后天遗传学( e p i g e n e s i s ) 三个层次的演化过程出发，提出了仿生硬件体系的p o e 模型。以p ( p h y l o g e n y ) 轴代表像遗传算法这类群体演化为基础的仿生硬件系统，以 南京航空航天大学硕士学位论文 o ( o n t o g e n y ) 轴代表像细胞分裂这类多细胞组织的生长过程的仿生硬件系统，以 e ( e p i g e n e s i s ) 轴代表像神经系统、免疫系统和内分泌系统这类能集成与外部环境相互 作用的大量信息的仿生硬件系统( 学习硬件) 。并以此框架在p e 平面、o e 平面、p o 平面甚至p o e 空间构思仿生硬件系统的发展方向。 据英国的a d r i a nt h o m p s o n 在2 0 0 2 年1 月统计，全世界主要有3 8 个研究机构在 进行硬件演化技术的研究并取得了一定的成绩。其中，英国有1 6 个研究机构，美国 有1 3 个，德国有6 个，日本有2 个。在这些研究机构里，有许多学者取得了突出的 成绩。典型的成果有： 1 h u g od eg a r is ( 2 0 0 0 年1 月至今，在美国进行硬件演化的研究) 研制出一 种大规模的硬件演化平台( c b m ，c a m b r a i r l s m a c h i n e ) ，c b m 包含7 2 片f p g a 芯片 ( x i l i f i x x c 6 2 6 4 b g 5 6 0 ) 。在c b m 平台上可以每秒使1 3 1 i 0 “个细胞进行更新， 能够进行自动控制的细胞高达8 9 3 1 0 ”个，可支配6 4 6 4 0 个神经系统模块，每个神 经系统模块中包含11 5 2 个神经元，整个c b m 中可以支持7 4 5 x1 0 7 个神经元，f p g a 可重构的单元为1 1 8 1 0 6 个，基因的存贮能力为1 1 8 g b y t e s ，计算能力为 1 0 0 0 0 p e n t i u m l i i s o o m h zp c s 2 日本的t e s u y ah i g u c h i 在工业硬件演化芯片及应用的研究上取得了很大的成 绩。他的研究成果主要是模拟量演化电路、数字打印的数据压缩、可重构的d s p 芯片、 肌电假肢和高速l s i 使用可演化的时钟计时技术，采用硬件演化技术的大部分产品已 经投入市场“。 3 英国的d e l o nl e v i ( 目前在x i l i n x 公司从事研究工作) 在制造高性能的演化 芯片上取得了突出的成绩，并且研究出支持芯片进行演化的支撑软件”“。 4 英国s u s s e x 大学的a d r i a nt h o m p s o n 在硬件演化内部演化技术上取得了突破 性的进展。他目前在进行极小规模电子电路的演化研究，其研究被证明符合摩尔定理 的。这种极小规模电子电路甚至小到只包含一个单一的晶体管。这种针对电路物理特 性的研究对研究硬件演化的内部机理有着深远的意义“”1 。 5 美国的n a s a d o d 所支持的研究项目包括研制自适应、自修复系统，目标是直 接用于航天飞机、宇宙飞船的电子系统“3 。 最近几年，国内少数单位的研究人员对演化硬件进行了研究，研究内容侧重于演 化算法、采用外部演化方式的函数级数字电路的硬件演化。采用的演化芯片集成度小， 如g a l ( g a t ea r r a yl o g i c ) 芯片，开展演化硬件应用基础研究不够，还没有成功应用的 报道。没有开展模拟系统硬件演化技术研究。国内的研究力量薄弱，缺少专门进行演 化硬件研究的研究群体 2 1 - 2 s l 。 1 。3 2 演化硬件的技术现状 以下从实现硬件演化的现场可编程器件、硬件演化算法、演化硬件的应用三方面， 1 硬件演化理论、方法及实现 来分析演化硬件技术现状。 1 可用于进行硬件演化的芯片 在硬件演化技术发展初期，演化硬件基本上基于g a l ( g a t ea r r a yl o g i c ) 芯片。前 几年主要使用的是x i l i n x 公司的现场可编程芯片( f p g a f i e i dp r o g r a m m a b l eg a t e a r r a y ) x c 6 2 0 0 1 2 6 i ，这种芯片较适合于硬件演化，且芯片内部结构位格式是公开的， 便于研究人员进行内部演化研究。但由于商业原因，这种芯片已经停产。现在主要使 用的演化芯片是x i l i n x 公司的v i r t e x 系列芯片，这种f p g a 芯片集成度高，便于组成 较大的应用系统。英国的d e l o nl e v i 研究出支持这种芯片进行硬件演化的仿真支撑 软件平台【5 】。上述芯片是通用的商业芯片，并不能全部满足进行硬件演化的需要，这 些芯片仅用于进行数字系统的硬件演化。另外，国外一些研究人员也在自行开发专用 演化硬件芯片，以提高演化系统的性能。 2 演化算法 目前硬件演化算法主要为遗传算法，这类算法比较适合进行硬件演化。其中遗 传算法主要是采用简单遗传算法、对遗传操作算子改进后的遗传算法以及变长染色 体编码遗传算法。 由于遗传算法是一种有向随机搜索优化方法，在其进化过程中至少有3 处使用 了基于概率型的操作，即选择操作、交叉操作和变异操作。这三个相对独立的遗传 性操作在演化过程中综合作用，使演化算法产生强大的优化搜索能力。但是，这些 基于概率型的操作使优化结果具有一定的不确定性。这样通过遗传算法进行硬件演 化，就存在着到演化终止代数仍未找到全局最优解( 函数功能完全正确的电路结构) 的可能性。 自从1 9 7 5 年j h h o l l a n d 提出遗传算法的完整结构和理论以来”，许多学者对 编码方式、控制参数的确定和交叉机理进行了深入的研究，提出了各种变形的遗传 算法。概括起来有”： ( d 改变遗传算法的组成部分，如控制参数的优化，适合具体问题的编码。 ( 2 ) 采用混合遗传算法。 ( 3 ) 采用动态自适应技术。 ( 4 ) 采用非标准的遗传算子。 ( 5 ) 采用并行遗传算法。 演化硬件的研究中，算法研究是一个重要内容。在算法的设计中有以下因素需 要考虑： ( 1 ) 染色体编码：随着大规模可编程集成电路的迅速发展，可编程芯片的规模越 来越大，参与操作的染色体位数也越来越多，染色体位数的增多大大增加了计算量， 影响了实时性。另外，目前的研究中，参与染色体编码的只有f p g a 中查找表中的配 南京航空航天大学硕士学位论文 置位，而没有包括配置逻辑块( c l b - - c o n f i g u r a t i o nl o g i cb l o c k ) 之间布线的控 制位，即其布线资源是预先定义好的，不参与演化，这样做主要是考虑演化速度， 但同时也使f p g a 中大量冗余资源得不到应用，降低了灵活性。 ( 2 ) 适应度评价：适应度的评价是指演化电路与期望电路的功能正确率，其评价 方法是划分内部演化和外部演化的标准。内部演化具有实时、准确等优点，但同时这 也对可编程芯片的性能提出了很高的要求，即芯片应具有s r a m 结构，可重复编程及 动态可重构的特点，另外还应该具有部分重构的能力，因为当遗传算法中染色体变异 的时候，可能仅仅只有一个很小的部分变化，这时候不希望重新配置整个位串，而只 对芯片中相对微小的部分进行重新配置，其他部分不变。如果每变异一位就必须重新 配置结构位，内部演化不会比外部演化快很多”1 。 ( 3 ) 算法的快速收敛：从工程应用的角度考虑，演化硬件要满足实时性的要求， 这就要求演化算法能够快速收敛到最优解。由于遗传算法具有很大的不确定性，针 对不同的演化对象，算法的性能也会有所差别。因此，如何针对具体的演化芯片结 构提出相应的算法设计是今后研究的核心问题。 1 3 3 硬件演化的发展趋势 1 演化硬件的难点 到目前为止，硬件演化技术尚未成熟，距离实际工程应用仍有很大差距，目前存 在的主要问题与技术难点有： ( 1 ) 演化算法本身的理论基础不很完善，由此给硬件演化与仿真分析带来了很大 的困难。尤其是如何提高演化速度和对演化结果进行优化，具体涉及到演化算法中染 色体的编码策略、个体的有效评估、演化的并行性等问题。对演化算法的理论研究和 改进将是推进硬件演化技术发展的一大动力。而从什么角度去结合算法和硬件，如何 结合，也将对硬件演化技术的发展方向产生重大影响。 ( 2 ) 目前没有非常适合进行硬件演化的通用可编程逻辑芯片。为此在国外取得突 出成就的一些研究机构中，常由研究人员参与专用演化芯片的设计。但无论对于国内 或国外的研究人员，芯片的结构位的格式是关键技术，但这往往是芯片制造商的技术 秘密。由研究人员自己设计演化芯片，面临的困难是设计难度大、设计时间长、设计 费用高、通用性差。而目前通用的商用芯片的规模还不能满足大系统硬件演化的需要， 特别是商用模拟现场可编程芯片不适合构成自适应系统。 ( 3 ) 国内研究人员缺少进行硬件演化研究的实验平台与软件。 2 演化硬件的发展趋势 ( 1 ) 研究基于f p g a 的系统级数字电路的硬件演化，以便组成自适应单芯片数字系 统。 ( 2 ) 基于f p t a 的模拟系统硬件演化是当前的研究热点，重点在f p t a 的拓扑结构、 演化方法，并进而研究数模混合系统的演化，为将来嵌入式单芯片微控制器的硬件演 5 硬件演化理论、方法及实现 化奠定理论基础”“。 ( 3 ) 专用硬件演化芯片的开发与研制，以实现硬件演化技术的工程应用；演化算 法在硬件演化的发展上占着很重要的位置，结合演化芯片的结构，继续改进演化算法 和寻找适合于硬件演化的新算法，这种算法要满足实时性要求。 ( 4 ) 演化硬件的应用研究，针对具体需要，研究基于演化硬件的自适应、自修复 系统。 1 4 论文的主要研究内容 本文的主要研究内容为： 第一章主要介绍了演化硬件的基本概念和分类，叙述了演化硬件的应用领域，讨 论了硬件演化技术的研究背景、技术现状及发展趋势。 第二章引入演化硬件的基本原理，着重说明了演化硬件研究中的关键技术并介绍 了演化硬件芯片的结构。 第三章主要讨论了硬件演化技术中的演化算法、编码方法及评价方法。 第四章介绍了j b i t sa p i 软件的基本开发流程并对内部演化和外部演化两种方 式的流程进行了研究。 第五章通过应用实例对硬件演化的两种方式加以验证，并对仿真结果进行了统 计、分析。 第六章对全文进行了总结，并对课题今后的研究提出一些设想。 6 南京航空航天大学硕士学位论文 第二章硬件演化技术原理 2 1 演化硬件的原理 演化硬件的概念最初是由日本的h u g od eg a r i s 和瑞士联邦工学院于1 9 9 2 年提 出的。1 9 9 2 年，h d eg a r i s 与一位电子工程师讨论硬件时，获悉可编程集成电路， 如p l d ( p r o g r a m m a b l el o g i cd e v i c e ) 的结构是由结构位串决定的，由此想到将结构 位串当作演化算法中的染色体，通过演化算法来完成硬件功能的设计。于是就有： 演化算法+ 可编程逻辑器件= 演化硬件 实现硬件演化的方法通常有两种【l7 】：一种是外部演化( e x t r i n s i ce h w ) ，另一种 是内部演化( i n t r i n s i ce h w ) ，如图2 - 1 所示。所谓外部演化是指通过建立电子器件 的模型，将由演化算法产生的染色体( 也就是相应的配置位，对应一种线路结构) 在 外部演化+ 内部演化e 专 图2 - 1 电子线路演化的主要步骤 模型上进行评判，当达到预期的目标时，就将这组染色体下载到硬件中去。这种方法 主要应用于早期的演化硬件中，由于硬件条件的局限，演化硬件研究早期是基于简单 的p l d ，如g a l ( g a t ea r r a yl o g i c ) 、p a l ( p r o g r a m m a b l ea r r a yl o g i c ) 等基础上的， p a l 、g a l 的电路结构规模小、编程次数有限，决定其不适合内部演化的方法。内部 演化是将演化算法每一代产生的每一条染色体都实际下载到器件中，并对每一种电路 结构的输出直接进行评判。这就对硬件本身提出很高的要求，它必须具有快速重构的 能力，这从根本上区别于传统的硅器件。 硬件内部演化原理：c p u 运行演化程序，如图2 2 中解空间所示，首先随机产生 初始解( 即一串二进制数) ，初始解对应着电路空间中的一种结构。这种电路功能与 期望电路的功能的符合程度通过适应度进行评价。评价的过程是将初始解从解空间映 射到电路空间，实际操作时是将初始解映射为f p g a 的配置位，下载至f p g a 中，输入 相应的测试集，并将输出结果与期望电路的输出进行比较，正确的程度即为适应度， 然后将适应度值返回，c p u 将得到的适应度作为评判，决定算法程序下一步的迭代。 硬件演化理论、方法及实现 f p g 毫一 l ：蓬电踺窑圃中评价并将 ：评价值蘧回篁法程蓐。 ，g l ! ： l 一 扭n i o 一 。l一7 蕴化出鹩屯路 电路空间 蹑化孽祛解至i 司 图2 2 硬件内部演化原理 2 2 演化硬件研究中的关键技术 演化硬件在实现过程中有两个关键技术： 1 演化硬件芯片的选择 用来进行内部演化的主要器件是f p g a ，不过早期的一些产品重构通常需要几秒钟 的时间，直到x “i n x 公司推出x c 6 2 0 0 ，这个问题才得以解决。x c 6 2 0 0 是基于s r a m 结构，这就意味着它可以实现快速配置。x c 6 2 0 0 系列用于e h w 的最重要的优点是其 结构公开性，所以用户可以知道任意一个配置位的功能。而且，x c 6 2 0 0 系列接受随 意的位串而不会受损坏。这种器件具有以下特点： ( 1 ) 微处理器接口：通过标准微处理器接口对静态r a m 进行配置。 ( 2 ) 部分重构：可以只改变器件的某一区域的配置，而不影响其他区域。 ( 3 ) 快速重构：使用并行接口从而大大提高了配置速度。 ( 4 ) 数据格式已知：可获取位流的格式，因此用户可以修改配置的某一部分。 ( 5 ) 配置安全：通过限制逻辑块之间的连接，器件设计为对随机配置安全可靠。 不过由于以上特点，也带来了一系列的问题，例如，为确保配置的安全性而限制 逻辑块的连接，使器件在一些复杂运算电路中的应用受到限制。由于这种芯片不能用 于一般应用，注定了它不能大规模生产制造。因此x i l i n x 公司于1 9 9 8 年终止了对 南京航空航天大学硕士学位论文 x c 6 2 0 0 系列的生产，现在很难再买到这种芯片。 自从x c 6 2 0 0 系列停产后，演化硬件曾一度被认为无法继续研究下去，直到v ifr e x 系列问世以后，才给演化硬件带来了希望。x i l i n x 推出的v i r t e x 系列同x c 6 2 0 0 有 很多相似的属性，并克服了一些缺点。v i r t e x 芯片的主要特点有： ( 1 ) 部分重构：可以在很小的结构里进行重构。 ( 2 ) 快速重构：具有s e l e c t m a p 接口，可以直接同微处理器连接。 ( 3 ) 数据格式未知：由于该器件要大量生产并形成下一代的f p g a 器件，数据格式 不公开。 ( 4 ) 配置的不安全性：与x c 6 2 0 0 不同的是，v i r t e x 器件返回到c l a s s i cf p g a 的 设计，具有c l b 之间和多方向的布线，这意味着会产生使输出端短接的位流。 由于器件可能被随机配置位流所破坏，因此普遍认为演化硬件无法在v i r t e x 器件 中完成，除非整个遗传算法包含x i l i n x 的布线工具。不过，随着j b i t sa p i 的引入， 又有了新的解决方法。 j b r sa p i 是由x i l l a x 公司的j b i t s 组开发的。由于j b i t s 组的研究人员了解 x i l i n x 芯片的核心技术，知道每一个配置位的功能，所以开发了j b i t sa p i 软件， 使任何人都能在4 0 0 0 和v i r t e x 系列芯片上研究演化硬件。这个软件是为商业性的重 构计算板设计的，板卡主要包括可编程芯片和p c 接口。这个工具为研究者开放了演 化硬件领域，如果x i l l a x 公开其结构，该领域就会更加开放。至此，新的r t e x 器 件基本解决了长期以来无法在数字电子器件中实现随机配置的问题。 v i r t e x 芯片和x c 6 2 0 0 相比，部分重构功能弱了。部分重构性对演化硬件来说是 基本的，因为当遗传算法中变异的时候，可能仅仅只有一个很小的部分变化，这时候 无需重新配置所有位串，而只要重新配置电路不同的部分，其他部分不变。如果每变 异一位就必须重新配置所有配置位，那么内部演化不会比外部演化快很多。 2 处理器的选择 演化硬件的远期目标是实现一个具有自组织、自适应、自修复的系统，随着大规 模集成电路的发展，已经可以实现将c p u 嵌入至可编程芯片中，这样就可以在一片可 编程芯片中实现可演化的片上系统( e v o l v a b l es y s t e mo nac h i p 一一e v 0 1 v a b l e s o c ) 。 由于我们起步比较晚，目前技术还不成熟，直接做到s o c 级难度很大。本课题中 处理器选择p c 机，其原因主要是： ( 1 ) 可以利用j b i t sa p i 软件，避免了对芯片内部结构位的直接操作，研究的重 点将是对演化算法、结构位的编码进行改进，以提高演化性能。 ( 2 ) p c 机有着方便的图形用户接口，便于对演化过程进行分析。 硬件演化理论、方法及实现 2 3 演化硬件芯片介绍乜“3 町 本节详细介绍v ir t e x 系列f p g a 芯片的内部结构。演化硬件不是简单的对可编程 器件的应用开发，必须对器件的结构有着深入的研究，这也是演化硬件研究的一个重 点与关键。 1 v i r t e x 器件结构 v i r t e x 系列f p g a 结构如图2 - 3 所示，它由一个可配置逻辑块( c o n f i g u r a t i o n l o g i cb 1 0 c k c l b ) 阵列组成，c l b 阵列周围由输入输出模块( 1 0 b ) 所环绕，在阵 列块的两边是r a m 块( b r a m ) 。c l b 是主要的构造块，包含了可编程门级逻辑电路、 触发器及通用布线等组成部分。每个c l b 包括两个切片( s l i c e ) ，每个s 1i c e 的主要 组成部分是f 、g 查找表，x 、y 触发器，l u t 可以用来实现门级组合电路或小规模 存储器，触发器用来建立状态机，快速进位逻辑用来实现算术运算。1 0 b 提供了同外 部器件进行信号通信的线路。b r a m 允许数据的同步或异步存储。 图2 3v i r t e x 器件结构 2 c l b 结构 c l b 的结构框图如图2 4 所示，每个c l b 包括两个s l i c e 。每个s 1 i c e 包括2 个 图2 - 4c l b 结构框图 南京航空航天大学硕士学位论文 四输入查找表( l u t ) ，2 个d 触发器和一些进位逻辑。一个v i r t e xs 1i c e 在功能上跟 x i1i n x4 0 0 0 的c l b 相似，也就是说，每个v i r t e xc l b 可以实现大约两个x c d 0 0 0c l b 的逻辑功能。通用布线( g e n e r a lr o u t i n g ) 允许传送数据到c l b 或从c l b 接收数据。 输入多路选择器( m u x ) 允许通过通用布线传送数据到s 1 i c e 而输出多路选择器允许 s 1i c e 传送数据到通用布线。 3 s 1 i c e 内部结构 s 1 i c e 的主要组成部分是f 、g 查找表，x 、y 触发器，l u t 可以用来实现门级 电路或实现小规模存储器，触发器用来建立状态机，s 1 i c e 也有内部m u x 用来控制内 部资源的连接，最后在每个s 1i c e 中有快速进位逻辑用来实现算术运算。每个s li c e 的输入输出信号如图2 5 所示。每个s l i c e 有1 3 个输入，包括f 1 f 4 ，g 1 一g 4 c l k 、 s r 、b x 、b y 、c e 。每个输入有一个m u x 与之相关联，决定哪条线驱动输入，使用j b i t s ， 每个输入m u x 有它自己的类名字。图2 - 6 为s l i c e 内部的详细结构。 图2 5s 1 i c e 输入输出信号 4 c l b 通用布线 通用布线包括两种连线：s i n g l e 和h e x 。s i n g l e 用于连接相邻的c l b ，而h e x 用于连接6 个c l b 以外的c l b ，即s i n g l e 用于本地c l b 之间传送数据，而h e x 用于 非本地c l b 之间的数据传送，详细结构如图2 8 所示。s i n g l e 和h e x 分组到沿四个 方向延伸的总线( b u s ) 里：东，南，西，北。相邻c l b 之间的连接是直接的。如： 一根北s i n g l e 线可与它上面c l b 的南sl n g l e 线直接相连。一根西h e x 线可直接与左 面6 个c l l 3 以外的根东h e x 线相连。s i n g l e 换向盒( s w i t c hb o x ) 用于将不同的 s i n g l e 线连接起来。例如，北总线中的一根s i n g l e 可与西总线上的s i n g l e 线或是 南总线中的s i n g l e 线相接。s i n g l e 换向盒用于延伸s i n g l e 线或改变其方向。h e x 换向盒( s w i t c hb o x ) 用于将不同的h e x 线连接起来。通过h e x 换向盒，可以将信号 通过h e x 线传送6 个c l b ，再转向传送6 个c l b 的距离。 主要的换向盒用于： ( 1 ) 连接输入多路选择器( i n p u tm u x ) 的s i n g l e 线 ( 2 ) 连接输出多路选择器( o u t p u tm u x ) 的s i n g l e 线 硬件演化理论、方法及实现 图2 - 6s 1 i c e 内部详细结构 2 o o 南京航空航天大学硕士学位论文 ( 3 ) s i n g l e 间的连接、h e x 问的连接 5 h e x 的规则 如图2 7 所示，只能向c l b 输入数据的h e x 线称为单向输入；只能由c l b 输出数 据的h e x 线称为单向输出。既可以输入数据也可以输出数据的h e x 线称为双向。但要 注意，电路在双向传送线中同一时间只能向一个方向传送数据，否则会导致器件的损 坏。 鎏辐铲 。 ” t t u s l l 图2 7h e x 线的方向规定 e 硬件演化理论、方法及实现 图2 - 8c l b 通用布线图 4 南京航空航天大学硕士学位论文 第三章硬件演化方法研究 硬件的演化方法可以从演化算法、编码方法和适应度评价方法三个方面进行研 究。 3 1 硬件演化算法研究 硬件演化主要通过演化算法实现。演化计算最初具有三大分支：遗传算法( 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 s t r a t e g y - - e s ) 。2 0 世纪9 0 年代初，在遗传算法的基础上又发展了一个分支：遗传程 序设计( g e n e t i cp r o g r a m m i n g 一g p ) 。本节主要介绍标准遗传算法的思想及其改进型。 3 1 1 遗传算法的基本思想乜町 遗传算法是从代表问题可能潜在解集的一个种群开始的，一个种群由经过基因编 码的一定数目的个体组成。每个个体实际上是染色体带有特征的实体。染色体作为遗 传物质的主要载体，即多个基因的集合，其内部表现( 即基因型) 是某种基因组合， 它决定了个体形状的外部表现。因此，在一开始需要实现从表现型到基因型的映射即 编码工作。初始种群产生之后，按照适者生存和优胜劣汰的原理，逐代演化出越来越 好的近似解。在每一代，根据问题域中个体的适应度大小挑选个体，并借助于自然遗 图3 - 1 遗传算法基本思想 硬件演化理论、方法及实现 传学中的遗传算子进行组合、交叉和变异，产生出代表新的解集的种群。这个过程将 使得种群像自然进化一样，后代种群比前代更加适应于环境，末代种群中的最优个体 经过解码，可以作为问题近似最优解。 遗传算法采用自然进化模型，如选择、交叉、变异等。图3 1 表示了基本遗传算 法的过程。计算开始时，一定数目个体( 父个体1 、父个体2 、父个体3 、父个体4 ) ， 即种群，随机地初始化，并计算每个个体的适应度函数，初始代就产生了。如果不满 足优化准则，就开始新代适应度的计算。为了产生下一代，按照适应度选择个体， 父代通过基因重组( 交叉) 而产生子代。所有的子代按一定概率变异。然后子代又被 重新计算适应度，插入到种群中替换父代，构成新的一代( 子个体1 、子个体2 、子 个体3 、子个体4 ) 。这一过程循环执行，直到满足优化准则为止。 3 1 2 遗传算法的基本步骤阻1 遗传算法的基本流程可由图3 - 2 表示。在设计遗传算法时，通常可以按以下的基 本步骤进行： ( 1 ) 确定编码方案：演化算法求解问题不是直接作用在问题的解空间上，而是利用 解的某种编码表示。选择何种编码表示对算法的性能、效率等将产生很大的影响。 ( 2 ) 确定适应度函数：适应度是对解正确度的一种度量。一般以目标函数的形式来 表示。解的适应度是演化过程中进行选择的唯一依据。 ( 3 ) 选择策略的确定：优胜劣汰的选择机制使得适应度值大的解有较高的存活概 率，这是演化算法与一般搜索算法的主要区别之一。不同的选择策略对算法的性能也 有较大的影响。 图3 2 遗传算法流程 ( 4 ) 演化算子的设计：演化算法中的演化算子，主要包括复制( r e p m d u c t i o n ) 、交叉 ( c r o s s o v e r ) 、变异( m u t a t i o n ) 及其它高级操作。 6 南京航空航天大学硕士学位论文 ( 5 ) 控制参数的选取：控制参数主要包括种群的规模、算法执行的最大代数、执行 不同遗传操作的概率以及其它一些辅助性的控制参数。 ( 6 ) 确定算法的终止准则：常用的办法是预先规定一个最大的演化代数或算法在连 续多少代以后解的适应值没什么明显的改进时，即终止。 下面对上述步骤涉及到的方法作具体的说明。 1 编码方法 编码是应用演化算法时要解决的首要问题，也是设计演化算法时的一个关键步 骤。编码方法不仅影响个体的基因排列形式，而且影响到交叉算子、变异算予等演化 算子的运算方法。由此可见，编码方法在很大程度上决定了如何进行群体的演化运算 以及演化运算的效率。一个好的编码方法，有可能会使得交叉运算、变异运算等演化 操作可以简单地实现和执行。而一个差的编码方法，却有可能会产生很多在可行解集 合内无对应可行解的个体，这些个体经解码处理后所表示的解称为无效解。虽然有时 产生一些无效解并不完全都是有害的，但大部分情况下它却是影响演化算法运行效率 7 的主要因素之一。 针对一个具体应用问题，如何设计一种完美的编码方案一直是演化算法的应用难 点之一，也是演化算法的一个重要研究方向。设计编码方案目前还没有一套既严密又 完整的指导理论及评价准则。所以对于实际应用问题，必须对编码方法、交叉方法、 变异方法、解码方法等统一考虑，以寻求到一种对问题的描述最为方便、演化运算效 率最高的编码方案。 编码策略通常采用三个评估规范： ( 1 ) 完备性。问题空间的所有点都能作为算法空间的染色体表示。 ( 2 ) 健全性。算法空间的染色体能对应所有问题空间的点。 ( 3 ) 非冗余性。染色体和问题空间的点一一对应。 总的来说，编码方法可以分为二进制编码方法、实数编码方法和符号编码方法。 2 适应度函数 在研究自然界生物的遗传和进化现象时，生物学家使用适应度这个术语来度量某 个物种对其生存环境的适应程度。对生存环境适应程度较高的物种将有更多的繁殖机 会；而对生存环境适应程度较低的物种，其繁殖机会就相对较少，甚至会逐渐灭绝。 与此相类似，演化算法中也使用适应度这个概念来度量群体中各个个体在优化计算中 有可能达到或接近于找到最优解的优良程度。适应度较高的个体保留到下一代的概率 就较大；而适应度较低的个体保留到下一代的概率就相对小一些。度量个体适应度的 函数称为适应度函数( f i t n e s sf u n c t i o n ) 。 演化算法的一个特点是它仅使用所求问题的目标函数值就可得到下一步的有关 搜索信息。而对目标函数值的使用是通过评价个体的适应度来体现的。 硬件演化理论、方法及实现 评价个体适应度的一般过程是： ( 1 ) 对个体编码串进行解码处理后，可得到个体的表现型( 个体在环境中表现的 性状) 。 ( 2 ) 由个体的表现型可计算出对应个体的函数值。 ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适应度。 演化算法中，群体的进化过程就是以群体中各个个体的适应度为依据，通过一个 反复迭代过程，不断地寻求出适应度较大的个体，最终就可得到问题的最优解或近似 最优解。由此可见，如何确定适应度对演化算法的性能有较大的影响。 3 选择算子 在生物的遗传和自然进化过程中，对生存环境适应程度较高的物种将有更多的机 会遗传到下一代；而对生存环境适应程度较低的物种遗传到下一代的机会就相对较 少。模仿这个过程，演化算法使用选择算子( 或称复制算子，r e p r o d u c t i o n0 p e r a t o r ) 来对群体中的个体进行优胜劣汰操作：适应度较高的个体被演化到下一代群体中的概 率较大；适应度较低的个体被演化到下一代群体中的概率较小。演化算法中的选择操 作就是用来确定如何从父代群体中按某种方法选取哪些个体保留到下代群体中的 一种演化运算。 选择算子有很多种，其中最常用和最基本的选择算子是比例选择算子。其基本思 想是：各个个体被选中的概率与其适应度大小成正比。设群体大小为 个体的适 ln 应度为p , - ，则个体，被选中的概率p 。为：p 。= f f ( f = 1 , 2 ，| v ) 。 由上式可见，适应度越高的个体被选中的概率也越大；反之，适应度越低的个体 被选中的概率也越小。比例选择算子的具体执行过程是： ( 1 ) 计算群体中所有个体的适应度的总和。 ( 2 ) 计算每个个体的相对适应度的大小，即为各个个体被遗传到下一代群体中的 概率。 ( 3 ) 使用模拟赌盘操作( 即0 到l 之间的随机数) 来确定各个个体被选中的次数。 4 交叉算子 在生物的自然进化过程中，两个同源染色体通过交配而重组，形成新的染色体， 从而产生出新的个体或物种。交配重组是生物遗传和进化过程中的一个主要环节。模 仿这个环节，在演化算法中也使用交叉算子来产生新的个体。 演化算法中的所谓交叉运算，是指对两个相互配对的染色体按某种方式相互交换 其部分基因，从而形成两个新的个体。交叉运算是演化算法区别于其它进化算法的重 要特征，它在演化算法中起着关键作用，是产生新个体的主要方法。 南京航空航天大学硕士学位论文 演化算法中，在交叉运算之前还必须先对群体中的个体进行配对。目前常用的配 对策略是随机配对，即将群体中的n 个个体以随机的方式组成| n 2i 对配对个体组， 交叉操作是在这些配对个体组中的两个个体之间进行的。 交叉算子的设计和实现与所研究的问题密切相关，一般要求它既不要太多地破坏 个体编码串中表示优良性状的优良模式，又要能够有效地产生出一些较好的新个体模 式。另外，交叉算子的设计要和个体编码设计统一考虑。 交叉算子的设计包括以下两方面的内容：确定交叉点位置和部分基因交换。 最常用的交叉算子是单点交叉算子。但单点交叉操作有一定的适用范围，故此人 们发展了其它一些交叉算子。