遗传算法基本理论及实例.doc

目录_一、遗产算法的由来1二、遗传算法的国内外研究现状2三、遗传算法的特点3四、遗传算法的流程5五、遗传算法实例9六、遗传算法编程13七、总结15附录一：运行程序16..遗传算法基本理论与实例一、遗产算法的由来遗传算法〔Genetic Algorithm,简称GA起源于对生物系统所进行的计算机模拟研究20世纪40年代以来,科学家不断努力从生物学中寻求用于计算科学和人工系统的新思想、新方法很多学者对关于从生物进化和遗传的激励中开发出适合于现实世界复杂适应系统研究的计算技术——生物进化系统的计算模型,以及模拟进化过程的算法进行了长期的开拓性的探索和研究John H.Holland教授及其学生首先提出的遗传算法就是一个重要的发展方向遗传算法借鉴了达尔文的进化论和孟德尔、摩根的遗传学说按照达尔文的进化论,地球上的每一物种从诞生开始就进入了漫长的进化历程生物种群从低级、简单的类型逐渐发展成为高级复杂的类型各种生物要生存下去及必须进行生存斗争,包括同一种群内部的斗争、不同种群之间的斗争,以及生物与自然界无机环境之间的斗争具有较强生存能力的生物个体容易存活下来,并有较多的机会产生后代；具有较低生存能力的个体则被淘汰,或者产生后代的机会越来越少。

直至消亡达尔文把这一过程和现象叫做"自然选择,适者生存"按照孟德尔和摩根的遗传学理论,遗传物质是作为一种指令密码封装在每个细胞中,并以基因的形式排列在染色体上,每个基因有特殊的位置并控制生物的某些特性不同的基因组合产生的个体对环境的适应性不一样,通过基因杂交和突变可以产生对环境适应性强的后代经过优胜劣汰的自然选择,适应度值高的基因结构就得以保存下来,从而逐渐形成了经典的遗传学染色体理论,揭示了遗传和变异的基本规律遗传算法由美国的John H.Holland教授1975年首先提出,其主要特点是直接对结构对象进行操作,不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法,能自动获取和指导优化的搜索空间,自适应地调整搜索方向,不需要确定的规则遗传算法的这些性质,已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域它是现代有关智能计算中的关键技术二、遗传算法的国内外研究现状遗传算法的鼻祖是美国Michigan大学的Holland教授及其学生他们受到生物模拟技术的启发,创造了一种基于生物遗传和进化机制的适合于复杂系统优化的自适应概率优化技术——遗传算法。

1967年,Holland的学生Bagley在其博士论文中首次提出了"遗传算法"一词,他发展了复制、交叉、变异、显性、倒位等遗传算子,在个体编码上使用双倍体的编码方法Holland教授用遗传算法的思想对自然和人工自适应系统进行了研究,提出了遗传算法的基本理论——模式定理〔Schema Theorem并于1957年出版了第一本系统论述遗传算法和人工自适应系统的专著《Adaptation in Natural and Artificial Systems》20世纪80年代,Holland教授实现了第一个基于遗传算法的机器学习系统,开创了遗传算法的机器学习的新概念1975年,De Jong基于遗传算法的思想在计算机上进行了大量的纯数值函数优化计算实验,建立了遗传算法的工作框架,得到了一些重要且具有指导意义的结论1989年,Goldberg出版了《Genetic Algorithm in Search,Optimization and Machine Learning》一书,系统地总结了遗传算法的主要研究成果,全面完整的论述了遗传算法的基本原理及其应用1991年,David出版了《Handbook of Genetic Algorithms》一书,介绍了遗传算法在科学计算、工程技术和社会经济中的大量实例。

