第四章遗传程序设计VIP免费

第4章遗传程序设计武汉大学计算机学院4.1遗传程序设计框架自动程序设计是计算机科学的中心目标之一。自动程序设计所涉及的问题是：怎样才能使计算机去解决给定的问题而无需显式编程？很多年来，人们一直在为实现这一目标而努力。遗传程序设计便是在该领域的一种尝试.自动程序设计是人工智能的一个重要研究领域。自动程序设计研究的重大贡献之一是作为问题求解策略的调整概念。已经发现，对程序设计问题，先产生一个不费事的有错误的解，然后再修改使它正确工作，这种做法一般要比坚持要求第一个解就完全没有缺陷的做法有效的多。遗传程序设计正是基于这样一种思想而发展起来的.4.1遗传程序设计框架遗传程序设计与遗传算法类似，所不同的是在遗传程序设计中，搜索空间是计算机程序空间，个体是计算机程序。遗传程序设计的流程图如下图所示。变异后的个体加入新种群复制的个体加入新种群Gen:=0产生初始种群终止准则被满足？指定结果结束评估个体适应度i:=0i=N?Gen:=Gen+1是否否是按概率选择遗传算子选择一个个体选择两个个体选择一个个体执行复制执行杂交执行变异i:=i+1i:=i+2i:=i+1两个后代加入新种群prpcpm4.1遗传程序设计框架为了用遗传程序设计演化求解问题的程序，首先需要解决以下问题：(1)程序的表示；(2)程序好坏的评价标准；(3)遗传算子设计。4.2程序的表示在遗传程序设计中，种群中的个体是计算机程序。为了程序表示的简单性和容易验证程序的句法，遗传程序设计用Lisp语言来表示程序。考虑一个简单的LISP程序，该程序简单地返回一个自然数n的平方.>SQUARE))()(squaredefun(nnn4.2程序的表示>(square4)16下面是出一个计算一个实数绝对值的LISP程序.>ABS>(abs–4)4))()(0)(if()(absdefun(xxxx4.2程序的表示从上面的例子可以看出，LISP程序的主体由类似于和的一些S-表达式所组成。构造LISP程序的S-表达式是以前缀表达式形式表示的。表示LISP程序的S-表达式与树型结构有一个自然的对应关系，也就是说，给定一个S-表达式，我们容易构造出一棵树，而对该树进行先序遍历便可得到给定的S-表达式。这棵树是S-表达式的语法树。)(nn))()(0)(if(xxx4.2程序的表示例如S-表达式所对应的语法树如下图所示。6))510)((if12(x+12if>56x10在语法树中，树的外部结点(叶结点)分别用变量x和常量5，6，10，12来标记，这些变量和常量通常称为端点，而内部结点分别用函数+，>，IF来标记.一般来说一个表示LISP程序的S-表达式通常由一些函数和端点组成。4.3遗传程序设计的实现技术用遗传程序设计求解问题有以下5个基本步骤：(1)选择端点集；(2)选择函数集；(3)确定适应函数；(4)确定控制参数；(5)确定指定结果的方法和终止程序运行的条件.4.3.1选择端点集和函数集在遗传程序设计中，计算机程序用LISP程序的语法树来表示。每一棵语法树的内部结点由一些函数构成，而叶结点由一些变量和常数构成.对于一个给定的问题，首先要确定由所有可能求解该问题的程序所组成的程序空间S。由于LISP程序通常可以由一些简单的函数、变量和常数经过有限次运算和复合而生成。因此若要指定程序空间S，我们只要指定可以构成中程序的函数集和端点集即可。},,,{21MfffF},,,{21NaaaT4.3.1选择端点集和函数集通常函数集可以包含(1)算术运算等；(2)数学函数sin,cos,exp,log等；(3)布尔运算AND,OR,NOT；(4)条件算子IF-THEN-ELSE;(5)循环算子DO-UNTIL，FOR，WHILE；端点集通常由变量和常量组成。/,,,4.3.2初始化假设问题的端点集和函数集分别为T和F。初始种群中的每个S-表达式，即每棵树，可如下产生：首先建立一个根结点，从函数集F中随机地选择一个函数作为根结点的标记。每当树中的一个结点被标记为函数集F中的一个函数后，则为该结点建立个儿子结点，而每个儿子结点的标记从中随机地选取，每当树中一个结点被标记为端点集T中的一个元素时，则该结点成为树的一个叶结点，如此反复进行，直到所有结点都被标记。f)(fzTFC4.3.2初始化假定。下面给出了建立一棵树结构的过程。},,,{/},,,,{dcbaTF++*c+*cab4.3.2初始化上述树生成过程...