Evolutionary Computation and Artificial Life (202-1-5171), Semester A, 2006-2007
| Exercise 3 |
Choose one of the following two options:
Notes:
If fitness evaluation is too slow use only a random sampling of the 65,536 test cases.
Submit:
In this option you are to use genetic programming to solve the problem of evolving a robot to follow a wall. The definition of the problem is given in Koza's paper.
Notes:
The edging distance (EDG) representing the preferred distance between the robot and the wall is 2.3 feet. The minimum safe distance (MSD) between the robot and the wall is 2.0 feet. Assume the two protrusions are 7 feet by 4. You can also assume the grid is 30 feet by 30 feet.
A simple way to compute where the sensor "line" intersects the wall or protrusion is to divide the grid into small boxes (say, 900, 1 foot by 1 foot each), and mark each box with zero (no protrusion) or 1 (protrusion). Then use a line algorithm (see also here).
Population size (M) is 500, and number of generations (G) is 51. You may change these values if they don't work.
Submit:
Option 2 carries an automatic 10-point bonus. In addition you can accumulate UP TO 10 additional bonus points by adding to the basic setup. For example:
The exact number of bonus points you receive will be decided by the grader according to quality and sophistication.
1. A random number generator in scheme.
2. Comments of Aviv Eyal (2004):
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