基于FPGA的演化硬件技术研究
摘要
在科学技术飞速发展的今天，遗传算法在越来越多的领域得到了应用。但这些 发展同时也对遗传算法提出了更高的要求。为了使遗传算能够在更大的范围，更多 的领域得到应用，很有必要对遗传算法的实现方式以及性能的改进进行更加深入的 研究。目前对于遗传算法的研究更多是集中在软件方面，关于遗传算法硬件实现方 面的研究国内外所发表的成果都不是很多。而遗传算法本质是并行的，用软件实现 会受到串行计算的制约而影响计算速度，硬件则能够实现算法的并行计算。
本文主要介绍了遗传算法的基本原理和各个遗传算子的具体实现方法和步骤， 列举了各个遗传算子的几种实现方式并分析比较了其中最为常用的几种。介绍了当 前遗传算法硬件实现的基本情况，并分析了它们的优缺点，指出了它们未解决的一 些问题和需要进一步改进的地方。接着介绍了遗传算法实现的硬件平台，包括实现 的器件，编程语言和开发以及仿真的软件等。在此基础上，设计了硬件的总体结构， 用两路并行运算来实现算法。对于遗传算法的各个步骤及算子，采用模块化处理， 并对其中各个细节都作了相应处理，使其符合硬件实现的要求。
本文主要工作及创新点为： (1)采用了一种新型的流水线实现方式，节省了运算的时间。 (2)文章使用硬件构建了一种两路并行执行的遗传算法，加入了基于确定性排
挤机制的小生境方法，从而能够处理复杂的多峰值函数。为了克服小生境方法中存 在的易早熟问题，采用适合硬件实现的自适应调整变异概率的方法，从而进一步提 高了算法的搜索性能。通过实验证明，该算法能够搜索出多峰值复杂函数的所有局 部最优值和全局最优值，克服了易早熟问题，具有良好的搜索性能，且具有较快的 运算速度。其运算速度比软件实现的遗传算法快两个数量级以上。
(3)将该硬件实现的改进遗传算法应用于 PID 控制器当中，结合电阻炉的特点， 设计了一个电阻炉炉温控制系统。炉温控制系统的成功设计验证了硬件实现遗传算 法可行性，并能应用于实际系统中。
最后，文章进行了总结，并提出了几点不足和将来需要进一步改进的地方。 关键字：FPGA；流水线；小生境遗传算法；Verilog HDL
第 1 章 绪 论
1.1 遗传算法的硬件实现研究现状
[1]
遗传算法最早由Holland教授提出
，是一种具有学习功能﹑组织功能﹑适应功
能诸多功能的优化算法，涉及非线性理论﹑人工智能﹑运筹学﹑神经网络理论﹑优 化理论﹑神经网络理论等诸多学科。其主要被用于优化复杂系统，可用于解决高度 非线性﹑不确定性及复杂的任务。
对于遗传算法的研究目前主要还是集中在软件实现方面。但在面临大规模复杂 的问题的时候，软件实现的遗传算法计算速度受到计算机系统串行本质的限制，往 往因难以满足实时性需求而无法寻求到理想的结果。硬件实现的遗传算法，可以并 行地实现整个流程，从而能够在很大程度上提高算法的搜索速度。但通常在进行硬 件设计时，需要事先对问题有个全面﹑精确的了解。即先对电路系统进行分解，然 后再分层进行设计。然而随着问题复杂程度的增加，完全把握整体电路系统是相当 困难的。新一代的现场可编程门列阵（FPGA）及其硬件描述语言的出现，使得遗
传算法的硬件实现变得十分的方便。
目前国内外对于硬件实现遗传算法的研究并不是十分的广泛
[2]
，只有为数不多
的文献予以了明确的报道：国外有少量文献介绍了微处理芯片结合FPGA进行硬件
[3]
遗传算法应用的情况
；国内则只有部分文献进行了讨论，实现方式也主要是使用
FPGA，其中使用算法针对具体的应用问题的文献则更是少数。 当前文献提出的各种硬件实现遗传算法，基本上都能在很大程度上提高算法的
速度（通常在50倍以上）。但同时存在以下几类问题；
1.使用可编程片上系统。可以提高系统的灵活性，但限制了硬件实现的速度优 势。如文献[4]。
2．采用硬件模块结构。划分了模块并对电路结构进行设计从而实现遗传算法 的基本功能。缺点是没有使用流水线来优化系统，并且其运算任然是串行的。如文 献[5]。
3.实现了部分流水线处理。如在模块之间需要握手，使两个模块并行工作。但 由于各个模块工作所需时钟周期数不同，因而未能实现数据的完全流水线处理。如 文献[6]。
4.使用遗传算法针对具体的问题进行硬件设计，但对算法本身并没有改进。 如 文献[7][8]。
从上面的介绍中可以看出，遗传算法的硬件实现还有许多需要改进的地方，是值得我们研究的。
目录
第 1 章 绪 论 1
1.1 遗传算法的硬件实现研究现状 1
1.2 PID 控制器简介 2
1.3 论文的主要内容及基本结构 3
第 2 章 遗传算法及硬件平台简介 5
2.1 遗传算法及其原理 5
2.2 遗传算法的基本操作 6
2.2.1 遗传算法的编码 6
2.2.2 选择操作 6
2.2.3 交叉操作 7
2.2.4 变异操作 9
2.2.5 适应度的计算 9
2.3 遗传算法的参数整定 10
2.4 小生境遗传算法简介 12
2.5 硬件开发环境 13
2.5.1 FPGA 概述 13
2.5.2 硬件描述语言 Verilog HDL 14
2.5.3 开发工具 ISE 14
2.6 本章小结 15
第 3 章 改进遗传算法硬件实现系统的总体设计 17
3.1 基于 FPGA 的改进遗传算法的总体结构 17
3.2 流水线设计 18
3.3 系统各模块的实现 20
3.3.1 初始化模块 20
3.3.2 控制模块 22
3.3.3 伪随机数产生模块 23
3.3.4 适应度计算模块 24
3.3.5 选择模块 25
3.3.6 交叉模块 27
3.3.7 变异模块 29
3.3.8 内存模块 31
3.3.9 小生境模块 32
3.4 仿真与结果分析 35
3.4.1 旅行商问题 35
3.4.2 多峰值函数问题 37
3.5 本章小结 38
第 4 章 硬件实现的遗传算法在 PID 控制器中的应用 40
4.1 PID 控制的基本概念 40
4.2 基于遗传算法寻优的 PID 控制器 42
4.3 FPGA 实现的基于遗传算法 PID 控制系统设计 43
4.3.1 主控芯片 Xilinx XC3s500E 工作过程 43
4.3.2 温度检测，转换和传送部分设计 44
4.3.3 驱动和控制电路设计 45
4.3.4 仿真与实验结果分析 46
4.3.5 实际运行中的问题 48
4.4 本章小结 49
第 5 章 总结 50
参考文献 52
致谢 56
附录 57
参考文献
[1] Holland J.H. AdaptationinNaturalandArtificialSystem[M]. MITPress, 1975.
[2] 周艳聪, 顾军华, 董永峰, 刘恩海. 遗传算法的FPGA硬件实现[J], 计算机工程与应用, 2011, 47(20): 9-13.
[3] 张颖波. 基于FPGA的遗传算法流水线设计[D], 硕士学位论文, 湖南大学, 2010.
[4] Jelodar M S,Kamal M,Fakhraie S M. SOPC-Based Parallel Genetic Algorithm[J]. Proc of IEEE Congress on Evolutionary Computation. 2006, 2800-2806.
[5] 王脂丹. 基于FPGA的遗传算法实现技术研究[D], 硕士学位论文, 南京航空航天大学，2006. [6] 房磊, 张焕春, 朱立力. 基于FPGA的并行遗传算法硬件实现的研究[J]. 南京航空航天大学
学报, 2004, 10: 628-632.
[7] 吴春英, 经亚枝. 基于FPGA的遗传算法硬件化技术的研究[D], 硕士学位论文, 南京航空航 天大学, 2004.
[8] 钟汝刚. 基于遗传算法的测试生成在FPGA上的研究与实现[D], 硕士学位论文, 湖南大学, 2009.
[9] 张卫东. PID控制器自整定技术的发展[J], 2002年世界控制大会总结报告, 2002.
[10] Astrom K J, Hagglund T. PID Controllers: Theory, Design, and Tuning. Instrument Society of America. 1995.
www.bysj360.com www.bysj360.com/html/4402.html www.bysj360.com/html/4385.html
www.bysj360.com/html/4391.html www.bylw520.net/ www.bylw520.net/html/4442.html www.bylw520.net/html/4435.html
