CS 495   Special Topics in CS:  Evolutionary Computation              Fall 2002,  Instructor:  Jeffrey Horn

ANNOUNCEMENTS (Wednesday, Dec. 11, 2002)

    What's REALLY New:

• THE FINAL!   Sorry.  I got swamped with end-of-semester work, and trying to obtain and process all the code I needed from people from the HW 3 work to get a "final project" for all of us.  Well, I've got all of the code, but now we have little time. so here's is what we'll do:  The final will be in two parts, an in-class part tomorrow at 2:00pm, and a take-home part that I promise to keep SHORT!  I don't want you working 'til Christmas on it!  More details:
  1. PART I:  in class (our usual classroom NSF 1205, 2:00pm to 4:00 pm, although we'll only need the first hour for this part, the other hour will be to discuss part II, wrap up the course, donuts, etc.  Again, this is for Thursday, Dec. 12, 2002), open book, open notes.  Bring your laptop and be prepared to use a calculator!  (that means bring your favorite calc. or be willing to use your TI interactive or built-in Windows accessory).  Topics that COULD be covered:
     1. Three basic operators of a GA:  selection, crossover, mutation.
     2. Two-point crossover, give an example of how it works.
     3. Give an example of  mutation.
     4. Give an example of a single tournament, maybe binary tournament, and maybe a k-ary tournament (with k competitors randomly chosen)
     5. Logistic convergence:  expected number of generations to convergence (to a uniform population) grows logistically in pop. size N:  time_conv = O(lg N).
     6. Niching:  if we used shared fitness for selection, with each individual's usual fitness f_i divided by the number of copies of itself, n_i, then use the equilibrium equation  f_i/n_i = f_j/n_j  to solve for the equilibrium population distribution, given, say, three possible individuals i,j,k.
     7. Here is an application (e.g., a strategy for a non-player character in a computer game).  Pick out the decision variables and come up with an encoding for them on a chromosome.
     8. That's enough!  Although I might think of something else.  But I would keep it reasonable, as in nothing you would have had to study for.
  2. PART II:  take-home, Java coding.  Now some people have gone ahead and done one of the projects I listed below and gave to you last week.  Matt of course has gone off and done his own, and I think Steve might pretty much have done that too, since he likes staying in C so much!  For everyone else, I WILL have a short, straightforward, programming assignment that I will hand out at the final exam, (actually it should be on the web late tonight, Wednesday).  It will be something along the lines of:  "here is the code, now modify it to do runs on NYC Tunnels with the following ordering of the pipe diameters on the chromosome....  Do 20 runs with 20 diff. random seeds, average out the performance in the following way... and deliver to me the following table with the values written in."  I will then take this data and try to write up a paper on it over the break, to be submitted to GECCO by Jan. 22, 2003, I hope!  I will make sure it is something you can do by Friday, so just a few hours of time, although I will take hand-ins right up until Monday Dec. 16, at noon.  Hand-ins will be electronic so you don't have to be on campus. 
• See you Thursday!

• Added a new (third) HW3 team (for the "missing" members of this class).
• Added a due date for HW3.
• Happy Halloween!  OK, looks like I won't have time to do the on-line exam, at least not today.  Maybe I'll try it first thing next week.  I'll let you know.  So here is what you have left to do IN PLACE OF CLASS TODAY (recall, no class on Halloween)
  1. Somehow come to an agreement with each other (we can work out "a few" conflicts Tuesday) on who is doing what in the task lists for HW 3 below.  I will ask each person on Tuesday what they are going to do for HW3.  
  2. Do one of the following:
     1. Attend the Biology seminar at 11am Monday Nov. 4 (see details here) on evolution, or
     2. grab one of the three video tapes from my mailbox in the dept. office and watch a half hour or so (it would be nice if several people could attend the same viewing, and you can use 1205 or 1209, if you can find them unlocked or get a prof to unlock it, and use the VCR and projector in there).  I will be asking each person what they watched (on Tuesday).
  3. That's all!  (for now)
• Homework 3, team projects, is now assigned.  See below.
• Changed "n=9" to "n=5" in part I of HW 2 below.
• HW 2 (see below)
• Gary Spinks is coming from Algoma University to present their Masters degree program Computer Game Development.  Sounds very interesting!  AND THERE WILL BE PIZZA!!  (Wed. Oct. 9, 2002, in NSF 1207 at 11:00am)
• HW1 Drop Box is finally up in WebCT.  Hand in your GA source code NOW (well, by Tuesday, Oct. 1)
• Added copy of my own most recent GA coding.  Look in HW 1 directory (link below).  It is not pretty, but it can help guide your own code design.  (Try to do better!)
• Started adding links to the LINKS section below.
• HW 1 finally!!   (see below)

CONTENTS

• Administrativa
• Previous Semesters of this Course
• Fall1998
• Syllabus
• Lecture Notes
• Homeworks & Programs
• Tests and Quizes

LECTURE NOTES

Topics

Handouts

• Homework 1,  BLACK BOX OPTIMIZATION
  • Due:    Thursday, September 26, 2002  
  • Go here for the code.  Note that the interface, BlackBox, has been changed slightly.
  • Implement your own simple GA, as in our text, that uses a population, selection, and either or both of mutation and crossover, to solve the following black box problems as best you can:
    • bb34
    • bb57
  • You can use these problems for practice, since I put the source up there as well:
  •  
    • bbOneMax
    • bbBCI
  • Hand in all your source code, and the results you obtained on the problems above.  First one to email me the correct answer (max.) for problem bb57, gets an automatic "A" on this HW (assuming they can show they found it in a "valid" way!).  Include both the chrom and the fitness (objective) value in your email.

• Homework 2, BLACKBOX PROBLEM DESIGN & IMPLEMENTATION
  • Assigned:  Thursday, October 3, 2002
  • Due:    Thursday, October 17, 2002
  • Create two blackbox problems by writing java code that implements the BlackBox interface from HW1:

    PART I:   Generalized Last Theorem of Fermat

    • As we discussed in class, the problem is to find positive integers a,b,c,d such that   aⁿ  +  bⁿ    +  cⁿ  =  dⁿ  (where n = 5)
    • Suggest you use a fitness function that returns how close the candidate solution is.  In other words, someone gives it a chromosome, it then decodes four positive integers, and it plugs them in, figures out how close the left hand side is to the right, and returns some function of the difference.  
    • It is up to you who you want to decode the integers from the bit string, but I suggest you use the BCI code in the HW1 folder (above).  Also, it is up to you whether you want to make this a min or max optimization BB.  Just make sure your "maximiation" method in your BB code responds correctly!   You also decide how many bits (chromosome length) you want to make this problem.

    PART II:  Your Own "Problem from 

    • The goal here is to design and implement a BB problem that is as hard as can be for everyone else, and yet is still solveable by a reasonably decent optimizer!
    • To try to meet that goal, your problem must be 1 to 60 bits in length (up to you), and you must demonstrate to me that your own GA can solve the problem.  Your GA cannot use "cheats", in other words, no truly problem-specific knowledge (like initializing the first generation with mostly zeroes, or using some kind of weird operator).  Furthermore, you must be able to demonstrate to me that your GA can find the optimum solution MOST of the time.  That is, we can re-start it on K random seeds, and it will find the solution for at least K/2 of those runs.  You can set your parameters (e.g., pop size, mutation rate, etc.) any way you like, but remember, NO CHEATS!
• Homework 3, TEAM RESEARCH PROJECTS (NYC Tunnels and Generalized Fermat)
  • Assigned:  Tuesday, October 29, 2002
  • Due:    Thursday, November 18 , 2002
  •  
  • TEAM FERMAT:   Generalized Last Theorem of Fermat
    • Here is our web page.
    • Suggest you use a fitness function that returns how close the candidate solution is.  In other words, someone gives it a chromosome,
  • TEAM NYC Tunnels:   NYC Tunnels, Water Distribution Pipe Network Design
    • Here is our web page.
    •  
  • TEAM RFS (Resource-Based Fitness Sharing):  RFS for Shape Nesting
    • Here is our web page.

   

   

TESTS AND QUIZES
 

FINAL

Our final exam date is Thursday, Dec. 12, 2002 from 2:00pm to 3:50pm.  You have two choices for the final exam, project or test, and you can change your mind (from project to test that is!) right up the last minute.   Either way, everyone has to be there.  (There will be donuts!)  Here are the details.

TEST

Open book, open notes, bring your laptop.  It will run from 2:00 to 3:00 pm.  You will have enough time, assuming you know the material pretty well (click here for an overview of the topics).  Click here for the actual test!

After the test, from 3:00 to 3:50 pm, we will eat donuts and grade final projects  (see below).

PROJECTS

Below are the choices.  You must accomplish the goals stated, and then show this to me, and anyone else in the room, by plugging your laptop into the projector and showing your results, and code.  This does not mean a formal presentation (don't even think Powerpoint!).  Rather it should be an informal discussion with a bunch of your colleagues.  

Here is the code directory, for all the code for projects.

1. FERMAT:    Throw a GA at this and do the BEST you can.  And YES, you MUST use Dan's visualization code!
   1. k=6, n=6
   2. k=7, n=7
   3. Any other n,k pair IF you can convince me it is worthwhile!
2. NYC Tunnels:  
   1. Multi-objective
   2. Re-ordered Pipes (I.e., 
   3.  
3. SHAPE NESTING:  

LINKS

• SOURCE CODE at the GA ARCHIVE S at NRL