1992年,Koza将遗传算法应用于计算机程序的优化设计及自动生成,提出了遗传编程〔Genetic Programming,简称GP的概念在控制系统的离线设计方面遗传算法被众多的使用者证明是有效的策略例如,Krishnakumar和Goldberg以及Bramlette和Gusin已证明使用遗传优化方法在太空应用中导出优异的控制器结构比使用传统方法如LQR和Powell〔鲍威尔的增音机设计所用的时间要少〔功能评估Porter和Mohamed展示了使用本质结构分派任务的多变量飞行控制系统的遗传设计方案与此同时,另一些人证明了遗传算法如何在控制器结构的选择中使用从遗传算法的整个发展过程来看,20世纪70年代是兴起阶段,20世纪80年代是发展阶段,20世纪90年代是高潮阶段遗传算法作为一种实用、高效、鲁棒性强的优化技术,发展极为迅速,已引起国内外学者的高度重视近些年来,国内外很多学者在遗传算法的编码表示、适应度函数、遗传算子、参数选择、收敛性分析、欺骗问题和并行遗传算法上做出了大量的研究和改进还有很多学者将遗传算法和其他只能算法结合,进一步提高局部搜索能力在遗传算法的应用上也有很多改进由于遗传算法具有全局并行搜索、简单通用、鲁棒性强等优点,使得遗传算法广泛地应用于计算机科学、自动控制、人工智能、工程设计、制造业、生物工程和社会科学等领域。

针对遗传算法的一些问题,还有一些问题需要进一步的探究,将大大促进遗传算法理论和应用的发展,遗传算法必将在智能计算领域中展现出更加光明的前景三、遗传算法的特点遗传算法是一种借鉴生物界自然选择和自然遗传机制的随机搜索算法它与传统的算法不同,大多数古典的优化算法是基于一个单一的度量函数〔评估函数的梯度和较高次统计,以产生一个确定性的试验解序列；遗传算法不依赖梯度信息,而是通过模拟自然进化进程来搜索最优解,它利用某种编码技术,作用于称为染色体的数字串,模拟由这些串组成的群体的进化过程遗传算法通过有组织的、随机的信息交换来重新组合那些适应性好的串,生成新的串的群体遗传算法有以下优点：〔1对可行解表示的广泛性遗传算法的处理对象不是参数本身,而是针对那些通过参数集进行编码的基因个体,此编码操作使得遗传算法可以直接对结构对象进行操作所谓结构对象,泛指集合、序列、矩阵、树、链、表等各种一维或二维甚至多维结构形式的对象这一特点使得遗传算法具有广泛的应用领域比如通过对连接矩阵的操作,遗传算法可用来对神经网络或自动机的结构或参数加以优化；通过对集合的操作,遗传算法可实现对规则集合和知识库的精炼而达到高质量的机器学习目的；通过对树结构的操作,用遗传算法可得到用于分类的最佳决策树；通过对任务序列的操作,遗传算法可用于任务规划,而通过对操作序列的处理,可自动构造顺序控制系统。

〔2群体搜索特性许多传统的搜索方法都是单点搜索,这种点对点的搜索方法,对于多峰分布的搜索空间常常会陷于局部的某个单峰的极值点相反,遗传算法采用的是同时处理群体中多个个体的方法,即同时对搜索空间中的多个解进行评估这一特点使遗传算法具有较好的全局搜索性能,也使得算法本身易于并行化 〔3不需要辅助信息遗传算法仅用适应度函数来的数值来评估基因个体,并在此基础上尽心遗传操作更重要的是,遗传算法的适应度函数不仅不受连续可微的约束,而且其定义域可以任意设定对适应度函数的唯一要求是,编码必须与可行解空间对应,不能有死码由于限制条件的缩小,使得遗传算法的应用范围大大扩展〔4内在启发式随机搜索特性遗传算法不是采用确定性规则,而是采用概率的变迁规则来指导它的搜索方向概率不仅仅是作为一种工具来引导其搜索过程朝着搜索空间的更优化的解区域移动的虽然看起来它是一种盲目搜索方法,实际上它有明确的搜索方向,具有内在的并行搜索机制〔5遗传算法在搜索过程中不容易陷入局部最优,即时在所定义的适应度函数是不连续的、非规则的或有噪声的情况下,也能以很大的概率找到全局最优解〔6遗传算法采用自然进化机制来表现复杂的现象,能够快速可靠地解决求解非常困难的问题。

