CS472 - Evolutionary Computation

Assignment Schedule

HW 1	Sun Sep 13 2020	150 pts
HW 2	Sat Oct 3 2020	150 pts
HW 3	Thu Oct 8 2020	150 pts
HW 4	Tue Oct 20 2020	200 pts
HW 5	Fri Nov 13 2020	200 pts
HW 6	Mon Dec 7 2020	250 pts

= currently tests NOT available
= tests available, HW not graded
= being graded
= graded

Frequent Links

• Class Policies
• My schedule

Class News

Dec 9

If you haven't done this yet, don't forget to fill out course evaluations. You only have until this Friday!

Dec 5
Let's take until Monday to finish assignment 6. I would love to see correct answers. Happy Hollidays!

Dec 4
Let's take "dead week" off! No classes next week and no final. We've all had a tough year. Let's do a great job on assignment 6 and call it a semester. Thanks for attending and I hope you will find the idea of adaptation and optimization through evolution a useful algorithmic idea for your programming toolbox. The topic is quite deep and has many yearly conferences. There is plenty more to learn if you are interested. Happy New Year!

Nov 20
Tests are available on the test machine for A6. Happy testing.

Nov 20
assignment 6 has been posted and test data is available: testDataA6.tar, testDataA6.zip

Nov 12

A lock file prevented any submissions from working from 3:44pm until 8:40ish. So I will extend the deadline by one day. Sorry for the system freeze. Really poor timing on the part of the system. :-)

Nov 7
Tests are available for assignment 5. Fitness is measured in distance between the points. NOTE: be sure to match the test machines number of digits of output! NOTE: updated the assignment 5 to give more information and fix example table to have fitness as distance. Be sure to run against the on-line tests early.

Nov 7
NOTE: if you want to make sure your sort routine is unbiased it needs to be sure to choose arbitrarily between equal elements. Here is a compare routine in qsort(3) form. In the case below we make a random choice of order if the order is equal so that qsort does not get to decide, in a biased way, the order.

// decreasing order
int fitnessCompare(const void *a, const void *b)
{
    double fitnessa = (*((Gene **)a))->fitness;
    double fitnessb = (*((Gene **)b))->fitness;

    if ( fitnessa > fitnessb) return -1;
    if ( fitnessa < fitnessb) return 1;   
    return (choose(.5) ? 1 : -1);         // choose a random order
}

Nov 6
Here is a program for drawing dots and a unit circle using Python+numpy+matplotlib see comments in code. I am also delaying the due date on the assignment to take some pressure off in these streesful times. I am not requiring you to use the normal distribution and sigma approach but you must use ES.

Nov 1
Links to class video web page and a dump of all the "whiteboards" used in the class can be found in the video section of the class BBLearn page.

Oct 29

With a withdrawal deadline coming up, I am working on grading today so you will have more input to your decision process.

Oct 28

assignment 5 has been posted.

Oct 20

There is NO CLASS ON WED. I have a doctor's appointment. We will be working on ES next. I will try to get the next assignment posted.

Oct 17

I am extending the due date for assignment 4 to Oct 20. The codes you will find most difficult are f387.code, o715.code, u659.code. They are short, or not well rounded example text, or not modern english. The others you should do fairly well on.

Oct 13

In case it might help here are the class "whiteboards" that we used in lecture. It is what I was typing during explanations to keep us focused.

Oct 9

Test data for assignment 4: testDataA4.tar, testDataA4.zip

Oct 7

assignment 4 has been posted. Test data and tests to come soon.

Sep 30

Assignment 2 due date is moved to 5pm on Saturday. Hurray!

Sep 28

assignment 3 has been posted. It is a copy of assignment 1 so people can make up for lost points on assignment 1. A separate submission entry will be made for it soon. Please use that to do your submissions.

Sep 27

Here is are the testfiles: testDataA2.tar, testDataA2.zip

Sep 20

assignment 2 due date has been delayed. Hurray!

Sep 20

assignment 2 has been posted.

Sep 14

NO CLASS. The Univerisity is closed on Monday Sep 14 due to smoke. The tone of the email suggests that even on-line classes are suspended. So enjoy Idaho's great sunny weather and blue skies... no wait. :-(

Sep 13
Once you have your program running and you don't anticipate using a debugger on it without a recompile, set the compile option from -g to -O3 to have the compiler optimize your code for speed. You should have plenty of time to run your code, but there is a time limit. O3 will probably give you about a 2x speed improvement. Which is always nice but probably not important for this assignment.

Sep 12
I have added some more material on Gray code section in the bit operations tutorial. Assignment 1 assumes for a couple of the variations that the binary number is in gray code and you need to degray it.

Sep 9
Test system is now up for HW 1 . Give it a try.

Aug 24
Welcome to Evolutionary Computation! Be sure to read the material in the Service section below. You are responsible for everything that appears on the class web pages. Many links will be dead links until we talk about them in class so I can update them for each semester. Information about accessing class machines and other IT questions can be found here: CS IT FAQ Have fun!

