Evolutionary Computation and Artificial Life (202-1-5171), Semester A, 2004-2005

Exercise 3

In this exercise you are to write a program in Scheme to solve the Artificial Ant Problem with Genetic Programming (GP). The problem consists of finding the best strategy for picking up food pellets (חתיכות מזון) along a trail in a grid. The solution to the problem is an algorithm for collecting food. The Santa Fe trail is often used for the Ant problem. The Sante Fe trail consists of 89 food elements on a two dimensional, 32x32, toroidal grid, shown below. `Toroidal' means that an ant never "falls" off the grid---when it gets to an edge (top, bottom, left, right), it continues moving as if the grid were circular (for example, from a cell on the right it will move to the opposite cell on the left). The ant starts in the northwest corner, facing east.

Ant functions and terminals. The functions and terminals are executed to move the ant on the grid during evaluation:

• if_food_ahead(a,b) : if the ant faces a food pellet then evaluate a, else evaluate b
• progn2(a,b) : evaluate a, then b, returning b's value
• progn3(a,b,c) : evaluate a, b then c, returning c's value
• left : turn the ant left by 90 degrees
• right : turn the ant right by 90 degrees
• move : move the ant forward by one square/step

Fitness measure. The fitness for this problem is measured as the number of pellets not picked up by the ant. The ant is typically given a total of 600 time steps to collect food pellets, where each terminal takes one time step to execute. Each candidate program is re-evaluated, without re-initializing the ant, until all the food has been collected or the maximum number of time steps is reached. That is, you treat the program as though it were a loop that executes until all food has been found or time is up.

Population size (M) is 500, and number of generations (G) is 51. You may change these values if they don't work.

Submit:

• Plots of best fitness versus time.
• Five LISP programs that you evolved using GP (along with their fitness values): a program from Generation 0, from three generations in the middle of the run, and the best program found. Along with each of the five programs submit an image of the trail that is taken by the ant defined by the program. This will show how the ant's "brain" evolves in time to solve the problem.

10-Point BONUS: Implement ADFs (Automatically Defined Functions). Compare runs with/without ADFs.

Please submit a reasonable documentation of your code, plus your detailed conclusions from the experiments you performed.

Some stuff that might help:

1. A random number generator in scheme.

2. Aviv Eyal's comments from last year:

 Subject: ex3: Scheme and gnuplot
 
 Hello all:
 
 Here's some help regarding the tools I recommend using for ex3.
 
 Language: Scheme is a version of LISP designed for elegance and
 simplicity. It's complete description[1] is shorter then the TOC of the
 most common of LISP descriptions[2]. You should use it for your coding.
 
 There are two versions installed in that labs: Chez Petite Scheme, and PLT
 scheme. Whatever I'm writing here is good for both. PLT scheme has two
 different implementations - DrScheme and MzScheme (Pronounced Doctor and
 Miss Scheme).
 DrScheme is a big, SLOW INTERPRETER, with really bad Garbage Collection.
 GP makes for a big, long programs that generate a lot of Garbage, so
 using DrScheme is a really bad idea for it.
 MzScheme, OTOH, is a small, neat, fast, NATIVE-CODE compiler. It runs
 (almost) as fast as C++, and has a very good GC. IT's much more useful.
 Petite is also very good.
 
 The procedure you need for GP is called eval. Here's a sample:
 
  > (define k (list '+ '3 '4))
 ; k is now a list of symbols. Symbols are nothing like anything you know
 ; from any other programming language. '+ is a symbol, + is a name of a
 ; primitive procedure. Symbols that look like '44 or '"a string" are just
 ; the number or string they look like.
  > k
 (+ 3 4)
  > (eval k)
 7
 ; I know what you're thinking. but take a look at:
  > (define k (list '+ 'a 4))
  > (eval k)
 reference to undefined identifier: a
 ; A has not yet been defined. We can define it right now:
  > (define a 3)
  > (eval k)
 7
  > (define + *)
  > (define a 2)
  > (eval k)
 8
 ; Get the idea? All the symbols in k are only given values (Evaluated)
 ; when running (eval k). While in k, they are just place-holders -
 ; variable names.
 
 There's a short description about the Quote and Unquote mechanism in
 Scheme in the first practical session of Compilation course[3].
 
 Best way to run MzScheme - write your file in DrScheme (Don't run!). Save
 it to d:\foo.scm, and run MzScheme or Petite. Type (load "d:\foo.scm"),
 and the files loads up. Make sure you know where your files are!
 
 [1] Called R5RS, http://www.schemers.org/Documents/Standards/R5RS/r5rs.pdf
 [2] Called The Little LISPer.
 [3] Bottum of page 4 at
 http://www.cs.bgu.ac.il/~gmayer/courses/compiler-construction/tirgul1.pdf