基于FPGA的遗传算法流水线实现

摘要

随着科学技术的发展,遗传算法(Genetic Algorithins,GAs)在许多领域得到了越来越广泛的应用。然而,目前人们对遗传算法的研究主要以软件实现为主,在速度上受到本质是串行计算的计算机系统的制约,使其在实时性要求高的场合的应用受到了限制。基于此,本文设计了一种遗传算法在FPGA(Field Programmable
　　 Gate Array,现场可编程门阵列)上流水线实现的方法,从硬件实现的角度提高遗传算法的运行速度。
　　 本文的主要工作有:
　　 1.详细论述了遗传算法的基本原理和操作流程,对遗传算法的特点进行了分析和研究,并着重介绍了遗传算法的三个基本算子:选择、交叉和变异算子。
　　 2.深入探讨了FPGA的设计方法和特点。在此基础上,根据遗传算法自身的结构特点,对遗传算法进行了模块的划分,并确定了遗传算法的运行参数、工作流程和控制时序。
　　 3.主要的创新点是对遗传算法的遗传操作部分进行了完全流水线设计优化,将其划分为选择、交叉、变异和适应度计算4级流水单元。每一级流水单元的数据处理时间都为一个时钟周期。这样通过所有流水单元的同时工作,大大减少了系统运行所需要的时钟周期数。
　　 4.对遗传算法内部各子模块的功能、端口连接、内部结构等进行了详细说明,并使用硬件描述语言Verilog HDL对各子模块进行了实现。
　　 5.在QuartusⅡ环境下对系统的各模块进行了功能仿真,验证了系统设计的正确性,并最终在ALtera公司cyclone系列EP1C6Q240C8芯片上对系统进行了下载实现。实现后的测试表明:基于FPGA的遗传算法能够实现在较高时钟频率下的稳定运行,与由软件实现的遗传算法相比较,运行速度提高了约三个数量级。同时,设计方案在资源利用率和速度方面也达到了较好的平衡,达到了预期的设计目的。

目录

文摘

英文文摘

插图索引

附表索引

第1章 绪论

1.1 研究背景与意义

1.1.1 遗传算法的应用情况

1.1.2 遗传算法的未来研究方向

1.1.3 遗传算法硬件化研究现状

1.2 论文主要工作及组织结构

第2章 遗传算法简介

2.1 遗传算法的生物学基础

2.1.1 遗传与进化

2.1.2 遗传算法和自然遗传学的基础用语

2.2 遗传算法的运行流程

2.3 遗传算法的编码

2.4 遗传算法的基本操作

2.4.1 选择操作

2.4.2 交叉操作

2.4.3 变异操作

2.5 遗传算法的运行参数

2.6 遗传算法的基本特点

2.7 小结

第3章 FPGA与开发环境

3.1 FPGA概述

3.1.1 FPGA技术

3.1.2 基于FPGA的设计流程

3.1.3 FPGA设计原则

3.2 硬件描述语言Verilog HDL

3.3 开发工具Quartus Ⅱ

3.4 硬件开发环境介绍

3.5 小结

第4章 遗传算法流水线设计

4.1 硬件系统整体设计流程概述

4.2 系统模块划分与参数选择

4.2.1 系统模块划分与运行流程

4.2.2 遗传操作方式选择

4.2.3 遗传算法运行参数的选择

4.3 流水线技术

4.3.1 流水线技术介绍

4.3.2 遗传算法的流水线划分

4.4 主要功能模块的设计

4.4.1 控制模块的设计

4.4.2 选择模块的设计

4.4.3 交叉模块的设计

4.4.4 变异模块的设计

4.4.5 适应度计算模块

4.4.6 存储器模块的设计

4.4.7 随机数模块的设计

4.4.8 初始化模块的设计

4.4.9 数据选择模块的设计

4.4.10 顶层模块的设计

4.5 小结

第5章 功能仿真与性能分析

5.1 各模块的功能仿真

5.1.1 控制模块的仿真

5.1.2 选择模块的仿真

5.1.3 交叉模块的仿真

5.1.4 变异模块的仿真

5.1.5 适应度计算模块的仿真

5.1.6 随机数模块的仿真

5.1.7 初始化模块的仿真

1.1.8 顶层模块的仿真

5.2 下载实现与性能分析

5.3 小结

结论

参考文献

致谢

附录A 攻读学位期间所发表的学术论文目录

附录B 攻读学位期间所参与的科研活动