In this lab you will experiment with an evolutionary computation method called NEAT (Neuro Evolution of Augmenting Topologies) developed by Kenneth O. Stanley. NEAT operates on both the weights and the structure of the neural network, allowing connections and nodes to be added as potential mutations. We will be using a python package that implements NEAT.

You may work with a partner on this lab.

• To begin, run update81 to copy some starting point files into your home directory (cs81/labs/3/).
• To be sure that you have access to the neat package do the following:

  % python
  >>> from neat import *
  

  If you are not able to import the neat package, let me know, otherwise exit from python.
• To see the source code for the neat package, go to:

  /usr/local/stow/cs81/lib/python2.5/site-packages/neat
  

In Lab1 we used the back propagation algorithm to learn the weights of a fixed architecture neural neural network to solve XOR. In this lab we will use NEAT to evolve both the weights and the architecture of a neural network to solve XOR.

• Go to your cs81/labs/3/xor/ directory and open the file xor.py in an editor. Notice at the top of this file that it imports a number of different classes from the neat package, including population, chromosome, genome, and nn (for neural network). In Lab 1, we used conx, which was part of pyrobot to implement neural networks. For this lab we will be using neat's implementation instead.
• Next the xor.py file loads a configuration file. Open the file xor_config in the editor as well. This is where all of the parameters are set for the evolutionary run. If you are curious about particular paramters, go to the source code to see how they are used.
• The user must define an appropriate fitness function for the problem being solved. In this case, fitness is defined in the eval_fitness function. For each chromosome in the population, the chromosome is first translated into a feed-forward neural network. Then that network is tested on the four standard XOR patterns, and the total sum-squared error is calculated. Finally the error value is used to create a fitness value that increases as error decreases.
• Go to a terminal window and try solving the XOR problem:

  % python xor.py
  

  This will produce a number of messages detailing the progress of the evolutionary process. For each generation you will see the average fitness, best fitness, number of species, and information about each species. At the end, will be a summary of the architecture of the best performing individual found, and a demonstration of how it perfroms on the four patterns.
• Executing the xor.py will also generate three files with a .svg extension. These can be viewed using inkscape:
  1. A graph of the average and best fitness over time (avg_fitness.svg)
  2. A picture of the best individual network's architecture (phenotype.svg)
  3. A depiction of how the speciation changed over time (speciation.svg)
• Try executing the xor evolution several times. Is the same neural network architecture found each time? How variable are the results?

The NEAT paper we discussed this week involved a very time consuming fitness test intended to create a co-evolutionary arms race. We will experiment with a simpler scenario in this lab. Rather than a robot duel, we will focus on a single robot foraging for food. We will place the robot in a large room with 10 randomly located lights, representing food, and allow it to explore for 200 steps. We will test the robot with three different random placements of the food. The initial network will begin with two input units representing the light sensor values and two output units representing the motor speeds of the left and right wheels of a simulated Pioneer robot. The fitness value will be based on the number of lights consumed by the robot.

• Go to your cs81/labs/3/robot/ directory and open the file eat.py. This file is similar to the xor.py file, but has additional code to start up the pyrobot simulator using the world LightAsFood.py. Try to understand how it works, and ask questions if you need any clarification.
• Go to a terminal window and start the evolution process running:

  % python eat.py
  

  This will take quite a while (probably several hours). I am working on ways to speed this up by running it without the GUI. The evolution is set to run for 20 generations, using a population of 30 individuals. Each fitness test involves at most 600 steps in the simulator (if the robot is ever stalled against a wall, the fitness test ends early).
• At the end of each generation, the chromosome with the highest fitness will be saved in a file called best_chromo_NUM where NUM is the generation number. After the entire evolution process is complete, you can test each of these chromosomes to understand how the final solution was incrementally developed.

  % python eat.py best_chromo_NUM
  

  This is will print out a summary of the network's architecture and then convert the chromosome into a feed-forward neural network and use it to control the robot in several new random food configurations. Create a text file called eat-summary and record how well each network performs in testing, as well as any changes in the network architecture in a table like this:

  Generation  TestFitness  DescriptionOfArch
  0
  1
  2
  ...
  

  In addition, do a qualitative analysis of the robot's behavior. In other words how does it change over the course of evolution? Do improvements in behavior seem to correlate with enhancements in the network architecture?

We will be using NEAT for our midterm project. Start brainstorming about what task you'd like to work on. Store your ideas in the directory cs81/labs/3/midterm/. If you will need a new simulator world create it here. Create a file called midterm-proposal where you describe your proposed task and provide a detailed explanation of the fitness function you would use.

• Be sure that all the relevant files are in your cs81/labs/3/ directory.
• Only one member of each team needs to run handin81 to turn in the completed lab work.