Spring 2006 CAP 6938 Topics in Neuroevolution and Artificial Embryogeny

MW 2:30 - 3:45 in COMM 110 (note room change from ENG 286)

Instructor: Dr. Kenneth Stanley
Email: kstanley@cs.ucf.edu
Website: http://www.cs.ucf.edu/~kstanley
Office: CSB 254

Office Hours (starting 1/17/06): Mondays at 4pm and Tuesdays at 3pm



New: Software Created in Our Class Available Here


Real-time NEAT source code available

You can download rtNEAT source code here. This version of NEAT is also stripped down so it should compile with any OS with minimal effort.

Stripped Down Version of NEAT

neatVS.zip

This version of NEAT is provided by Jared Johnson based on my original code. He is making it available so people having trouble compiling NEAT have a chance to play with it now. Here's what Jared says about it:

"I just took out all visualization and guile references, as well as modified a few syntactical errors which showed up in Visual Studio which gcc supports. It is hard-coded to run the XOR test, which I have run with this version of the code. I haven't tested the other two experiments, though they should work. It just requires you to include the initialization file you are using as a command line argument."

Texts

Fundamentals of Neural Networks by Laurene V. Fausett (1994)

An Introduction to Genetic Algorithms by Melanie Mitchell (1996)

Assorted Current Research Papers

Overview

The purpose of this artificial intelligence (AI) course is to introduce students to current topics at the intersection between neural networks and evolutionary computation. Recent advances in evolving artificial neural networks (i.e. neuroevolution) have resulted in new ways to produce controllers for a broad range of difficult sequential decision tasks, including robot and autonomous vehicle control, pattern generation, limb coordination, warning systems, factory optimization, and intelligent video games. Neuroevolution has helped make such applications possible because it allows the computer to learn control policies without any prior knowledge of the domain on the part of the experimenter: A Darwinian survival-of-the-fittest competition among neural networks leads to increasingly sophisticated solutions without the need for human design. However, such a process requires a principled approach to combining, selecting, and encoding large, complex neural networks. This course will introduce students to the cutting edge of such research, culminating in a project in which students program their own variant of the NeuroEvolution of Augmenting Topologies (NEAT) method, which can evolve increasingly complex structures over time. While the original NEAT evolves only neural networks, students will not be restricted in the type of structure their system can evolve. In this way, students will become experts through hands-on experience. The class will conclude by examining sophisticated encoding techniques based on the growth of an embryo from a single cell (i.e. artificial embrogeny). Such techniques promise to facilitate the evolution of neural networks with orders of magnitude more complexity than has been heretofore possible.

Grading Policy

Grades will be based 25% on implementation milestones and 75% on a final project. Students may work with a partner or work alone. Students working with a partner must periodically report how they are allocating tasks.

Project Milestones (25% of grade):
2/6: Initial proposal and project description
2/15: Domain and phenotype code and examples
2/27: Genes and Genotype to Phenotype mapping
3/8: Genetic operators all working
3/27: Population level and main loop working
4/10: Final project and presentation due (75% of grade)

Syllabus

Week 1 (Jan. 9 - 14)

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

Lecture 1

Lecture 2

Read chapter 1 of Fausett

Week 2 (Jan. 16 - 20) (only the 18th; 16th is MLK Day)

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

Lecture 3

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 (Jan 23 - 27)

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

Lecture 4

Lecture 5

For 1/23: Mitchell ch.1 (pp. 1-31) and ch.2 (pp. 35-80) ..Note Section 2.3 is "Evolving Neural Networks"
For 1/25: Mitchell pp. 117-38, ch.5 (pp. 170-177)
paper: No Free Lunch Theorems for Optimization (1996) by David H. Wolpert, William G. Macready

Week 4 (Jan 30 - Feb. 3)

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

Lecture 6

Lecture 7

Homework due 2/6/06: 1 page project proposal including project description and goals, a falsifiable hypothesis on what you expect to happen, why it involves structure, and what platform you will use (language and OS). If partners, describe briefly division of labor. Please turn in a hardcopy

For 1/30/06:
Genetic Algorithms and Neural Networks by Darrell Whitley (1995)
Evolving 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)

For 2/1/06:
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)

Week 5 (Feb. 6 - Feb. 10) Projects Officially Begin

NeuroEvolution of Augmenting Topologies (NEAT): Overcoming the obstacles

