This assignment involves writing a one-dimensional cellular automata (1DCA) and evolving rule sets for it via both the genetic algorithm (GA) and genetic programming (GP). The desired rule set is one that generates a random sequence of bits in the time series of states for the middle cell of the 1DCA. Randomness is measured as entropy, as discussed in the Koza article (ICGA '91) and an excerpt from Koza's book (Pick up at IFI main office or in the ITX box outside the institute on the 4th floor).
In both the GA and GP case, the 1DCA will be run on the same initial string: all 0's except for a 1 in one of the 2 middle cells (i.e., the cell at which you take the entropy readings). Use 32 cells in your state and assume a neighborhood of radius 1. However, your 1DCA should take the radius and state width as parameters, thus allowing for more general simulations. The timesteps that the 1DCA runs should also be a parameter. So your 1DCA will accept as input an initial binary string, a rule number, a neighborhood radius, and the total number of timesteps. It will return an entropy value.
Your 1DCA should never actually generate a rule table. The rule number itself (and its binary representation) are enough to compute the next state for any of the possible neighborhoods (8 in the radius=1 case). To convert between rule numbers and their binary representations, and between neighborhood state vectors and their corresponding indices into the virtual rule table, use the functions bitarray-to-integer, bitlist-to-integer andinteger-to-bitarray in file listops3.lsp.
To calculate the the entropy of a time series, use the function bitlist-entropy instats.lsp.This includes a chunk-size parameter, which you should set to 4 (just like Koza). That means that you'll be considering 4-bit strings to compute randomness/entropy. Remember: high entropy implies more randomness. When you're counting n-bit sequences, the maximum entropy is n.
In the GA case, your genome should simply encode the rule number in binary, as discussed in class. In the GP case, the s-expressions can get pretty long and take a lot of time to run. An important shortcut is the following: test each individual s-expression on all possible neighborhoods. The neighborhood-output pairs for the s-expression can then be used to figure out which rule the s-expression encodes. The appropriate rule number can then be used in the 1DCA, thus saving the expense of running the s expression thousands of times! Note that crossover will still occur between s-expressions to generate new generations, but the s-expressions should be converted to rules before running the 1DCA.
Another time-saving trick is to keep a table of entropy values associated with each of the rule numbers. Then if you generate an s-expression that corresponds to rule 73, and if rule 73 was already tested (on the current input) and yielded a 4-bit entropy of 2.75, then there's no reason to run the 1DCA again with the same rule and same input. The result will be exactly the same. The table will grow as more rules are tested, so the latter generations should be quicker to simulate. The table should be generated from scratch on each run of the entire system (GA/GP and 1DCA) to account for possible changes to the initial input state from run to run.
Failure to use at least the first of the two shortcouts could result in hours of needless work for your computer, leaving you yawning in front of the computer screen while your friends are out enjoying this wonderful Trondheim winter, so use these shortcuts!!
To actually run the s-expressions, you will need a wrapper macro which is called at runtime. Most macros are called at compile time, so to delay the call, you'll need to use eval. Here are excerpts from a GP soccer program that illustrate one possible approach.
(defmacro sanacc (angaccel) `(setf angleacc (* (signum ,angaccel) (mod ,angaccel (* 2 pi)))))
(defmacro sang (new-angle) `(setf angle (* (signum ,new-angle) (mod ,new-angle (* 2 pi)))))
(defmacro svel (new-vel) `(setf vel (* (signum ,new-vel) (mod ,new-vel 10))))
(defmacro run-goalie-code (goalie ball)
`(let ((xdiff (- (locx
,ball) (locx ,goalie)))
(ydiff (- (locy ,ball) (locy
,goalie)))
(xvel (* (vel ,ball) (cos (angle ,ball))))
(yvel (* (vel ,ball) (sin (angle ,ball)))))
(with-slots
(acc angleacc angle vel) ,goalie
,(phenotype goalie))))
The run-goalie-code is a macro that produces a code chunk consisting of a wrapper and the s-expression, which resides in the phenotype of the goalie. The wrapper, a let expression, contains 4 key variables: xdiff, ydiff, xvel and yvel. These variables are part of the GP terminal set. It is important that the let variables have exactly the same names as the terminals, since these terminal names will appear in the s-expression (phenotype goalie). This extra level of complexity is required, since these terminals are not constants but depend upon the positions of the goalie and ball, and these vary in time. See soccer.lsp for all the details.
Normally, macros are called at compile time, but in GP scenarios, the macro must be called at runtime, since we don't know the phenotypic s-expression until runtime. To delay the macro call until runtime, the goalie-move method uses an eval. Without the eval, run-goalie-code would be expanded at compile time, but since (phenotype goalie) is unbound at compile time, we would get a worthless expansion or an error. Other approaches are conceivable, but the nature of eval makes things tricky. In a nutshell, eval uses a null lexical closure, making it hard to use evals inside of wrappers. Here, we have a wrapper (the macro) inside the eval, so when running the phenotypic s-expression, Lisp gets the correct bindings for xdiff, ydiff, etc.
(defmethod goalie-move ((g goalie) (b ball) timestep)
(eval
`(run-goalie-code ,g ,b)) ;; code can alter acc and angleacc
(move g
timestep))
The formal assignment is thus to write the 1DCA and use it to evolve rule populations. In one case, the rules will be encoded as GA chromosomes, while in the second case, the rules will be encoded as s-expressions (but converted to rule numbers using the shortcut mentioned above). In both cases, your job is to experiment with different settings of the GA/GP as you let the system search for good high-entropy rules. Hand in your (thorougly commented!) code and a description of the different parameter settings that you used in search of good rules. Also answer the following questions in detail:
1. Which method seems most appropriate for this task, GA or GP? Why?
2. Compare the search spaces for the GA and GP approaches to this problem. Are they the same? Why or why not?
Minor warning: This is probably the most time-consuming of the 4 homework assignments. If you think carefully about the 1DCA, you should be able to code it up in about a page. Use the bitarray-integer conversion functions as much as possible. Also, read Koza's paper and book excerpt carefully before beginning.