Fall 2006 CAP 6938 Topics in Neuroevolution and Developmental Encoding:
Homework Assignments and Lectures

Because of school cancellation due to Ernesto, homework due 8/30/06 is now due 9/6/06 instead (9/4 is Labor Day). The project proposal deadline has been extended to 9/13 to give you more time to find a partner. Please post a personal add by emailing our TA, Shafaq Chaudry. I will hold additional office hours at 2:30 on 9/6/06, to make up for Labor Day.

MW 4:30 - 5:45 in ENG2 room 105

Instructor: Dr. Kenneth Stanley

Email: kstanley@cs.ucf.edu
Website: http://www.cs.ucf.edu/~kstanley
EPlex Research Group: http://eplex.cs.ucf.edu
Office: Harris 332

Office Hours (starting 8/28/06): Mondays at 2:30pm and Tuesdays at 3pm

TA: Shafaq Chaudhry, email: shafaq@cs.ucf.edu

Link to Class Syllabus

Late Policy:
1 Class Day Late: 10 points off 2 Class Days (i.e. 1 week) Late: No credit (5% off final grade)

Project Milestones (25% of grade):
9/11: Initial proposal and project description
9/22 (note extension): Domain and phenotype code and examples
10/9 (note extension): NN/CPPN activation, Genes ,and Genotype to Phenotype mapping
10/18: Genetic operators all working
11/1: Population level and main loop working
11/22 Final project and presentation due (70% of grade)

NEAT source code

Note that you will be writing your own version of NEAT so existing source code is only to be used as a reference. My homepage contains links to NEAT source code in many languages. The latest clean version written by myself is rtNEAT, available here. A stripped down version of my non-real-time code is neatVS.zip, refitted for easy compiling by Jared Johnson..

Partner Ads

In order to place an ad for a partner, please send an email to Shafaq Chaudhry (our TA) at shafaq@cs.ucf.edu. Please include in the subject line "CAP 6938." In the body of the message, please include your name, email, and a brief description of who you are, what you currently are interested in, and what you are looking for in a partner. When you find a partner, you should ask Shafaq to remove your ad.

All ads are available here.

Assigned Work

Week 1 (August 21, 23)

Context within AI, Prior Projects, Neural Networks Basics, Sequential Decision Problems, Complexity and Search

Lecture 1
Lecture 2

For 8/23: Read chapter 1 of Fausett

For 8/30 (note you have 1 week):
Fausett pp. 39-80 (in Chapter 2)
Fausett pp. 289-316 (in Chapter 6)
Chapter 1 of Sutton (on RL): Online Book ch.1
Optional: Kaelbling RL survey paper

Week 2 (August 28, 30)

NEAT/CPPNs Overviews and Applications (head start on project thinking);
August 30th cancelled due to Ernesto

Lecture 3

For 8/30 (extended to Sep. 6 because of Ernesto and Labor Day):
Fausett pp. 39-80 (in Chapter 2)
Fausett pp. 289-316 (in Chapter 6)
Chapter 1 of Sutton (on RL): Online Book ch.1
Optional: Kaelbling RL survey paper

Week 3 (Sept. 6 only; Labor Day off)

Topics in Neural Networks: Backprop, Hebbian Learning, Biological Inspirations, Reinforcement Learning

Extra office hours added 4-6pm Thursday, Sept. 7

Lecture 4

For 9/11: Mitchell ch.1 (pp. 1-31) and ch.2 (pp. 35-80) Note Section 2.3 is "Evolving Neural Networks"

Week 4 (Sept. 11, 13)

9/13/06 Milestone 1: Project Proposals Due (note extension)

Topics in Evolutionary Computation: Types of EC, Genetic Algorithms Basics
Genetic Algorithms Theory, Criticisms of EC, No Free Lunch;

Lecture 5
Lecture 6

For 9/13: Mitchell pp. 117-38, and ch.5 (pp. 170-177)
No Free Lunch Theo rems for Optimization (1996) by David H. Wolpert, William G. Macready

For 9/18:
Genetic Algorithms and Neural Networks by Darrell Whitley (1995)
Evolvin g Artificial Neural Networks by Xin Yao (1999)
Genetic set recombination and its application to neural network topology optimisation by Radcliffe, N. J. (1993). (Skim from section 4 on, except for 9.2)

