chap4 机器进化 人工智能课程 上海交大课件.ppt

《chap4 机器进化 人工智能课程 上海交大课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章机器进化生物系统进化子孙比祖先更先进。能运用与进化类似的过程来产生有用的程序么？生物进化过程中，先是双亲生产后代，然后这些后代中的一部分“有选择地生存”下来，并生产更多的后代。繁殖和选择性生存这两个方面足以生产繁殖能力越来越强的一代代个体。想像这样一幅数学“风景画”：那里有山峰、山谷和平地，还居住着一群个体，它们随机地分布在这幅画的不同地方。个体在风景画中所处的高度是衡量此个体相对其他个体完成任务的能力。那些处于海拔低的个体停止“生存”，其概率随着其海拔越来越低而增大。那些处于海拔高的个体进行“繁殖”，其概率随着其海拔越来越高而增

2、大。繁殖就是生产新的个体，使这些个体在风景画中的位置与其单亲或双亲的位置相关但不同。最有趣且有效的一种繁殖就是父亲和母亲联合生产新个体。这些子女在风景画中所处的位置是其双亲的位置的函数。应用函数优化是最直接的应用，这种应用试图求出一个函数的最大值，如f(x1,...,xn)，其中自变量(x1,...,xn)说明个体的位置，f值为高度。JohnHolland提出了一种解决这类问题的算法—“遗传算法（GA）”另一种应用就是用进化程序解决具体问题—如控制响应agent的程序。而“遗传编程（GP）”[Koza1992,Koza1994]是另外一

3、种技术，它采用一种比GA更直接的方式来进化程序。4.2遗传编程4.2.1遗传编程的程序表示遗传编程一般使用函数式程序设计语言，如LISP。这样的程序可以表示为树。树的内部节点为带有一个或多个参数的函数、谓词或动作。叶节点为程序常数、或不带自变量的动作函数。右图说明了如何用树结构来表示计算3+(5×4)/7的程序。例中，叶节点为3、4、5和7，内部节点为函数+、×和/。运用遗传编程来进化一个沿墙运动的机器人这个机器人的任务与第2章所述相同。设此机器人所处的世界为二维网格世界，如图4-2所示。我们进化一个程序，此程序把机器人当前的传感器数据

4、作为输入，并计算出一个动作。我们希望重复运行此程序来控制机器人，并把机器人从任一初始位置移到与墙毗邻的一个单元中，使其永远沿墙运动。布尔函数定义为：1)当x=0时，AND(x,y)=0；否则为y。2)当x=1时，OR(x,y)=1；否则为y。3)当x=1时，NOT(x)=0；否则为1。4)当x=1时，IF(x,y,z)=y；否则为z。四个动作定义如前：north：将机器人在网格中向上移动一个单元。east：将机器人在网格中向右移动一个单元。south：将机器人在网格中向下移动一个单元。west：将机器人在网格中向左移动一个单元。布尔函数

5、—AND、OR、NOT和IF；四个动作—north、east、south和west。4.2.2遗传编程过程在遗传编程中，我们从随机程序开始，并运用那些能使程序对感兴趣的问题域有效的函数、常数和传感器输入。这些初始程序构成0代(generation0)。0代程序的大小是遗传编程中的一个参数。在对遗传编程的阐述中，我们将从5000个随机程序开始来进化一个沿墙运动的机器人。从基本函数AND、OF、NOT和IF，动作north、east、south和west，传感器函数n、ne、e、se、s、sw、w和nw以及常数0和1中产生这些初始随机程序。

6、每一代程序均接受评估，而且直到有一个程序的表现十分令人满意时才产生新的一代程序。依据一个程序如何完成所设定的任务来对它进行评估。把一个程序运行60次，并计算在这60次运行中被访问的与墙毗邻的单元个数（共有32个单元与墙毗邻，因此，从未走近墙边的程序的计数为0，而理想的程序的计数为32）。然后让机器人分别在10个随机选择的不同初始位置进行前面这个步骤。在这10个运行中被访问的与墙毗邻的单元的总数即为此程序的“合理度”。可能的合理度的最高值为320—机器人只有在这10个步骤的每一步的60次运行中均访问了所有与墙毗邻的单元，才可能达到这一最高

7、值。评估1）把第i代的500个程序（10%）直接复制到第i+1代。用下列“锦标赛选拔”过程来选择这500个程序：从5000个程序中随机选出7个，再从中选择最合适的那一个（“锦标赛选拔”是选择合适个体的一种有效的方法。数字7和直接复制的程序的百分比是遗传编程过程中的附加参数）第i代按照下列方式建构第i+1代2)把4500个新的“孩子(child)”程序（90%）归入第i+1代。每一个孩子程序通过以下“交叉”操作由一个母亲(mother)程序和一个父亲(father)程序共同生产出来：这些双亲程序均从第i代的锦标赛选拔中选出，把母亲程序中一

8、个随机选择的子树替换为父亲程序中的一个随机选择的子树，便产生出孩子程序（以下要求保证孩子程序的可执行度：即此程序的所有函数对所有参数的可能值来说均可执行）。建构第i+1代－2建构第i+1代－33)有时，还用