《遗传算法基本理论与实例》由会员分享，可在线阅读，更多相关《遗传算法基本理论与实例（18页珍藏版）》请在金锄头文库上搜索。
1、目录目录_ 一、遗产算法的由来.1二、遗传算法的国内外研究现状.2三、遗传算法的特点.3四、遗传算法的流程.5五、遗传算法实例.9六、遗传算法编程.13七、总结.15附录一：运行程序.16遗传算法基本理论与实例遗传算法基本理论与实例一、遗产算法的由来一、遗产算法的由来遗传算法（Genetic Algorithm，简称 GA）起源于对生物系统所进行的计算机模拟研究。20 世纪 40 年代以来，科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法。很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术生物进化系统的计算模型，以及模拟进化过程的算法进行了长
2、期的开拓性的探索和研究。John H.Holland 教授及其学生首先提出的遗传算法就是一个重要的发展方向。遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说。按照达尔文的进化论，地球上的每一物种从诞生开始就进入了漫长的进化历程。生物种群从低级、简单的类型逐渐发展成为高级复杂的类型。各种生物要生存下去及必须进行生存斗争，包括同一种群内部的斗争、不同种群之间的斗争，以及生物与自然界无机环境之间的斗争。具有较强生存能力的生物个体容易存活下来，并有较多的机会产生后代；具有较低生存能力的个体则被淘汰，或者产生后代的机会越来越少。 ，直至消亡。达尔文把这一过程和现象叫做“自然选择，适者生存” 。按照孟
3、德尔和摩根的遗传学理论，遗传物质是作为一种指令密码封装在每个细胞中，并以基因的形式排列在染色体上，每个基因有特殊的位置并控制生物的某些特性。不同的基因组合产生的个体对环境的适应性不一样，通过基因杂交和突变可以产生对环境适应性强的后代。经过优胜劣汰的自然选择，适应度值高的基因结构就得以保存下来，从而逐渐形成了经典的遗传学染色体理论，揭示了遗传和变异的基本规律。遗传算法由美国的 John H.Holland 教授 1975 年首先提出，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适
4、应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。二、遗传算法的国内外研究现状二、遗传算法的国内外研究现状遗传算法的鼻祖是美国 Michigan 大学的 Holland 教授及其学生。他们受到生物模拟技术的启发，创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术遗传算法。1967 年，Holland 的学生 Bagley 在其博士论文中首次提出了“遗传算法”一词，他发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用双倍体的编码方法。Hollan
5、d 教授用遗传算法的思想对自然和人工自适应系统进行了研究，提出了遗传算法的基本理论模式定理（Schema Theorem）并于 1957 年出版了第一本系统论述遗传算法和人工自适应系统的专著Adaptation in Natural and Artificial Systems 。20世纪 80 年代，Holland 教授实现了第一个基于遗传算法的机器学习系统，开创了遗传算法的机器学习的新概念。1975 年，De Jong 基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验，建立了遗传算法的工作框架，得到了一些重要且具有指导意义的结论。1989 年，Goldberg 出版了Gene
6、tic Algorithm in Search，Optimization and Machine Learning一书，系统地总结了遗传算法的主要研究成果，全面完整的论述了遗传算法的基本原理及其应用。1991 年，David 出版了Handbook of Genetic Algorithms一书，介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。1992 年，Koza 将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程（Genetic Programming，简称 GP）的概念。在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略。例如，Krishnakumar
7、和 Goldberg 以及 Bramlette和 Gusin 已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如 LQR 和 Powell（鲍威尔）的增音机设计所用的时间要少（功能评估）。Porter 和 Mohamed 展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案。与此同时，另一些人证明了遗传算法如何在控制器结构的选择中使用。从遗传算法的整个发展过程来看，20 世纪 70 年代是兴起阶段，20 世纪 80年代是发展阶段，20 世纪 90 年代是高潮阶段。遗传算法作为一种实用、高效、鲁棒性强的优化技术，发展极为迅速，已引起国内外学者的高度重视。近些年来，国内
8、外很多学者在遗传算法的编码表示、适应度函数、遗传算子、参数选择、收敛性分析、欺骗问题和并行遗传算法上做出了大量的研究和改进。还有很多学者将遗传算法和其他只能算法结合，进一步提高局部搜索能力。在遗传算法的应用上也有很多改进。由于遗传算法具有全局并行搜索、简单通用、鲁棒性强等优点，使得遗传算法广泛地应用于计算机科学、自动控制、人工智能、工程设计、制造业、生物工程和社会科学等领域。针对遗传算法的一些问题，还有一些问题需要进一步的探究，将大大促进遗传算法理论和应用的发展，遗传算法必将在智能计算领域中展现出更加光明的前景。三、遗传算法的特点三、遗传算法的特点遗传算法是一种借鉴生物界自然选择和自然遗传机制
9、的随机搜索算法。它与传统的算法不同，大多数古典的优化算法是基于一个单一的度量函数（评估函数）的梯度和较高次统计，以产生一个确定性的试验解序列；遗传算法不依赖梯度信息，而是通过模拟自然进化进程来搜索最优解，它利用某种编码技术，作用于称为染色体的数字串，模拟由这些串组成的群体的进化过程。遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串，生成新的串的群体。遗传算法有以下优点：（1）对可行解表示的广泛性。遗传算法的处理对象不是参数本身，而是针对那些通过参数集进行编码的基因个体，此编码操作使得遗传算法可以直接对结构对象进行操作。所谓结构对象，泛指集合、序列、矩阵、树、链、表等各种一维或二维
10、甚至多维结构形式的对象。这一特点使得遗传算法具有广泛的应用领域。比如通过对连接矩阵的操作，遗传算法可用来对神经网络或自动机的结构或参数加以优化；通过对集合的操作，遗传算法可实现对规则集合和知识库的精炼而达到高质量的机器学习目的；通过对树结构的操作，用遗传算法可得到用于分类的最佳决策树；通过对任务序列的操作，遗传算法可用于任务规划，而通过对操作序列的处理，可自动构造顺序控制系统。（2）群体搜索特性。许多传统的搜索方法都是单点搜索，这种点对点的搜索方法，对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点。相反，遗传算法采用的是同时处理群体中多个个体的方法，即同时对搜索空间中的多个解进行评估。这
11、一特点使遗传算法具有较好的全局搜索性能，也使得算法本身易于并行化。 （3）不需要辅助信息。遗传算法仅用适应度函数来的数值来评估基因个体，并在此基础上尽心遗传操作。更重要的是，遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域可以任意设定。对适应度函数的唯一要求是，编码必须与可行解空间对应，不能有死码。由于限制条件的缩小，使得遗传算法的应用范围大大扩展。（4）内在启发式随机搜索特性。遗传算法不是采用确定性规则，而是采用概率的变迁规则来指导它的搜索方向。概率不仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的。虽然看起来它是一种盲目搜索方法，实际上它有明确的搜索方向，具有内
12、在的并行搜索机制。（5）遗传算法在搜索过程中不容易陷入局部最优，即时在所定义的适应度函数是不连续的、非规则的或有噪声的情况下，也能以很大的概率找到全局最优解。（6）遗传算法采用自然进化机制来表现复杂的现象，能够快速可靠地解决求解非常困难的问题。（7）遗传算法具有固有的并行性和并行计算的能力。（8）遗传算法具有可扩展性，易于同别的技术混合使用。遗传算法作为一种优化算法，也有它自身的局限性：（1）编码不规范及编码存在表示的不准确性。（2）单一的遗传算法编码不能全面地将优化问题的约束表示出来。考虑约束的一个方法就是对不可行解采用阈值，这样，计算的时间必然增加。（3）遗传算法通常的效率比其他传统的优化
13、方法低。（4）遗传算法容易出现过早收敛。（5）遗传算法对算法的精度、可信度、计算复杂性等方面，还没有有效的定量分析方法。遗传算法的基本内容如下：个体和种群。个体就是模拟生物个体而对问题中的对象（一般就是问题的解）的一种称呼，一个个体也就是搜索空间中的一个点。种群(population)就是模拟生物种群而由若干个体组成的群体，它一般是整个搜索空间的一个很小的子集。适应度与适应度函数。适应度(fitness)就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度。适应度函数（fitness function）就是问题中的全体个体与其适应度之间的一个对应关系。它一般是一个
14、实值函数。该函数就是遗传算法中指导搜索的评价函数。染色体与基因。染色体（chromosome）就是问题中个体的某种字符串形式的编码表示。字符串中的字符也就称为基因（gene） 。例如个体上 9，染色体的表示形式是 1001，0 和 1 是染色体上的基因。遗传操作。也称为遗传算子，就是关于染色体的运算。遗传算法中有三种遗传操作：选择-复制，交叉和变异。四、遗传算法的流程四、遗传算法的流程遗传算法在整个进化过程中的遗传操作是随机的，但它所呈现出的特性并不是完全搜索，它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集。这样一代代的不断进化，最后收敛到一个最适应环境的个体上，求得问题的最优解
15、。遗传算法所涉及的五大要素是：参数编码、初始种群的设定、适应度函数的设计、遗传操作的设计和控制参数的设定。流程如图 1 所示。图 1 遗传算法基本流程简单遗传算法的运行过程为一个典型的迭代过程，其必须完成的工作内容和基本步骤如下：1）选择编码策略，把参数集合 X 和域转换为位串结构空间 S。2）定义适应度函数 。3）确定遗传策略，包括选择群体大小 n，选择、交叉、变异方法，以及确定交叉概率 、变异概率 等遗传参数。4）随机初始化生成种群 P。5）计算群体中个体位串解码后的适应度值 。6）按照遗传策略，运用选择、交叉和变异算子作用与群体，形成下一代群体。7）判断群体性能是否满足某一目标，或者已完
16、成预定迭代次数，不满足则返回步骤 6） ，或者修改遗传策略再返回步骤 6） 。下面对基本步骤进行分解，进一步详细介绍流程中一些细节。编码表示。在许多问题求解中，编码是遗传算法中首要解决的问题，对算法的性能有很重要的影响。Holland 提出的二进制编码是遗传算法中最常用的一种编码方法，它采用最小字符编码原则， 编/解码操作简单易行，利于交叉、变异操作的实现，也可以采用模式定理对算法进行理论分析。但二进制编码用于多维、高精度数值问题优化时，不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固有结构，精度不高，并且个体长度大、占用内存多。针对二进制编码存在的不足，人们提出了多种改进方法，比较典型的有以下几种：（1）格雷码编码。为了克服二进制编码在连续函数离散化时存在的不足，人们提出了用格雷码进行编码的方法，它是二进制编码的变形。格雷码不仅具有二进制编码的一些优点，而且能够提高遗传算法的局部搜索能力。假设有一个二进制编码为，其对应的格雷码为，121mmXx xx x 121mmYy yy y 则mmyx1,2,1imm
