遗传算法的由来及应用.doc

遗传算法的由来及应用经验分享 2009-05-31 23:42 阅读157评论0 字号： 大大 中中 小小 遗传算法的研究前背景和发展历史 1967年，Holland的学生J.D.Bagley在博士论文中首次提出“遗传算法（GeneticAlgorithms）”一词。此后，Holland指导学生完成了多篇有关遗传算法研究的论文。1971年，R.B.Hollstien在他的博士论文中首次把遗传算法用于函数优化。1975年是遗传算法研究历史上十分重要的一年。这一年Holland出版了他的著名专著自然系统和人工系统的自适应（AdaptationinNaturalandArtificialSystems），这是第一本系统论述遗传算法的专著，因此有人把1975年作为遗传算法的诞生年。Holland在该书中系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极其重要的模式理论（schematheory）。该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。同年，K.A.DeJong完成了他的博士论文一类遗传自适应系统的行为分析（AnAnalysisoftheBehaviorofaClassofGeneticAdaptiveSystem）。该论文所做的研究工作，可看作是遗传算法发展进程中的一个里程碑，这是因为，他把Holland的模式理论与他的计算实验结合起来。尽管DeJong和Hollstien一样主要侧重于函数优化的应用研究，但他将选择、交叉和变异操作进一步完善和系统化，同时又提出了诸如代沟（generationgap）等新的遗传操作技术。可以认为，DeJong的研究工作为遗传算法及其应用打下了坚实的基础，他所得出的许多结论，迄今仍具有普遍的指导意义。 进入八十年代，遗传算法迎来了兴盛发展时期，无论是理论研究还是应用研究都成了十分热门的课题。1985年，在美国召开了第一届遗传算法国际会议（InternationalConferenceonGeneticAlgorithms，ICGA），并且成立国际遗传算法学会（InternationalSocietyofGeneticAlgorithms，ISGA），以后每两年举行一次。1989年，Holland的学生D.E.Goldberg出版了专著搜索、优化和机器学习中的遗传算法（GeneticAlgorithmsinSearch,Optimization,andMachineLearning）。该书总结了遗传算法研究的主要成果，对遗传算法及其应用作了全面而系统的论述。同年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计(geneticprogramming,GP)方法，成功地解决了许多问题。 在欧洲，从1990年开始每隔一年举办一次ParallelProblemSolvingfromNature学术会议，其中遗传算法是会议主要内容之一。此外，以遗传算法的理论基础为中心的学术会议还有FoundationsofGeneticAlgorithms，该会也是从1990年开始隔年召开一次。这些国际会议论文，集中反映了遗传算法近些年来的最新发展和动向。 1991年，L.Davis编辑出版了遗传算法手册（HandbookofGeneticAlgorithms），其中包括了遗传算法在工程技术和社会生活中的大量应用实例。 1992年，Koza发表了他的专著遗传程序设计:基于自然选择法则的计算机程序设计”。1994年，他又出版了遗传程序设计，第二册:可重用程序的自动发现深化了遗传程序设计的研究，使程序设计自动化展现了新局面。有关遗传算法的学术论文也不断在ArtificialIntelligence、MachineLearning、Informationscience、ParallelComputing、GeneticProgrammingandEvoluableMachinesIEEETransactionsonNeuralNetworks,IEEETransactionsonSignalProcessing等杂志上发表。1993年，MIT出版社创刊了新杂志EvolutionaryComputation。1997年，IEEE又创刊了TransactionsonEvolutionaryComputation。AdvancedComputationalIntelligence杂志即将发刊，由模糊集合创始人L.A.Zadeh教授为名誉主编。目前，关于遗传算法研究的热潮仍在持续，越来越多的从事不同领域的研究人员已经或正在置身于有关遗传算法的研究或应用之中。 当前科学技术正进入多学科互相交叉、互相渗透、互相影响的时代，生命科学与工程科学的交叉、渗透和相互促进是其中一个典型例子，也是近代科学技术发展的一个显著特点。遗传算法的蓬勃发展正体现了科学发展的这一特点和趋势。 制造机器智能一直是人类的梦想，人们为此付出了巨大的努力。人工智能技术的出现，就是人们得到的成果。但是，近年来，随着人工智能应用领域的不断拓广，传统的基于符号处理机制的人工智能方法在知识表示、处理模式信息及解决组合爆炸等方面所碰到的问题已变得越来越突出，这些困难甚至使某些学者对强人工智能提出了强烈批判，对人工智能的可能性提出了质疑。 众所周知，在人工智能领域中，有不少问题需要在复杂而庞大的搜索空间中寻找最优解或准优解。像货朗担问题和规划问题等组合优化问题就是典型的例子。在求解此类问题时，若不能利用问题的固有知识来缩小搜索空间则会产生搜索的组合爆炸。因此，研究能在搜索过程中自动获得和积累有关搜索空间的知识，并能自适应地控制搜索过程，从而得到最优解或准有解的通用搜索算法一直是令人瞩目的课题。遗传算法就是在这种背景下产生并经实践证明特别有效的算法。 遗传算法(GeneticAlgorithm,GA)是近年来迅速发展起来的一种全新的随机搜索与优化算法,其基本思想是基于Darwin的进化论和Mendel的遗传学说。该算法由密执安大学教授Holland及其学生于1975年创建。此后，遗传算法的研究引起了国内外学者的关注。自1985年以来.国际上已召开了多次遗传算法的学术会议和研讨会.国际遗传算法学会组织召开的ICGA(InternationalConferenceonGeneticAlgorithms)会议和FOGA(WorkshoponFoundationofGeneticAlgorithms)会议。为研究和应用遗传算法提供了国际交流的机会。 作为一种通用的问题求解方法，遗传算法采用简单的编码技术来表示各种复杂的结构并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。 近年来，遗传算法已被成功地应用于下业、经济答理、交通运输、工业设计等不同领域.解决了许多问题。例如，可靠性优化、流水车间调度、作业车间调度、机器调度、设备布局设计、图像处理以及数据挖掘等。本文将从遗传算法的理论和技术两方而概述目前的研究现状。描述遗传算法的主要特点、基木原理以及各种改进算法，介绍遗传算法的程序设计。 遗传程序设计是借鉴生物界的自然选择和遗传机制，在遗传算法的基础上发展起来的搜索算法，它己成为进化计算的一个新分支。在标准的遗传算法中，由定长字符串(问题的可行解)组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解。遗传程序设计运用遗传算法的思想，常采用树的结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法。 把遗传算法和计算机程序结合起来的思想出现在遗传算法中，Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程序上。近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术它己经与遗传算法并驾齐驱。1996年，举行了第1次遗传程序设计国际会议，该领域己引起越来越多的相关学者们的兴趣。遗传算法简介遗传算法(GeneticAlgorithm，简称GA)是一种基于进化论优胜劣汰、适者生存的物种遗传思想的搜索算法。本世纪50年代初，由于一些生物学家尝试用计算机模拟生物系统，从而产生了GA的基本思想。美国密执根大学的霍勒德（J.H.Holland）于70年代初提出并创立了遗传算法。遗传算法作为一种解决复杂问题的崭新的有效优化方法，近年来得到了广泛的实际应用，同时也渗透到人工智能、机器学习、模式识别、图像处理、软件技术等计算机学科领域。GA在机器学习领域中的一个典型应用就是利用GA技术作为规则发现方法应用于分类系统。遗传算法将个体的集合群体作为处理对象，利用遗传操作交换和突变，使群体不断进化，直到成为满足要求的最优解。在霍勒德的GA算法中采用二进制串来表示个体。考虑到物种的进化或淘汰取决于它们在自然界中的适应程度，GA算法为每一个体计算一个适应值或评价值，以反映其好坏程度。因而，个体的适应值越高，就有更大的可能生存和再生，即它的表示特征有更大的可能出现在下一代中。遗传操作交换旨在通过交换两个个体的子串来实现进化；遗传操作突变则随偶地改变串中的某一（些）位的值，以期产生新的遗传物质或再现已在进化过程中失去的遗传物质。霍勒德提出的遗传算法也称为简单遗传算法（simplegeneticalgorithm,SGA），是一种基本的遗传算法。SGA的处理过程如下：begin1.选择适当表示，生成初始群体；2.评估群体；3.While未达到要求的目标dobegin1.选择作为下一代群体的各个体；2.执行交换和突变操作；3.评估群体；endend因此，对于一个SGA算法来说主要涉及以下内容：编码和初始群体生成；群体的评价；个体的选择；交换；突变；1.编码和初始群体的生成GA的工作基础是选择适当的方法表示个体和问题的解（作为进化的个体）。SGA要求个体均以0、1组成的串来表示，且所有个体串都是等长的。实际上，可以任意指定有限元素组成的串来表示个体，而不影响GA的基本算法。对于同一问题，可以有不同的编码表示方法。由于遗传操作直接作用于所表示的串上，因而不同的表示方法对SGA的效率和结果都会有影响。从原理上讲，任何取值为整数（或其它有限可枚举的值）的变量，均可用有限长度的0、1串来表示，而任何取值为连续实数的变量也均可用有限长度的0、1串来近似表示。因此，对任何一个变量，均可在一定程度上用0、1串来表示（编码），而当问题的解涉及多个变量时，则可用各变量对应串的拼接（形成一个长串）来表示相应解。SGA处理的起始点并非一个个体，而是由一组个体所组成的群体。一般可用随机方法来产生初始群体，当然最好能考虑各个体的代表性和分布概率。2.群体的评价对群体中各个体的适应性评价常需直接利用待优化问题的目标函数。这一目标函数也可称为适应函数，个体选择（或再生）过程正是基于这一函数来评价当前群体中各个体的再生概率。3.个体的选择选择操作是对自然界适者生存的模拟。评价值（目标函数值）较大的个体有较高的概率生存，即在下一代群体中再次出现。一种常用的选择方法是按比例选择，即若个体i的适应值（目标函数值）是fi，则个体i在下一代群体中复制（再生）的子代个数在群体中的比例将为：fi/fi。其中，fi示指所有个体适应值之和。若当前群体与下一代群体的个数均维持在n，则每一个体i在下一代群体中出现的个数将是：n*fi/fi=fi/f,其中f=fi/n是群体评价的平均值。fi/f的值不一定是一个整数。为了确定个体在下一代中的确切个数，可将fi/f的小数部分视为产生个体的概率。如，若fi/f为2.7，则个体i有70的可能再生2+1=3个，而有30的可能只再生2个。SGA采用称为旋转盘（roulettewheel）的方法来产生各个体的再生数。方法是：每一个体均对应于旋转盘中的一个以园点为中心的扇形区域，区域角度为2*fi/fi，因而，各个体的区域角度之和等于2。然后随机产生一个0到2的值，根据该值所对应的区域，再生一个对应个体，直到产生的个体个数达到所需的数目，从而生成下一代的原始群体。这个群体还需进一步应用交换和突变操作。4.交换交换是GA中最主要的遗传操作，其工作于选择过程结束后产生的下一代群体。交换操作应用于从这一群体中随机选择的一系列个体对（串对）。SGA采用的是单点交换。设串长为L，交换操作将随机选择一个交换点（对应于从1到L-1的某个位置序号），紧接着两串交换点右边的子串互换，从而产生了两个新串。例如，设1，2为要交换的串，交换点被随机选择为7（串长为10）。1100001111121111111011交换得新串1，2：1100001101121111111111当然，并非所有选中的串对都会发生交换。这些串对发生交换的概率是Pc。Pc为事先指定的01之间的值，称为交换率。5.突变另一种遗传操作是突变，它一般在交换后进行。突变操作的对象是个体（即串），旨在改变串中的某些位的值，即由0变为1，或由1变为0。并非所有位都能发生变化，每一位发生变化的概率是Pm。Pm为事先指定的01之间的某个值，称为突变率。串中每一位的突变是独立的，即某一位是否发生突变并不影响其它位的变化。突变的作用是引进新的遗传物质或恢复已失去的遗传物质。例如，若群体的各串中每一位的值均为0，此时无论如何交换都不能产生有1的位，只有通过突变。遗传算法进化循环的一个例子设每一串的长度为10，共有4个串组成第一代群体（POP1），目标函数（适应函数）为各位值之和，因而函数值为010。POP1中四个串的适应值分别为：3，6，6，9，所以再生的比例个数为：0.5，1，1，1.5。若最后实际的再生个数为0，1，1，2，则产生选择后的群体POP2。下一步对POP2中各串配对，随机选择串1和串4为一对，串2和串3为另一对。群体POP1串适应值00000111003100001111160110101011611111110119群体POP2（选择后）串适应值10000111116011010101161111111011911111110119群体POP3（交换后）串适应值100001101150110101011611111110119111111111110群体POP4（突变后）串适应值10000110115011011101171111111011901111111119设交换率为0.5，即只有一对串发生交换，如串1和串4。若交换点随机选在位置7，因而交换后产生群体POP3。设突变率为0.05，即在POP3的40个位中，共有2个位发生突变，不妨设突变发生在串2的第6位和串4的第1位，从而产生群体POP4。注意，仅群体POP4代表新一代的群体（上一代为POP1），POP2和POP3只是一些进化中的中间群体。在SGA算法中，一般采用的群体大小为30到200，交换率为0.5到1，突变率为0.001到0.05。这些参数：群体大小、交换率、突变率，统称为GA的控制参数，应在算法运行前事先设定。当然，已有人研究了控制参数在算法运行中的自适应调整，以提高GA的灵活性。尽管遗传算法在实际优化问题中取得了很好的效果,目前对该算法尚无一个清楚完整的理论解释。霍勒德的图式理论(schematheory)和戈尔伯格（Goldberg，1989）的积木块假设仅在一定程度上解释了GA的工作原理。遗传算法的应用遗传算法提供了一种求解复杂系统优化问题的通用框架，它不依赖于问题的具体领域，对问题的种类有很强的鲁棒性。所以，广泛应用于很多学科。下面是遗传算法的一此主要应用领域。1、函数优化函数优化是遗传算法的经典应用领域，也是对遗传算法进行性能评价的常用算例。很多人构造出了各种各样的复杂形式的测试函数。有连续函数也有离散函数，有凸函数也有凹函数，有低维函数也有高维函数，有确定函数也有随机函数，有单峰值函数也有多峰值函数等。用这些几何特性各具特色的函数来评价遗传算法的性能，更能反映算法的本质效果而对于一些非线性、多模型、多目标的函数优化问题，用其他优化方法较难求解。而遗传算法却可以方便地得到较好的结果。2、组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧扩大。有时在目前的计算机上用枚举法很难或甚至不可能求出其精确最优解。对这类复杂问题，人们已意识到应把主要精力放在寻求其满意解上，而遗传算法是寻求这种满意解的最佳工具之一。实践证明，遗传算法已经在求解旅行商问题、背包问题、装箱问题、布局优化、图形划分问题等各种具有NP难度的问题得到成功的应用。3、生产调度问题生产调度问题在很多情况下建立起来的数学模难以精确求解，即使经过一些简化之后可以进行求解.也会因简化得太多而使得求解结果与实际相差甚远。目前在现实生产中主要是靠一些经验来进行调度。现在遗传算法已成为解决复杂调度问题的有效下具。在单件生产车间调度、流水线生产间调度、生产规划、任务分配等方面遗传算法都得到了有效的应用。4、自动控制在自动控制领域中有很多与优化相关的问题需要求解。遗传算法已在其中得到了初步的应用，并显示出良好的效果。例如用遗传算法进行航空控制系统的优化、使用遗传算法设计空间交会控制器、基于遗传算法的模糊控制器的优化设计、基于遗传算法的参数辨识、基于遗传算法的模糊控制规则的学习、利用遗传算法进行人工神经网络的结构优化设计和权值学习等。都显出了遗传算法在这此领域中应用的可能性。5、机器人学机器人是一类复杂的难以精确建模的人工系统，而遗传算法的起源就来自于人工自适应系统的研究。所以，机器人学理所当然地成为遗传算法的一个重要应用领域。例如，遗传算法已经在移动机器人路径规划、关节机器人运动轨迹规划、机器人逆运动学求解、细胞机器人的结构优化和行为协调等方而得到研究和应用。6 、图像处理图像处理是计算机视觉中的一个重要研究领域。在图像处理过程中，如扫描、特征提取、图像分割等不可避免地会存在一此误差，从而影响图像的效果。如何使这些误差最小是使计算机视觉达到实用化的重要要求。遗传算法在这些图像处理中的优化计算方面找到了用武之地。目前已在模式识别(包括汉字识别)、图像恢复、图像边缘特征提取等方而得到了应用。7 、人工生命人下生命是用计算机、机械等人下媒