（控制理论与控制工程专业论文）基于fpga的遗传算法的硬件实现技术研究.pdf

硕士论文基于f p g a 的遗传算法的硬件实现技术研究 摘要 遗传算法是一种基于自然选择原理的优化算法，在很多领域有着广泛的应用。但是， 遗传算法使用计算机软件实现时，会随着问题复杂度和求解精度要求的提高，产生很大 的计算延时，这种计算的延时限制了遗传算法在很多实时性要求较高场合的应用。 为了提升运行速度，可以使用f p g a 作为硬件平台，设计数字系统完成遗传算法。 和软件实现相比，硬件实现尽管在实时性和并行性方面具有很大优势，但同时会导致系 统的灵活性不足、通用性不强。本文针对上述矛盾，使用基于功能的模块化思想，将基 于f p g a 的遗传算法硬件平台划分成两类模块：系统功能模块和算子功能模块。针对不 同问题，可以在保持系统功能模块不变的前提下，选择不同的遗传算子功能模块完成所 需要的优化运算。 本文基于x i l i n x 公司的v i r t e x 5 系列f p g a 平台，使用v e r i l o g h d l 语言实现了伪随 机数发生模块、随机数接口模块、存储器接口控制模块和系统控制模块等系统功能模 块，以及基本位交叉算子模块、p m x 交叉算子模块、基本位变异算子模块、交换变异 算子模块和逆转变异算子模块等遗传算法功能模块，构建了系统功能构架和遗传算子 库。该设计方法不仅使遗传算法平台在解决问题时具有更高的灵活性和通用性，而且维 持了系统架构的稳定。 本文设计了多峰值、不连续、不可导函数的极值问题和1 6 座城市的旅行商问题 ( t s p ) 对遗传算法硬件平台进行了测试。根据测试结果，该硬件平台表现良好，所求 取的最优解误差均在l 以内。相对于软件实现，该系统在求解一些复杂问题时，速度 可以提高2 个数量级。最后，本文使用f p g a 实现了粗粒度并行遗传算法模型，并用于 t s p 问题的求解。将硬件平台的运行速度在上述基础上提高了近l 倍，取得了显著的效 果。 关键词：遗传算法，硬件实现，并行设计，f p g a ，t s p a b s t r a c t硕士论文 a b s t r a c t g e n e t i ca l g o r i t h m ( g a ) i sak i n do fo p t i m i z a t i o nm e t h o d sb a s e do nn a t u r a ls e l e c t i o n ， w h i c hi sa p p l i e dt om a n yd i f f i c u l to p t i m i z a t i o np r o b l e m s g ah a sb e e nw i d e l yu s e di nm a n y a r e a s ；h o w e v e r , a p p l i c a t i o no fg a t o i n c r e a s i n g l yc o m p l e xo ra c c u r a c yr e q u i r e dp r o b l e m s w i l lc a u s eu n a c c e p t a b l ed e l a y si no p t i m i z a t i o np r o c e s sw h i c hl i m i tt h ea p p l i c a t i o n so fg at o m a n yr e a l - t i m es y s t e m sa n dp r o b l e m s c o m p a r e dt os o f t w a r ei m p l e m e n t a t i o n ，h a r d w a r e s y s t e mi ss u p e r i o ri na s p e c t so fr e a l - t i m ea n dp a r a l l e l i s m ，b u ts h o r tf o rf l e x i b i l i t ya n d c o m p a t i b i l i t y f o c u s i n go nt h e s ec o n f l i c t s ，m o d u l e sa r ed i v i d e db a s e do nf u n c t i o n s ，i no r d e r t os u i tf o r d i f f e r e n tp r o b l e m si nd i f f e r e n tc i r c u m s t a n c e s m o d u l e sa r ed i v i d e di n t ot w ok i n d s ：s y s t e m f u n c t i o nm o d u l e sa n dg ao p e r a t o rm o d u l e s t h ea d v a n t a g e so ft h ed i v i s i o na r et h a td i f f e r e n t g a o p e r a t i o n sc a i lb ec h o s e nt oc o m p l e t et h ea l g o r i t h m s ，a c c o r d i n gt od i f f e r e n tp r o b l e m r e q u i r e s ，w i t h o u tc h a n g i n gs y s t e ma r c h i t e c t u r e i nt h i sp a p e r , s y s t e mf u n c t i o nm o d u l e sa n dg ao p e r a t o rm o d u l e sa r ei m p l e m e n t e du s i n g v e r i l o g h d ll a n g u a g eb a s e d o nx i l i n xv i r t e x 5s e r i e sf p g ap l a t f o r m ，i n c l u d i n gs y s t e m f u n c t i o nm o d u l e s ，s u c ha s ，p s e u d o r a n d o mr a n d o mn u m b e rm o d u l e ，r a n d o mn u m b e r i n t e r f a c em o d u l e ，m e m o r yi n t e r f a c e c o n t r o lm o d u l e s ，s y s t e mc o n t r o lm o d u l ea n ds oo n ， a n dg ao p e r a t o rm o d u l e s ，s u c ha s ，b a s i cd i g i t a lc r o s s o v e rm o d u l e ，p m xc r o s s o v e r m o d u l e s ，b a s i cd i g i t a lm u t a t i o nm o d u l e s ，p o s i t i o nc h a n g em u t a t i o nm o d u l e s ，r e v e r s e m u t a t i o nm o d u l e sa n ds oo n c o n s t r u c tt h el i b r a r yo fg ao p e r a t o r sa n da r c h i t e c t u r eo f s y s t e m ，w h i c h n o t o n l y c o n t r i b u t em o r e f l e x i b i l i t y a n dc o m p a t i b i l i t yt oh a r d w a r e i m p l e m e n t a t i o no fg a ，b u ta l s om a i n t a i nt h es t a b i l i t yo f t h es y s t e ma r c h i t e c t u r e m u l t i p e a k ，n o n c o n t i n u o u s ，n o n d i f f e r e n t i a b l ef u n c t i o na n d16c i t i e st r a v e l i n gs a l e s m a n p r o b l e m ( t s p ) a r ed e s i g n e df o rt e s t i n gt h i sh a r d w a r ep l a t f o r mo fg a a c c o r d i n gt ot h et e s t r e s u l t h a r d w a r ep l a t f o r mo b t a i n e dt h eo p t i m a ls o l u t i o ne r r o rw i t h i nl m e a n w h i l e ，o n s o l v i n gs o m ec o m p l e xp r o b l e m s ，t h es p e e di sa c c e l e r a t e d2o r d e r so fm a g n i t u d ec o m p a r e dt o s o f t w a r e a n dac o a r s e g r a i n e dp a r a l l e lg am o d u l ei sd e s i g n e df o rs o l u t i o no ft s r c o m p e t e db a s i cd o u b l e c o r ec o a r s e - g r a i n e dp a r a l l e lg am o d u l e ，h a r d w a r ec o m p u t es p e e d i si n c r e a s e dn e a r l y1t i m e sf u r t h e r , r e c e i v e das i g n i f i c a n te f f e c t k e yw o r d ：g e n e t i ca l g o r i t h m s ，h a r d w a r ei m p l e m e n t a t i o n ，p a r a l l e l ，f p g a ，t s p i i 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在本 学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同工作的同事对本学位论文做出的贡献均已在论文 中作了明确的说明。 研究生签名：趑匝这p 年口汨扣e l 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅或 上网公布本学位论文的部分或全部内容，可以向有关部门或机构送交并 授权其保存、借阅或上网公布本学位论文的部分或全部内容。对于保密 论文，按保密的有关规定和程序处理。 研究生签名： 丝犀盗 扣加年形月日 硕士论文基于f p g a 的遗传算法的硬件实现技术研究 l 绪论 1 1 本文的研究背景及意义 智能算法【1 , 2 1 是一类具有学习功能、适应功能、组织功能等特点的优化算法，涉及 人工智能、运筹学、非线性理论、知识工程、神经网络理论、模糊集合理论、优化理论 等诸多学科。智能算法主要被用于解决复杂系统的优化问题，其中包括复杂工业过程控 制系统、航空航天控制系统、智能机器人控制系统、交通运输系统等【2 7 引，可以解决 具有高度非线性、不确定性和复杂的任务要求。遗传算法 1 , 4 , 5 1 是智能算法的一个分支， 该算法是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法簇，最早由 h o l l a n d 教授提出【1 1 ，其主要特点是群体搜索策略和群体中个体之间的信息交换，优点 是搜索不依赖于梯度信息，所以适应范围较一般的优化算法更广1 7 岿j 。 经历了近半个世纪的发展，遗传算法在很多领域都有了成功的应用 9 - 1 2 j ，但因其基 础理论不尽完善、算法结构缺乏严谨性，很多情况下，算法的应用超前理论【l3 ，1 4 j 。此外， 不同问题的定义域需要不同的编码方式和不同的遗传算子，不同问题的目标又需要不同 的适应度计算函数，因此，遗传算法在适应不同问题的过程中逐步发展成为一个算法簇。 很多学者设计了大量具有针对性的遗传算子，一方面，丰富了遗传算法 1 4 0 1 6 j ，但另一方 面，也限制了遗传算法的通用性。这种限制主要表现在如下两个方面： 1 ) 遗传算法在解决一些问题时，可能出现运算求解时间过长和算法的收敛性得不 到理论上的保证等现象。因此，在一些实时性、复杂性和动态性要求较高情况下，该算 法难以得到应用。 2 ) 一般情况下，复杂的系统存在大量待优化的参数，这些参数的定义域和优化目 标的评价存在差异，因此每类参数的遗传算法编码、遗传算子和评价函数也存在差异。 然而，对于不同类的参数重新设计实现遗传算法，将导致设计周期过长、设计成本过大， 这也限制了遗传算法的应用。 综上，遗传算法的运算速度和通用性成为影响其在实际工程应用的两大瓶颈。提高 算法的运算速度和通用性将使其在实际工程中应用更为广泛，存在较大的工程应用价 值：首先，提高算法的运算速度不仅有助于提高系统的响应速度并在一定程度上提高系 统的稳定性，而且可以使得遗传算法在相同时间内能解决更复杂的问题。其次，使用模 块化的思想设计遗传算法的运算平台，算法平台仅需要做少量配置，就可以适应新的问 题需要，这不仅增加了算法的灵活性，也扩大了算法平台的应用范围。 1 2国内外研究现状 遗传算法是一类基于自然选择和遗传学原理的有效搜索方法，具有天然的并行性， l 绪论硕士论文 在许多领域取得了成功的应用【1 7 汐】。在遗传算法的运算过程中，对于个体适应度评价、 选择、基因交叉，基因变异实现等操作都耗时不多，但是当将这些操作放置于整个种群 时，程序的耗时将随种群数量急剧增加，而且随着求解问题的复杂度及难度的增加，基 因编码串的长度也要变长以满足精度要求等等【5 , 1 8 , 1 9 j ，这就使得提高遗传算法的运行速 度变得十分迫切。目前，可以通过两方面提高遗传算法的运算速度： 1 ) 算法改进 2 0 。2 4 】：通过建立并行算法模型来提升遗传算法的运行速度。其本质是 多机运行，使用多台计算机联网来提高速度。 2 ) 硬件实现 2 5 讲】：针对遗传算法操作简单等特点，设计相应的数字系统或专用芯 片以完成相应的遗传操作，提高算法的并行性和实时性。其缺点是早期设计投入较大。 此外，硬件化的遗传算法可以作为一个片上系统( s o c ，s y s t e mo nc h i p ) 集成在一个 芯片上。这样的嵌入式设计可以在一些p c 无法使用的场合，例如对实时性要求较高或 对时序要求较严格的场合，代替p c 完成优化计算。 1 2 1 算法结构的改进 算法结构的改进，即把遗传算法等价地变换成一种并行方案，改进遗传算法的模型 结构，使其形成并行群体模型【1 2 , 2 8 , 2 9 1 。并行遗传算法分为三种基本模型：全局并行模型 3 0 , 3 1 1 、粗粒度模型 3 2 , 3 3 和细粒度模型【3 4 ，3 5 1 。以上三类模型必须借助于多台计算机组成的 网络来实现。 1 ) 全局并行模型。全局并行模型是遗传算法的一种直接并行化方案，主要实现方 法是主、从多机处理，其中主机负责选择操作，从机负责交叉、变异和适应度计算。因 此，该模型只有一个群体，个体之间可以任意匹配，因而在群体上所作的选择和匹配是 全局的。在该模型中，增加从机数量可以提高并行度，但过分增加从机数量，会导致通 信开销急剧上升。有关从机数量与通信量的研究表明【5 j ，对于大部分问题来讲，全局并 行算法在特定的运算规模下，存在着一个最优的从机数。 2 ) 粗粒度模型，又称为孤岛模型，其思想是扩展算法结构。该模型将群体划分为 多个子群，每个子群独自运行一个遗传算法，分别在不同计算机上运行，并且通过一定 的机制将子种群的最优个体扩散到整体种群。在该模型中，次级种群选择取代了全局选 择，配偶取自同一子群，并且子代与同一子群中的其他个体竞争。这类并行遗传算法除 了基本的遗传算子外，还引入了“迁移”算子，负责管理区域之间的个体交换。 3 ) 细粒度模型，又称为扩散模型。在系统运算资源充足的情况下，可为种群内部 的每个个体分配一个处理器，即种群中的每个个体相当于一个自动机。让每个个体相互 独立地执行进化操作，可以获得最大可能的并发性。该模型的难点在于设计个体之间通 信模式。解决这一难点的通常方法是将个体分配到特定的空间环境，如平面网格或者环 状网格等。在该模型中，交叉操作仅允许在相邻的个体之间发生，较优的个体通过通信 2 硕士论文基于f p g a 的遗传算法的硬件实现技术研究 机制传播到整个种群。 总体而言，粗粒度模型与细粒度模型使用较为广泛，但是粗粒度模型与细粒度模型 孰优孰劣，尚是一个未知数【3 6 , 3 7 1 。相比之下，粗粒度模型目前更为流行，一方面，因为 实现方法容易，即只需在遗传算法中增加迁移子例程，并定期交换几个个体；另一方面， 实现环境简单，即使用多台计算机进行联网计算。 1 2 2 硬件实现 硬件实现，即为遗传算法设计具有针对性的数字系统，将其软件的串行处理模式通 过硬件系统实现并行化。使用硬件实现遗传算法的途径有两种：开发通用a s i c 器件和 使用可编程芯片。 a s i c 器件是为解决某些问题而专门设计的集成电路。虽然遗传算法有固定的结构， 但是算法必须针对特定问题设计相应的适应度函数和编码方式。这要求硬件平台具有很 高的重用性和灵活性。因此，不论从时间消耗还是成本花费的角度，开发通用a s i c 器 件都不是理想的硬件实现方案。另外，a s i c 器件使用和修改也不灵活，不能满足要求。 现场可编程门阵y f j ( f p g a ) n 件的发展使得芯片的集成度越来越高，用f p g a 实现 遗传算法因此成为可能。同时，因为具有针对性设计的数字系统可以做到并行处理，所 以遗传算法的f p g a 硬件化将是一种提高算法运行速度的有效方式 3 8 , 3 9 1 。此外，由于可 以通过配置下载特定的比特流文件在f p g a 芯片上构建数字系统，因此对系统的修改将 变得非常容易，这符合算法对设计灵活性的要求。在实现结构上，硬件实现主要有两种 方式： 1 ) 全硬件模式【4 0 ，4 1 1 。该模式将所有问题付诸硬件实现，这样可以获得最大的速度 提升，但是该实现对于不同的问题需要不同的遗传算法模型，即需要重新改写数字系统 的内部结构，重新配置f p g a 。设计过程繁琐，适用范围有限。 2 ) 半硬件模式f 4 2 ，4 3 1 。该模式将耗时较多的个体选择，交叉，变异等运算用f p g a 实现，而其他部分通过软件实现，此时f p g a 可以作为计算机的协处理器，对于不同问 题，仅需要改写程序即可。但是，使用该模式，运行速度将受到影响，而且f p g a 本身 和电脑之间的通讯也是一个值得考虑的问题。 国外一些学者已经对硬件实现做出了研究m 础】，而相比较而言国内对该问题的研究 起步较晚4 9 , 5 0 】。这些研究针对特定问题，设计了具体的遗传算法硬件系统，使得遗传算 法的运行速度得到了提高，获得了不少探索性和阶段性的成果。但是，使用硬件实现遗 传算法仍然面临很多问题，例如以往的研究对于不同遗传算法都必须重新设计硬件系 统，即遗传算法硬件平台的通用性较差，这就给硬件实现遗传算法的实际应用带来不小 的困难。 如何系统化和模块化地设计硬件；如何设计对于不同遗传算法具有一定通用性的系 1 绪论硕士论文 统平台；如何实现数字系统模块的有效划分；如何实现遗传算子模块化设计和标准化接 口等，以及流水线操作和并行化等等都是亟待解决的问题。 综上所述，如果能够将遗传算法的硬件系统设计成可配置的s o c 片上系统模式、 构建出可以支持遗传算子运算的系统框架、标准化每个模块的输入输出和模块接口，同 时预先设计好常用的遗传算子模块。那么对于不同的问题，只需要调用相应的遗传算法 模块，即可完成整个遗传算法的f p g a 实现。这样既解决了全硬件模式的局限性，也不 用考虑硬件和电脑间的通讯、时序匹配、接口匹配等问题。而且这种嵌入式的设计也使 得系统的可维护性，可复用性等方面的性能有所提高。 此外，在硬件设计上融入并行遗传算法的模型思想，如粗粒度模型等，也是提高遗 传算法运算速度的一种方法。 1 3 主要研究内容 本文的主要研究内容：以f p g a 硬件系统为平台，以v e r i l o g h d l 语言为工具，在 软件仿真和i s e 数字系统开发集成平台上，针对经典遗传算法问题，如函数极值、组合 优化问题等，进行f p g a 数字系统的设计，完成硬件系统的架构、模块设计、时序设计、 仿真及实现；建立遗传算法各模块的接口标准；实现遗传算法各模块的功能，进行仿真 验证，最终使用硬件化的遗传算法解决优化问题。 论文的主要内容： 第一章：介绍了遗传算法的研究现状及当前存在的问题，重点介绍了基于f p g a 遗 传算法硬件实现的优点和工程意义。 第二章：介绍了遗传算法的基本原理和本文使用的硬件平台，详细介绍了遗传算法 的关键算子和硬件系统的开发流程，并且对常见问题的遗传算法模型和遗传算法参数的 自适应调节进行了简要阐述。 第三章：对硬件系统进行了总体设计。针对遗传算法算子和编码多变性的具体情况， 详细阐述了硬件系统的总体设计方案，将系统划分为系统功能模块和遗传算法功能模块 两个部分，并且标准化了模块接口，提高了遗传算法功能模块的可重用性和可移植性。 第四章：对硬件系统的每个子模块进行了设计。详细设计、验证、完成了遗传算子 模块和系统模块，其中遗传算子模块包括：多种交叉算子模块、选择算子模块和变异算 子模块等；系统模块包括：伪随机数模块、随机数接口模块和存储器接口等。 第五章：对于函数极值和组合规划这两类经典遗传算法问题分别进行软件实现和 f p g a 硬件实现，总结实验数据、并对实验结果作出分析对比。 最后，总结了论文工作，并对今后的研究作出展望。 4 硕+ 论文基于f p g a 的遗传算法的硬件实现技术研究 2 遗传算法及硬件平台简介 2 1 遗传算法简介 遗传算法( g e n e r a t i ca l g o r i t h m s ，g a ) 最早由j h o l l a n d 教授在1 9 7 5 年的著作自然系 统和人工系统的配适( a d a p t m i o ni nn a t u r a la n da r i t i c i a ls y s t e m s ) d ? 提出，其主要思想 是模拟自然界生物进化过程和机制，把自然选择的最优结果和问题的最优解相对应，模 拟达尔文的自然进化论和孟德尔的遗传变异理论。 遗传算法本质上是一类搜索算法，其主要特点是利用群体搜索策略和群体中个体之 间的信息交换解决问题。因此，搜索不依赖于梯度信息，适应范围较一般的优化算法更 广+ 。有关理论研究证明，种群中较优的个体数会以指数增长【25 l 。遗传算法作为一种非确 定性的拟自然随机优化算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等 显著特点得到广泛应用。它尤其适用于组合优化、规划设计和最优值求解等领域，在复 杂系统优化、机器学习、系统识别、故障诊断、分类系统、控制器设计、神经网络设计、 自适应滤波器设计等方面已经有很好的应用【”巧3 1 。 2 1 1 遗传算法的生物学基础 表2 1 给出了一些生物学和遗传学的基本概念和术语，这对于深入理解遗传算法是 很有必要的： 表2 1生物学和遗传学的基本概念和术语表 染色体( c h r o m o s o m e ) 细胞内具有遗传性质的物体，遗传物质的主要载体，由基因组成 基因( g e n e ) 基因型( g e n o t y p e ) 表现型( p h e n o t y p e ) 个体( i n d i v i d u a l ) 种群( p o p u l a t i o n ) 进化( e v o l u t i o n ) 遗传的物质基础，分子上具有遗传信息的特定核苷酸序列的总称 是指生物的遗传型，即控制生物性状的基因组合类型 具有特定基因型的个体，所表现出来的外部性状特征的总和 带有特定染色体特征的实体 一类个体的集合，其中所含个体的个数又称为种群规模 生物不断改变表现型以适应环境的过程 生物对于自然环境的适应能力宏观上表现为达尔文的自然进化论所描述的优胜劣 汰。而从生物进化的本质来讲，是因为繁衍后代时基因变异和重组带来子代表现型的改 变，即孟德尔的遗传变异理论。遗传算法就是受此启发而诞生的i l p 】，把自然界优胜劣 汰的机制抽象为评价函数，把个体抽象为待解决问题的参数，把基因抽象为编码，而父 代到子代的遗传、变异被抽象为相应的进化操作，在进化计算收敛后所得到的最优个体 即为问题的最优解。 遗传算法将以上过程抽象为以下几个操作算子： 2 遗传算法及硬件平台简介 硕士论文 1 ) 编码( c o d i n g ) ：将待解决问题的有关参数映射成算法搜索空间中的个体基因。 2 ) 适应度( f i t n e s s ) ：将基因按照特定适应度函数评价出相应的适应度值。 3 ) 选择( s e l e c t ) ：按照适应度值的大小，按一定机制选择出合适的个体。 4 ) 交叉( c r o s s o v e r ) ：将两个父代个体的基因按照一定规律重组成新的子代个体。 5 ) 变异( m u t a t i o n ) ：在交叉中以很小的概率改变基因，使子代具有新的表现型。 6 ) 解码( d e c o d i n g ) ：将个体基因映射回待解决问题的有关参数。 遗传算法的基本步骤就是：将问题的定义域经过编码映射成个体空间，即将每个自 变量映射成带有染色体特征的个体，其外在的表现型为适应度函数解算的数值。遗传算 法从问题可能的某些解集( 初代种群) 开始搜索，按照选择、交叉、变异的方式产生新 的个体，按照适应度的评价优胜劣汰，逐代进化产生越来越好的个体( 近似最优解) 。 整个过程就像自然界中的种群一样越来越适应环境，末代种群中的最优个体经过解码后 可以作为问题的近似最优解。 2 1 2 遗传算法的基本原理 遗传算法的操作算子本身具有随机搜索的特质，而评价体系又有着优化机制，数学 原理方面可由积木块假谢5 4 】和模式定理 1 1 加以分析讨论，此外m a r k o v 链也是分析遗传 算法的有效工具之一。相关研究表明对于特定问题，在保留当前最优个体的情况下，遗 传算法可依概率l 收敛到全局最优解f 5 9 1 。 2 1 2 1 模式定理 模式( s c h e m a ) 1 1 是描述一个字符串或者数列的某些位置上出现的相似性。例如，二 进制字符集合 0 ，1 所组成的字符串，我们可以定义集合 o ，1 ，零 ，其中枣表示无关符，并 且由此集合所产生的能描述具有某些相似性的0 ，1 字符串称作模式。 具体到遗传算法来说，模式可以描述基因串中某些特征位相同的结构。为了定量描 述模式，我们引入两个参数：模式阶( s c h e m ao r d e r ) 和模式距( d e f i n i n gl e n g t h ) ： 1 ) 模式阶：模式h 中确定位置的个数。 2 ) 模式距：模式h 中第一个确定位置和最后一个确定位置之间的距离。 模式定理【l 】：在遗传算子选择、交叉和变异的作用下，具有低阶、短定义距并且平 均适应度高于群体平均适应度的模式在子代中将以指数增长。 模式定理是保证遗传算法正确性的基本理论，它保证了较优模式( 较优的基因片段) 的数目呈指数增长，为遗传算法提供了数学基础。 2 1 2 2 积木块假设 积木块( b u i l d i n gb l o c k ) 被定义为：在模式定理中所指的具有低阶、短定义距以及高 适应度的模式。 积木块假设( b u i l d i n gb l o c kh y p o t h e s i s ) 7 ，5 4 】：遗传算法通过短定义距、低阶以及高于 6 硕士论文基于f p g a 的遗传算法的硬件实现技术研究 平均适应度的模式( 积木块) ，在遗传操作作用下相互结合，最终接近全局最优解。 虽然这只是一个假设，但是有关学者的大量实践表明积木块假设在许多领域获得了 成功1 5 5 螂】，因此适用于常见的遗传算法优化问题。 2 2 遗传算法基本框图 遗传算法的基本框图如图2 1 所示，将问题的解空间经过编码映射到遗传空间，经 过个体的选择、交叉和变异运算，不断地差生新的个体，经过适应度评价后优胜劣汰， 使得种群不断进化，最终搜索到最优解。 i 一i 赢百ji 一磊i j 2 3 遗传算法的实现 图2 1 遗传算法基本框图 遗传算法的性能主要由以下几点决定：编码模式、解码模式、初始种群的生成方法、 评价函数的设计、遗传算子的设计、算法的终止条件以及算法参数的设置。 2 3 1 编码方式 把一个问题的可行解从其解空间转化到遗传算法所能处理的搜索空间的转化方法 口q 做编码。编码方式应具有如下性质1 5 】：完备性( c o m p l e t e n e s s ) 、封闭性( c l o s u r e ) 、健全 性( s o u n d n e s s ) 和非冗余性( n o n r e d u n d a n c y ) 。 遗传算法的编码方式有很多种，二进制编码方式是最常用的编码方式之一，最早由 h o l l a n d 提出【。但是二进制编码的遗传算法进行数值优化时，存在连续到离散的映射 误差、精度不高，最优解附近搜索较慢等缺点。虽然提高个体编码串长度可以提高精度， 7 2 遗传算法及硬件平台简介硕士论文 但是会使遗传算法的搜索空间增加，从而使得搜索变得异常缓慢。 后来的学者针对这些缺点提出了许多改进意见 5 , 1 4 , 5 9 , 6 0 】，例如：使用g r a y 码可以增 加遗传算法的局部搜索能力，对于一些多维、高精度要求的连续函数优化问题，可以使 用浮点数编码模式，个体编码长度等于决策变量的个数。这样一方面可以增加精度，一 方面有效地限制了搜索空间的增加。此外，还有符号编码、二倍体编码、排列编码、混 合编码和d n a 编码等编码方式。但是，这些编码方式在基因交叉和变异时都会产生额 外的运算量。 2 3 2 适应度评价函数 遗传算法不依赖原问题的梯度、导数等外部信息，仅以适应度函数( f i t n e s sf u n c t i o n ) 为唯一的依据，利用种群中个体的适应度来进行选择和搜索，不受目标函数连续可微的 限制。因此，适应度函数的设计就显得尤为重要，直接影响到遗传算法的收敛速度以及 收敛效果。适应度函数由目标函数经过一定变换得到，变换后的适应度函数需要满足选 择算子的要求，例如对于轮盘赌选择方式，要求个体适应度均为正数等。一般的情况下， 适应度函数的设计应满足以下几点【5 ，6 ，1 4 】：连续、单值、非负；一致性，能反映解的优劣 性；计算量少。 2 3 3 遗传算子 2 3 3 1 选择算子 自然进化中，对生存环境适应较好的个体有较高的机会生存下来，从而可以将本身 的基因遗传到下一代。选择算子即体现了这种思想：适应度较高个体的基因遗传到下一 代的概率更大，通过某种机制从父代种群选择出较好的个体产生子代种群，实现优胜劣 汰。 选择算子是遗传算法中保证种群择优进化的关键，不同的选择机制会带来不同的竞 争压力。过于严格的选择机制会导致收敛过快而陷入局部最优解；反之，过于宽松的选 择机制则会导致算法运行时间过长。 如下是几种常用的选择算子【6 ，8 】： 1 ) 轮盘赌选择算子( r o u l e t t ew h e e l ) 这是一种原理和实现都较为容易，选择效果尚佳的选择算子，因而应用比较广泛。 其方法是根据个体相对种群的适应度： n 。- ，1 p i = f f i t i ( 2 、) i = 0 把一个圆盘分成份，每个个体所对应的圆心角为2 r e p ，进行选择时产生【o ， 1 的随机数r 。，获得圆心角2 x r 。将此作为指针，选择出相应个体。厅卉为个体f 的适应 硕士论文基于f p g a 的遗传算法的硬件实现技术研究 度，k 为所选中个体编号。明显的，个体的适应度越大，被选中的几率就越大，其基因 被遗传到下一代的概率就越大。 2 ) 锦标赛选择算子( t o u r n a m e n t ) 锦标赛选择算子的方法是：随机地从父代种群中选出一定数目的个体，然后将评价 度最优的个体选出作为代交叉个体。锦标赛算子的参数为竞赛规模丁，丁越大，收敛速 度越快，反之越慢。 3 ) 精英保存算子( e l i t i s tm o d e l ) 将本代里的最优个体保存到下一代，而不进行交叉，一般用父代中的最优个体替换 子代中的最差个体实现。该算子一般作为辅助算子，在运算过程的中后期加速算法的收 敛速度。 此外，还有无回放式随机采样、稳态复制、均匀排序等选择算子，具体的选择算子 应根据具体问题具体选择，亦可以将不同的选择算子综合使用。 2 3 3 2 交叉算子 交叉算子是遗传算法实现的主要算子，其作用是产生新的个体，实现遗传空间地搜 索，交叉算子是遗传算法区别于其他优化算法的重要特征。但是必须注意的是，在产生 新的个体时必须尽量降低对有效模式的破坏概率。同时，采用不同编码模式能进行的交 叉操作不一样，故可以选择的交叉算子类型也不一样。经典的交叉算子【l ，】有单点交叉， 多点交叉，均匀交叉等。 1 ) 单点交叉 单点交叉是最基本的交叉方式，根据0 到基因长度之间的随机数k ，以概率p c 将k 为界交换基因片段产生新的个体，如图2 2 。 n d a = 0 0 0 0 00 0 0 c r o s s n e w l n d a = 0 0 0 0 011 1 i n d b ：1 l11 1f111 叫n e w l n d b ：川l1j0 0 0 图2 2 单点交叉示意图 2 ) 多点交叉 多点交叉是随机产生若干对交叉点，将交叉点之间的基因片段进行交换，以概率 只产生新的个体。其中两点交叉是常用的一个特例。 3 ) 部分匹配交叉算子( p m x ，p a r t i a l l ym a t c h e dc r o s s o v e r ) 该算子最早被设计用于操作搜索空间与编码的交叉空间不相等的情况【6 1 1 。例如：旅 行商问题( t s p ) 。此类问题的特点是问题搜索空间比编码空间小很多，如果按照基本算 子进行搜索，必然造成计算量的浪费和算法效率低下。有的学者提出罚函数的概念，但 是有关研究表明【6 l 】：这种方法的效率是很低的，因为它将问题的搜索空间从扩展到 u u 。 9 2 遗传算法及硬件平台简介硕士论文 一种行之有效的解决方案就是改变交叉算子，使其不产生这种不合法的个体，p m x 就是其中的一种方法。p m x 算子的基本思路是：保持搜索空间不变的情况下，尽量保 存交叉部分的基因序列，这样可以尽可能的保存适应度高的积木块。一些研究也证明该 方法比使用罚函数的方法更有效。 此外，除了上述交叉模式之外，还有均匀交叉、顺序交叉、周期交叉、算数交叉和 循环交叉等交叉算子。 2 3 3 3 变异算子 变异算子是除了交叉算子之外产生新个体的另一种方式。当交叉算子产生的新个体 比父代种群的适应度低而又未找到最优解的时候，我们称这种情况为早熟收敛，其根本 原因是在种群的初始和进化过程中产生了基因缺失 1 , 7 , 1 5 】，使用变异算子可以克服这种情 况。 1 、基本位变异算子 对个体的基因随机地选出一个或者几个基因座的基因以概率尸卅做出改变，若取一 位则称为单点变异，若多位则称为多点变异。 2 ) 交换变异算子 对于个体基因的基因随机选择某两个基因座，将其基因以概率己互换，交换变异 过程可以由该算子可以重复一次或多次操作组成。 3 ) 逆转变异算子 对个体的基因随机地选出一对基因座当成逆转点，将逆转点之间的基因以概率p 卅 逆向排列。如图2 3 。 i n d = 1 01 0 0 1 0 il 型竺：与n e w l n d = 1 00 1 0 0 1 il 图2 3 逆转变异示意图 逆转算子在一些排列组合问题，比如旅行商问题中，有着如下的特点：逆转点之间 的基因片段的适应度不随变异而改变，即路径a b c d 和路径d c b a 的长度是一样的， 也就是说这种变异对于该类问题可以有效地保存积木块的结构，而且起到了重新排序的 作用。有关研究也表吲5 】此变异方式在求解组合规划问题中有着良好的效果。 4 ) 自适应变异算子 自适应变异算子的主要思想是将遗传、变异的概率从固定的变为可调的，此概率和 遗传算的运算进度或者群体的组成情况有关【1 4 】：在运算的初期可以加大变异的概率以保 持种群的多样性，而在运算的末期减少变异概率以加速收敛；或者在群体中大多数个体 都己经相似的情况下增加变异概率以保持种群的多样性，在群体中大多数个体相差很大 的情况下减少变异概率以提高收敛速度等。也有的学者将模拟退火算法的思想融合到自 适应变异算子的设计中【6 2 】。 l o 硕士论文 基于f p g a 的遗传算法的硬件实现技术研究 2 3 4 种群的初始化 种群初始化方式主要由编码方式决定，对于函数极值问题和组合优化问题，编码方 式不尽相同，主要有以下两种初始化方式： 1 ) 随机二进制编码初始化，此方法主要针对使用二进制编码解决函数最优值的问 题，其特点是编码空间和搜索空间大小相同，故产生初始个体的方法比较简单， 产生和基因编码长度相同的二进制序列即可。 2 ) 随机符号编码初始化，此方法主要针对使用符号编码解决规划问题，例如t s p 问题，其特点是编码空间和搜索空间不等，使用随机的二进制序列产生的初始个 体可能是不合法的个体，一个解决的方法就是由一种或几种固定的合法个体经过 合法的变异，例如交换变异，以产生初始种群。 2 4 遗传算法运行参数选择 遗传算法中需要选择的参数主要有串长三，群体大小，交换概率尸c 以及变异概率 厶等，这些参数对g a 性能影响很大。除了使用固定参数外，很多学者也进了大量研 究 1 4 , 6 3 】，设计了很多其他的变参数运行模式，取得了良好的成果。总的来说，遗传算法 的运行参数选择分为两大类1 5 , 1 4 】：确定性调节和自适应调节。 2 4 1 确定性的参数调节 带有计划性的、策略性的参数调节成为确定性的参数调节，其特点是参数的改变机 制是固定的，调节具有明确的目的性，简单的一个实现就是变异概率随着遗传代数的增 加而逐渐减少【7 5 】： 仃 己= 一后丢型 ( 2 2 ) u l i l a x 其中，p 加，为初始变异概率，k 是改变率，g 驯为当前运算代数，g 一为总代数， 若p 加, - - 0 8 ，k = 0 7 则变异概率p 垅就从开始的o 8 到结束时的0 1 。这样变异概率p m 的 改变可以保证算法运算的早期不会早熟收敛，随着迭代次数的增加砌逐渐降低以加速 收敛，以保证算法的收敛性。当然，还可以使用其他诸如指数和反比例函数的形式来实 现这一机制。 确定性调节是指在遗传算法运行前将主要参数设定完毕，按照一定规律改变( 一般 是随着进化代数的变化而变化) ，也不从种群中获得反馈信息，有点是参数调节的设计 和实现简单。 2 4 2 自适应的参数调节 从进化过程中获得信息以形成某种形式的反馈，并用来确定参数调整的大小和方向 2 遗传算法及硬件平台简介 硕士论文 的参数调整策略称为自适应的参数调节。由于算法计算过程中各种状态变化比较复杂， 所以这种方法到目前为止成功的机制并不多，成功的代表案例是r e c h e n b e r g 的1 5 策略， 用于修改变异概率和步长， r e c h e n b e r g 认为【5 】：在所有变异中，成功的变异占总变异 数的比例应为1 5 ，如果结果大于1 5 则说明种群中的优化个体不多，应增加变异概率 和变异步长。反之，则减少。此外，w h i t e l y 1 4 】也提出了厶与父代个体的相似程度成反 比的自适应策略。 自适应调节的基本思想是根据运行状态和种群信息改变各种参数的选取，包括种群 大小、变异概率和交叉概率。如此一来，参数调节本身就是一个优化算法，甚至参数本 身的调节也可以用遗传算法实现，这样自适应设计参数的遗传算法稳定性、局部搜索能 力和通用性等都将得到提高，但是优化参数的算法本身的也会增加遗传算法的复杂度也 会增加降低搜索效率。 总的来说，确定型参数调节实现比较简单，性价比较高，因而应用比较广泛；而自 适应调节性能虽然好，但是调节机制较为复杂，如何寻找有效的自适应调节机制也是遗 传算法一个有前景的研究方向。 2 5 小生境与多目标优化 自然界中，物以类聚是一种常见的现象，生物总是倾向和自己的同类生活在一起， 因为这些个体有着和自己相似的特征和性状，在生物上把这种特定环境的自组织现象叫 做小生境( n i c h e ) t 5 1 ，而有共同性状的组织成为物种。一些学者在遗传算法中引进y d , 生 境技术，以下是几种小生境的实现机n - 1 ) 预选机制【7 2 1 ：只有子代个体的适应度超过父代个体时，才会被替换。因为这种方 法替换的是和子代本身相似的父代个体，因而该方法可以较好的维持群体的分布 特性。 2 ) 排挤机制【7 3 】：设定排挤因子c f ，在产生新的个体后，在种群中随机选出一组个 体，数目为1 c f 。将新生个体替