遗传算法的作用.doc

遗传算法的应用一、什么是遗传算法？ 遗传算法是一种全局概率搜索优化算法。遗传算法( Gnectci Algortihms) ，是一种模拟自然界生物进化过程的全局随机搜索算法，由美国Mcihigna大学的Hollnad 教授于60 年代首先提出。它将计算机科学与进化论思想有机结合起来，借助于生物进化机制与遗传学原理，根优胜劣汰和适者生存的原则，通过模拟自然界中生物群体由低级、简单到高级、复杂的生物进化过程，使所要解决的问题从初始解逐渐逼近最优解或准最优解。作为一种新的全局优化搜索算法，遗传算法因其简单易用，对很多优化问题能够较容易地解出令人满意的解，适用于并行分布处理等特点而得到深入发展和广泛应用，已在科学研究和工程最优化领域中展现出独特魅力.二、遗传算法的发展：从20世纪40年代，生物模拟就成为了计算科学的一个组成部分；20世纪50年代中期创立了仿生学；进入60年代后，美国密切根大学教授Holland及其学生创造出遗传算法。三、遗传算法的特点：遗传算法作为具有系统优化、适应和学习的高性能计算和建模方法的研究渐趋成熟。遗传算法具有进化计算的所有特征，同时又具有自身的特点：（1）搜索过程既不受优化函数的连续性约束，也没有优化函数导数必须存在的要求。（2）遗传算法采用多点搜索或者说是群体搜索，具有很高的隐含并行性，因而可以提高计算速度。（3）遗传算法是一种自适应搜索技术，其选择、交叉、变异等运算都是以一种概率方式来进行，从而增加了搜索过程的灵活性，具有较好的全局优化求解能力。（4）遗传算法直接以目标函数值为搜索信息，对函数的性态无要求，具有较好的普适性和易扩充性。（5）遗传算法更适合大规模复杂问题的优化。四、遗传算法的原理和方法：（1） 编码：编码是把一个问题的可行解从其解空间转换到GA 所能处理的搜索空间的转换方法。而解码是由GA 解空间向问题空间的转换。编码机制直接影响着算法的整体性能，也决定了种群初始化和各种遗传算子的设计等各种过程。常用的编码方案有：二进制编码、Gray 编码和实数编码等。（2） 种群的初始化：种群的初始化是指如何生成第一代初始种群。对于二进制编码机制，初始化就是生成多个二进制数串；对于实数编码机制，初始化是指生成多个实数数串。（3） 适应度函数：适应度是用来衡量群体中各个个体在优化计算中能达到或接近于或有助于找到最优解的优良程度。适应度较高的个体遗传到下一代的概率就较大；反之遗传到下一代的概率就相对较小。度量个体适应度的函数称为适应度函数，是根据目标函数确定的，用于区分群体中个体好坏的标准，是算法演化过程的驱动力。（4） 选择算子：选择算子是从一个旧种群选择生命力顽强的个体位串进行复制，从而产生新种群的过程。不同的选择操作会导致不同的选择效果，较大的选择压力将会使当前种群中的最优个体具有较高的复制数目，算法会以较快的速度收敛，容易出现“早熟”问题。相反，较小的选择压力能使种群的保持多样性，有利于跳出局部最优，收敛于全局最优点，但缺点是收敛速度慢，效率低下。常用的选择算子有：轮盘赌选择、基于排序的选择、局部竞争选择、最佳个体保存选择和Boltzmann 选择等。（5） 交叉算子：交叉算子是指两个相互配对的染色体按照某种方式相互交换自身的部分基因片，从而构成两个新个体的过程。交叉算子不仅要考虑生成更多不同的个体，保持种群的多样性；还要避免破坏种群中的优良个体，加快种群的收敛速度，才能使种群的多样性和收敛性达到和谐的统一。常用的交叉算子有：单点交叉、多点交叉、均匀交叉和算术交叉等。（6） 变异算子：变异是指父代染色体中的某些基因片，以相对较小的概率发生随机改变的操作过程。变异的概率决定了种群中个体发生变异的机会大小，如果制定过高，容易破坏种群中已有的优良个体结构；如果制定过低，则产生新个体的速度慢，收敛速度慢，甚至可能陷入局部最优。常用的变异算子有：倒位变异、交换变异和插入变异等。研究表明，将多种变异算子在交叉使用或者按照一定的概率进行分配使用，会带来较好的效果。五、遗传算法实现的基本流程：遗传算法的早期研究，其基本实现步骤如下：（1） 确定种群规模、交叉概率、变异概率以及算法终止条件（2） 以一定的方式产生初始种群（3） 计算种群中个体的适应度（4） 对当前种群实施选择、交叉、变异操作、产生新种群（5） 进化终止条件判断，若满足终止条件，则进化终止，输出优化结果，否则转到步骤（3）。具体流程如下图1所示。图1 遗传算法基本流程图六、遗传算法的三种基本操作：1、选择 选择即是在种群中选择一个个体，它是随机映射: .特别地，按照概率：其中N为种群规模，表示个体 的适应值，为选择压，适应值大的选中概率越大，复制多，反之相反。常见选择方法的优劣比例选择的问题：记为第t代个体x出现的概率，其中x为任一个体，则 其中为种群平均适应值。一般不是常数，种群平均适应值是随时间变化的量。从而实际计算中的常值计算存在偏差。比例选择应用广泛，但存在一些不合理之处。1.对选择函数有要求。2.容易过早收敛而得到局部最优解。3.对于较平均的现象，则会出现算法变慢的现象。比例选择的常见问题还是选择压的问题。另外，如其他选择，排序选择具有一致的、可控的选择压。联赛选择操作既能使好的个体得到较多繁殖的机会，又能防止其繁殖过多的个体。稳态选择比起线性排序选择来说有较高的增长率，这容易导致早熟。稳态选择一般适用大种群规模或多种群进化策略。2、交叉交叉是母体的操作，是母体空间到母体空间的映射，记做（1）单点交叉：等概率地随机确定一个基因位置作为交叉点，再把一对母体从交叉点分为前后两部分，交换两个个体的后部分，得到两个新个体。若以概率交换两个个体的后半部分，得到两个新个体，称为单点随机交叉，称为交叉概率。如果确定两个基因位置将一对母体分成三部分，交换中间部分，则称为两点交叉。同样有两点交叉与两点随机交叉之分。（2）一致随机交叉：独立地以概率把母体的一个个体想要分量交换为第二母体相应分量，从而得到交叉结果。其数学表述如下：对于长度为l的两个个体、,设置长度为l的二值交叉串,定义：,当交叉字串t以一定概率选取，上式的交叉也以一定概率发生时，称为一致随机交叉，记为。3、变异变异是个体空间到个体空间的随机映射，其独立地以概率改变个体分量的取值，称作变异概率。单点变异：等概率地随机确定一个基因，改变个体分量的取值。单点随机变异：等概率地随机确定一个基因，以概率改变个体分量的取值。一致变异：等概率地对个体的每一个基因，改变个体分量的取值。一致随机变异：等概率地对个体的每一个基因以概率改变个体分量的取值。数学表达式如下：对于个体，设置二进制变异字串,则的一致变异定义为：其中分别表示个体、的第i位基因值，表示二进制变异字串t的第i位值。当变异字串一定概率选取，上式的变异也以一定的概率发生时，称为一致随机变异。变异模仿自然界汇总的基因突变，保证算法能搜索到问题解空间的每一点，从而使遗传算法具有全局寻优能力。七、遗传算法应用实例遗传算法在可靠性中的应用：如图：受力示意图各单元截面面积与惯性矩的关系为（i=1,2）,弹性模量均为，单元截面积以及外荷载为随机变量。如果节点3的水平控制位移u为最大变形控制，允许的最大位移：求解该框架结构的可靠度指标。变量编码采用3个9位二进制编码串表示框架结构的3个变量。其中，的取值为0.2000.400，的取值为0.1000.300，的取值为10.0050.00KN，均用二进制编码串000000000111111111对应表示。将编码串连成一个27位长的二进制编码串，构成了框架结构的软色体编码，则解空间和遗传算法的搜索空间具有一一对应关系。变量解码解码和编码的过程是互逆的。所以解码时，应先将二进制编码串根据编码时所表示的设计变量个数切断为若干个二进制编码串，然后将其转换为十进制代码，最后用解码公式算出变量X。编码为的个体，十进制代码为，其解码公式。其中分别表示参数的最大值和最小值。因此可得到： 结构的设计变量A1，A2，p通过上式可计算得到。 利用MATLAB 根据改进遗传算法的优化程序，对框架结构的可靠度进行编程，可得到可靠性结果。遗传算法正日益和神经网络、模糊推理以及混沌理论等其他智能计算方法相互渗透和结合，起到取长补短的作用。这对开拓新的智能计算技术将具有重要意义。八、遗传算法的应用： (1) 函数优化：是GA的经典应用领域，也是对GA进行性能评价的常用算例，对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解，GA却可以得到较好的结果。（2） 组合优化：随问题规模的扩大，搜索空间急剧扩大，对这类复杂问题，实践证明，GA对于组合优化的NP完全问题非常有效。 (3) 生产调度问题：GA已成为解决复杂调度问题的有效工具，在单件生产车间调度、流水线生产车间调度、生产规模、人物分配等方面都得到了有效的应用。 (4) 自动控制：GA在自动控制领域中的应用日益增加，并显示了良好的效果。如在参数辨识、人工神经网络的结构优化设计和权值学习，都显示了GA的应用优势。 (5) 机器人智能控制：GA是源自于对人工自适应系统的研究，已经在移动机器人路径规划、关节机器人运动轨迹规律、机器人逆运动学求解、细胞机器人的结构优化和行动协调等方面得到研究和应用。 (6) 图像处理和模式识别在图像处理过程中，如扫描、特征提取、图像分割等不可避免的会产生一些误差。目前，GA已在图像恢复、图像边缘特征提取、几何形状识别等方面得到了应用。（7） 人工生命人下生命是用计算机、机械等人下媒体模拟或构造出的具有自然生物系统特有行为的人造系统。自组织能力和自学习能力是人下生命的两大主要特征。人下生命与遗传算法有着密切的关系。基于遗传算法的进化模型是研究人下生命现象的重要基础理论。虽然人下生命的研究尚处于启蒙阶段，但遗传算法已在其进化模型、学习模型、行为模型、自组织模型等方面显示出了初步的应用能力，并且必将得到更为深入的应用和发展。人工生命与遗传算法相辅相成，遗传算法为人下生命的研究提供一个有效的下具，人下生命的研究也必将促进遗传算法的进一步发展。（8） 遗传编程1989年，美国Standford大学的Koza教授发展了遗传编程的概念,其基木思想是:采用树型结构表示计算机程序,运用遗传算法的思想,通过自动生成计算机程序来解决问题。虽然遗传编程的理论尚米成热,应用也有一此限制,但它已成功地应用于人工智能、机器学习等领域。目前公开的遗传编程实验系统有十多个。例如，Koza开发的ADF系统，While开发的GPELST系统等。（9） 机器学习学习能力是高级自适应系统所具备的能力之一，基于遗传算法的机器学习，特别是分类器系统，在很多领域中都得到了应用。例如，遗传算法被用于学习模糊控制规则，利用遗传算法来学习隶属度函数，从而更好地改进了模糊系统的性能；基于遗传算法的机器学习可用来调整人工神经网络的连接权，也可用于人工神经网络结构优化设计；分类器系统也在学习式多机器人路径规划系统中得到了成功的应用。（10） 数据挖掘数据挖掘是近几年出现的数据库技术，它能够从大型数据库中提取隐含的、先前未知的、有潜在应用价值的知识和规则。许多数据挖掘问题可看成是搜索问题，数据库看作是搜索空间，挖掘算法看作是搜索策略。因此，应用遗传算法在数据库中进行搜索，对随机产生的一组规则进行进化.直到数据库能被该组规则覆盖，从而挖掘出隐含在数据库中的规则。Sunil已成功地开发了一个基于遗传算法的数据挖掘下具。利用该工具对两个飞机失事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之一。参考文献1.人工智能专著(日)沟口理一郎,石田亨编；卢伯英译北京：科学出版社，20032. 自适应遗传算法理论及应用专著