遗传规划.ppt

河北大学,吴彬(),1,3遗传规划(2),遗传规划应用实例,河北大学,2,吴彬(),n变量 奇-偶判断函数,Even-n-Parity problem(n=3),河北大学,3,吴彬(),函数集,and,or,nand,nor and(a,b):a和b都等于1时返回1,否则返回0,or(a,b):a或b等于1时返回1,否则返回0,nand(a,b):a和b都等于1时返回0,否则返回1.nor(a,b):a或b等于1时返回0,否则返回1.上述函数集可表示出xor，如or(nor(a,b),and(a,b),河北大学,4,吴彬(),终止集,d1,d2,d3,适应度,错误的分类数,河北大学,5,吴彬(),机器人控制,河北大学,6,吴彬(),感知,这个机器人能够感知出它周围八个单元格是否空缺。这些传感器输入用二进制变量 n,ne,e,se,s,sw,w和nw表示,单元格为空时变量为0，单元格有障碍物时变量为1.如果机器人处于有X标记的地方,传感器的输入值(从 s 开始顺时针计算)为(0,0,0,0,0,1,0,0)。,河北大学,7,吴彬(),动作,该机器人能够向与它同行或同列的毗邻的（空缺）单元格移动，共有如下四种动作：north:机器人在网格中向上移动一个单元east:机器人在网格中向右移动一个单元south:机器人在网格中向下移动一个单元west:机器人在网格中向左移动一个单元,河北大学,8,吴彬(),知觉和动作部分,河北大学,9,吴彬(),任务,我们要求这个机器人完成以下动作：走到与一边界或物体毗邻的单元格中，然后沿着它的边界一直走下去。要能够完成这一沿边界运动的行为，机器人必须能够感知一个单元格是否空缺而可以向其移动，并且必须能够做一些基本的动作。,河北大学,10,吴彬(),函数集,此程序的基本函数包括:and,or,not和if.函数具有它们通常的定义：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。,河北大学,11,吴彬(),终止集,感知变量n,ne,e,se,s,sw,w和nw来表示。当相应的单元空缺使得机器人可移入时，输入值为0;否则为1.四个动作north,east,south和west。north:机器人在网格中向上移动一个单元east:机器人在网格中向右移动一个单元south:机器人在网格中向下移动一个单元west:机器人在网格中向左移动一个单元,河北大学,12,吴彬(),解的形式,河北大学,13,吴彬(),相对树形解的代码,河北大学,14,吴彬(),适应度,依据一个程序如何完成所设定的任务来对它进行评估。这里，我们把一个程序运行 60次，并计算在这60次运行中被访问的与墙毗邻的单元个数(共有32个单元与墙毗邻，因此，从未走近墙边的程序的计数为0，而理想的程序的计数为32)。然后，我们让机器人分别在10个随机选择的不同初始位置进行前面这个步骤。在这10个运行中被访问的与墙毗邻的单元的总数即为此程序的”适应度”。可能的合理度的最高值为320机器人只有在这10个步骤的每一步的60次运行中均访问了所有与墙毗邻的单元，才可能达到这一最高值.,河北大学,15,吴彬(),实际计算出的解的形式,河北大学,16,吴彬(),谢谢！,参考文献Steven Matt Gustafson,An Analysis of Diversity in Genetic Programming,http:/www.cs.nott.ac.uk/smg/thesis_html/thesis.html.郑扣根、庄越挺译,人工智能,机械工业出版社,2000-10-10.,