Lecture 8

Lecture 9

Student Projects Begin.

Remember: Homework due 2/6/06: 1 page project proposal including project description and goals, a falsifiable hypothesis on what you expect to happen, why it involves structure, and what platform you will use (language and OS). If partners, describe briefly division of labor. Please turn in a hardcopy

Homework due 2/15/06: 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.

Read in detail for 2/6/06:

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

Read for 2/8/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)

Week 6 (Feb. 13 - Feb. 17)

Artificial Embryogeny: The Power of Reuse, Prior Work, Biological Underpinnings, Skeptical Perspective

Lecture 10

Lecture 11: Only given in class

Remember: Homework due 2/15/06: 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.

Read for 2/13/06:

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

Read for 2/15/06:

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 amd R. Pfeifer (2003)
Multi-cellular development: is there scalability and robustness to gain? by Daniel Roggen and Diego Federici (2004)

Week 7 (Feb, 20- Feb. 24)

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

Lecture 12

Lecture 13

Homework due 2/27/06: Working genotype to phenotype mapping. Genetic representation completed. Saving and loading of genome file I/O functions completed. Turn in summary, code, and examples demonstrating that it works.

Read for 2/20/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)

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)

Read for 2/22/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

Week 8 (Feb. 27 - Mar. 3)

Continuing real-time NEAT and more realistic neural models (adaptive synapses)

Lecture 13-2 (continuing lecture 13 from the last lecture, which we didn't complete)

Lecture 14

Homework due 2/27/06: Working genotype to phenotype mapping. Genetic representation completed. Saving and loading of genome file I/O functions completed. Turn in summary, code, and examples demonstrating that it works.

New Homework due 3/8/06:
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.

Read for 3/1/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 9 (Mar. 6 - 10)

More on realistic neurons: Leaky integrator neurons Non-neural NEAT (Cellular Automata, FSMs, Music, Morphologies, RBFs, Graph structures, etc.)

Lecture 15

Lecture 16

Homework due 3/8/06:
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.

Read for 3/6/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 3/8/06: Mitchell Textbook pp. 44-55 (Evolving Cellular Automata)

__Spring Break__ (Mar. 13 - 17)

Week 10-12 (Mar. 20 - 24, Mar. 27 - 31, April 3-7, April 10) Projects Officially End on April 12

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

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

Homework due 3/27/06:
Population level and main loop working:

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.

Weeks 13-14 (April 12, April 17,19, April 24, Final (April 26th 1-3:50)

Projects Due April 12th (note the date has been extended by 2 days)

Projects should be formatted as a conference paper:

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

Final Presentation Schedule

Schedule:
4/12/06
2:30-2:45 Nick Beato: Melody Composition
2:48-3:03 Chris Gullette: Bejeweled Player
3:06-3:21 Sean Szumlanski: Bartering with Images
3:24-3:39 Scott DeBoer: Guitar Distortion Effects


4/17/06
2:30-2:45 David Duncan: Instrument Synthesis
2:48-3:03 David Adams and Adam Campbell: Alife World
3:06-3:21 Jason Gauci: Riot simulation
3:24-3:39 David D'Ambrosio: Soda Race


4/19/06
2:30-2:45 Erin Hastings: Interactive 3D Models and Particle Systems
2:48-3:03 Jared Johnson: Ant Colony
3:06-3:21 Anton Kiriwas: Poker Player
3:24-3:39 Shafaq Chaudry and Victor Hung: Sensor Networks


4/24/06
2:30-2:45 Chris Millward: First-capture Go
2:48-3:03 Remo Pillat: Resilient Lego Buildings
3:06-3:21 Michael Rosario: Beat Generation
3:24-3:39 Jimmy Secretan: NLP Parse Tree


Final (4/26, 1-3:50)
1:00-1:15 Andy Schwartz: Chord Progressions
1:18-1:33 Musawir Shah: Image Super-resolution
1:36-1:51 Gary Stein: Human Modeling
1:54-2:09 Jin Lyu: Interactive Image Evolution
2:12-2:27 Greg Tener: Grammar Compression
2:30-2:45 Ben Vanik: Space Game
2:48-3:03 Ian Wharton: Air Hockey
3:06-3:21 Jaakko Konttinen: Tone Mapping
3:24-3:39 Buffer time