CSE 848 Syllabus, Evolutionary Computation, M W, 3:00-4:20, 1455A BPS, Fall 2011

1.0 Description

Graduate survey course in Evolutionary Computation, with emphasis on its use in search and optimization. Will concentrate on fundamental aspects of Evolutionary Computation including history, theory and application. Pre-requisites are CSE or ECE Grad standing or permission of instructor (ECE majors, if you wish to have your enrollment in this course appear on your record as ECE-848, enroll in this section and then contact the ECE department when this class is completed.)

2.0 Objectives

This is an introduction to Evolutionary Computation (EC) for graduate students. It is intended as a fundamental introduction, as well as a survey of the many aspects of evolutionary algorithms (EAs), in particular GA, GP, ES, DE, PSO, and will concentrate on the basic concepts of representation, operators and overall control, followed by examples of the use of these concepts in important applications. As such, this course will not do much in-depth study of any one area. Rather this course is intended as a good introduction for those who have had no exposure to EC and as a stepping stone for those interested in more specific areas. Instead of using any particular book as a textbook, we shall try cover many key research papers related to EC. Students will make class presentations on articles they are assigned or chosen to present and also on their own term projects.

3.0 Instructors

Kalyanmoy Deb, Office 3247 Engg. Building, tel: 432-2144 and 1452 Beacon Center (BPS), tel: 884-2567. Email kdeb AT egr DOT msu DOT edu (preferred means to communicate with me).

4.0 Textbooks

A number of papers will be uploaded at the course website http://www.cse.msu.edu/~cse848 under "Tentative Course Schedule" as course notes. However, you can always look for papers anywhere that is appropriate. Remember, you have free access to many resources through MSU's Electronic Resources access point. Some recommended books for getting additional materials are as follows:

5.0 Grading

The grading scheme will be as follows:

Home Assignments (H1 to H4) 30%
Paper Presentation/Summary 30%
Term Project Presentation/Report 40%

There will be three components to the overall grading procedure. Four home assignments will be posted on the course website and will be announced in the class. Students are expected to return the solutions within the announced due date. Some assignments may require some computer coding and running them to get results. There will be one paper presenation assignment in which the students is expected to choose a suitable paper of interest on EC, read it carefully, prepare a two-page summary and make a presentation to the whole class. Finally, students are also expected to do a term project, preferably in a group of two formed by the students themselves. The project report will be due on 12 December 2011 (Monday) by 5 PM.

This is a graduate course, thus, all work is expected to be of professional quality. Mature programing skills are expected, such as in-program documentation (whenever asked to submit), style and completeness and the projects will be graded on these qualities as well as on their operation.

In particular, I expect all students to read the papers presented before the class. If the instructors feel that students are not participating in the class due to a lack of effort, then we will revert to having a midterm and/or a final to rectify the situation.

There is no late policy for grades. Anything turned in late gets 0% credit unless excused under university policy.

Office hours: 10:00-12:00 Hrs, Mondays at 1452 BPS. There will be time at the beginning of class to answer questions that might be of interest to the whole class, such as clarifications of assignments, etc. Appointments outside of normal office hours are available on request (preferably through email).

6.0 Tentative Course Schedule (Revised 10 Oct)

Date Topic with Lecture material Assignments Papers for Download
31-Aug Introduction to course, Scope of optimization   Classical optimization
7-Sep Intro to search and optimization, NFL theorem    
12-Sep Introduction to genetic algorithms (GAs) H1 announced Introduction to EAs
14-Sep Schemata and schema theorem, 2-arm bandit   A GA Tutorial
19-Sep GA basics, a case study   Constrained EAs
21-Sep Constraint Handling in GAs H1 due, H2 announ.  
26-Sep Constraints, Customized EAs, Schema comput.   Customized EAs
28-Sep Real-parameter EAs, DE, PSO, and ES   SBX recomb., PCX, DE, PSO
3-Oct Real-parameter EAs continued  
5-Oct PCX, DE Paper topic & H2 due
10-Oct Evolution strategy, multimodal EAs   See Introduction to GAs
12-Oct Multi-objective Optimization TP prop. & H3 announ. EMO tutorial
17-Oct Genetic Programming Prof. Punch
19-Oct Epistasis and Fitness landscapes Prof. Heckendorn
24-Oct Innovization Papers Uploaded Innovization
26-Oct Decision Making H3 due EMO-MCDM
31-Oct Analysis of EA Operators, population sizing Papers to be downloaded Selection operators, Mixing, Population sizing  
2-Nov Scheduling, meta-modeling, uncertainity Paper summary due Reliability based EAs
7-23 Nov Student paper presentations 11/07: H4 announced  
28-Nov - 14-Dec Term project presentations (three each day) 11/28: H4 due  
14-Dec   TP report due  