Class Description

An introduction to a wide variety of robust optimization algorithms based on the theme of nature inspired optimization techniques. This is a hands on programming class. All assignments will be programmed in C++ for speed and uniformity of grading. It is expected that you are a skilled C++ programmer and understand UNIX utilities such as make. GAs, GPs, ESs, EPs, EDAs, etc will be covered. Theory including representations, landscapes, epistasis, code bloat, diversity, and problem structure will be discussed. We will play with some special techniques such as predator/prey. Most of all, we will try to have fun. :-)

Time: 9:30-10:30 MWF
Location: Live at the time above via Zoom. See BBLearn for class for zoom id.
Tests: None
Final: None
Coding: Lots of C++, plus UNIX skills.

Covid-19 Adjustments This class will be taught entirely on Zoom. ZOOM ID in bblearn for class. All zoom lectures will be recorded and appear in the videos section in the class BBLearn page. Except for videos and grades all else will appear here on the class web page. All email from students should have the subject: CS472. Since almost no one showed up for office hours last semester I will try office hours BY APPOINTMENT ONLY. Please send email. Appointments will be in 20 minute slots. Multiple people can arrange to see me at the same time if you wish. There are no exams or final so proctoring is not an issue.

Textbook: Introduction to Evolutionary Computation, 2nd Ed. by A. E. Eiben and J. E. Smith, ISBN: 978-3662448731

Sample Syllabus (WARNING: NOT UP-TO-DATE)

This syllabus is an estimate of what we might cover this semester. The class varies from semester to semester to reflect new and interesting topics.

Wk#	Monday of that Week	Topics/Links	Assignments	Comments
1	Aug 24	Evolution as search and the strength of evolution as a technique. When can you apply evolution? Evolution as a general framework.	Read Chapter 1
2	Aug 31	The nature and relationship of landscapes, operators, representations. Intro to local search	Assignment 1 [pdf]
3	Sep 7	Simulated annealing, memory and taboo search	Read Chapter 2	NO CLASS ON MONDAY - LABOR DAY
4	Sep 14	Landscapes and representation, start GAs
5	Sep 21	Genetic Algorithms as population based search	Assignment 2 [pdf], Read Chapter 3
6	Sep 28	xover and other components of GAs	Assignment 3 [pdf]
7	Oct 5	GAs for permutation problems, xover operators for permutations
8	Oct 12	Epistasis, schema, schema theory, implicit parallelism
9	Oct 19	Evolution Strategies, diversity and population structure	Assignment 4 [pdf]Read Chapter 4
10	Oct 26	Genetic programming in general, tree based GP	Read Chapter 5 & 6
11	Nov 2	GP operators, Code bloat and hints on the cipher problem
12	Nov 9	Cartesian Genetic Programming
13	Nov 16	Multiobjective and Multimodal Optimization
14	Nov 23		THANKSGIVING BREAK!	NO CLASS THIS WEEK
15	Nov 30	Ant Colony Optimization, Estimation of Distribution Algorithms, Epistasis, What if you don't have a fitness function, Prisoner's Dilemma		Extra Credit Assignment 5 [pdf], Read Chapter 9
16	Dec 7
17	Dec 14		FINALS WEEK (NO FINAL FOR US)

References and Resources

Problem Resources

• englishFreq.cpp

General Resources

• A makefile tutorial
• A basic UNIX tutorial

General EC References

• A star field for use as a fitness landscape
• Some Example Fitness Landscapes
• A tutorial on bitwise operations in C and C++
• mapFunctions.cpp and
• mapFunctions.h for mapping a range of numbers to another range
• Fast portable 64 bit random number generators (read the header file first): rand.tar or rand.zip portable random number generator
• A basic tree library for GP with debugging
• Example code for random permutation by shuffling
• A review of the basic ant colony optimization techniques
• A paper that describes the Santafe Ant Problem
• The path of particles
• Highest mountain peaks
• Karl Sims virtual creatures page

LaTeX References

• AMS math guide
• LaTeX for Computer Scientists
• The Giant Book of Symbols
• Cool tool that lets you draw a latex symbol and it will do pattern matching to look it up. Try it! Don't always pick the first symbol it picks.
• The Source for all things TeX and LaTeX
• examples-tex.tar are the notes I used when I talked about LaTeX in one of my other classes
• A weird LaTeX example just doing lots of things. It requires the files: latexGraph.png, latexHyenaBib.bib, latexStripedHyena.jpg

Services

• Homework submission page. This our homework submission page. This is not to be confused with any other submission tools used in the CS department.
• Submitting homework without a browser
• Computer Science IT FAQ including information on logging onto class machines.
• The CS472/572 student machine is called cs-475.cs.uidaho.edu. That is not a typo. We are just reusing the machine from CS475. If you are off campus you can access this machine only by first "coming on campus" with VPN. For details see CS IT FAQ

Policies and Processes

• Policies