摘 要

遗传算法是一种模拟生物进化过程的计算模型^[1]，是按照生物进化规律演化而来的一类搜索算法。它是从上个实际70年代开始兴起的，之后也是在不断地发展。

随着社会和科技的进步，遗传算法的发展也越来越迅速。关于它的研究有许多，就比如在高校的排课问题中，可以运用遗传算法进行排课，将教师、教室、多媒体等资源更加合理的利用；又如在研究旅行线路的问题中，可以运用遗传算法对旅行线路进行选择。；还有对公交进行调度等等。然而，大部分的研究上都是通过软件来实现的，而软件对于运行速度方面的限制，也大大的降低了遗传算法的作用。因此也让遗传算法在许多方面的应用大打折扣。遗传算法是具有天然的并行性^[2]，通过硬件系统的运行上可以让它更快的实现。因此我们可以在FPGA(现场可编程门阵列)上实现并行化的遗传算法来提高它的运行速度。

本文的主要内容为：

1.简要的分析了遗传算法的研究背景。详细的说明了遗传算法整体框架和执行过程，并对FPGA相关内容进行了介绍。

2. 根据遗传算法的功能和运算流程，对遗传算法的部分流程采用流水线设计，并结合硬件平台，进行模块化的划分。

3.根据各个模块的功能需求，使用Verilog HDL语言作为编程工具，完成模块的代码，并在QuartusⅡ中对模块进行综合和仿真。并通过模块实例化对完整的遗传算法功能进行验证。

4.通过MATLAB实现遗传算法的计算过程。

关键词：遗传算法；并行性；FPGA；Verilog；

Abstract

Genetic algorithm is a computing model that simulates the evolution process of organisms, and it is a type of search algorithm that evolves according to the laws of biological evolution. It started from the last real 70s, and has continued to develop since then.

With the advancement of society and technology, the development of genetic algorithms has also become more and more rapid. There are many studies on it. For example, in the scheduling of colleges and universities, genetic algorithms can be used to arrange courses to make more reasonable use of resources such as teachers, classrooms, and multimedia; as in the study of travel routes. The genetic algorithm selects the travel route; there is also the scheduling of public transportation and so on. However, most of the research is implemented through software, and the limitation of software on the running speed has greatly reduced the role of genetic algorithms. Therefore, it also greatly reduces the application of genetic algorithms in many aspects. Genetic algorithm has natural parallelism, which can be realized faster through the operation of the hardware system. Therefore, we can implement parallel genetic algorithm on FPGA (field programmable gate array) to improve its running speed.

The main contents of this article are:

1. Briefly analyze the research background of genetic algorithm. The overall framework and execution process of the genetic algorithm are explained in detail, and the FPGA related content is introduced.

2. According to the function and operation flow of the genetic algorithm, part of the flow of the genetic algorithm is designed by pipeline, and combined with the hardware platform, the modularization is divided.

3. According to the functional requirements of each module, use Verilog HDL language as a programming tool, complete the code of the module, and integrate and simulate the module in Quartus II. And through the module instantiation to verify the complete genetic algorithm function.

4. Realize the calculation process of genetic algorithm through MATLAB.

Key words : Genetic algorithm; Parallelism; FPGA; Verilog;

目录

第一章 绪论 7

1.1 研究背景和意义 7

1.2 遗传算法的发展 7

1.2.1 遗传算法的历史发展 7

1.2.2 遗传算法的应用 8

1.2.3 国内外研究现状 10

1.4 主要研究内容及结构 10

第二章 遗传算法简介 11

2.1遗传算法的基本概念 11

2.1.1 遗传与进化 11

2.1.2遗传算法基本用语 11

2.2 遗传算法的基本流程 12

2.3基本遗传算法 14

2.3.1遗传算法的编码 14

2.3.2初始种群的设定 15

2.3.3 选择算子 15

2.3.4 交叉算子 16

2.3.5变异算子 17

2.3.6 遗传算法的控制参数 17

2.4 本章小结 18

第三章FPGA 19

3.1 FPGA简介 19

3.2 FPGA的设计流程 19

3.2 Verilog HDL 21

3.3 QuartusⅡ 21

3.4 本章小结 22

第四章 系统模块设计 23

4.1 遗传算法的流水线设计 23

4.2 系统模块划分 24

4.3 主要模块的设计 25

4.3.1 随机数发生模块 25

4.3.2 存储模块 25

4.3.3 选择模块 26

4.3.4 初始化模块 27

4.3.5 交叉模块 27

4.3.6 变异模块 28

4.3.7 适应度计算模块 29

4.3.8 主函数模块 30

4.3.9 本章小结 31

第五章 实验结果与分析 32

5.1 模块功能实现 32

5.1.1 随机数模块 32

5.1.2 选择模块 32

5.1.3 初始化模块 33

5.1.4 交叉模块 34

