CS81 Lab3: Evolving with NEAT

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.

• To begin, run update81 to copy some starting point files into the directory cs81/labs/3/.
• If at any point you are interested in seeing how NEAT has been implemented, the source code is available here:

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

In Lab 1 we used the back propagation algorithm to learn the weights of a fixed architecture neural network to solve XOR. Now we can 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 evolveXOR.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). The line pop.epoch(...) is what starts a NEAT evolution. The first parameter specifies the maximum number of generations to run, which in this case is 30.
• The evolveXOR.py file loads a configuration file. Open this file, called xor_config, in an editor. This is where all of the parameters are set for the evolutionary run. You must define the number of input and output nodes in the neural network as well as the activation function that will be used. You must also determine the population size and a maximum fitness threshold that if reached will terminate evolution. There are many parameters that must be set for NEAT. If you are curious about particular paramters, refer back to the NEAT paper we read or 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 in the file evolveXOR.py. 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 evolveXOR.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. If evolution found a particular network that surpassed the maximum fitness threshold it will terminate early. Otherwise it will complete the entire 30 epochs.
• Executing evolveXOR.py will generate two files with a .svg extension. These can be viewed using xv:
  1. A graph of the average and best fitness over time (avg_fitness.svg)
  2. A depiction of how the speciation changed over time (speciation.svg)
  Look at these graphs. Note the best fitness achieved and in what generation it was found.
• Executing evolveXOR.py will also generate a file storing the chromosome of the best network from every generation of evolution. We can test out any one of these networks by doing the following and replacing n with the appropriate generation number:

  % python evaluateXOR.py best_chromo_n
  

This will print a description of the nodes, the connections, and the network's output (both the target values and actual output). Sometimes these networks can be quite complex. Executing evaluateXOR.py will also generate a file to help you visualize the network structure. To see a visualization of the network from generation n do:

% xv phenotype_best_chromo_n.svg

Evaluate the best network found by NEAT. Also visualize its architecture.
• Try executing the xor evolution several times. How variable are the results? Does the complexity of the resulting networks seem to match the difficulty of the problem? How many hidden nodes did you need to solve XOR with backprop?

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 world with 10 randomly located lights, representing food, and allow it to explore and eat as long as it has energy to move. We will test the robot with three different random placements of the food. The network has three input units representing the left and right light sensor values as well as an energy warning value. As its energy level gets low the warning value increases. The network has two output units representing the motor speeds of the left and right wheels of a simulated Pioneer robot. The fitness value is based on the total number of steps the robot survives in the three trials.

• Go to your cs81/labs/3/energy/ directory and open the file evolveEnergy.py. This file is similar to the evolveXOR.py file, but has additional code to run the pyrobot simulator. Read through the next step, start the evolutionary process running, and then come back and look through this file.
• Go to a terminal window and start the evolution process running:

  % python evolveEnergy.py
  

  This program uses the pyrobot simulator, but does not display it in order to speed up the fitness evaluations. This will still take some time to complete. The evolution is set to run for just 11 generations, using a population of 20 individuals. A more reasaonable test would be to use a larger propulation (at least 30-50 individuals) and more generations.
• As in the XOR problem, at the end of each generation the chromosome with the highest fitness will be saved in a file called best_chromo_n where n is the generation number. You can test these chromosomes while evolution is still running by doing:

  % python evaluateEnergy.py best_chromo_n log_file
  

  The second parameter is the name of a log file (of your choice) where details of the evaluation will be saved. Observe the behaviors of the best networks from each generation and look at the log files that are produced. Are robots from later generations able to survive longer than their predecessors? Does NEAT complexify the networks in order to achieve this increased rate of survival? What kinds of behaviors are developed?

There are many different ways of implementing a food foraging task. Each of the choices made in the above program could affect the types of behavior that resulted. Here are just some of the issues that must be considered:

• How should energy be handled?
  • How much initial energy should the robot be given?
  • How much energy should eating a piece of food provide?
  • How much food should be provided in the environment?
  • Should each step consume an equal amount of energy?
  • Should staying still consume less energy than moving?
  • Should moving fast consume more energy than moving slowly?
• What sensors should be provided?
  • How should the robot's energy level be represented?
  • Should the robot be given range sensors for detecting walls?
  • How should the robot detect food?
• How should fitness be measured?
  • Should networks be tested in random environments?
  • Should networks be tested in identical environments to ensure fair comparisons?
  • How many trials per fitness test are sufficient?
  • When a robot stalls should it die immediately and lose any accumulated energy?
• How should the NEAT parameters be set?
  • Should more speciation be encouraged?
  • Should the probability of adding nodes or connections be changed?

Look carefully at the file evolveEnergy.py and list each of the choices that were made for each issue given above.

Then in the directory cs81/labs/3/modifiedTask create your own version of the food foraging task that makes some different choices. In the text file experimentalLog keep a record of the options you tried (even if they failed). Be sure to explain each idea you explored, how you tested its effectiveness (list key parameter settings such as population size, maximum number of generations, etc.), and the results.

For example, you might decide that testing each network in random environments is too noisy, and that a better test would be to use a fixed environment similar to the one in the robot duel. Re-write the code to do this, run it, and report on what happens.

When you are done run handin81 to turn in your completed lab work.