遗传规划.pptVIP

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