遗传算法及其应用毕业论文

遗传算法及其应用I摘 要遗传算法是一种模拟自然界生物进化的搜索算法，由于它的简单易行、鲁棒性强，尤其是其不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程，从而使它的应用范围极为广泛，并且己在众多领域得到了实际应用，取得了许多令人瞩目的成果，引起了广大学者和工程人员的关注。在简要的介绍了遗传算法的发展历史和研究现状及其生物学、数学基础后，文中引出了遗传算法的基本概念和原理、分析了遗传算法的基本实现技术。如：编码、适应度函数、遗传算法的三大遗传操作、参数规则等。最后在介绍了遗传算法程序设计原则的基础上，编程实现了遗传算法在图像识别中的应用，在实践中检验了遗传算法的实际效果。关键词：遗传算法，适应度函数，图像识别遗传算法及其应用IIABSTRACTThe genetic algorithm is a kind of searching method which simulates the natural evolution. It is simple and easy to implement, especially it do not need the special field knowledge, so it has been using in very broad fields. Now the genetic algorithm has got a lot of fruits, and more and more scholars begin to pay attention on it.After brief introducted the genetic algorithm and studyed the history of the development status and biology, mathematical basis, we brought out the basic genetic algorithm concepts and principles, analysised the genetic algorithm to achieve the basic technology. Such as: coding, fitness function, genetic algorithm of the three major genetic manipulation, and other parameters of the rules. Finally, introduced a genetic algorithm procedures based on the principles of design, programming a genetic algorithm in the application of image recognition, in practice, we test the practical effects of genetic algorithm.Key word：genetic algorithm，Fitness function，image recognition遗传算法及其应用III引言当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中的一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。制造机器智能一直是人类的梦想，人们为此付出了巨大的努力。近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对人工智能提出了强烈批判，对人工智能的可能性提出了质疑。在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准优解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。遗传算法(Genetic Algorithm GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。自1985年以来。国际上已召开了多次遗传算法的学术会议和研讨会。国际遗传算法学会组织召开的ICGA(International Conference on Genetic Algorithms)会议FOGA(Workshop -on Foundation of Genetic Algorithms)会议。为研究和应用遗传算法提供了国际交流的机会。作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择，来指导学习和确定搜索的方向。近年来，遗传算法已被成功地应用于工业、经济管理、交通运输、工业设计等不同领域。解决了许多问题。例如：可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。遗传算法及其应用1第一章 绪论1.1 遗传算法的发展历史与研究现状20 世纪 60 年代，美国 Michigan 大学的 John Holland 教授开始研究自然和人工系统的自适应行为，在这些研究中，他试图发展一种用于创造通用程序和机器的理论，使得通用程序和机器具有适应任意环境的能力。他意识到用群体方法搜索以及选择、交换等操作策略的重要性。在六十年代中期至七十年代末期，基于语言智能和逻辑数学智能的传统人工智能十分兴盛，而基于自然进化的思想则遭到怀疑和反对，Holland 及其数位博士生仍坚持了这一方向的研究。Bagley 发明“遗传算法”一词，并发表了第一篇有关遗传算法应用的论文，在他开创性的博士论文中采用双倍体编码，发展了与目前类似的复制、交换、突变、显性、倒位等基因操作，他还敏锐地察觉到防止早熟收敛的机理，并发展了自组织遗传算法的概念。与此同时，Rosen-berg 在他的博士论文中进行了单细胞生物群体的计算机仿真研究，对以后函数优化的研究颇有启发，并发展了自适应交换策略。Cavicohio 1970 年研究了基于遗传算法的子程序选择和模式识别问题，在模式识别问题上，采用整数编码，检索空间很大，他提出了以预选择策略保证群体多样性，对遗传算法参数进行中心控制的方法。同年，Weinberg 研究了生物体的计算机仿真，他的贡献在于提出运用多层遗传算法来进行遗传算法的参数自优化。1968 至 1971 年，Holland 提出了重要的模式理论，建议采用二进制编码。与前面几位博士不同，Holland 首次采用二进制编码来研究函数优化问题，并指出了运用 Gray码的一些优点，他研究了从生物系统引申出的各种不同的选择和配对策略。1972 年，Frantz 的博士论文中研究了许多新的问题，如基因非线性(异位显性)现象，基因迁移操作及多点交换操作等，由于没有设计出诸如 GAeception 之类合适的非线性优化问题，实验结果并不具备说服力。这一年，Holland 的模式理论也渐趋成熟，但在编码策略上出现了至今仍执争论的二派，一派根据模式定理建议用尽量少的符号编码，一派以数值优化计算的方便和精度为准采用一个基因一个参数的方法，并把相应的基因操作改造成适合实数操作的形式，Bosworth，Zoo 和 Zeigler 是后者的开创者。1975 年竖遗传算法及其应用2立了遗传算法发展史上的两块里程碑，一是 Holland 出版了经典著作Adaptation in Nature andArtificial System ，该书是作者十几年间许多思想及其实现的结晶，详细阐述了遗传算法的理论，并为其奠定了数学基础，发展了一整套模拟生物自适应系统的理论；二是 De Jong 完成了具有指导意义的博士论文An Analysis of the Behavior of a Class of Genetic Adaptive System ，他深入领会了模式定理并做了大量严格的计算实验，给出了明确的结论，他还建立了著名的 De Jong 五函数测试平台，定义了性能评价标准，并以函数优化为例，对遗传算法的六种方案的性能及机理进行了详细实验和分析，他的工作成为后继者的范例并为以后的广泛应用奠定了坚实的基础。为克服 De Jong的轮盘赌(随机)选择操作中的随机误差，Brindle 于 1981 年在她的博士论文中研究了六种复制策略。进入八十年代，随着以符号系统模仿人类智能的传统人工智能暂时陷入困境，神经网络、机器学习和遗传算法等从生物系统底层模拟智能的研究重新复活并获得繁荣。Goldberg 在遗传算法研究中起着继往开来的作用，他在 1983 年的博士论文中第一次把遗传算法用于实际的工程系统煤气管道的优化，从此，遗传算法的理论研究更为深入和丰富，应用研究更为广泛和完善，自 1985 年起，遗传算法及其应用国际会议每二年召开一次，有关人工智能的会议和刊物上大多有遗传算法的专题，Goldberg 的课本，及其他学者的专著的出版有力地推动了遗传算法的传播。进入九十年代，以不确定性、非线性、时间不可逆为内涵，以复杂问题为对象的科学新范式得到学术界普遍认同，如广义进化综合理论。由于遗传算法能有效地求解属于 NPC 类型的组合优化问题及非线性多模型、多目标的函数优化问题，从而得到了多学科的广泛重视，一些学者也认识到求解复杂问题最优解是不现实的，故而寻求满意解，而遗传算法是最佳工具之一，生物进化的历史比任何数学证明都强有力，问题是遗传算法在吸收遗传学、进化论及分子生物学最新成果和在实验得到证明和证伪的同时本身也在进化。目前，遗传算法引起包括数学、物理、化学、生物学、计算机科学等领域的科学家的极大兴趣。遗传算法的研究领域和内容十分的广泛，如遗传算法的设计与分析，遗传算法的理论基础及其在各个领域的应用。随着理论的深入研究和应用领域的不断拓展，遗传算法必将取得更大的发展。遗传算法及其应用31.2 遗传算法的生物学基础1.2.1 生物的进化过程19世纪50年代。英国生物学家达尔文根据他对世界各地生物的考察结果和人工选择实验。提出了“生物进化论” 。1859年达尔文发表了物种起源巨著。提出了以自然选择为基础的生物进化论学说。根据达尔文的进化论，生物进化的发展来源于三种动力：遗传、变异和选择。 遗传就是子代总是保持和亲代的相似性，遗传性是一切生物所共有的特征。正是这种遗传性，使得生物能够把它的特性、性状传给后代，并在后代中保持相似。现代遗传学研究表明，生物都具有遗传性。遗传学的建立和发展有力地推动和促进了进化论，变异是子代和亲代有某些不相似的现象。即子代永远不会和亲代完全一样，变异是一切事物所具有的共同特征，是生物个体之间相互区别的基础。引起变异的原因主要是生活条件的影响，器官使用的不同及杂交。变异性为生物的进化发展创造了条件，选择决定了生物进化的方向，所谓选择是指生物具有保留和淘汰的特性，选择分为人工选择和自然选择。人工选择是在人为环境下把对人有利的生物保留下，把对人不利的个体淘汰掉；自然选择就是指生物在自然界的生存环境中适者生存，世界上所有形形色色的生物都是在自然选择的影响下、在悠久的岁月中形成的。自然选择的过程是通过生存斗争的过程来实现生存斗争的结果，优胜劣汰。这样就保证了生物去适应环境，通过不断地自然选择，那些有利于生存的变异就遗传下去，日积月累越来越大，逐步产生了新的物种。 生物的各项生命活动都有他的物质基础。生物的遗传和变异也不例外。遗传物质的主要载体为染色体。研究表明，染色体主要有脱氧核糖核酸和蛋白质，其中脱氧核糖核酸在染色体中含量稳定，结构相对稳定，能够自我复制，前后保持一定的连续性，能够产生可遗传的变异。因此它是主要的遗传物质。生物的性状遗传主要是通过染色体传递给后代。因此，基因是控制生物性状的遗传物质的功能和结构单位。生物变异与遗传一样，也是很复杂的，由遗传物质引起的变异称为遗传变异。它有三种来源：基因重组、基因变异和基因突变。基因重组是控制不同性状的基因的重新组合；基因变异是指基因内部的化学变化；基因突变的产生是在一定外界环境条件和生物内部因遗传算法及其应用4素的作用下，基因的分子结构发生改变的结果。每种生物染色体无论结构和数目都是相对恒定的。但在自然条件和人为条件的影响下染色体结构和数目都可以发生变化， 染色体数目的改变是染色体变异的一个重要方面。遗传算法正是借鉴生物自然选择和遗传机制的随机搜索算法。它之所以能够增强解决问题的能力，是因为自然演化过程本质就是一个学习与优化的过程。遗传算法通过模拟“优胜劣汰，适者生存”的规律激励好的结构，通过模拟孟德尔的遗传变异理论在迭代过程中保持已有的结构，同时寻找更好的结构。1.2.2 生物学对遗传算法的启示生物是在遗传的过程中保持物种性状的，而变异是生物在综合作用过程中不断向前发展和进化的动力，选择通过遗传和变异起作用，变异为选择提供资料。遗传巩固与积累选择资料，而选择则能控制变异与遗传的方向。使变异和遗传向着适应环境的方向发展。虽然生物进化论揭示了生物长期自然选择的进化发展规律。然而科学家从中受到了启迪，进化论的自然选择过程蓄含一种搜索和优化的先进思想。而将这种思想用于工程技术领域发展起来的遗传算法，为解决许多传统的优化问题提供了许多途径。1.3 遗传算法的数学基础遗传算法之所以能在众多优化问题中得到广泛应用且效果较好，必然有其理论上的机理。Holland 提出的模式定理和积木块假设即是遗传算法的理论基础。模式定理作为描述遗传算法动力学机理的基本定理，奠定了遗传算法的数学基础。1.3.1 模式理论定义1.1：模式是表示一些相似的模块，它描述了在某些位置上具有相似结构特征的个体在编码串的一个子集。为不失一般性，考虑二值字符集0,1，由此可产生通常的0,1字符串，为了方便描述一个模式，增加一个通配符“*” ，也称为无关符，用它来表示不确定字符，它既可代表字符集中的0，也可代表字符集中的1，并且可在字符集中的任意位置，这样，遗传算法及其应用5二值字符集0,1就扩展成三值字符集0，1，*。引入模式的概念后，我们可以看到一个串实际上隐含着多个模式，一个模式可以隐含在多个串中，不同的串之间通过模式而相互联系。定义1.2：在模式H中具有确定基因值的位置数目称为该模式的模式阶(Schema Order)，记为 O(H) 。如模式011 * 1*的模式阶为4，模式0*的模式阶为1。显然，一个模式的阶数越高，其样本个数越少，因而确定性越高。定义1.3：模式H中第一个确定基因值的位置和最后一个确定基因值的位置之间的距离称为该模式的模式定义长度(Schema Defining Length)或模式定义距，记为S(H)。如模式011 * 1*的定义距为4，而模式0*的定义距为0。在研究交叉算子对模式的作用时可以发现：对于单点交叉算子，模式1*0比模式10*更易被破坏，这两个模式具有相同的阶，为了描述这一性质，我们引入了模式定义距。定理1.1(模式定理)：在遗传算子选择、交叉和变异的作用下，具有低阶、短模式距以及平均适应度高于种群平均适应度的模式在子代中以指数级增长。模式定理从模式角度论证了N个初始种群在经过选择、交叉、变异算子后模式H的变化：()()()(,1),11oHCmfHmHttPpl（1.1）其中， 表示第 代种群 中模式所能匹配的样本的数量, ( )、 分(,1)tt别表示第 代所有模式 的平均适应度与种群平均适应度， 表示串的长度， 、t lcp分别表示交叉概率与变异概率。mp定理中的三项分别说明了GA运算中选择、交叉和变异对种群中模式数量的影响： (1)模式的增长(减少)，即样本数量的增加(减少)，依赖于模式的平均适应度与群体适应度之比，那些平均适应度高于种群平均适应度的将在下一代中得以增长，而那些平均适应度低于种群平均适应度的将在下一代中减少；（2）具有短模式距的模式经过交叉后样本的数量越多；（3）具有低阶的模式经过变异后 的生存率越大，它大约为：H。1(),1moHp:遗传算法及其应用6从定理可以简单地分析一下交叉概率P C和变异概率P m的作用，当其它值不变时，PC、P m越小，则模式 在下一代( 代)群体中的个体数量越大，即个体趋向相似和一H1t致，新个体的数量减少，从而使搜索范围减小，能快速收敛但也容易产生“早熟”现象；P C、P m增大，群体多样性增强，搜索范围扩大，但有可能破坏群体中好的模式，使收敛速度变慢。因此，在实际应用时，可参照该定理设置或调整P C、P m的值。作为指导遗传算法的基本理论，模式定理同时还对遗传算法作了如下的启示：（1）编码中根据模式定理，遗传过程中存活的都是长度短、阶次低、适应度高的模式，因此编码时应使所研究的主要性质用一长度短、阶次低的模式表示；而次要性质用其它模式表示。因为二进制字符串拥有的内涵(模式数目)比较大，编码时尽量使用二进制或字符变化少的字符串。（2）交叉操作中当亲代的优良模式介于字符串首尾之间时，如果采用一点交叉方式，它必然被破坏，在子代中就没法保留其优良模式，而相反，若采用两点交叉，其子代个体不仅保留原来亲代个体1的优良模式，而且兼容亲代个体2的优良模式，从而形成比原来更优良的模式。因此，在遗传算法中常使用该交叉方式，尤其是当字符串长度比较大的时候。1.3.2 积木块假设符合模式定理的这类模式在GA中非常有用，我们将它定义为积木块。GA模拟了生物的进化机制，模式定理则提供了一种解释这种机理的数学工具。定