5.1.5 变异模块 34

5.1.6 适应度计算模块 35

5.1.7 主函数模块 36

5.2 本章小结 37

结论 38

第一章 绪论

1.1 研究背景和意义

当今社会已经进入了一个飞速发展的时代，科学技术也在不断地进步，经常在解决一个问题时需要用到多个学科的知识。不同学科的知识相互交叉，并促进彼此更好的发展，这也让目前的科学技术能够发展得更加迅速，工程科学在自然科学的促进下蓬勃发展就是非常具有代表性。而随着科技的进步，人们也越来越需要优化算法来解决一些愈加复杂的计算问题。但随着问题越来越复杂，那些简单的优化算法已经没有办法去解决问题了。例如在人工智能领域，由于人工智能的迅速发展，原有的方法已经无法顺利的处理大量的模式信息等问题。遗传算法(Genetic Algorithm，简称GA)的出现很有效的解决了这类问题。

GA是根据进化论而设计出来的一种优化算法，可以在杂乱庞大的搜寻空间中搜查出最优解，近些年来飞速发展。该算法起源于Holland教授对于机器学习问题的研究，1975年《Adaptation in Natural and Artificial Systems》^[3]问世了，这是由Holland教授编写的关于GA的经典著作。在书中详细地介绍了GA的相关理论。

经过多年的发展和应用，遗传算法的使用以及比较普及了，它能够很好的解决许多问题。由于GA能够广泛的适用在许多问题中，所以对GA进行深入的研究就能够帮助其他学科的进步。就比如在高校的排课问题中，可以运用遗传算法进行排课，将教师、教室、多媒体等资源更加合理的利用。又如在研究旅行线路的问题中，可以运用遗传算法对旅行线路进行选择。还有对公交进行调度，让公交车能够在乘客较多的时候能够缩短发车间隔的时间，做到让乘客们不用等过长的时间或者挤在一辆车中等等。

1.2 遗传算法的发展

1.2.1 遗传算法的历史发展

虽然现在关于遗传算法的应用比较多，但是其实遗传算法的历史并不长。遗传算法的研究是从上个世纪的中期出现的，那些学者早期主要是生物的遗传现象进行研究，从生物学的视角对生物的进化和遗传过程进行探讨，并在计算机上进行模拟。由于缺少一些带有指导意义的相关理论以及缺乏相应的计算工具，所以那是一个没有明确目标的发展阶段。

在1962年，Fraser通过研究提出了一种概念和见解，这个概念和现在的GA有些相似，不过他并没有意识到自然遗传可以转变成人工遗传算法。但不久后Holland教授和他的学生却从中受到了启发，他们发现了将自然遗传转变成人工遗传算法是非常有用的。因此，就在1965年，Holland教授第一次表达了可以将自然遗传转变成人工遗传算法，同时还将这个想法加以应用。"遗传算法"这个术语第一次出现是在1967年，这一年Bagley发表了他的博士论文，在论文中就提及了这个术语。在70年代初，模式定理的概念被提了出来，提出这个概念的人还是Holland教授。而这个定理的出现给GA产生了很大的促进作用，给它打下了十分重要的理论基础。1975年，第一本详细说明GA和人工自适应系统的著作出现了，这就是Holland教授所发表的《自然人工系统的自适应》一书。还是1975年，DeJong也发表了《遗传自适应系统的行为分析》这一论文。在论文里，在模式定理的基础下他完成了许多的实验，并建立了GA的框架。

进入80年代之后，遗传算法开始变得热门起来，GA也是进入了兴起和发展的时代，在应用研究方面变得非常活跃。分类器系统就是在这时出现的，而实现它的人还是Holland教授。分类器系统的实现也是创立了一种新技术，说明是可以通过遗传算法来实现机器学习的。1987年，通过总结，Davis公开出版发表了《遗传算法和模拟退火》一书，在书中他采用了许多的例子为我们介绍了GA。著作《搜索、优化和机器学习中的遗传算法》^[4]在1989年发表了，在这本书中Goldberg详细的归纳了当时通过GA所获得的收获。该书也可以说是给现代遗传算法打下了科学基础。

到了90年代之后，GA的发展更加深入了。1991年，Davis公开发表了著作《遗传算法手册》，在书中他纳入了GA在许多方面的大量实例。该书让更多的人接触了解了遗传算法的应用，对GA的应用更加普及。1992年，遗传编程的概念被提了出来，Koza把GA应用到了计算机方面，运用GA对程序进行优化，并将这个方法应用到了实际当中，如人工智能方面以及机器学习等方面都有所应用。随着GA的发展，遗传算法引起了许多领域的科学家们的极大研究兴趣，因此GA的研究领域也在不断地发展壮大。

1985年，举办了第一届GA的国际会议，自此以后，每隔两年都会举办一次这种会议让与会者相互交流关于研究应用遗传算法的经验。