第15讲-基因编程

第13讲基因编程

张凯博士教授

计算机科学技术系

：62380002

邮件：一、什么是演化计算二、什么遗传算法三、什么遗传程序设计四、什么基因表达式程序设计五、国内的基因编程研究背景材料一、什么是演化计算自然界的生物体通过自然选择和自然遗传机制来自组织、自适应地解决问题。受此启发，人们通过模拟自然演化过程来解决某些复杂问题，并进一步开展出计算机科学领域内一个崭新的分支——演化计算。80年代中期以来，很多国家掀起了研究演化计算的热潮。演化计算是一种通用的问题求解方法，具有自组织、自适应、自学习性和本质并行性等特点，不受搜索空间限制性条件的约束，也不需要其它辅助信息。因此，演化算法简单、通用、易操作、能获得较高的效率，越来越受到人们的青睐。1.演化计算的开展过程大自然是人类灵感的源泉。几百年来，将生物界提供的答案应用于实际问题求解，已被证明是一个成功的方法，并已形成一个专门的科学分支——仿生学(bionics)。自然界提供的答案是经过漫长的自适应过程(即演化过程)所得的结果。除了演化过程的最终结果，我们也可以利用这一过程本身去解决一些较为复杂的问题。演化计算正是基于自适应过程(即演化过程)思想而开展起来的一种通用的问题求解方法。它采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择，来指导学习和确定搜索的方向。由于采用种群(即一组表示)的方式组织搜索，所以它可以同时搜索解空间内的多个区域，而且特别适合大规模并行处理。在赋予演化计算自组织、自适应、自学习等特征的同时，优胜劣汰的自然选择和简单的遗传操作使演化计算具有不受其搜索空间限制性条件(如可微、连续、单峰等)的约束，以及不需要其它辅助信息(如导数)的特点。这些崭新的特点使演化算法不仅能获得较高的效率，而且具有简单、易操作和通用的特性。在60-70年代演化计算并未受到普遍重视。一是因为当时这些方法本身还不够成熟；二是由于这些方法需要较大的计算量，而当时的计算机还不够普及，且速度跟不上要求，因而限制了它们的应用；三是当时基于符号处理的人工智能方法正处于顶峰状态，使人们难以认识到其它方法的有效性和适应性。80年代，人们越来越清楚地意识到传统人工智能方法的局限性，而且随着计算机速度的提高及并行计算机的普及，演化计算对机器速度的要求已不再是制约其开展的因素。演化计算在机器学习、过程控制、经济预测、工程优化等领域取得的成功，已引起了数学、物理学、化学、生物学、计算机科学、社会科学、经济学及工程应用等领域专家的极大兴趣。80年代中期以来，世界上许多国家都掀起了演化计算的研究热潮。2．演化计算的主要分支自从计算机出现以来，生物模拟(也称仿生)便成为计算机科学的一个组成局部。其目的之一是试图建立一种人工模拟环境，在这个环境中使用计算机进行仿真，以便更好地了解人类自己和人类的生存空间；另一个目的那么是从研究生物系统出发，探索产生根本认知行为的微观机理，然后设计成具有生物智能的机器或模拟系统，以解决复杂问题。演化计算最初具有三大分支：遗传算法(GeneticAlgorithm，GA)、演化规划(EvolutionaryProgramming，EP)演化策略(EvolutionStrategy，ES)。(1)遗传算法把计算机科学与进化论结合起来的尝试始于50年代末，但由于缺乏一种通用的编码方案，人们只能依赖变异而非交配来产生新的基因结构，故而收效甚微。到60年代中期，美国Michigan大学的JohnHolland在和等人工作的根底上提出了位串编码技术。这种编码既适于变异操作，又适于交配(即杂交)操作，并且强调将交配作为主要的遗传操作。(2)演化策略60年代初，柏林工业大学的学生I.Rechenberg和等在进行风洞实验时，由于设计中描述物体形状的参数难以用传统方法进行优化，因而利用生物变异的思想来随机改变参数值，并获得了较好的结果。随后，他们对这种方法进行了深入的研究和开展，形成了演化计算的另一个分支——演化策略。(3)演化规划演化规划的方法最初是由等在60年代提出的。他们在人工智能的研究中发现，智能行为就是具有预测其所处环境的状态、并按给定目标做出适当响应的能力。在研究中，他们将模拟环境描述成由有限字符集中的符号组成的序列。于是问题转化为，怎样根据当前观察到的符号序列做出响应，以获得最大收益。3.演化计算的主要特点演化算法与传统算法有很多不同之处，最主要的特点表达在下述两个方面：(1)自组织、自适应和自学习性(智能性)(2)本质并行性4.演化计算的研究内容及前景演化计算的研究主要集中在以下几个方面：(1)演化计算的理论研究(2)新的计算模型(3)演化优化(4)演化人工神经网络(5)并行和分布式演化计算(6)演化机器学习(7)演化计算应用系统(8)演化硬件(9)演化软件二、什么遗传算法1.什么是遗传算法遗传算法(GeneticAlgorithm，GA)是近几年开展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点表达了自然界中“物竞天择、适者生存〞进化过程。1962年Holland教授首次提出了GA算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面，并奠定了坚实的理论根底。用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空间定义的GA(GeneticAlgorithminContinuousSpace，GACS)，暂不讨论。GA编码整个遗传算法GA的编码是通过基因链码来决定。何为基因链码？生物的性状是由生物遗传基因的链码所决定。使用遗传算法时，需要把问题的每一个解编码成为一个基因链码。设1552是问题的一个解，我们可以用二进制形式来表示这个解所对应的基因链码，每个基因链码也被称作个体。GA编码方法：二进制编码、格雷码编码、浮点数编码、符号编码、多参数级联编码、多参数交叉编码。GA中最常用的算子(1)选择算子(selection/reproduction)：对两个相互配对的染色体按某种方式相互交换局部基因，从而形成两个新的个体。(2)交叉算子(Crossover)：交叉算子将被选中的两个个体的基因链按概率进行交叉，生成两个新的个体，交叉位置是随机的。(3)变异算子(Mutation)：将个体染色体编码串中的某些基因座上的基因值用该基因座上的其它等位基因来替换，从而形成新的个体，称为变异。三、什么遗传程序设计1.遗传程序设计遗传程序设计是学习和借鉴大自然的演化规律、特别是生物的演化规律来解决各种计算问题的自动程序设计的方法学。为了阐述什么是自动程序设计，我们先引入程序结构(ProgramStructure，PS)的概念。1976年，N.Wirth曾用下面的公式来表示计算机程序：算法+数据结构=程序(Algorithms+DataStructures=Programs)。

