Final Project - Progress Report 3
Forrest Sondahl
Multi-Agent Modeling (2005)


Summary:

I expected this project to be quite a bit of work.  And it hasn't disappointed me yet.  Fortunately, this week I managed to put in a lot of time, and it's beginning to pay off.
  • The base genetic programming engine is basically finished now.  (There may be a few things I have to tweak along the way, but hopefully not.)
    • Cloning, mutation, and crossover are fully implemented, with sliders to control the frequency of each type of operation. 
    • Generations occur, and a fitness function is calculated.
    •  I succeeded in making it fairly modular, so that it shouldn't be hard to adapt it for all sorts of different models.
  • The maze marcher model is starting to come together now.  (A picture of a beta run is shown at right).



 random codeturtles
(Maze marchers try to find the goal!)

Details:

Genetic Programming Engine

I don't have too much more to say about the base genetic programming engine.  Besides finishing up the genetic operations, there was only one major change that I can think of.  I made it so that command block nodes can directly be the children of command block nodes.  In Netlogo, this would look something like this:

repeat 3
[
  [
    [ rt 90 fd 1 ]
    [ lt 90 fd 2 ]
  ]
  [
    [ set y 6   set color blue  ]
    [ pd        set z 7 ]
  ]
]

Note that this is not valid Netlogo code.   However, it is useful for the following reason.  For the purposes of genetic programming, our programs are represented as trees.  And during crossover one node is replaced with another node.  However, let's say that one of our successful programs had a block of code with 20 commands, of which five make up a useful sequence.  That is to say, the five lines of code are useful when they are run in that order.  With the old scheme, either the whole command block of 20 lines of code had to be transferrred to a new creature, or only one of the individual commands within the command block.  With the new system, the trees have many more command block nodes which may be chosen, instead of choosing single commands.  And these command blocks contain subsequences of the total number of commands.  This might allow us to choose a command block with just 8 lines of code, which contains the five good lines, and perform crossover with it.  I'm not sure that I've been overly clear, but the basic idea is that the new tree structure allows more groupings of commands to be transferred around as genetic material, rather than simply large groups or single items.

Maze Marchers

I decided to implement mazes as files, which may be loaded.  To this end, I built a seperate NetLogo model for maze generation -- it loads, saves, and edits maze files.

Currently, the maze marcher is evolving whole programs for finding the path through a particular maze, using the following very simple program ingredients:

  (list "maze-forward" TYPE_COMMAND 30)    ;; chosen 60% of the time
  (list "maze-turn-right" TYPE_COMMAND 10) ;; chosen 20% of the time
  (list "maze-turn-left" TYPE_COMMAND 10)  ;; chosen 20% of the time

The code for these commands is very simple:

to-report maze-wall-ahead?
  report ((pcolor-of patch-ahead 1) = blue)
end

to maze-forward
  if (not maze-wall-ahead?)
    [ fd 1 ]
end

to maze-turn-right
  rt 90
end

to maze-turn-left
  lt 90
end

The agents all start with randomly generated program trees, consisting of a lot of turning left and right, and moving forward into the next patch (or bumping into a wall that blocks them).  And then as generations go by, they (hopefully) evolve toward better maze marchers over time.  I shouldn't say hopefully -- they definitely do evolve towards better maze walkers, but whether or not they totally get to the goal is not guaranteed.   But what guides this evolutionary process, so that they get better?  This is where the fitness function comes in, which determines how likely codeturtles are to reproduce offspring for the next generation.  Here is the current fitness function:

;; turtle procedure
to gp-calculate-fitness
  let dist (distance-nowrap (one-of patches with [pcolor = red ]))
  set gp-fitness 1 / (1 + dist)
end

Note that there is only one red patch, which is the goal state.  We first calculate the geometric distance towards the goal state.   The 1 / (1 + dist) part of the function makes it so that more fit a codeturtle have higher fitness values, and adjusts the distribution in a manner recommended in the genetic programming literature.  The probability that a given codeturtle is selected for a genetic operation that passes code on to a codeturtle in the next generation is (gp-fitness of this codeturtle) / (sum of gp-fitness of all the codeturtles). 

Results:  On a simple maze, they do quite well.  On a more complicated maze, they got very close to the solution, but didn't seem to be able to get the final bit.  It is important to note that the fitness function is currently only applied at the end of their run, which means that they could walk over the goal patch, and then end up on another patch farther away from it, and their fitness is calculated from the farther away patch.  Also, there was a problem of code bloat.  I believe that mutations are causing codeturtle programs to grow in size as they go along.  I may need to correct this somehow.  At any rate, turtles were ending up with over 4000 commands in their trees.  Now some useless commands (e.g. turning around in circles and walking into walls) are to be expected, and are healthy for the DNA of the codeturtle.  However, I think at some point, the amount of useless DNA becomes unmanageable, and hinders useful evolution of the creature.  Perhaps a more fundamental problem with this genetic approach to solving a single maze is that it is very inefficient.  That is to say, when we have code that finds its way halfway to the goal, what we really want to do is just modify the end of that code -- only the later half, so that we can help it walk further to the goal.  However, the genetic programming approach chooses tree nodes at random, such that it is just as likely to change the first half of the code as the latter half.  And a single change early on in the code can throw the turtle off  so that it can't get nearly as far as it could before.  I think this problem grows worse and worse as the turtle approaches the goal.   Changes to 99% of the codeturtles code will be massively destructive, and cause the codeturtle to not make it very far at all in the maze.

So currently, codeturtles are just evolving walking directions for solving one maze.  What I originally wanted to do (and still plan to do), is to have the codeturtles evolve rules for walking any maze (hoping that they will discover something like the right hand rule).  Instead of having them evolve a full program, they will evolve rulesets that are applied each timestep, to help them choose a direction to go.  (See my discussion on looping in the previous progress report).  This will make use of more advanced concepts in the genetic programming engine, such as if statements and reporters.

Random Notes:

None this time.

Conclusion:

Still plenty to be done:

Forrest's NetLogo Main Page.