第4章机器进化.pptVIP

第4章 机器进化 生物系统 进化 子孙比祖先更先进。 能运用与进化类似的过程来产生有用的程序么？ 生物进化过程中，先是双亲生产后代，然后这些后代中的一部分“有选择地生存”下来，并生产更多的后代。 繁殖和选择性生存这两个方面足以生产繁殖能力越来越强的一代代个体。 想像这样一幅数学“风景画”：那里有山峰、山谷和平地，还居住着一群个体，它们随机地分布在这幅画的不同地方。个体在风景画中所处的高度是衡量此个体相对其他个体完成任务的能力。那些处于海拔低的个体停止“生存”，其概率随着其海拔越来越低而增大。那些处于海拔高的个体进行“繁殖”，其概率随着其海拔越来越高而增大。繁殖就是生产新的个体，使这些个体在风景画中的位置与其单亲或双亲的位置相关但不同。最有趣且有效的一种繁殖就是父亲和母亲联合生产新个体。这些子女在风景画中所处的位置是其双亲的位置的函数。 应用 函数优化是最直接的应用，这种应用试图求出一个函数的最大值，如f (x1,. . .,xn)，其中自变量(x1,. . ., xn)说明个体的位置，f值为高度。John Holland提出了一种解决这类问题的算法—“遗传算法（G A）” 另一种应用就是用进化程序解决具体问题—如控制响应a g e n t的程序。而“遗传编程（G P）”[Koza 1992, Koza 1994]是另外一种技术，它采用一种比G A更直接的方式来进化程序。 4.2 遗传编程 4.2.1 遗传编程的程序表示 遗传编程一般使用函数式程序设计语言，如L I S P。这样的程序可以表示为树。树的内部节点为带有一个或多个参数的函数、谓词或动作。叶节点为程序常数、或不带自变量的动作函数。右图说明了如何用树结构来表示计算3 + ( 5×4 ) / 7的程序。例中，叶节点为3、4、5和7，内部节点为函数+、×和/。 运用遗传编程来进化一个沿墙运动的机器人 这个机器人的任务与第2章所述相同。设此机器人所处的世界为二维网格世界，如图4 - 2所示。我们进化一个程序，此程序把机器人当前的传感器数据作为输入，并计算出一个动作。我们希望重复运行此程序来控制机器人，并把机器人从任一初始位置移到与墙毗邻的一个单元中，使其永远沿墙运动。  布尔函数定义为： 1) 当x = 0时，A N D ( x , y ) = 0；否则为y。 2) 当x = 1时，O R ( x , y ) = 1；否则为y。 3) 当x = 1时，N O T ( x ) = 0；否则为1。 4 ) 当x = 1时，I F ( x , y , z ) = y；否则为z。 四个动作定义如前： n o r t h：将机器人在网格中向上移动一个单元。 e a s t：将机器人在网格中向右移动一个单元。 s o u t h：将机器人在网格中向下移动一个单元。 w e s t：将机器人在网格中向左移动一个单元。 4.2.2 遗传编程过程 在遗传编程中，我们从随机程序开始，并运用那些能使程序对感兴趣的问题域有效的函数、常数和传感器输入。这些初始程序构成0代(generation 0 )。0代程序的大小是遗传编程中的一个参数。在对遗传编程的阐述中，我们将从5 0 0 0个随机程序开始来进化一个沿墙运动的机器人。 从基本函数A N D、O F、N O T和I F，动作n o r t h、e a s t、s o u t h和w e s t，传感器函数n、n e、e、s e、s、s w、w和n w以及常数0和1中产生这些初始随机程序。每一代程序均接受评估，而且直到有一个程序的表现十分令人满意时才产生新的一代程序。 评估 依据一个程序如何完成所设定的任务来对它进行评估。 把一个程序运行6 0次，并计算在这6 0次运行中被访问的与墙毗邻的单元个数（共有3 2个单元与墙毗邻，因此，从未走近墙边的程序的计数为0，而理想的程序的计数为3 2）。 然后让机器人分别在1 0个随机选择的不同初始位置进行前面这个步骤。在这1 0个运行中被访问的与墙毗邻的单元的总数即为此程序的“合理度”。可能的合理度的最高值为3 2 0—机器人只有在这1 0个步骤的每一步的6 0次运行中均访问了所有与墙毗邻的单元，才可能达到这一最高值。 第i代按照下列方式建构第i+ 1代 1）把第i代的5 0 0个程序（ 1 0 %）直接复制到第i+ 1代。用下列“锦标赛选拔”过程来选择这5 0 0个程序：从5 0 0 0个程序中随机选出7个，再从中选择最合适的那一个（“锦标赛选拔”是选择合适个体的一种有效的方法。数字7和直接复制的程序的百分比是遗传编程过程中的附加参数） 建构第i+ 1代－2 2) 把4 5 0 0个新的“孩子(c h i l d)”程序（9 0 %）归入第i+ 1代。每一个孩子程序通过以