# CAP 5512 Evolutionary Computation

## Spring 2007

by Ivan Garibay, University of Central Florida, January 16, 2007.

The students final projects for this class have been published as a CS technical Report:

- Garibay I.(Editor) (2007). "Student Papers, Evolutionary Computation Class, Sprint 2007".
*Technical Report Number CS-TR-07-11, SEECS, University of Central Florida*.

Skip to Lecture Notes (topics covered, distributed material, homeworks, deadlines, etc.)

Skip to Important Dates

Student presentations schedule (last updated: Feb 19, 2007)

•

**Instructor:**Dr. Ivan Garibay, UT 556, 407-882-1163, igaribay@cs.ucf.edu (please include CAP5512 on the subject line of all emailed correspondence)•

**Prerequisites:**Graduate standing or instructor permission. No knowledge of biology or evolutionary search is assumed. Computer programming ability in some language is necessary for the projects.•

**Class Times:**Tuesdays and Thursdays, 4:30 PM – 5:45 PM•

**Class Location:**BA 0212•

**Final Exam Period:**April 26, 4:00 PM – 6:50 PM•

**Office Hours:**Before or after classes and by appointment at the UCF Office of Research and Commercialization, 12201 Research Parkway, Suite 501, Orlando, FL 32826 (UCF Research Park, University Towers Building). Map.•

**Textbook:**Evolutionary Computation: A Unified Approach, Kenneth A. De Jong, ISBN-10:0-262-04194-4; ISBN-13: 978-0-262-04194-2

## Objectives and Structure

This course has two main objectives:

**To teach the subject matter of evolutionary computation**with emphasis on discussing theoretical foundations, applications, and current active areas of research. Evolutionary Computation (EC) is a stochastic search method based on evolutionary biology. EC has been successfully applied to a variety of problem domains such as optimization and learning. This course will provide the students with the knowledge to implement EC algorithms, discuss trade-off between variations of EC algorithms, and discuss issues related to the application of EC algorithms to a particular problem.

**To provide experience with the research process**Students will be ask to read, review, present and discuss papers from scholarly publications. Two homeworks will provide experience to implement and/or use evolutionary algorithms and apply them to practical problems. The students will be asked to work throughout the course in a student-selected final class project. This project must be proposed, implemented, written-up as a paper, presented to the class, and peer reviewed by other students. In this way, the students will gain experience in the complete research cycle.

This course will be structured as follows:

- Two papers will be assigned each week. You will be asked to read the papers and write a one page summary/critique/comparison of the papers each week. These summaries will made up 15% of your final grade. Late summaries will not be accepted. You may drop two summaries.

- Each week two students will be asked to present the papers for that week to the class in an oral presentation. This presentation will include summarizing the paper and leading a discussion on the paper topic. These presentations will made up 20% of your final grade.

- You will have two homework projects during the first half of the course. All programming can be done in any programming language. These homeworks will be worth 25% of your final grade.

- Throughout the class you will work on a final research project. Before the middle of the course each student proposes an individual project. The proposed ideas are discussed in one or more individual meetings and one particular project is agreed upon between the instructor and the student. During the second half of the course, the student carries out the agreed project. The student writes up his/her work in a 8 to 10 pages paper (in the style of a conference paper). Towards the end of the semester all students will be ask to present their project to the class. The project due date, students must bring three extra copies of their project to be distributed to other three students to be anonymously peer reviewed. The last day of classes all students must bring their written reviews. Your final project grade will be partially based on the peer reviews of your work and the reviews that you write about other students projects. All projects will be compiled into a class book and published as an EECS Technical Report and also in the class website. Copies of this book will be distributed to all students. This final research project is worth 40% of your final grade.

## Important Dates

- First lecture – Tuesday, January 9, 2007
**Project proposal approved – Tuesday, February 27, 2007****Project Update – Tuesday, March 20, 2007****Projects due – Tuesday, April 10, 2007**- Last lecture – Thursday, April 19, 2007
- Project peer reviews due – April 26, 2007
- Distribution of course book – April 26, 2007
- Grades due – Thursday, May 3, 2007

## Lecture Notes

### Lecture 1, January 9, 2007

- Course introduction and administrative stuff
- Materials:
- CAP5512 Syllabus
- Presentations Schedule (last updated: Feb 9)

### Lecture 2, January 11, 2007

- Topics Covered:
**Evolutionary Algorithms (EAs): What are they?**- Darwinian Evolution, Mendelian Genetics, Turing's Genetic Search, and Holland's Genetic Algorithms (GAs).
- Stochastic Search and Evolutionary Computation
- GA components: problem representation, selection function, fitness function, and genetic operators.
- GA pseudocode

- Materials:
- Introduction to Evolutionary Algorithms: CAP5512: Handout 1 and CAP5512: Presentation 1

### Lecture 3, January 16, 2007

- Topics Covered:
- Evolutionary Process
**EAs: How do they work?**- GA Optimization: One Max Problem: our class becomes a random number generator for running a single GA loop by hand
- Tournament Selection
- One-point Crossover
- Bit-flip Mutation
- Analysis of One Max Problem's experimental results.

- Materials:
- Genetic Algorithms (CAP5512: Handout 2)
- CAP5512 Homework Assignment 1

