A Demonstration of Genetic Programming

Zhu Chongkai
Shanghai JiaoTong University
zhuchongkai@online.sh.cn

In the nature, those biology with higher fitness of the environment will have higher survival rate and higher propagation rate. Biologists think that fitness of the environment is the result of natural selection, that is, by natural selection, recombination and variation, new structures will be made.

Computer program is one of the most complex artificial structures. In the 1950's, A.Samuel has set the problem of automatic programming one of the most important objects of Computer Science and Artificial Intelligence. What is called automatic programming is that only tell computer what to do , but not tell how to do.

Here I demonstrate a newly developed automatic programming technique, the Genetic Programming. I show how GP can be used to evolve a wall-following robot.[1]

The robot lives in a two-dimensional grid-space would, which is defined as:

occupied[x_, y_] = 
        x < 1 || x > 8 || y < 1 || y > 8;
bound = {{1, 1}, {2, 1}, {3, 1}, {4, 1}, {5, 1}, {6, 1}, {7, 
            1}, 
{8, 1}, {8, 2}, {8, 3}, {8, 4}, {8, 
            5}, {8, 6}, {8, 7}, 
{8, 8}, {7, 8}, {6, 
            8}, {5, 8}, {4, 8}, {3, 8}, {2, 8}, 
{1, 
            8}, {1, 7}, {1, 6}, {1, 5}, {1, 4}, {1, 3}, {1, 
            2}};

Or, in human language, it is a 8*8 block space, from {1,1} to {8,8}. So there are 64 blocks free, and the boundary cells of the space is defined as bound, which has 28 blocks.

The task of the robot is to move to a cell adjacent to a boundary and then follow that boundary along its perimeter forever. To be capable of such boundary-following behavior, the robot is able to sense whether or not the eight cells surrounding it are occupied or free. These sensory inputs are denoted by e,se,s,sw,w,nw,n,ne. The robot can move to a (free) adjacent cell in its column or row.

We want to evolve a program that takes as inputs the robot's current sensory data and computes a single action. The robot is controlled by repeated execution of this program, and we want repeated execution to move the robot from an arbitrary initial position to a sell adjacent to the wall and then follow the wall around forever.

The primitive functions to be used in the program include four Boolean functions, And,Or,Not,If; and four actions, east,south,west,north. The evaluation of any of the action functions terminates the program. All of the action functions have their indicated effects unless the robot attempts to move into an occupied cell, in that case, the action has no effect except to terminate the program.

For GP, we must ensure that all expressions and subexpressions used in a program have values for all possible arguments, unless execution of a expression terminates the program.

In GP, we start with a population of random programs, using functions, constants and sensory inputs that we think may be the ones that will be needed by programs if they are to be effective in the domain of interest. These initial programs are said to constitute generation 0. The size of the population of programs in a generation is one of the parameters of a GP run. In my illustration of how GP works, we are going to start with 1000 random programs and attempt to evolve a wall-following robot. We produce these initial programs from the primitive functions, the actions, the sensory functions, and the constants 0 and 1.

randomp := 
Block[{r = 
            Random[Integer, {1, 
                26}]}, 
Which[
r ≤ 3, 
          If[randomp, Evaluate[randomp], 
            Evaluate[randomp]], 
r ≤ 6, 
          And[randomp, randomp], 
r ≤ 9, 
          Or[randomp, randomp], 
r ≤ 12, 
          Not[randomp], 
r == 13, 
          e, 
r == 14, 
          se, 
r == 15, 
          s, 
r == 16, 
          sw, 
r == 17, 
          w, 
r == 18, 
          nw, 
r == 19, 
          n, 
r == 20, 
          ne, 
r == 21, 
          east, 
r == 22, 
          south, 
r == 23, 
          west, 
r == 24, 
          north, 
r == 25, 
          True, 
r == 26, False]]

Do[program[i] = randomp, {i, 1000}]

A program is evaluated by running it to see how well it does on the task we set for it. In our case, we run a program again and again until it moves to a cell it has already visited, and count the number of cells next to the wall that are visited. There are 28 cells next to the wall, so a program that never gets to the wall would have a count of 0, and a perfect program would have a count of 28. Then we do five of these runs with the robot starting in five randomly chosen starting positions. The total next-to-wall cells visited during these five runs is then taken as the fitness of the program. The highest possible fitness value will be 140, achievable only by a robot that on each of its five fitness runs visits all of the next-to-wall cells.

