基于FPGA并行遗传算法的硬件实现技术研究

论文摘要

至今,国内外对遗传算法的算法实现的研究仍然主要是通过软件实现的。而软件语言的执行方式是串行的,这无疑与遗传算法天然的并行性相违背,极大地限制了遗传算法执行的实时性。从而局限了遗传算法应用的广泛性。为此,本课题提出了一种基于FPGA的并行化遗传算法(PGAs)的硬件实现系统,在遗传过程中通过地址用其中的最优个体及其适应度代替最差的个体及其适应度,从硬件实现的角度提高遗传算法的收敛速度。本文首先分析了遗传算法的基本原理及方法,并介绍了FPGA与HDL的特点及其开发过程。然后依据FPGA与HDL的特点和遗传算法的功能要求,按照自顶向下的设计思想进行模块划分,并对各个模块的功能进行了详细地解析。最后采用VHDL编写代码实现各个模块的功能,在QuartusⅡ8.0开发集成环境中对各个模块一一进行了分析与语法检查、功能仿真、综合、布局布线、时序仿真、并下载到Cyclone系列的目标芯片EP1C12Q240C8上完成了整个设计的验证。结果表明:1.本设计采用遗传算法并行化途径中的粗粒度模型,实现了并行化遗传算法的基本功能。2.整个硬件系统使用了流水线技术,其收敛速度比软件实现有了大幅度地提高。3.在设计系统的编译过程中利用了LogicLock优化技术,合理分配了硬件资源,提高了系统的工作速度和可靠性。4.本设计系统所占用的目标芯片的面积较小。

论文目录

• 摘要
• ABSTRACT
• 第1章 引言
• 1.1 遗传算法发展历史概述
• 1.2 并行化遗传算法的发展现状
• 1.3 遗传算法的原理及实现技术
• 1.3.1 遗传算法的基本原理
• 1.3.1.1 简单遗传算法的原理
• 1.3.1.2 并行遗传算法的原理
• 1.3.1.3 遗传算法的基本用语
• 1.3.2 遗传算法的实现技术
• 1.3.2.1 编码
• 1.3.2.2 遗传算法的三个基本遗传算子
• 1.3.2.3 粗粒度并行遗传算法控制参数的讨论
• 1.3.2.4 粗粒度并行遗传算法的流程
• 1.4 课题的研究背景及意义
• 1.5 本课题的主要研究内容和预期效果
• 1.6 本课题使用的主要技术和方法
• 第2章 FPGA设计系统及HDL概述
• 2.1 FPGA设计系统概述
• 2.1.1 FPGA的结构特点
• 2.1.2 FPGA设计特征
• 2.1.3 FPGA的EDA开发流程
• 2.2 HDL语言
• 2.2.1 HDL语言概述
• 2.2.2 VHDL语言
• 2.2.2.1 VHDL语言的特点
• 2.2.2.2 VHDL语言的设计流程
• 2.3 本课题使用的硬件开发环境简介
• 2.4 本章小结
• 第3章 硬件电路系统的模块划分与参数选择
• 3.1 并行遗传算法硬件系统的模块划分与结构设计
• 3.2 并行遗传操作及其控制参数的选择
• 3.2.1 粗粒度并行遗传算法模型及遗传算子方式的选择
• 3.2.2 并行遗传算法控制参数的选择
• 3.3 本章小结
• 第4章 硬件电路系统的模块具体设计与实现
• 4.1 RTL级设计的一般性指导原则
• 4.2 系统设计中采用的技巧
• 4.3 系统各模块的具体设计
• 4.3.1 CP控制模块的设计
• 4.3.2 CP存储器模块的设计
• 4.3.3 CP选择模块的设计
• 4.3.4 CP交叉变异模块的设计
• 4.3.5 CP随机数模块的设计
• 4.3.5.1 伪随机数产生的基本原理
• 4.3.5.2 随机数模块的设计
• 4.3.6 初始化生成种群模块的设计
• 4.3.7 CP多功能多路分配器模块的设计
• 4.3.7.1 常规多路分配器模块的设计
• 4.3.7.2 适应度计算模块的设计
• 4.3.7.3 次选择模块的设计
• 4.3.8 CP的最优和最差个体地址产生模块的设计
• bestWorst的设计'>4.3.8.1 模块generateFlag_bestWorst的设计
• address的设计'>4.3.8.2 模块choose_address的设计
• 4.3.9 CP的其它多路分配器模块的设计
• wr_en的设计'>4.3.9.1 模块ram1_wr_en的设计
• ram1_RdAddrA的设计'>4.3.9.2 模块mux_ram1_RdAddrA的设计
• ram1_WrAddr的设计'>4.3.9.3 模块mux_ram1_WrAddr的设计
• Ina1Fita1的设计'>4.3.9.4 模块mux_Ina1Fita1的设计
• ram1_DininDinfit的设计'>4.3.9.5 模块mux_ram1_DininDinfit的设计
• 4.3.10 迁移控制模块的设计
• 4.3.11 迁移系统的多路分配器模块的设计
• FitbestInbest的设计'>4.3.11.1 模块mux_FitbestInbest的设计
• address_for_trans的设计'>4.3.11.2 模块mux_address_for_trans的设计
• 4.3.12 整个PGAs硬件系统的最顶层模块的设计
• 4.4 本章小结
• 第5章 并行遗传算法硬件电路系统的仿真与实现
• 5.1 硬件系统各功能模块的仿真分析
• 5.1.1 随机数产生模块的仿真分析
• 5.1.2 初始化生成种群模块的仿真分析
• 5.1.3 CP的多功能多路分配器模块的仿真分析
• 5.1.3.1 适应度计算模块的仿真分析
• 5.1.3.2 CP多功能多路分配器模块的仿真分析
• 5.1.4 CP的选择模块的仿真分析
• 5.1.5 CP交叉变异模块的仿真分析
• 5.1.6 CP控制模块的仿真分析
• 5.1.7 CP存储器模块的仿真分析
• 5.1.8 迁移控制模块的仿真分析
• 5.1.9 硬件系统的整体仿真分析
• 5.2 硬件设计系统的编译
• 5.2.1 系统的综合
• 5.2.2 系统的布局布线
• 5.3 硬件设计系统的下载配置与实现
• 5.4 本章小结
• 第6章 课题总结与工作展望
• 6.1 课题总结
• 6.2 工作展望
• 致谢
• 参考文献
• address'>附录1 模块choose_address
• of_adaptability'>附录2 模块degree_of_adaptability
• 附录3 模块initial
• 4₂'>附录4 模块mux₄₂
• address_for_trans'>附录5 模块mux_address_for_trans
• FitbestInbest'>附录6 模块mux_FitbestInbest
• max'>附录7 模块choice_max
• variation'>附录8 模块cross_variation
• bestWorst'>附录9 模块generateFlag_bestWorst
• Ina1Fita1'>附录10 模块mux_Ina1Fita1
• ram1_DininDinfit'>附录11 模块mux_ram1_DininDinfit
• ram1_QafitQain'>附录12 模块mux_ram1_QafitQain
• ram1_RdAddrA'>附录13 模块mux_ram1_RdAddrA
• ram1_WrAddr'>附录14 模块mux_ram1_WrAddr
• ram1_wren'>附录15 模块mux_ram1_wren
• 附录16 模块random1
• 附录17 模块transfer
• 附录18 模块xuanze
• 附录19 模块control
• 攻读学位期间的研究成果