1985年由Cramer首次提出遗传程序设计。1992年，美国Stanford大学的J.Koza出版了专著《遗传程序设计(GeneticProgramming：OntheProgrammingofComputersbyMeansofNaturalSelection)》，介绍用自然选择的方法进行计算机程序设计。1992由Koza教授将其完善开展。GP是一种全局性概率搜索算法，它的目标是根据问题的概括性描述自动产生解决该问题的计算机程序。GP吸取了遗传算法〔GA〕的思想和达尔文自然选择法那么，将GA的线性定长染色体结构改变为递归的非定长结构。这使得GP比GA更加强大，应用领域更广。Koza选择Lisp作为GP的程序设计语言。有了程序结构的概念，即可讨论自动程序设计(AutomaticProgramming，AP)。可以用下面的公式来概括自动程序设计的思想：EA+PS=AP(演化算法+程序结构=自动程序设计)。四、什么基因表达式程序设计1.基因表达式编程起源基因表达式编程(GeneExpressionProgramming，GEP)是一种全新的进化算法，它是葡萄牙科学家CandidaFerreira于2000年提出来的。随后CandidaFerreira注册了公司，专门研究有关GEP在函数发现、分类、时间序列分析等方面的工作，已经取得了一定的成果，并形成了具有自主知识产权的GEP软件GepSoft。GEP起源于生物学领域，它继承了传统的遗传算法和遗传编程的优点，在此根底上开展了属于GEP特有的遗传操作，大量的实验说明，GEP算法以及各种改进的GEP算法在发现未知先验知识的数据函数关系以及对时间序列分析都有着非常好的表现。2.基因表达式编程(GEP)简介GEP继承了GAs和GP的优点：使用简单、线形、固定长度的个体表达了不同大小和形状的结构(simple，plasticstructure)。这种结构能：编码任何可能的程序并高效的进化；轻易的利用功能强大的遗传算子有效的搜索解空间；不会产生无效的个体。在进化计算中唯一使用了多基因的算法〔更高的层次，许多新的值得探索的东西〕。使用Karvalanguage读取和表达存贮在GEP个体中的信息。GEP、GA以及GP的比较(1)GA个体编码简单，因此操作方便，但只能处理简单问题；(2)GP个体编码复杂，因此操作麻烦，且遗传操作不具备封闭性，很多资源消耗在处理无效结构上，但常用于求解复杂问题；(3)GEP是简单编码解决复杂问题，而且遗传操作方便，不会产生无效结构。3.GEP的基因结构GEP的基因结构主要包括两个主要的成员：染色体(Chromosome)和表达式树(K-Expression)。两者之间的关系是：染色体中所包含的遗传信息由表达式树来解码。其中染色体是由一个或者多个基因组成，每个基因包括头部(head)和尾部(tail)。GEP中基因组〔染色体〕由一个线性的定长基因符号串组成。它是一种ORF(Openreadingframesandgenes)的编码序列。GEP的基因主要有头部〔head〕和尾部〔tail〕构成。其中头部是从函数集F和终点集T中随机产生，而尾部只能从终点集T中随机产生。背景材料康立山，男，1934年1月6日出生于湖南衡山(现为衡东县)三樟市，1952年毕业于衡山中学(国师附中与省立十二中合并而成)，1956年毕业于武汉大学数学系。195