遗传算法的研究及应用
作者：彭志勇邓世权
来源：《计算机光盘软件与应用》2013年第07期
摘要：遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式，它可以应用与生活中的很多领域。
关键词：遗传算法；函数优化；生产调度；自动控制
中图分类号：TP183文献标识码：A文章编号：1007-9599 (2013) 07-0000-02
遗传算法是一种典型的优化搜索算法，它的构造是使用人工的方式，并对生物遗传学和自然选择机理来进行模仿，是一种典型的数学仿真，而这种数学仿真是通过生物进化的过程来进行的，它是进化计算的一种非常重要的形式。
与传统的数学模型进行比较，遗传算法有很多的不同的地方，因为它能够解决很多复杂的问题，而传统的数学模型却没办法做到。
1遗传算法的理论研究
1.1遗传算法的由来。
美国密西根大学的霍兰德（Holland）将该算法应用于自然和人工系统的自适应行为的研究之中，并且在二十世纪七十年代中期，出版他的第一部著作《自然与人工系统中的适应》。
随后，Holland与他的学生们将该算法进行了大力的推广，并把它应用到优化及机器学习等问题之中，而且正式定名为遗传算法。
1.2遗传算法的发展。
遗传算法的兴起于20世纪70年代，而到了20世纪80年代的时候，它正好属于一个发展中的过程，到了20世纪90年代时，它已经发展到了颠疯时刻。
为一种实用性较强而又很有效率的优化技术，遗传算法的发展还是非常迅速，在国内外已经造成了非常大的影响力。
1.3遗传算法的基本思想。
遗传算法是从一个种群（population）开始的，而这个种群代表问题可能潜在解集的，一个种群是由经过基因（gene）编码（coding）的一定数目的个体（individual）所组成。
染色体是遗传物质的主要载体，它是由多个基因的集合，其内部表现是某种基因组合决定的。
自从初始种群产生以后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解。
在每一代，根据问题域中个体的适应度（fitness）大小来挑选（selection）个体，遗传算法是采纳了选择、交叉、变异、迁移、局域与邻域等自然进化模型，并借助于自然遗传学的遗传算子（genetic operators）进行组合交叉（crossover）和变异（mutation），从而产生出代表新的解集的种群。
遗传算法和传统搜索算法有很大的不同，它是通过一组随机产生的初始解开始搜索过程。
染色体是类似于二进制串的一串符号，对于染色体的测量，我们通常是用适应度来它的好坏
的，染色体也会生成下一代的，对于所生成的下一代，我们把它称作为后代，它们是上一代染色体进行相互交叉或者是相互变异运算而形成的。
根据适应度的大小，在后代的形成过程中我们对其进行选择或者是淘汰，这样也就能够保持种群大小的稳定性。
对于适应度比较高的染色体通溃被选中的可能性是比较大的，这样，在经过若干代的交叉和变异之后，对于最优的染色体而言，算法对其自然也是收敛的，这个过程将导致种群通过自然进化的后代种群，比上一代能够更加的适应于环境，因此末代种群中的最优个体经过解码（decoding），可以作为问题近似最优解，如图1所示，清晰的表明了遗传算法的基本思想。
图1遗传算法的基本思想
1.4遗传算法的基本原理。
霍兰德的遗传算法通常情况下被称作为简单遗传算法（SGA），现在我们以此来作为讨论的主要对象，然后再加上适当的改进，用来分析遗传算法的结构和机理。
首先我们来介绍它的主要概念，并在讨论中会结合推销员旅行问题（TSP）加以说明：假设现在有m个城市，城市i与城市j它们之间的距离为d（i，j）（i，j=1，……m），而推销员旅行问题必须得寻找访问到每个城市，并且恰好每次只有一条回路，寻找到的路径总长度也必须是最短的。
遗传算法GA是把问题的解表示成“染色体”，在给出一群“染色体”后再来执行遗传算法，作为假设解，然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从当中选择出较适应环境的“染色体”来进行复制，再通过交叉和变异过程来产生更加适应环境的新一代“染色体”群。
这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，从而就可以得出问题的最优解。
2遗传算法的应用
遗传算法不会受搜索空间的限制性假设的束缚，因此没有必要对类似于连续性、导数存在以及单峰等这样的假设进行过多的要求，因为全局最优解可以通过遗传算法在一些高维问题中以最大的可能性找到，尽管这些高维问题是离散的和多极值的，并且还含有噪音。
正是因为遗传算法具有并行性这一特点，它比较适用于一些大规模的并行计算，已在很多领域得到了越来越广泛的应用，它的应用领域主要有以下的几个方面：
2.1函数优化问题。
遗传算法中的一个经典应用领域就是函数优化问题，它也是对遗传算法进行性能评价的常用例子，目前有各种各样的复杂形式的测试函数来评价遗传算法的性能。
而且用传统的算法来解决一些诸如非线性和多模型以及多目标这一类的函数优化问题是很困难的，而我们使用遗传算法却能很容易就取得比较满意的效果。
2.2组合优化问题。
随着各种各样的问题产生，规模也慢慢变得越来越大，因此组合优化问题在搜索空间这方面也慢慢变得越来越大，而目前在计算机上使用枚举这也是很不现实的，
有时候甚至是没办法求出它的精确的最优解。
针对这种比较复杂的问题，人们也开始慢慢意识到了我们应该尽最大努力去寻找满意的解决方案，这才是目前比较重要的事情，而遗传算法便能够对这些问题进行很好的解决。
实践也证明，遗传算法是种非常有效的求解组合优化问题的算法，在求解旅行商问题、图形划分问题等方面遗传算法已经得到成功的应用。
2.3生产调度问题。
生产调度问题所建立起来的数学模型在很多时候是很难精确求解，就算是我们在进行了大量的简化以后能够求解出来，但也会由于简化太过于多，因而使得所求解出来的结果与实际的结果差距非常大。
因为在这里可以使用字符编码来进行，而且也没有必要用那些恰好的目标函数来进行估值，正是由于遗传算法的一些特点它能够很好的去解决一些比较复杂的调度问题。
2.4机器学习。
对于高级自适应系统而言，它所具有的一个典型特征就是学习能力，机器学习在遗传算法方面的应用还是有很多都比较成功的。
例如，当我们要学习类似于模糊控制规则和确定模糊集的隶属函数以及改进模糊系统的性能等知识的时候，就可以应用遗传算法来进行学习；使用遗传算法能够对人工神经网络的连接权进行很好的调整，还可以对网络拓扑进行优化。
参考文献：
[1]雷英杰.MATLAB遗传算法工具箱及应用[M].西安:西安电子科技大学出版社,2005:140-143.
[2]王辉.用遗传算法求解TSP问题[J].南昌:计算机与现代化,2009,4:81-83.
[作者简介]彭志勇（1984-），男，湖北武汉人，凯里学院教师，硕士研究生学历，研究方向：算法设计与分析。