7.0 Presentations

Look for an assignment of paper presentation here. Each student will be required to make one paper presentation to the class, and also to present a term project (preferably, in a group of two). The paper presentations will last 20 minutes (15-minute presentation, 5 minutes of questions). Presentations will be strictly timed, just as if being done at a professional conference. You are adviced to practice your presentation before giving it, with the overhead materials you will actually use, to make sure it does not take too long. Don't try to memorize the presentation -- use the overheads as clues about what you should be talking about, but also (very important) don't just READ the overheads. You may use your laptop to make a presentation. For the paper presentation, each student will prepare a two-page summary sheet that summarizes the paper to be presented and is to be submitted before the presentation. This summary should provide an overview of the important points of the paper, as well as any background material that may be required. The summary should address issues like the following:

Application Papers

  1. Briefly describe, the problem, in terms of inputs, outputs, evaluation function etc.
  2. How well does the representation of the problem match the problem itself? What is left out, what important aspects are represented? Is there a better way?
  3. What special operators are provided for this problem? Were they necessary?
  4. Is EC the "best" way to solve this kind of problem? Is computational complexity growth an issue?

Theory Papers

  1. What is the fundamental EC problem being addressed by the paper? How does it relate to current EC approaches (is it a rehash)?
  2. Are the advantages clearly stated? Proven (empirically, theoretically)?
  3. Does the paper address the computationally complexity increases/decreases.
A list of represenative papers can be looked at from here. However, I would recommend you to look at the internet or through MSU library search papers related to EAs and your interest. You are expected to provide the instructor a copy of the paper by 24 October 2011 and a two page summary by 2 November 2011 on Angel before the presentation. The whole class is expected to read the papers before the presentation. Lack of participation indicating papers are being unread will result in a midterm over the topics covered in the papers.

You will turn in a proposal for your paper on 5 October 2011.

8.0 Term Project

Here is the term paper presentation schedule. Every presentation is scheduled for 20 minutes. Additional 5 minutes is kept for questions and answers.

We have two locally developed toolsets, GALOPPS and lilgp, here at MSU but both are dated. There exist a number of toolsets on the internet, including RGA, NSGA-II, DE codes at http://www.iitk.ac.in/kangal/soft.htm, any of which you can use to develop your project. You can even develop your own toolset, but that is not recommended. For starters, you can look at the MATLAB toolsets or ECJ out of George Mason. However, it is up to you.

On 12 December 2011, you will submit a term project report that will detail the following:

Write this as if you were trying to publish results in a professional journal. Your evaluation will be based on this viewpoint. One of two things must be true about your project problem.
  1. It is not one of the old stand-bys like traveling salesman, set partitioning etc. Pick something different, more interesting (complicated evaluation function, interesting representation, etc.).
  2. If it is an old stand-by problem, it is because you are testing out a unique and interesting EC feature/approach and you want to benchmark it against something known. This would be something like a new EC operator.
Deliverables from your project include the final written report (due on 12 December 2011), the oral presentation (during last few weeks of class), and, before starting your project (on 12 October 2011), a two-page write-up of what you propose to do, turned in on at the end of the 6th week. This early write up is to assure us that your project has been properly selected and thought out.

9.0 Notes

A class directory has been established called http://www.cse.msu.edu/~cse848. All handouts will be available in that directory for your convenience.

There is a forum on angel for forum discussions. We will monitor and answer questions but it is also a place for you to ask and answer questions amongst yourselves!

While an attempt has been made to lay out the course in advance, we reserve the right to update/change this syllabus during the course of the semester.

The Department of Computer Science and Department of Electrical and Computer Engineering expect all students to adhere to MSU's policy on Integrity of Scholarship and Grades, as stated in the Academic Programs publication.

Last modified: Aug 27 15:41:43 EDT 2011