Week 5 (Sept. 18, 20)

9/20/06 Milestone 2: Domain and Phenotype Code Due: Working domain and phenotype code. Turn in summary, code (if too long just include headers and put rest on web), and examples demonstrating how it works.

Neuroevolution (Evolving Neural Networks): Combining EC with NNs, Significance to AI
History of Neuroevolution, TWEANNS, The Competing Conventions Problem, Classic Obstacles

Lecture 7
Lecture 8

For 9/20:

Evolving Optimal Neural Networks Using Genetic Algorithms with Occam's Razor by Byoung-Tak Zhang and Heinz Muhlenbein(1993)
A Comparison between Cellular Encoding and Direct Encoding for Genetic Neural Networks by Frederic Gruau, Darrell Whitley, Larry Pyeatt (1996)
Solving Non-Markovian Control Tasks with Neuroevolution by Faustino J. Gomez and Risto Miikkulainen (1999)

For 9/25:

Evolving Neural Networks Through Augmenting Topologies by Kenneth O. Stanley and Risto Miikkulainen (2002)

Week 6 (Sept. 25, 27)

NeuroEvolution of Augmenting Topologies (NEAT): Overcoming the obstacles
Advanced NEAT;

Lecture 9
Lecture 10

For 9/27/06:

Evolving a Roving Eye for Go by Kenneth O. Stanley and Risto Miikkulainen (2004)
Neuroevolution of an Automobile Crash Warning System by Kenneth O. Stanley and Risto Miikkulainen (2005)

For 10/2/06:

A Taxonomy for Artificial Embryogeny by Kenneth O. Stanley and Risto Miikkulainen (2003)

Week 7 (Oct. 2, 4)

Developmental Encoding: The Power of Reuse, Prior Work, Biological Underpinnings, Skeptical Perspective
Shafaq presents her project and lessons learned from last semester

Lecture 11

For 10/9/06 (note that you have 1 week):

The Advantages of Generative Grammatical Encodings for Physical Design by Greg Hornby and Jordan Pollack (2001)
Evolving Complete Agents Using Artificial Ontogeny by J. Bongard and R. Pfeifer (2003)
Multi-cellular development: is there scalability and robustness to gain? by Daniel Roggen and Diego Federici (2004)

Week 8 (Oct. 9, 11)

10/9/06 (note extension) Milestone 3: NN/CPPN activation, Gene, And Genotype to Phenotype Mapping Due: Arbitrary-topology NN/CPPN activation with example inputs and outputs working. Genetic representation completed. Examples of genome to NN or CPPN mapping working. Saving and loading of genome file I/O functions completed. Turn in summary, code, and examples demonstrating that it works.

Advanced Topics in Developmental Encoding
Compositional Pattern Producing Networks (CPPNs)

Lecture 12
Lecture 13: Only shown in class

For 10/11/06:

Exploiting Regularity Without Development by Kenneth O. Stanley. To appear in: Proceedings of the AAAI Fall Symposium on Developmental Systems. Meno Park, CA: AAAI Press, 2006 (8 pages)
Optional longer version: Patterns Without Development Kenneth O. Stanley University of Central Florida Dept. of EECS Technical Report CS-TR-06-01 (40 pages)

For 10/16/06:

Competitive Coevolution through Evolutionary Complexification by Kenneth O. Stanley and Risto Miikkulainen (2004)
Towards Metrics and Visualizations Sensitive to Coevolutionary Failures by Ari Bader-Natal and Jordan B. Pollack (2005)

Optional Advanced Coevolution Papers of Interest:
Ideal Evaluation from Coevolution by De Jong, E.D. and J.B. Pollack (2004)
Monotonic Solution Concepts in Coevolution by Ficici, Sevan G. (2005)

Week 9 (Oct. 16, 18)

10/18/06 Milestone 4: Genetic Operators Due.
Genetic operators all working: Turn in summary, code, and examples demonstrating that all functions work. Must include checks that phenotypes from genotypes that are new or altered are created properly and work.

Lecture 13
Lecture 14