- Coding Options:
**Write your own**, any language (highly encouraged, you can base your system in the textbook's sample code)- Use available systems (if you choose this option, be prepared to expend time to fully undestand the source code and to make code changes)

**UCF ECLab Basic GA Code (Java)**: (tar.gz format) (zip format) . Code instructions: (1) Unzip/Untar-ungzip; (2) compile "javac Search.java"; (3) run "java Search onemax.params". Pros: simple to use. Cons: not very well documented, only GA.**De Jong's Very Simple EC System (Java):**see Appendix A from the textbook, download code here. Pros: simple to use, well documented, basis for any EA. Cons: very minimal

**Luck's ECJ (Java):**ECJ 14 and 15. Pros: complete complex large system, relatively well documented, mostly used for GP but basis for any EA. Cons: complex large system**Garibay's EC System (C):**Available to students upon request

- Deadlines:
- Homework Assignment 1 Due: January 30th, 2007

### Lecture 4, January 18, 2007

- Topics Covered:
**EAs: Why do they work? (stochastic search answer)**- Universal limits of search: No Free Lunch Theorems
- Search Spaces, Fitness Landscapes
- Random, Needle-in-a-haystack, and one-max fitness landscapes
- Search Algorithms and Stochastic Search
- Why stochastic search works? Key property

- Papers for next week presentations :
- Optimization of Control Parameters for Genetic Algorithms, by John J. Grefenstette

### Lecture 5, January 23, 2007

- Topics Covered:
- Biological Terminology, DNA, RNA, crosmosomes, individuals, gene, protein, genotype, phenotype, development, genome, proteome.
- Presentation: Kevin Kelly

- Papers for next week presentations :
- Parameterized versus Generative Representations in Structural Design: An Empirical Comparison, by Rafal Kicinger et. al.
- Understanding Cooperative Co-evolutionary Dynamics via Simple Fitness Landscapes, by Elena Popovici et. al.

### Lecture 6, January 25, 2007

- Topics Covered:
**GAs: Why do they work? (GA schema analysis answer)**- Building Block Hypothesis
- Schema Theorem (Holland, 1975)
- How does GA process schemata?
- GA implicit parallelism

### Lecture 7, January 30, 2007

- Topics Covered:
- Presentation:Anthony Vaiciulis
- Presentation:Victor Hung

- Deadlines:
- Homework Assignment 1 Due Today
- Homework Assignment 1 Due: Feb 13th.

- Materials:
- Papers for next week presentations :
- Measuring, Enabling and Comparing Modularity, Regularity and Hierarchy in Evolutionary Design, by Gregory S. Hornby
- On the Complexity of Hierarchical Problem Solving, by Edwin D. De Jong, Richard A. Watson, and Dirk Thierens

### Lecture 8, February 1, 2007

- Topics Covered:
**The evolution of cooperation**- Iterated Prisoner's Dilemma
- Axelrod's tournaments and orginal experiments
- Evolutionary Stable Strategies, Evolutionary Game Theory
**EAs: Why do they work? (GA schema analysis answer)**- Schema Theorem with only selection

### Lecture 9, February 6, 2007

- Topics Covered:
**EAs: Why do they work? (GA schema analysis answer)**- Destructive and Constructive Effects of Crossover and Mutation on Schemata
- Probabilities of Schema Surviving Crossover
- Presentation: Kevin Kelly

- Papers for next week presentations :
- A Game-Theoretic Memory Mechanism for Coevolution , by Sevan G. Ficici and Jordan Pollack
- Emergence of Collective Behavior in Evolving Populations of Flying Agents , by Lee Spector et.al.

### Lecture 10, February 8, 2007

- Topics Covered:
**EAs: Why do they work? (GA schema analysis answer)**- Probabilities of Schema Surviving Mutation
- Complete Schema Theorem (selection, crossover and mutation)
**Evolutionary Computation: A Historical Perspective**- Early Algorithmic Views
- EC = Optimization
- EC = Adaptation (feedback-controler)
- EC = Evolution of Programs (DNA code)

- 1970's
- Evolutionary Programming
- Evolution Strategies

### Lecture 11, February 13, 2007

- Topics Covered:
- Presentation: Abhishek Das
- Presentation: Grantham Anil

- Deadlines:
- Homework Assignment 2 Due Today
- Project Proposal Presentation Due: Feb 27th. (to be presented in class, you have 5-10 minutes)
- 5 presentation slides: ( maximun of 8 if you have to )
- The Research Problem
- Previous Approaches (summarize 3 recently published papers)
- The Proposed Idea (your approach)
- The Proposed Methodology
- Timeline

- 5 presentation slides: ( maximun of 8 if you have to )

- Materials:
- Papers for next week presentations :
- An evolved circuit, intrinsic in silicon, entwined with physics, by Adrian Thompson
- Demonstrating the Evolution of Complex Genetic Representations: An Evolution of Artificial Plants, by Marc Toussaint

### Lecture 12, February 15, 2007

- Topics Covered:
**Evolutionary Computation: A Historical Perspective (cont.)**- 1970's
- Genetic Algorithms

- 1980's
- Optimization Applications
- Other Applications

### Lecture 13, February 20, 2007

- Topics Covered:
- Presentation: Verbancsics
- Presentation: McDaniel

- No Papers for next week, Next week only Final Project Proposal Presentations
- Schedule one-to-one meetings to discuss with me about your proposal

### Lecture 14, February 22, 2007

- Topics Covered:
- 1990's
- 2000's
**Canonical Evolutionary Algorithms**- EV(m,n)
- Evolutionary Programming
- Evolution Strategies
- Genetic Algorithms