摘 要

在这篇论文中主要使用商业数学软件MATLAB来编写相关的程序。文章侧重于遗传算法的编程以及利用几个已知极值的数学函数如Schaffer函数、Rastrigin函数来测试编写的代码。通过对比理论极值与算法输出值之间的差异来评估算法的可行性和精确性。同时，因为MATLAB自带有遗传算法工具箱gatool，所以也使用了工具箱来实现优化。将工具箱的优化性能与编写的遗传算法的优化性能相比较，就可以了解到很多不足之处且有利于算法的改良。

论文主要研究了遗传算法的优化理论、实现方法以及相关的改良手段。文中将介绍遗传算法的理论依据包括选择、交叉和变异的意义，然后以代码的形式实现以上各个步骤。最后给出完整程序的测试结果以及对于算法缺陷的优化方式。

通过最后的测试结果可以看出：所编写的遗传算法已经具备了完整的功能，可以实现二元多峰数学函数的最优解计算，基本克服了陷入局部最优的问题。

文章的特色表现在：对于遗传算法理论知识的正确解读，简单的解释了遗传算法的由来和发展历程；对于算法实现过程分步明确，通过理论与代码的比对可以很容易理解程序的实现方法；采取了一系列的优化措施来解决遗传算法中常见的一些问题与缺陷。

关键词：遗传算法；MATLAB；选择；交叉；变异

Abstract

In this paper, we mainly used the commercial mathematical softwar MATLAB to to write the related program. Article focus on the programming of genetic algorithm and the testing of the program by a few mathematical functions which extremum has been known such as Schaffer function and Rastrigin function. We will compare the differences between the theory and algorithm output value to assess the feasibility and accuracy of the algorithm. At the same time, we will use the toolbox named gatool that come with the MATLAB to to achieve optimization.Comparing the optimization performance between the toolbox and the program has been written,we will find more advantages and improve it.

Thesis mainly studied in the the optimization theory of genetic algorithm, implementation method and relevant improvement methods. This paper introduced the theory basis of genetic algorithm including selection, crossover and mutation, then implementation the steps above in the form of code.In the end, we will show the test results of the completed program and the method for the algorithm optimization.

What can be seen in the final test result is that the genetic algorithm has a complete function which can solve the optimal solution calculation of a binary multi peak mathematical function and almost overcome the problem of falling into a local optimum.

The article’s features embodied in: The correctly understanding of the genetic algorithm and explanate the origin and the development of it simply; Because of clear code of the algorithm,we can understand it easily by comparing the code with the theory; We has taken a series of optimization measures to deal with the common problems and defects in the genetic algorithm.

Key Words： genetic algorithm; MATLAB; select; crossover; mutation

目 录

摘 要 I

Abstract II

第1章 绪论 1

1.1 遗传算法简介及发展前景 1

1.2 论文主要内容与意义 2

第2章 遗传算法的实现过程 3

2.1 基本概念 3

2.2 遗传算法程序 3

2.2.1 流程图 3

2.2.2 创建种群 4

2.2.3 适应度函数 5

2.2.4 遗传算子 6

2.2.5 相关参数 9

第3章 简单优化及测试 11

3.1 算法优化 11

3.1.1 最优个体保留 11

3.1.2 重组种群 11

3.1.3 适应度函数的选择 12

3.2 优化测试 13

3.3 界面设计 17

3.4 gatool工具箱测试与比较 18

第4章 结论 23

参考文献 24

致 谢 25

第1章 绪论

大自然中一直存在着一种优胜劣汰的选择形式，在这过程中优秀个体具有更大的几率生存下去并通过与其他优秀个体的染色体的结合来保留这一优秀的基因形式，而不良的基因则会被各种自然因素所淘汰，通过这样循环往复的筛选择优过程最终将会达到某种意义上的收敛，产生出此时可视为最优的个体。这是一种最为原始的优化方式，鉴于这一点，Holland教授开始对这种通过遗传的过程来解决问题以得出最优解的形式进行了研究，并在1975年具体提出遗传算法这一概念^[1]。尽管人类在日常生活中发现了各种优化手段，但这些优化算法往往都具有一些局限性，相比之下，遗传算法则拥有更大的广泛性，在大群体中的搜索性能尤为突出^[2]。虽然遗传算法有诸多的优点，但同时也存在一系列的缺点影响着它的发展。

1.1 遗传算法简介及发展前景

根据大自然中的演化规律，我们将遗传算法简单分成四个部分：编码、选择、交叉和变异^[3]。每一个部分都对最终能否精确搜索到全局最优解起着至关重要的作用，同时也影响着整个算法的运算速度。

编码过程是一个群体的创建，在算法中是以若干码型表现的，一般选用二进制码，构成群体的个体有一串固定长度的二进制数即0和1构成，这一串二进制码形成了一个染色体记录遗传信息，也是算法的作用对象。选择即是通过各种自然环境作为约束条件，引导着整个演化的发展方向，在算法中就会以一种具体的数学或者逻辑判断的形式表现出来，预先会设定一个适应度函数来标定个体的适应能力从而来进行选择。要将优秀的基因保留并演化出更佳的表现形式，就需要交叉和变异这两个部分。通过交叉，优秀个体的基因得以互相结合以得到更优秀的基因型^[4]。而变异则可以为群体带入全新的基因，提升群体的多样性，这种低概率的变异也可以缓解一般遗传算法容易陷入的局部最优情况以及提前收敛的问题^[5]。

通过结合这几个部分，将形成一个初步具备择优选择功能的遗传算法，为了减少算法的缺陷导向输出错误解的情况，还需要对其进行一系列的优化。遗传算法的优点有：具有优良的大范围搜索特性、解的表示形式多样、不像传统算法那样依赖助信息等等。相对的，其中的缺陷也不容忽视，如编码形式往往没有一定的规范、在运行效率上不如传统的优化方式、过快的收敛等。

在多年的发展历程中，人们没有减缓探究遗传算法的脚步。近年来有很多研究表明遗传算法在函数的组合和优化领域的应用已经逐渐消退，特别是优化方面已经逐渐淡出了我们的视线。但是，遗传算法在自动控制和生产调度等领域的表现却十分突出。显然，随着算法的逐渐成熟，人们已经将其切实应用于实际的领域。图像处理和机器人学也在逐渐成为研究的热点。虽然当前有关遗传算法的文章中很少涉及数据挖掘研究方面，但随着数据挖掘技术的普及，遗传算法在其中的应用可能会成为将来一个新的热点^[6]。

1.2 论文主要内容与意义

论文的重点在于整个算法程序体在MATLAB环境下的编写和优化，文章将一步步解释程序中各个函数的意义与作用，一般来说，遗传算法包含三个遗传算子分别是选择算子、交叉算子和变异算子^[7]。各个参数具体值的选定都将直接影响算法的效率和精确度。在程序完成后将进行一些优化比如对编码的多次重组、适应度函数的选择、各个参数的选择等，最后会通过几个数学函数的测试结果来给出优化前和优化后的差别，并设计一个简单的用户界面呈现一个完整的遗传算法。

此外，由于MATLAB中自带有gatool工具箱，这是一个比较成熟的遗传算法程序，拥有多种编码方式，其计算速度也很快运行效率很高。文中也会用函数来测试其优化性能并与自己编写的程序相比较，在比较中寻找优化算法的途径，不断提升其优化的效率和精确度。