estimate[
        p_] := 
Block[{fitness = 
            0}, 
Do[
Block[{arrived = {}, 
x = Random[Integer, {1, 8}], 
              y = Random[Integer, {1, 8}]}, 
While[
              FreeQ[arrived, {x, y}], 
arrived = 
                Prepend[arrived, {x, y}]; 
program[
                  p] /. 
{e :> 
                    occupied[x + 1, y], 
                  se :> 
                    occupied[x + 1, 
                      y - 1], 
s :> 
                    occupied[x, y - 1], 
                  sw :> 
                    occupied[x - 1, 
                      y - 1], 
w :> 
                    occupied[x - 1, y], 
                  nw :> 
                    occupied[x - 1, 
                      y + 1], 
n :> 
                    occupied[x, y + 1], 
                  ne :> 
                    occupied[x + 1, 
                      y + 1], 
east :> (If[! occupied[x + 1, y], x++]; 
                      Continue[]), 
south :> (If[! occupied[x, y - 1], y--]; 
                      Continue[]), 
west :> (If[! occupied[x - 1, y], x--]; 
                      Continue[]), 
north :> (If[! occupied[x, y + 1], y++]; 
                      Continue[])}]; 
fitness += 
              Length[Intersection[arrived, 
                  bound]]], 
{5}]; 
fitness]

The (i+1)-th generation is constructed from the i-th one in the following manner:

1. One hundred programs (10%) from generation i are copied directly into generation i+1. Individuals are chosen for copying by the following tournament selection process: seven programs are randomly selected (with replacement) from the population of 1000. Then the most fit of these seven programs is chosen. Tournament selection has been found to be an efficient method for selecting fit individuals. The number 7 and the percentage of programs to be copied are additional parameters of the GP process.

tour := 
      Block[{group = 
            Table[Random[
                Integer, {1, 
                  1000}], {7}]}, 
group[[Position[
                evalu[[group]], Max[evalu[[group]]]][[1, 
                1]]]]]

2. Nine hundred new child programs (90%) are put into generation i+1. Each child program is produced from a mother and a father program by a crossover operation as follows: a mother and a father are each chosen from generation i by tournament selection (as before). Then a randomly chosen subtree from the father replaces a randomly selected subtree from the mother. The result is the chile program. Executability of the child is guaranteed by the requirement that all functions used in the programs be executable for all possible values of their arguments.

crossover := 
Block[{father = program[tour], 
          mother = program[tour], fasub, mosub}, 
fasub = 
          Position[father, _, 
            Heads -> False]; 
mosub = 
          Position[mother, _, 
            Heads -> False]; 
ReplacePart[
          mother, 
Extract[father, 
              fasub[[Random[
                    Integer, {1, 
                      Length[fasub]}]]]]
 /. {} -> 
              father, 
mosub[[Random[
                Integer, {1, Length[mosub]}]]]]]

Programs in each generation are evaluated, and a new generation is produced until a program is produced that performs acceptably well.

While[
      Max[evalu = Table[estimate[i], {i, 1000}]] < 140, 
Do[
        nextgen[i] = program[tour], {i, 100}]; 
Do[
        nextgen[i] = crossover, {i, 101, 1000}]; 
Do[
        program[i] = nextgen[i], {i, 1000}]]

Note that several rather arbitrary parameters must be set in constructing the next generation, including the number of individuals to be copied, the number to be produced by crossover and the number used in tournament selection.

Starting with our population of 1000 random programs, and using the techniques just described, we use the GP process for evolving a wall-following robot. Many of the random, generation 0 programs do nothing at all. In each generation, the max of the fitness well be improved (but often small). Finally, a program with fitness 140 will be found.

program[Position[evalu, Max[evalu]][[1, 1]]]

As is usual with GP, the program is rather difficult to read and has many redundant operations, but it runs well.

Reference:
[1] Nils J. Nisson, Artificial Intelligence - A New Synthesis