〔7遗传算法具有固有的并行性和并行计算的能力〔8遗传算法具有可扩展性,易于同别的技术混合使用遗传算法作为一种优化算法,也有它自身的局限性：〔1编码不规范及编码存在表示的不准确性〔2单一的遗传算法编码不能全面地将优化问题的约束表示出来考虑约束的一个方法就是对不可行解采用阈值,这样,计算的时间必然增加〔3遗传算法通常的效率比其他传统的优化方法低〔4遗传算法容易出现过早收敛〔5遗传算法对算法的精度、可信度、计算复杂性等方面,还没有有效的定量分析方法遗传算法的基本内容如下：个体和种群个体就是模拟生物个体而对问题中的对象〔一般就是问题的解的一种称呼,一个个体也就是搜索空间中的一个点种群就是模拟生物种群而由若干个体组成的群体,它一般是整个搜索空间的一个很小的子集适应度与适应度函数适应度就是借鉴生物个体对环境的适应程度,而对问题中的个体对象所设计的表征其优劣的一种测度适应度函数〔fitness function就是问题中的全体个体与其适应度之间的一个对应关系它一般是一个实值函数该函数就是遗传算法中指导搜索的评价函数染色体与基因染色体〔chromosome就是问题中个体的某种字符串形式的编码表示。

字符串中的字符也就称为基因〔gene例如个体上9,染色体的表示形式是1001,0和1是染色体上的基因遗传操作也称为遗传算子,就是关于染色体的运算遗传算法中有三种遗传操作：选择-复制,交叉和变异四、遗传算法的流程遗传算法在整个进化过程中的遗传操作是随机的,但它所呈现出的特性并不是完全搜索,它能有效地利用历史信息来推测下一代期望性能有所提高的寻优点集这样一代代的不断进化,最后收敛到一个最适应环境的个体上,求得问题的最优解遗传算法所涉及的五大要素是：参数编码、初始种群的设定、适应度函数的设计、遗传操作的设计和控制参数的设定流程如图1所示图1 遗传算法基本流程简单遗传算法的运行过程为一个典型的迭代过程,其必须完成的工作内容和基本步骤如下：1选择编码策略,把参数集合X和域转换为位串结构空间S2定义适应度函数 3确定遗传策略,包括选择群体大小n,选择、交叉、变异方法,以及确定交叉概率 、变异概率 等遗传参数4随机初始化生成种群P5计算群体中个体位串解码后的适应度值 6按照遗传策略,运用选择、交叉和变异算子作用与群体,形成下一代群体7判断群体性能是否满足某一目标,或者已完成预定迭代次数,不满足则返回步骤6,或者修改遗传策略再返回步骤6。

下面对基本步骤进行分解,进一步详细介绍流程中一些细节编码表示在许多问题求解中,编码是遗传算法中首要解决的问题,对算法的性能有很重要的影响Holland提出的二进制编码是遗传算法中最常用的一种编码方法,它采用最小字符编码原则, 编/解码操作简单易行,利于交叉、变异操作的实现,也可以采用模式定理对算法进行理论分析但二进制编码用于多维、高精度数值问题优化时,不能很好地克服连续函数离散化时的映射误差；不能直接反映问题的固有结构,精度不高,并且个体长度大、占用内存多针对二进制编码存在的不足,人们提出了多种改进方法,比较典型的有以下几种：〔1格雷码编码为了克服二进制编码在连续函数离散化时存在的不足,人们提出了用格雷码进行编码的方法,它是二进制编码的变形格雷码不仅具有二进制编码的一些优点,而且能够提高遗传算法的局部搜索能力假设有一个二进制编码为,其对应的格雷码为,则〔2实数编码该方法适合于遗传算法中表示范围较大的数,使遗传算法更接近问题空间,避免了编码和解码的过程它便于较大空间的遗传搜索,提高了遗传算法的精度要求；便于设计专门问题的遗传算子；便于算法与经典优化方法的混合。