Competitive Coevolution and Complexification
Real-time NEAT and the NERO video game

Read for 10/18/06:

Shorter symposium paper: Evolving Neural Network Agents in the NERO Video Game by Kenneth O. Stanley and Risto Miikkulainen (2005)
Optional journal (longer, more detailed) paper: Real-time Neuroevolution in the NERO Video Game by Kenneth O. Stanley and Risto Miikkulainen (2005)

Visit The NERO Website

Read for 10/23/06:

Evolutionary Robots with On-line Self-Organization and Behavioral Fitness by Dario Floreano and Joseba Urzelai (2000)
Evolving Adaptive Neural Networks with and Without Adaptive Synapses by Kenneth O. Stanley, Bobby D. Bryant, and Risto Miikkulainen (2003)

Week 10 (Oct. 23, 25)

More realistic neural models: Adaptive synapses
More on realistic neurons: Leaky integrator neurons

Lecture 15
Lecture 16

Read for 10/25/06:

Levels of dynamics and adaptive behavior in evolutionary neural controllers by Blynel, J., and Floreano, D. (2002)
Evolution of Central Pattern Generators for Bipedal Walking in a Real-Time Physics Environment by Torsten Reil and Phil Husbands (2002)
Optional: Evolution and analysis of model CPGs for walking I. Dynamical modules by Chiel, H.J., Beer, R.D. and Gallagher, J.C. (1999)

Read for 10/30/06: Mitchell Textbook pp. 44-55 (Evolving Cellular Automata)

Week 11 first class (Oct. 30)

Non-neural NEAT (Cellular Automata, FSMs, Music, Morphologies, RBFs, Graph structures, etc.)

Lecture 17

Recommended Reference:

Section 3 of Real-time Neuroevolution in the NERO Video Game by Stanley, Bryant, and Miikkulainen

Week 11-12, 13 (Nov 1; Nov. 6, 8, Nov. 13)

11/1/06 Milestone 5: Population Level and Main Loop Due

Upon completing this assignment, you are running evolution. You may not necessarily get good results (you have a couple more weeks to get it working well), but the main architecture of your system is completed. Turn in summary, code, and examples demonstrating that all functions work.

Technical topics in implementing complexifying evolutionary systems and presenting results. (this unit will help people in finishing up their projects)

Weeks 13-15 (Nov. 15; Nov. 20, 22; Nov. 27, 29; Final)

Final Projects Due November 22nd

Projects should be formatted as a conference paper and all must be turned in on November 22nd:

Student Final Presentations: Students will have created their own complexifing evolutionary systems and will present results and methods from their projects.

Date Group Project Group Members Begin End  
22-Nov 1 Town planner Ashar Ahmad Swastikkumar Brahma 4:30 PM 4:50 PM  
  2 Arm thrower Gautham Anil Jeremiah T Folsom-Kovarik 4:55 PM 5:15 PM  
  3 Eye for faces Daniel Barber Alex Anatoly Katchourine 5:20 PM 5:40 PM  
27-Nov 4 Eye for shapes  Pavel Babenko   4:30 PM 4:50 PM  
  5 Game difficulty Thomas F Carbone   4:55 PM 5:15 PM  
  6 Reflectance Mark Colbert Elena Erbiceanu 5:20 PM 5:40 PM  
29-Nov 7 Song Composer James G Crowley Douglas Marshall Hathaway 4:30 PM 4:50 PM  
  8 Shirt design Abhishek Ajay Karnik John J Tanner 4:55 PM 5:15 PM  
  9 Tone Mapper Jaakko Tapio Konttinen   5:20 PM 5:40 PM  
4-Dec 10 Car Bodies Merrill Edward McKee Eric Andrew Risser 4:00 PM 4:20 PM  
  11 Risk Justin Miller Phillip Ryan Verbancsics 4:25 PM 4:45 PM  
  12 Audio filter Thomas Brendan Moore Wade H Spires 4:50 PM 5:10 PM  
  13 Morph Adelein Rodriguez Michael D Whiteley 5:15 PM 5:35 PM  
  14 Speech recog. Mark Varvak   5:40 PM 6:00 PM  
There are 50 more minutes of buffer time in the final after the last presentation.