（微电子学与固体电子学专业论文）基于fpga的soc设计方法实现进化硬件的研究.pdf

基于f p g a 的s o c 设计方法实现进化硬件的研究 摘要 进化硬件是基于进化算法改变自身结构与功能的硬件电路。它结合了可编 程器件、人工智能、容错机制以及自动控制系统，能够依据与外部环境的相互 作用，自主、动态的改变自身结构和行为。具有上述特点的进化硬件，不仅可 以实现复杂电路的自动设计从而获得新颖、优化的电路结构，更是实现具有自 我修复功能系统的有效途径。 进化硬件可以概括为进化算法与可编程器件的融合，因此对于进化硬件的 研究应包含进化算法的实现以及对可编程器件的编码与配置，本文分别对这两 部分进行了研究，并利用基于f p g a 的s o c 设计方法实现了相应的设计。 本文首先介绍了进化硬件的概念，并做出分类和说明。随后概述了遗传算 法以及f p g a 的结构及重构原理。在此基础上，利用x i l i n x 的集成开发环境i s e 以及嵌入式开发套件e d k ，实现了基于f p g a 的s o c 方法的进化硬件设计。 最后，采用c h i p s e o p e 软件对其内部功能进行验证，同时对进化过程中的相关 数据进行了分析。结果表明，采用基于f p g a 的s o c 设计方法对进化硬件的研 究取得了预期效果，具有一定的可行性及研究价值。 关键字：进化硬件，现场可编程门阵列，片上系统，遗传算法 t h er e s e a r c ho ft h ei m p l e m e n to fe v o l v a b l eh a r d w a r eu s i n g t h es o c d e s i g nf l o wo naf p g a 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 san e wf i e l db a s e do nt h ee v o l u t i o n a r ya l g o r i t h m s ( e a ) t oc r e a t ec i r c u i t s i ti sc o m p r i s e do fr e c o n f i g u r a b l eh a r d w a r e ，a r t i f i c i a l i n t e l l i g e n c e ，f a u l tt o l e r a n c ea n da u t o n o m o u ss y s t e m s e v o l v a b l eh a r d w a r er e f e r st o t h eh a r d w a r et h a tc a nc h a n g ei t sa r c h i t e c t u r ea n db e h a v i o rd y n a m i c a l l ya n d a u t o n o m o u s l yb yi n t e r a c t i n gw i t hi t se n v i r o n m e n t w i t ht h e s ec h a r a c t e r i s t i c s ，t h e e v o l v a b l eh a r d w a r en o to n l yc a nr e a l i z et h ea u t o m a t i cd e s i g no fc o m p l e xc i r c u i t s ， o p t i m i z ec i r c u i ts t r u c t u r e ，b u ta l s oa c h i e v es e l f - r e p a i rf u n c t i o ni na ne f f e c t i v ew a y e h wc a nb em e r g e da st h ei n t e g r a t i o no fe v o l u t i o n a r ya l g o r i t h m sa n dt h e p r o g r a m m a b l ed e v i c e s ；a sar e s u l tt h es t u d yo fi m p l e m e n t a t i o ne h w s h o u l di n c l u d e t h ea l g o r i t h mr e a l i z a t i o na sw e l la st h ec o n f i g u r a t i o no fp r o g r a m m a b l ed e v i c e s t h i st h e s i sf o c u s e so nt h er e s e a r c ho ft h e s ep a r t s ，a n di m p l e m e n t st h e mu s i n gt h e s o c d e s i g nm e t h o do naf p g a f i r s t l y , t h ec o n e e p to fe h w i si n t r o d u c e di n t h i st h e s i s ，a sw e l la ss o m e c l a s s i f i c a t i o n sa n dd e s c r i p t i o n s t h e na no v e r v i e wo ft h eg e n e t i ca l g o r i t h m sa n dt h e s t r u c t u r eo ft h er e c o n f i g u r a b l ef p g aa r eg i v e n o nt h e s eb a s e saf p g a - b a s e ds o c e h w d e s i g nu s i n go ft h ei s ea n dt h ee d kd e v e l o pk i ts o f t w a r ei sm a d e f i n a l l y , t h ei n t e r n a ll o g i cf u n c t i o ni sv a l i d a t e db yc h i p s c o p e ，a tt h es a m et i m et h er e l a t e d d a t ai sa l s oa n a l y z e d t h er e s u l ts h o w st h a tt h ef p g a b a s e ds o cd e s i g nm e t h o do f e h w i m p l e m e n ta c c o m p l i s h e st h ep u r p o s ed e s i r e d ，i sf e a s i b l ea n do b t a i n st h ev a l u e o fr e s e a r c h k e yw o r d s ：e v o l v a b l eh a r d w a r e ，f p g a ，s o c ，g e n e t i ca l g o r i t h m 插图清单 图1 - 1 进化硬件在人造假肢上的应用2 图1 - 2 基于进化硬件技术的k h e p e r a 机器人3 图2 - 1 遗传算法的迭代过程。8 图2 - 2 交叉操作示意图1 1 图2 - 3 变异操作示意图1 2 图2 - 4 硬件进化循环过程1 3 图3 - 1s p a r t a n 3 ef p g a 结构图。1 5 图3 - 2c l b 结构示意图1 6 图3 - 3slic e 结构示意图1 6 图3 - 4io b 结构示意图1 7 图3 - 5f p g a 开发流程1 8 图3 - 6f p g a 的配置过程1 8 图3 - 7 虚拟可重构电路示意图2 0 图3 8 可编程单元p e 内部结构示意图2 l 图3 9p e 阵列示意图2 1 图3 - 1 0 虚拟可重构的染色体基因型2 1 图4 - 1s p a r t a n 3 e 开发板2 3 图4 2 系统硬件架构2 4 图4 - 3m i c r o b l a z e 内部架构示意图2 5 图4 - 4b r a m 及l m b 总线的连接2 6 图4 - 5m i c r o b l a z e 及l b m 、x c l 和o p b 总线的连接2 6 图4 - 6o p b 设备i p i f 接口特征2 7 图4 - 7o p b 可进化模块的i s e 文件结构。2 8 图4 8o p b 可进化模2 8 图4 - 9o p b 从接口读写时序2 9 图4 - 1 0o p b 可进化模块r t l 结构及t m r 模块3 0 图4 - 11t m r 模块r t l 结构及c e l1 a r r a y 模块3 1 图4 - 1 2 可重构阵列r t l 结构3 2 图4 - 1 3p e 单元染色体配置仿真3 3 图4 - 1 4c e l l a r r a y 染色体配置仿真3 3 图5 - 1s d k 工程文件窗口图5 1 4 1 图5 - 2 主程序运行流程4 1 图5 - 3 字符l c d 的通信时序图5 0 图5 - 4 字符l c d 通信方式5 2 图6 1c h i p s c o p ev i o 界面截图5 4 图6 2v 1 0 对错误的反应截图5 5 图6 3 显示屏的演示5 5 图6 - 4 进化过程中适应度变化过程5 6 表格清单 表4 1p e 可编程单元的染色体编码3 3 表4 2 地址分配表3 9 表4 3 微处理器资源占用表3 9 表4 4o p b 可重构模块资源占用表3 9 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金胆王些太堂 或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了 明确的说明并表示谢意。 学位论文作者签名： 夜彩 签字日期：二甲年争月2 f 0 e j 学位论文版权使用授权书 本学位论文作者完全了解金胆王些态堂有关保留、使用学位论文的规定，有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授 权金e 曼三些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：丧冬充 签字日期力1 年争月矽日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师躲嗣哥 签字日期：多7 年华, e j 幻日 电话： 邮编： 致谢 首先感谢我的导师解光军教授! 本论文是在导师悉心指导下完成的，他治 学严谨，学识渊博，在论文的选题、资料查询、开题、研究和撰写的每一个环 节，都给了我很大帮助。衷心感谢解教授对我的培养和教诲。 感谢伴随我度过研究生学习生涯并给予我帮助的同学们! 感谢我的家人和亲友! 第一章绪论 随着集成电路制造业的不断发展，电路系统的结构日益复杂，增加了对系 统稳定性及可靠性的要求，同时随着工艺尺寸的不断减小，常规的设计方法因 严重依赖设计规则、先验知识和人工干预而变得效率低下，影响了电路的设计 能力。与此同时对于耐温特性以及容错能力的需求也在不断提高，例如飞行器、 深海探测任务等难以实施人工控制的特殊环境中的电子系统更是如此。基于可 编程器件的进化硬件因具有自组织、自适应、自我修复的能力，从而成为解决 上述问题的有效途径i lj 。 1 1 进化硬件的特性 进化硬件( e v o l v a b l eh a r d w a r e ) e 1 】【2 】 3 1 或称演化硬件是进化计算( e v o l u t i o n a r y c o m p u t a t i o n ) 和可编程器件( p r o g r a m m a b l ed e v i c e ) 的一体化整合，它具有通过自 动重构硬件结构来实现提升性能以及改变电路功能的特性。因为常规的硬件在 设计制造后其结构与功能很难再被改变，而进化硬件具有自动重新配置其结构 的能力，所以从根本上不同于常规硬件。尽管一些可编程器件，诸如p l d ( p r o g r a m m a b l el o g i cd e v i c e ) 和f p g a ( f i e l dp r o g r a m m a b l eg a t ea r r a y ) 等容许在 制造后进行一些功能上的变化，然而这些结构变化的执行过程离不开人为的干 预和介入，即不能自动的进行，而进化算法的引入使得进化硬件具有自动改变 其结构与功能的能力。 1 2 进化硬件的研究与应用 对于进化硬件最早的研究可以追溯到1 9 9 2 年由t e t s u y ah i g u c h i 以及1 9 9 3 年由d a n i e lm a n g e 分别所从事的研究，t e t s u y ah i g u c h i 致力于使用遗传算法重 新配置硬件结构实现硬件进化 4 1 【5 】，而d a n i e lm a n g e 致力于将仿生机制应用于 常规硬件实现自我复制和自我修复。 继早期的将人工智能和人工生命应用于硬件，实现自动进化电路结构后， 近期对于进化硬件的研究主要着重于半导体工程学和机械工程学领域，例如： 大规模集成电路量产前的修整、耐温特性的改善、大规模集成电路的自我检测 和自我修复、模拟电路的设计、微型机电系统( m i c r oe l e c t r om e c h a n i c a ls y s t e m ) 的微调、精密光学系统的自适应控制、空间任务的进化天线( e v o l v a b l ea n t e n n a ) 等。 关于进化硬件研究活动的报道主要集中在两个国际会议上，其一是国际演 化系统会议( i c e s ) ，自1 9 9 6 年起分别在日本、瑞士、英国、挪威、西班牙以及 中国等国家举行。另一个是自19 9 9 年起每年在美国举办的国家宇航局( n a s a ) 进化硬件会议。下面将对目前国际上的进化硬件研究作以分类和概述，随着研 究及应用的不断深入，本文只列举了其中的一部分为例。 12 1 数字进化硬件 在此类别中根多新颖的可进化数字电路技术被应用：t o r r e s e n 提出新的模式 分类进化硬件结构，并应用于人造假肢的控制6 州；g a r v i e 等人展示了具有内 建自测试功能的一位加法器以及二位乘法器的进化数字电路，表明进化硬件比 人工设计在资源占用上具有优越性【8 】；k o r e n e k 等学者发明了基于普通f p g a 的相对大型排序网络的特殊可进化结构。同时也有许多新颖而又实际性的应用： 例如应用于职层( b z - l e 州) 图像无损压缩技术以及时钟时序调整技术的进化硬件 1 ；m a r t i n c k 等人实现了将可进化的图像过滤器完全实现于f p g a 上此系统 可以在得到原图片和损坏的图片后的数秒内进化得到图像过滤器【”l ；s m i t h 等 将基于遗传算法的进化硬件应用于非线性的图像处理操作，并最终实现此设计。 数字进化硬件也被应用于机器人的控制器上【1 1 1 ：k i m 等人试验的双足机器人展 现了基于遗传算法的可靠性和流畅性【1 2 】；i s l a m 等使用一种基于两阶段渐进进 化系统的方法发明了可应用于高复杂任务的自控机器人【i ”；h a r d i n g 等人讨论 了实时机器人控制器的稳定性和重构特性，对于涉及编程和进化的其他物理领 域相当重要“。 如图l 一1 是进化硬件芯片及其在人造假肢上的运用芯片中包含一个遗传 算法e h w 硬核、c p u 核( n e cv 3 0 ) 、a d 变换器，以及f i f o 核，其中e h w 核中含有遗传算法( g a ) 的硬核、可重构硬件模块( p l a ) 以及控制寄存器模块。 图卜1 进化硬件在人造假肢上的应用 图1 - 2 为采用内部( i n t r i n s i c ) 进化硬件技术，使用x i l i n x v i r t e x 系列f p g a 实现的红外近距感应器k h e p e r a 机器人及其躲避障碍物的轨迹【2 】； 霭 图卜2 基于进化硬件技术的k h e p e r a 机器人 在仿生机器领域也有许多研究，并且开始于进化硬件研究的初期；胚胎电 子( e m b r y o n i ce l e c t r o n i c s ) 是一个用于实现特殊数字计算机的工程项目，启发于 生物体的发育过程，具有多级容错功能；r e s t r c p o 等提出了具有自我复制 和自我修复能力的多细胞通用图灵机实现方法【l q ：p r o d a n 等设计了基于人造 d n a 细胞的胚胎机器【l9 】：s t a u f f e r 等生产了基于一系列微小的处理单元的有白 愈能力的审子计时器口0 】ib a r k e r 等提交了基于p o e t i c 系统的容错硬件的试验 结果“i j ；而m o t e n o 等人假设了p o e t i c 器件的结构，组建了主要的构成元素【”i ： g r o e n s t e d 等提出类似于内分泌系统的多处理器系统的软件模型，此系统能够对 任意的数据流进行处理口”；b r a d l e y 等分析了人体免疫系统的容错机制，展示 了此机制可以应用于硬件容错系统 2 “。 122 模拟进化硬件 模拟进化硬件是相对于数字进化硬件而言的新类别，而模拟进化硬件又分 为基于基因遗传算法的模拟电路以及使用遗传编程设计的电路。 f p t a ( f i e l dp r o g r a m m a b l et r a n s i s t o ra r r a y ) o w 口”是进化模拟电路实现的一 个可重构平台，许多基于遗传算法的模拟进化硬件研究都是基于f p t a 的。例 如z e b u l u m 等研究的可用于进行信号分离任务的被称为独立板级进化系统 ( s t a n d a l o n eb o a r d - l e v e le v o l v a b l es y s t e m ) 的模拟进化电路口7 j ：s e k a n i n a 等进化 出了仅使用4 个f p t a 一2 芯片单元的简单1 位和2 位可控的振荡器 2 8 1 ft r e f z e r 等使用f p t a 处理了综合可转移和可重利用操作的放大器口。一些进化模拟器 件的有效应用研究也在进行：k a s a i 等利用遗传算法在数据传输中实现了自适 应的波形控制，并展示了基于此控制器的自适应收发器t 3 0 i ；j d l o h n 等提出了 使用线形代表与简单展开技术的进化模拟电路，给出了使用此系统实现模拟滤 波问题的最初结果旧。遗传编程( g e n e t i cp r o g r a m m i n g ) 是遗传算法概念在计 算机编程领域的拓展，j rk o z a 等成功的使用遗传编程设计出了两波段交叉滤 波器，同时在运算放大器的频率特性优化上取得较好效果【3 3 1 。 1 2 3 机械硬件进化 使用进化算法来调整机械部件的工作被称为机械硬件的进化( m e c h a n i c a l h a r d w a r ee v o l u t i o n ) ，例如可进化的飞秒激光器、基于进化算法的m e m s 陀螺 仪微调以及基于遗传算法的自调整八木天线等。 1 2 4 国内的相关研究 国内对于智能计算及演化技术的研究发展较快，主要从事相关研究的有武 汉大学、西安电子科技大学、南京航空航天大学、深圳大学、军械工程学院、 西安微电子技术研究所以及中国地质大学等院校及单位3 4 】【3 5 】【3 6 】【3 7 1 。 这其中武汉大学从事的研究主要为：基于可进化硬件的f i r 数字滤波器设 计、基于组合逻辑电路的演化硬件设计、模拟电路在线演化平台、演化计算在 仿真和控制中的应用、演化平台的数字电路电路仿真方法、演化硬件设计的改 进演化程序、基于p f l c 的可演化模糊逻辑控制器的设计、实现演化硬件的软 硬件协同工作模式及用函数型可编程器件实现演化硬件等。 西安电子科技大学的研究主要为：基于典型结构的电路自适应进化设计新 方法、基于多目标自适应遗传算法的逻辑电路门级进化方法、基于函数级f p g a 原型的硬件内部进化、利用自适应遗传算法实现模拟电路自动设计以及演化硬 件及面向演化的v l s i 可重构体系结构的设计等。 南京航空航天大学的研究内容主要：变长染色体遗传算法在演化硬件中的 应用、采用主流f p g a 的数字电路在线生长进化方法、复杂数字电路多级在线 进化技术研究、基于f p t a 的模拟演化硬件研究、使用进化硬件的自适应形态 滤波器设计等。 深圳大学的研究文献为：关于遗传算法硬件化过程中适应度函数的研究、 模拟退火与遗传算法结合的数字f i r 滤波器硬件进化算法、一种改进的遗传算 法进化有限状态机、用于进化硬件的遗传算法的选择策略初探等。 军械工程学院的研究内容是：电路外部演化生成的软件模拟、基于f p g a 的l e d 控制器的演化实现、演化母板的构思、基于虚拟可重构电路的演化硬件、 基于演化母板的e h w 平台上电路的演化生成、基于演化母板的通用演化硬件 平台研究、基于演化硬件技术实现武器系统自修复的研究、可演化t m r 容错 表决电路的设计研究、内进化演化硬件平台的设计与实现、使用常规i c 的演化 硬件电路设计实例、以f p g a 和q u a r t u s 为基础平台的e h w 环境实现等。 中国地质大学所发表的相关文献有：基于演化的电路自动化设计、模糊逻 辑控制器的演化硬件实现、演化计算及其在深空探测应用可行性研究等。 4 1 3 基于f p g a 的s o c 设计方法实现进化硬件 s o c 片上系统是以应用为中心，以计算机技术为基础，并且软、硬件可剪 裁，适用于应用系统对功能、可靠性、成本、体积、功耗有严格要求的计算机 系统。片上系统一般由嵌入式微处理器、外围硬件设备、嵌入式操作系统以及 应用程序等四个部分组成。基于f p g a 的s o c 设计理念将f p g a 可编程的优点 带到了s o c 领域，其系统由嵌入式处理器内核、d s p 单元、大容量处理器、吉 比特收发器、混合逻辑、i p 以及原有的设计部分组成，而相应的f p g a 规模大 多在百万门以上，适用于诸多领域。 使用f p g a 设计实现s o c 的最大优势在于其定制性【3 8 】【3 9 】【4 们，相比传统的 嵌入式c p u ，f p g a 可以配置与添加外设的种类和数量，裁剪不需要的外设， 同时还可以根据实际需要修改外设的功能，甚至可以自主设计独特的外设。基 于f p g a 平台的融入，将s o c 逐步推向了新的实用领域。 使用基于f p g a 的s o c 系统的开发及设计流程来实现进化硬件，不仅可以 依靠嵌入式微处理器执行进化算法，可以使得在所实现的算法上具有极强的灵 活性与易修改性，而且能够利用f p g a 可自定义结构与功能分配其资源的特点， 以用于实现可进化部分的设计，因此具有一定的研究及实用价值。 1 4 本文的工作及内容安排 本文简要概述了进化硬件的发展过程，做了相应的归类，系统分析了遗传 算法及操作步骤，并针对进化硬件独立、实时进化的需要，在英国约克大学 ( u n i v e r s i t yo fy o r k ) a n d r e wg r e e n s t e d 博士所提供实验的基础上【4 1 1 ，使用 s p a r t a n 3 e 开发板进行了基于f p g a 嵌入式软核处理器m i c r o b l a z e 的可进化系 统的实验：首先在i s e 集成开发环境中构建了可以挂接于o p b ( o n c h i p p e r i p h e r a lb u s ) 总线的基于虚拟重构电路( v i r t u a lr e c o n f i g u r a b l ec i r c u i t ) 的可进 化i p 核；然后在x p s 中使用了x i l i n xm i c r o b l a z e 微处理器软核；添加了u a r t 通信接口i p 、输入输出控制接口以及液晶显示i p 等模块构建了此进化系统的 硬件部分；随后在s d k 中完成了系统软件的开发，实现了标准遗传算法及对上 述硬件的读写控制，在此基础上进行进化操作；最后对实验结果进行验证，并 对实验结果作出相应的数据分析，提出进步修改及实现方法。 本文中的整个设计采用基于x i l i n xf p g a 片上可编程系统( s o c ) 开发流程， 具有良好的硬件通用性及算法上的易修改性，从而为进化硬件的实现及应用提 供了新的设计思路和解决方案。 第一章，对进化硬件研究领域及现状的分析，给出本文研究内容的安排； 第二章，分析了遗传算法的操作及实现方法及其在进化硬件中的作用； 第三章，剖析了常规f p g a 的结构，解释了f p g a 的重构与虚拟可重构( v r c ) 的区别与实现方式； 第四章，构建了基于三模冗余( t m r ) 结构可进化的4 b i t 奇偶校验器，以此 为例叙述了基于i s e 及e d k 建立可进化系统的硬件设计方法； 第五章，叙述了该进化系统的软件设计，重点描述了对虚拟可重构模块的 读写及进化操作以及对基于g p i o 液晶显示器的控制； 第六章，给出了系统验证结果，并对其进行了分析和对比，提出了进一步 修改及实现的研究方向。 6 第二章遗传算法与进化硬件 具有自组织自修复能力的进化硬件实现的关键是进化算法的实现【4 z 】- 【4 9 1 ，进 化算法目前主要有遗传算法( g e n e t i ca l g o r i t h m ，g a ) 、遗传编程( g e n e t i c p r o g r a m m i n g ，g p ) 、进化策略( e v o l u t i o n a r ys t r a t e g y , e s ) 以及进化规划( e v o l u t i o n p r o g r a m m i n g ，e p ) 四大主要分支。这其中遗传算法随着其理论和方法不断地得 到改进和完善，现已成为一种较为成熟、高鲁棒和广泛适用的全局进化算法， 在进化硬件( e h w ) 领域被广泛应用。遗传算法是基于种群进化的优化算法，它 使用了仿生学的机制，诸如：变异、交叉、自然选择以及最优适应的原则，以 达到优化结果的目的。本章将首先详细的就遗传算法的基本迭代过程和操作方 法予以说明，后将适于进化硬件的遗传算法的作用予以讨论。 2 1 遗传算法的概念及理论概述 遗传算法【4 4 】【4 5 】是模仿自然界生物进化机制发展起来的随机全局搜索和优化 方法，借鉴了达尔文的进化论和孟德尔的遗传学说，其本质是一种高效、全局 搜索的方法，能在搜索过程中自动获取和积累有关搜索空间的知识，并自适应 地控制搜索过程以求得最优解。遗传算法操作使用适者生存原则，在潜在的解 决方案种群中逐次产生一个近似最优的方案。在遗传算法的每一代中，根据个 体在问题领域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选 择，产生一个新的近似解。这个过程导致种群中个体的进化，得到的新个体比 原个体具有更高的适应性。 遗传算法有效性的理论依据为模式定理和积木块假设。模式定理保证了较 优的模式( 遗传算法的较优解) 的样本呈指数级增长，从而满足了寻找最优解 的必要条件，即遗传算法存在着寻找到全局最优解的可能性。而积木块假设指 出，遗传算法具备寻找到全局最优解的能力，即具有低阶、短距、高平均适应 度的模式( 积木块) 在遗传算子的作用下，相互结合，能生成高阶、长距、高 平均适应度的模式，最终生成全局最优解。h o l l a n d 的模式定理通过计算有用相 似性，即模式( p a t t e r n ) ，奠定了遗传算法的数学基础。该定理是遗传算法的主 要定理，在定程度上解释了遗传算法的机理、数学特性以及很强的计算能力 等特点。 遗传算法与传统的优化算法不同，大多数古典的优化算法是基于一个单一 的量度函数( 评估函数) 的梯度或较高次统计，以产生一个确定性的试验解序 列。遗传算法不依赖于梯度信息，而是通过模拟自然进化过程来搜索最优解， 通过有组织的、随机的信息交换来重新组合适应性较高的解。 遗传算法提供了一种求解复杂系统优化问题的通用框架，不依赖于问题的 7 具体领域，具有较强的鲁棒性。广泛地被运用于函数优化、组合优化、生产调 度、自动控制、机器人学、图像处理、人工生命、遗传编程及机器学习等诸多 领域。 2 2 遗传算法的基本操作过程 生物的进化( e v o l u t i o n ) 过程主要是通过染色体之间的交叉和变异来完成的， 遗传算法基于对自然界中生物遗传与进化机理的模仿，个体或者当前近似解被 编码为由数字组成的串，即染色体( c h r o m o s o m e ) 。针对不同的问题，有许多不 同的染色体编码方法来表示问题的可行解，使得基因( g e n e ) 能在( 表现) 域决 策变量上被唯一地描述。遗传算法通过有组织的、然而是随机的信息交换，重 新组合那些适应性好的染色体编码。 遗传算法模拟了自然选择和遗传中发生的复制、交叉和变异等现象，从任 一初始种群( p o p u l a t i o n ) 出发，通过随机选择、交叉、和变异操作，产生一个适 应性更好的个体，使群体适应度上升，不断地重复迭代，从而进化到搜索空间 中的最优解。 使用上述遗传算法的主要运算过程如下所述： ( 1 ) 初始化：进化代数计数器t 置0 ，设置最大进化代数r ，随机生成m 个个 体作为初始群体尸( 0 ) ； ( 2 ) 适应度评估：计算群体p ( t ) 中各个个体的适应度； ( 3 ) 遗传操作：执行选择、交叉、变异运算，得到下一代群体e ( t + 1 ) ； ( 4 ) 终止条件判断：若t t ，则t t ，则以进化 过程中所得到的具有最大适应度的个体作为最优解输出；或者当适应度达到某 一指标后终止计算，输出最优解。 图2 1 示意了上述迭代过程： 图2 - 1 遗传算法的迭代过程 嗲回 2 2 1 编码和初始种群产生 编( c h r o m o s o m ec o d i n g ) f f z 遗传算法应用过程中的首要问题，是设计遗传 算法的关键步骤，除了决定个体染色体的排列形式外，还决定了从个体搜索空 间的基因变换到解空间的表现型的解码方法，且也影响到交叉、变异等遗传算 子的运算方法。 d ej o n g 曾提出了两条操作性强的实用编码原则( 编码规则) 【4 9 】：有意义积 木块编码原则，应使用能易于产生于所求问题相关且具有低阶、短定义长度模 式的编码方案；以及最小字符集编码原则，应使用能使问题得到自然表示或描 述的具有最小编码字符集的编码方案。编码方案可以分为三大类：二进制编码、 浮点数编码、符号编码。 其中二进制编码方法是遗传算法中常用的一种编码方案，其符号集为 o ，1 ) ， 由它构成的个体基因是一个二进制编码符号串，其长度与问题所要求解的精度 有关。因为其具有硬件及程序容易实现特点，因而在本文中被使用，其具体特 征为： 若某一参数的取值范围为 【厂曲，u 蚴 ，用长度为，的二进制编码符号来表示 该参数，则功能产生2 。种不同的编码。二进制编码的优点有：编码、解码操作 简单易行：交叉、变异等遗传操作便于实现；符合最小字符集编码原则；便于 利用模式定理对算法进行理论分析。 遗传操作是对众多个体同时进行的，称之为种群。在遗传算法处理流程中， 继编码设计后的任务是初始种群的设定，以此为起点逐代进化直到按某种进化 停止准则终止进化过程，并由此得到最后一代( 或种群) 。群体规模，z 影响遗传 优化的最终结果以及遗传算法的执行效率，初始种群中的各个基因可用均匀分 布的随机数来产生。 2 2 2 适应度评估 适应度( f i t n e s s ) 是衡量群体中各个个体在优化计算中有可能达到或接近于 以及有助于找到最优解的优良程度，度量个体适应度的函数即为适应度函数 ( f i t n e s sf u n c t i o n ) 。评价个体适应度的一般过程是： ( 1 ) 对个体编码串进行解码处理后，得到个体的表现型； ( 2 ) 由个体的表现型可计算出对应个体的目标函数值； ( 3 ) 根据最优化问题的类型，由目标函数值按一定的转换规则求出个体的适 应度。 个体的适应度是进行选择操作的重要依据，确定合适的适应度转换规则对 遗传算法性能有较大的影响，扩大最佳个体适应度与其他个体适应度之间的差 异程度可以提高个体间的竞争性。适应度函数的设计需要满足：单值、连续、 非负、最大化；反映对应解的优劣程度；计算量小以及通用性强。 2 2 3 遗传操作 遗传算法有三个基本操作：选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 以及变异 ( m u t a t i o n ) 。 9 2 2 3 1 选择操作 选择又称复制( r e p r o d u c t i o n ) ，是在种群中选择生命力强的个体产生新的种 群的过程。依据个体适应度值的大小选择，适应度高的个体被遗传到下一代群 体中的概率较大，使得群体中的适应度值不断接近最优解。选择操作建立在对 个体的适应度进行评价的基础上，其目的是避免有用遗传信息的丢失，提高全 局收敛性和计算效率。 常用的选择算子有： ( 1 ) 轮盘赌选择( r o u l e t t ew h e e ls e l e c t i o n ) ，又称比例选择( p r o p o r t i o n a lm o d e l ) 方法，是一种放回式随机采样方法，每个个体进入下一代的概率为其适应度值 与整体种群中个体适应度之和的比例，设群体大小为m ，个体f 的适应度为只， 则个体f 被选中的概率p b 为： | 坠 p ，= 鼻鼻 ( f = 1 ，2 ，m ) ，t = 1 ( 2 ) 最优保存策略( e l i t i s tm o d e l ) ，将当前种群中适应度最高的个体不参与交 叉和变异运算，而是直接复制到下一代群体，或者替换掉本代群体中经过交叉、 变异等遗传操作后所产生的适应度最低的个体。最优保存策略可视为选择操作 的一部分，保证迄今为止所得到的最优个体不会被破坏，是遗传算法收敛性的 一个重要保证条件。但同时使得某个局部最优个体不易被淘汰，影响算法的全 局搜索能力。 ( 3 ) 确定式采样选择( d e t e r m i n i s t i cs a m p l i n g ) ，按照一种确定的方式来进行操 作，首先计算群体中各个个体在下一代群体中的期望生存数目m ： 丝 m = m 。e f ( i = 1 , 2 ，m ) ， i = 1 用以的整数部分l n ，j 确定各个对应个体在下一群体中的生存数目。其中b j 表 示不大于。的最大整数，可确定下一代种群中的9 im1 个个体。 - _ i = 1 材 再按照f 的小数部分对个体进行降序排序，顺序取前m 一l f j 个个体加 入到下一代群体中，得到下一代群体中的m 个个体。 ( 4 ) 无回放随机选择，也称为期望值选择方法( e x p e c t e dv a l u em o d e l ) ，首先 计算每个个体在下一代种群中的生存期望数目m ，若菜一个体被选中参与交叉 运算，其生存期望数为，一o 5 ，若某一个体未被选中，则其生存期望为f 一1 。 随着选择过程进行，某一个体的生存期望小于0 时就没有机会被选中。 ( 5 ) 无回放余数随机选择( r e m a i n d e rs t o c h a s t i cs a m p l i n gw i t hr e p l a c e m e n t ) 首先计算个体在下一代种群中的生存期望数目f ，取其整数部分l ，j 为对 应个体在下一代种群中的生存数目，确定兰l j 个个体，以只一l f j 兰i = i 互石 为各个个体新的适应度，用比例选择方法来随机确定下一代种群中未确定的 m y im1 个个体。 厶一l - i j f = l ( 6 ) 排序选择( r a n k b a s e dm o d e l ) ，依据个体适应度之间的大小关系分配各个 个体的选中概率，对个体适应度是否正值或负值以及个体间的数值差异程度无 特别要求。 ( 7 ) 随机联赛选择( s t o c h a s t i ct o u r n a m e n tm o d e l ) ，选取一定数量的个体( 联 赛规模) ，基于个体之间适应度大小，将适应度高的个体遗传到下代种群 中。重复m 次，就得到下一代种群的m 个个体。在联赛选择操作中，无需对适 应度之间进行算术运算，只比较个体适应度的大小。 2 2 3 2 交叉操作 交叉，是对两个相互配对的染色体按某种方式以一定概率( 交叉概率， c r o s s o v e rr a t e ) 相互交换其部分基因，从而形成两个新个体。交叉运算是遗传 算法区别于其他算法的重要特征，在遗传算法中起着关键作用，是产生新个体 的主要方法。图2 2 示意了此过程： i i 竺a ：1 0 竺l ! lo竺111i型!ji 呈! ! ! 竺! ! ! ! ! i ! ! ! !j 交叉位交叉操作 图2 - 2 交叉操作示意图 卜1 0 1 10 1 1 1 1 1 l l b ：0 0 0 11 1 0 00 0 1 1 l 适合二进制编码个体或浮点数编码个体的交叉算子有： ( 1 ) 单点交叉( o n e p o i n tc r o s s o v e r ) ，若种群大小为m ，则共有lm 2l 对相互 配对的个体组，对于每队相互配对的个体，随机设置某一基因座之后的位置为 交叉点，若染色体长度为n ，则共有n 一1 个可能的交叉点位置，以设定的交叉 概率p ，在其交叉点处交换部分染色体，产生新的个体。 ( 2 ) 双点交叉与多点交叉( t w o p o i n t m u l t i p o i n tc r o s s o v e r ) ，在相互配对的两 个个体编码串中有两个或多个交叉点，通常多点交叉算子可能会破坏一些好的 模式，影响算法的性能。 ( 3 ) 均匀交叉( u n i f o r mc r o s s o v e r ) ，将两个配对个体的每个基因座上的基因 都以相同的概率进行交换，从而得到两个新的个体，属于多点交叉的范围，其 操作可以通过设置屏蔽字来确定新个体的各个基因如何由哪个父代个体提供， 过程为：随机产生一个与个体编码长度等长的屏蔽字w = m w 2 w m ，其中 ，为个体编码串长度，若= 0 ，则彳在第f 个基因位上基因继承a 的对应基因 值，b 在第f 个基因位上继承口对应的基因值，若w f = 1 ，则彳在第i 个基因位 上基因继承口的对应基因值，艿在第i 个基因位上继承a 对应的基因值。 ( 4 ) 算术交y , ( a r i t h m e t i cc r o s s o v e r ) ，将两个个体线性组合产生出两个新的个 体，其操作对象通常是由浮点编码所表示的个体。其运算过程为： i x 7 1 = n x ：+ ( 1 一口) x j i x 爹1 = a x ：+ ( 1 - a ) x ： 其中，参数a 可以是常数，也可以是有进化代数所决定的变量。 2 2 3 3 变异操作 变异，是按一定的概率( 变异概率，m u t a t i o nr a t e ) 将个体染色体编码串中 的某些基因位上的基因值用该基因位的其他等位基因来替换，从而形成一个新 的个体。其目的是改善遗传算法的局部搜索能力，维持了种群的多样性，防止 早熟现象。图2 。3 示意了此过程： 变